We conducted a study to analyze the characteristics of memory layouts and assembly code of the Vec, VecDeque and HashMap types and clearly understand the structures and behavior of each type.
The memory layout of the Vec type is described below:
The memory layout of the VecDeque type is described below:
The memory layout of the HashMap type is described below:
The management struct as described below manages each type.
In debug builds, capacity() and len() reference this struct.
- Vec type
stack {
offset + 0x00: Maximum number of elements,
offset + 0x08: Address to the heap,
offset + 0x10: Number of the current elements,
}- VecDeque type
stack {
offset + 0x00: Maximum number of elements,
offset + 0x08: Address to the heap,
offset + 0x10: Index of the first data
offset + 0x18: Number of the current elements,
}- HashMap type
stack {
offset + 0x00: Address of the bucket (the data struct storing hash values generated from keys),
offset + 0x08: Maximum number of elements,
offset + 0x10: Number of the empty elements,
offset + 0x18: Number of the current elements,
offset + 0x20: Random number,
}The sample program we used in this study is shown [later](#Sample program we used) in this document.
The Vec type is held in the heap memory as shown below:
The code shown below places data in the allocated heap. Along with this operation, the management struct is initialized.
The figure below shows push() and a management struct and a buffer around it.
In release builds, push() is inlined by optimization and we cannot recognize calls to it. We can, however, find that data is added and the management struct for Vec is updated.
- Management struct and buffer before push
- Management struct and buffer after push
The figure below shows insert() and a management struct and a buffer around it.
Similarly, insert() is also inlined by effects of optimization in release builds, but the data placed at the position where new data should be inserted is moved backward and the new data is inserted there.
Effects of optimization, however, prevent the number of the current elements in the management struct from being updated. In contrast, we found that the management struct is also updated in debug builds.
- Management struct and buffer before insert
- Management struct and buffer after insert
As shown below, the VecDeque type allocates a buffer and then places data in the buffer memory. Finally, it builds a management struct in the stack.
The VecDeque type is designed to be a circular buffer.
The example below shows the layout on memory when using push_front() to insert data (see the sample program).
In release builds, push_front() is inlined by effects of optimization and we cannot recognize calls to it. We can, however, find that data is added and the management struct for VecDeque is updated.
- Management struct and buffer before push_front
- Management struct and buffer after push_front
Running push_front() appends data to the end of existing data in the buffer.
We can interpret that the characteristics of the circular buffer of VecDeque causes this behavior and the management struct increments the number of the current elements after the data is inserted.
The index of the first data in the management struct is 0 because the first data value was 2 before the data is inserted.
After the data is inserted, the first data should be 1 because push_front() inserts 1 before the value 2. The index of the first data in the management struct should be 5 because the data is appended to the end of data in the struct.
The figure below shows the assembly code illustrating how HashMap::new() creates HashMap.
Although we cannot recognize a call to HashMap::new() due to effects of optimization, we can find processing that creates the management struct for HashMap.
A 16-byte random number is obtained using a Windows API, ProcessPrng().
This random number is handled in units of 8 bytes. HashMap creates a hash value from an input value and manages it by linking with a key/value.
This random number is used when generating a hash value from a key. Then, the management struct for HashMap is created in the stack.
Rust v1.35 or later uses SwissTable as its HashMap algorithm and SipHash as its Hash function.
In the assembly, insert(), which adds elements of the HashMap type, receives the management struct in its first argument, the key in its second argument, and the value in the third argument.
Then, follow the flow described below to add values:
-
- Generating a hash value
Using a standard library function core::hash::BuildHasher::hash_one(), generate a hash value based on the key and the random number from the management struct.
This hash value is used to generate an identifier linking with a key/value or to generate an index the identifier of which is placed in a bucket.
-
- Generating an identifier and checking for duplicated identifiers
After generating a hash value, generate an identifier and check for duplicated identifiers.
Extract the upper seven bits of the generated hash value by shifting it 0x39 bits rightward.
This resulting value is placed in a bucket as a value linked with a key/value.
Because the extracted upper seven bits are handled as a one-byte value, the most significant bit of the identifier is always zero, which is one of the characteristics of the identifier.
Use this characteristic to determine whether an identical identifier already exists in the bucket.
Then, check for duplicated identifiers.
Calculate the logical product of the hash value and the maximum number of elements. Using the resulting product as the offset, retrieve a value of 16 bytes from the bucket.
Use the pcmpeqb instruction to determine whether an identical identifier already exists in the 16-byte value retrieved from the bucket.
The pcmpeqb instruction compares each byte of the 16-byte value with the corresponding byte of the identifier and, for each identical byte, places 0xFF in the corresponding position of the first operand.
If the bytes are not identical, it places 0x00 in that position.
After completion of this instruction, if the first operand contains only 0x00, the identifier is not duplicated.
-
- Generating an index
After generating an identifier, generate an index that indicates the position where the identifier should sit in the bucket.
Using the pmovmskb instruction, generate a mask based on the 16-byte data retrieved from the bucket as described in "2. Generating an identifier and checking for duplicated identifiers."
The pmovmskb instruction extracts in its second operand the most significant bit of each byte from the 16-byte register and aggregates the extracted bits into a bit string in the first operand.
All the unused areas in the bucket are filled with 0xFF and the most significant bit should be one.
In the bit string the pmovmskb instruction has aggregated, all the bits corresponding to the position where an identifier is placed are zero and the other bits are one, because the most significant bit of an identifier is always zero as described in the previous section.
Then, run the tzcnt instruction on this mask.
The tzcnt instruction counts the number of successive zeros from the least significant bit in the value specified in the second operand until the value one first appears and stores the count in the first operand.
We can use this processing to calculate how many areas from the lowest one of the bucket are filled.
In addition, add the logical product of the hash value and the maximum number of elements, which we used also in the previous section, to the count calculated by the tzcnt instruction.
This addition enables us to obtain a candidate for the index where the identifier should be placed.
Finally, adjust the index so that it is equal to or less than the maximum number of elements through logical product of this addition result and the maximum number of elements.
This value obtained finally is used as the index of the position where the identifier should be placed.
-
- Updating the management struct, bucket and buffer
Lastly, update the management struct, bucket and buffer (the storage for key/value pairs). When adding elements, the number of elements increases, and the number of empty elements decreases in the management struct.
- Vec type
fn main() {
// 1. Create Vec
let mut vec_num = vec![1, 2, 3, 4, 5];
// 2. Length and capacity of Vec
println!("vec_num length: {}, capacity: {}", vec_num.len(), vec_num.capacity());
// 3. Add elements
vec_num.push(6);
println!("vec_num length: {}, capacity: {}", vec_num.len(), vec_num.capacity());
vec_num.insert(3, 99);
// 4. Iteration
// Make vec_num Vec containing only odd numbers
let odd_numbers: Vec<i32> = vec_num.iter()
.filter(|&num| num % 2 != 0)
.cloned()
.collect();
println!("odd_numbers element:");
for value in &odd_numbers {
println!("{}", value);
}
}- VecDeque type
use std::collections::VecDeque;
fn main() {
// 1. Create VecDeque
let mut vec_num = VecDeque::from([2, 3, 4]);
let vec_iter_test = VecDeque::from([0, 1, 2]);
let it = vec_num.iter();
// 2. Length and capacity of VecDeque
println!("vec_num length: {}, capacity: {}", vec_num.len(), vec_num.capacity());
// 3. Add elements
vec_num.push_front(1);
vec_num.push_front(0);
vec_num.push_back(5);
vec_num.push_back(6);
vec_num.push_back(7);
vec_num.push_back(8);
vec_num.push_back(9);
vec_num.push_back(10);
let it2 = vec_num.iter();
let num = vec_num[3];
println!("{}", num);
// 4. Delete elements
vec_num.pop_front();
// vec_num.pop_back();
// 5. Iterator trait
let numbers: VecDeque<i32> = vec_num.iter()
.filter(|&&num| num % 2 != 0)
.map(|&num| num * 2)
.collect();
println!("numbers element:");
for value in &numbers {
println!("{}", value);
}
let numbers: VecDeque<i32> = vec_iter_test.iter()
.filter(|&&num| num % 2 != 0)
.map(|&num| num * 2)
.collect();
println!("numbers element:");
for value in &numbers {
println!("{}", value);
}
}- HashMap type
use std::collections::HashMap;
fn main() {
// Create HashMap
let mut processes = HashMap::new();
// Add elements
processes.insert("ProcessA", 1001);
processes.insert("ProcessB", 1002);
processes.insert("ProcessC", 1003);
// Obtain the capacity and the number of elements
println!("processes length: {}, capacity: {}", processes.len(), processes.capacity());
// Add data exceeding the capacity
processes.insert("ProcessD", 1004);
println!("processes length: {}, capacity: {}", processes.len(), processes.capacity());
// Obtain the number of existing elements
let pid = processes.get("ProcessB");
match pid {
Some(&id) => println!("PID of ProcessA.exe: {}", id),
None => println!("ProcessA.exe not found"),
}
// Obtain the number of non-existing elements
let pid = processes.get("ProcessE");
match pid {
Some(&id) => println!("PID of ProcessD.exe: {}", id),
None => println!("ProcessD.exe not found"),
}
// Delete existing data
processes.remove("ProcessA");
// Delete non-existing data
processes.remove("ProcessE");
}