Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Mini Project 1: Build your own Vector!

In this homework, you will:

  1. Build two versions of vector, we will start with an easier but slower one, and then implement a more complex but much faster one.
  2. Get familiar with memory managements including manual memory allocations and pointers, as well as Rust references and move semantics.

Group Work

You should do this project in a group with one other student. Groups of size 3 are not allowed.

The handout will give you instructions on how to split the work between the two group members. Each member is only responsible for their parts. However, note that the instructions will sometimes ask both members to do something. In this case, feel free to do that work together, or each of you separately.

The instructions will refer to student 1 and student 2. Decide of which of you is which before beginning this work.

Both members must be registered in the same discussion section!

Pre-requisites

Before you get to work on this project, read the following Rust book chapters:

  1. Using structs.
  2. Defining structs up to and excluding “Using the Field Init Shorthand”.
  3. Structs and Methods: ignore the box titled “Where’s the -> Operator?”.

Part 1: SlowVec

Your task in part 1 of the project is to complete the implementation of SlowVec (located in project_1_vec/slow_vec/src/lib.rs). Our very first implementation of our own vector type.

This implementation will be a little slower, but it is easier to implement, so we will start with it.

You will implement a faster version in part 2 next week.

Step 0 - GitHub Repository: Forking and Cloning

Student 1 should fork our code GitHub repository. If you already have a fork of the repository, all you need is to update it so it receives the latest changes from our repository. You should confirm that your fork contains project_1_vec.

Make sure you add student 2 as a collaborator to the repository using these instructions. Make sure you give student 2 admin permissions.

Both students should clone the fork to their computers.

If you need a reminder on how to fork or clone the repos, look at the instructions and screenshots from homework 3.

Step 1 - Getting Started

Both students should open the slow_vec folder using VSCode and navigate to slow_vec/src/main.rs.

main.rs

First, run the main function inside that file using VSCode or using the following command:

cd project_1_vec/slow_vec
cargo run --bin main

You will notice the program prints some output and then crashes with an error. This is because you have not completed the implementation of this Part 1 yet!

Let’s understand what this file contains.

fixed_sized_array(): The fixed_sized_array() function (line 9) demonstrates the FixedSizeArray type does and how it works. FixedSizeArray is fully implemented for you, you do not have to change it. Although you are welcome to read its source code (located under project_1_vec/fixed/src/lib.rs) if you are curious.

FixedSizeArray<i32> provides 4 important functions:

  1. ::allocate(n: usize): creates a new FixedSizedArray that can store exactly n elements. It cannot store any more!
  2. .put(element: i32, i: usize): stores the given element at index i in the array.
  3. .get(i: usize) -> &i32: returns a reference to the element located at index i.
  4. .move_out(i: usize) -> i32: moves the element at index i out of the array and return it.

get and move_out have almost the same exact signature, the only difference is that get returns &i32 while move_out returns i32. The & stands for reference. For now, please think of a reference as a read only “copy” of the element. Crucially, with a reference (i.e. what get returns) you cannot modify the element. Furthermore, the array is unchanged after calling get: the element is still in it and the element cannot be modified because it is read only. move_out on the other hand changes the array: after calling it, the element at index i is returned and removed from the array: the array no longer has it!

The best way to understand this is by trying it out. Line 17 and 18 call get twice on the same index, and Rust executes them without a problem. Line 21 calls move_out on index 0, uncomment line 22 so that move_out is called twice and run the code. What do you see?

What if you call get after move_out?

Finally, slow_vec_push and slow_vec_remove test out .push and .remove

slow_vec_basics(): This function (line 33) demonstrates the SlowVec type:

  1. Line 35 creates a new variable of type SlowVec<i32>. You will have to complete the implementation of this type in the following steps. For now, you just need to get a sense of what its API looks like.
  2. Line 35 already puts 10, 20, and 30 in that SlowVec.
  3. Notice that you can print the content of SlowVec using println!.
  4. Line 38 to 40 iterates of the SlowVec and prints out its elements one at a time.

Behind the scenes, SlowVec is implemented using FixedSizeArray. But it’s implementation is missing two key functions push() and remove(), you will have to implement those in the next step.

slow_vec_push() and slow_vec_remove() demo pushing and removing elements from SlowVec.

They currently produce errors because you do not have push() and remove() implemented. When you do, go back and run these functions to make sure everything is correct!

lib.rs

After you are done running and tinkering with main.rs, let us look at project_1_vec/slow_vec/src/lib.rs.

Lines 11-13 define the SlowVec type using a struct! This is Rust’s way of defining custom types. Feel free to refer back to the Rust book for information about structs!

However, there is a difference between how this struct is defined and what it looked like in main.rs.

In main.rs, we saw SlowVec<i32>, which contained elements of type i32. Here, however, we see SlowVec<T>! This is Rust’s way of making a type generic, that is, making it work with any underlying type we later choose.

Indeed, SlowVec can be used with i32 or any other type. For example, feel free to try this code out (e.g., by putting it and running it in main.rs).

#![allow(unused)]
fn main() {
let slow_vec: SlowVec<bool> = SlowVec::from_vec(vec![true, false]);
println!("{slow_vec}");
let element = slow_vec.get(0);
// Look at the type of element in VSCode, it is &bool!
// If you change the first line to use i64, the type of element automatically changes to &i64!
}

We will dive much deeper into generics later in the course. For now, in your mind, think of T as being i32 whenever you see it in the code.

The SlowVec struct provides a bunch of methods (lines 16-70). Many of them are provided to you. You do not need to modify these functions and you can assume they are correct:

  1. new(): creates a SlowVec that contains an empty FixedSizeArray of size 0.
  2. into_vec(...) and from_vec(...): transform between SlowVec and Rust’s built in Vec. You do not need to use or understand these functions, we provide them mostly for testing and tinkering.
  3. len(...): returns the current length of the SlowVec.
  4. clear(...): clears all the elements in the SlowVec, resetting its contents to an empty FixedSizeArray.
  5. get(...): retrieves a reference to the element at index i. It does so by simply calling get on the underlying FixedSizeArray.

One important thing about many of these functions is that they take a self as a first argument. This is similar to self in Python: it is a special parameter that represents the SlowVec that this method is called on. For example, consider the following code:

#![allow(unused)]
fn main() {
let my_var: SlowVec<i32> = SlowVec::from_vec(vec![10, 20, 30]);
let element = my_var.get(0);
}

In this case, when fn get(&self, i: usize) is called, Rust automatically assigns self to my_var and 0 to i. So, self.fixed refers to the field called fixed (defined in line 12) that is inside my_var. This is why this call returns 10.

Step 2 - Implementation

Student 1 must implement the push function (line 62), while Student 2 must implement the remove function.

The trick to both function is similar. The fixed field is of type FixedSizeArray, so we cannot change its size. We cannot add more elements to it nor remove any elements from it.

Thus, we have to create a new FixedSizeArray with the new desired length, move over the elements from the old fixed to it, as well as adding the new element (in the case of push) or skipping the removed element (in the case of remove) to it, and then replace self.fixed with it.

So, the solution to both functions have a similar structure:

#![allow(unused)]
fn main() {
// Create a new FixedSizeArray of a different length
// If pushing, length should be old length + 1
// If removing, length should be old length - 1
// Look at the code in `lib.rs`, is there some function
// that can tell us what the old length is?
let tmp = FixedSizeArray::allocate(<<<<new length>>>>);

// loop over self.fixed and move over its elements to tmp
// either skip the one that should be removed (in case of remove)
// or add the new element to the end of tmp (in case of push)
...

// get rid of the old fixed field and replace it with tmp!
self.fixed = tmp;
}

You can test out your implementation using slow_vec_push() and slow_vec_remove() in main.rs.

Student 1 must implement and push their solution to a branch called std1 student 2 must implement and push their solution to a branch called std2

When both students are done, student2 should merge branch std1 into std2: after this merge branch std2 should contain both codes.

We will look at your git commit history: make sure you use these branches.

Step 3 - Testing and Experimenting

After finishing both solutions and merging both branches, both students should move over to branch std2 and then run the tests:

cargo test -- --test-threads=1

If you pass all the tests, then your solutions are correct and you will get full credit. If you fail some tests, go to the corresponding file under tests/, read the failing test, and try to find out what went wrong so you can fix it.

Both students should also look at the content of src/memory.rs and then run it using this command:

cargo run --bin memory

This program confirms that SlowVec does not mismanaged memory, e.g. by losing track of data or forgetting to remove elements in memory. You have not used any features that corrupts memory. So this is actually guaranteed by Rust.

However, in part 2, you will use some unsafe Rust features that may corrupt memory. These features allows us to implement a faster vector. However, they are dangerous, and if you make mistakes in that implementation, your vector may lose elements or forget to clean them up. memory.rs will come back and help you find and fix such errors in step 2.

Step 4 - Submission

When both students are happy with the code and the tests pass, student 2 must create a new branch called submission1 with all of the code. Do not change submission1 after the part 1 deadline if you do not want to incur a late submission penalty.

Student 2 must submit the code via Gradescope. You will need to provide the link to the GitHub repo. Student 2 must remember to add student 1 as a group member to that submission on Gradescope.

Both students can continue to edit std1, std2, or any branches other than submission1 for their work on part 2.

Part 2: FastVec

Your task in part 2 of the project is to complete the implementation of FastVec (located in project_1_vec/fast_vec/src/lib.rs).

This implementation will be much faster than part 1, but it will be more complicated to implement.

Step 0 - Background

Both students: Before you get to coding, you need to understand our strategy for how to make FastVec be (significantly) faster than SlowVec. This strategy relies on two parts:

  1. Doubling the size of the vector when pushing to a full vector.
  2. Manually managing memory (instead of relying on FixedSizeArray).

Doubling Vector Size on Resize.

The main idea behind push with SlowVec is to create a new FixedSizeArray, whose length is one plus the old length, then moves over all the previous elements to the new, bigger array. This makes it so push always takes O(n) steps, where n is the current length of your vector. However, with Rust’s builtin Vec (and equivalent in other languages, such as a list in Python), push is O(1) (on average). How come?

These faster implementations distinguish two notions:

  1. The length of the vector: the number of elements currently in the vector,
  2. The capacity of the vector: how many elements the vector can have at most before it needs to be resized.

In SlowVec, these two were the same, thus, for every push, the SlowVec needed to be resized. In FastVec, you will notice that the struct contains len and capacity fields. In fact, if you create a new FastVec using FastVec::new(), you will notice it starts with capacity 1 (and len 0, because it is empty). This allows you to push one element “for free”, as the FastVec already has space for it.

The key idea is that when the capacity equals the len, the vector is full, and any future push will need to make it bigger so that it can add a new element to it. In that case, we double the capacity (i.e., the size), rather than just increasing it by 1 (as in SlowVec).

For example, consider starting with a fresh new FastVec, and then issuing 8 pushes to it:

  • FastVec::new returns an empty vector with capacity 1: len = 0, capacity = 1
  • First push: the vector has enough capacity to simply put the element in, without resizing. This push is free, i.e., takes one step. len = 1, capacity = 1.
  • Second push: len equals capacity, the vector is full, we resize it so that capacity = 2*1 = 2, and move all previous elements to the new resized vector (similar to SlowVec), then add the new element at the end. This takes two steps (one to move the previous element, one to add the new element). len = 2, capacity = 2.
  • Third push: len equals capacity, the vector is full, we resize it so that capacity = 2*2 = 4, and move all previous elements. This takes three steps. len = 3, capacity = 4.
  • Fourth push: len < capacity, we simply add the new element at the end. This takes one step. len = 4, capacity = 4.
  • Fifth push: len equals capacity, vector is full, resize it to capacity = 4*2 = 8. This takes 5 steps. len = 5, capacity = 8.
  • Sixth, seventh, and eight pushes: len < capacity for each of these pushes, so they each take only one step, after all of them, len = 8 and capacity = 8.

Using this strategy, we pushed 8 elements, and it took 1+2+3+1+5+1+1+1 = 15 steps in total. Which averages out to less than 2 steps per element. In fact, if we use this strategy to push infinitely many elements, the average converges to 1 step per element.

If you want a more visual demonstration of what this looks like, take a look at this helpful video.

Manually Managing Memory

We will not use FixedSizeArray in this part, and instead we will directly manage the underlying memory using pointers. This is more complex to implement (and can be dangerous if not implemented correctly as it can result in various memory corruptions and problems!). However, it gives you way more control about when and how to allocate memory, including allocating memory without using it directly, but rather, saving some of it free for the future.

Using the provided memory allocator library (MALLOC)

To help you with memory management, we provide a memory allocator library as part of the stencil. lib.rs already uses it:

#![allow(unused)]
fn main() {
use malloc::MALLOC;
}

The library provides you with two important functions that you will need to use:

#![allow(unused)]
fn main() {
// Allocate new memory with the given size (in bytes).
// Returns a pointer to this newly allocated memory.
malloc(bytes: usize) -> *mut u8

// Free a previously allocated region of memory
// You must pass a pointer than was returned by malloc
// and free will free the corresponding memory (all of it).
// free remembers how many bytes that allocation was, and will
// automatically free all these bytes.
free(ptr: *mut u8)
}

Here is an example:

#![allow(unused)]
fn main() {
// Allocate four bytes
let ptr1: *mut u8 = MALLOC.malloc(4);
// We can now do things with these four bytes
// When we are done, we should free them.
MALLOC.free(ptr1);
}

Look closely at the type of ptr1, it is *mut u8. u8 represents a single byte in Rust. So, *mut u8 is a mutable pointer to byte(s). But what if we want to deal with other types that are not one byte, for example, an i32? Fortunately, everything boils down to bytes on a computer, because everything is simply zeros and ones. We just need to make sure we have allocated the correct size for that type.

An i32 is 4 bytes in size, so the above exam allocates enough memory for exactly one i32. However, it is not a good idea to try to memorize the sizes of different types. Furthermore, we may not even know what the type is (e.g., FastVec like SlowVec is generic over any type the user of the vector chooses, denoted by T). Fortunately, Rust has a helpful function we can use that tells us the size of a type.

#![allow(unused)]
fn main() {
let size_of_i32 = size_of::<i32>();
let size_of_t = size_of::<T>();
}

Now, we can allocate pointers to these other, more helpful types! We have to use the correct size (in bytes) and then cast the resulting pointer to our desired type using the as keyword:

#![allow(unused)]
fn main() {
let ptr1: *mut i32 = MALLOC.malloc(size_of_i32) as *mut i32;
let ptr2: *mut T = MALLOC.malloc(size_of_t) as *mut T;
}

Now, what if we want to allocate memory for more than one element? It’s all bytes: we just need to make sure that we have enough of them.

#![allow(unused)]
fn main() {
// ptr3 can hold up to 10 elements of type i32s.
let ptr3: *mut i32 = MALLOC.malloc(size_of_i32 * 10) as *mut i32; 
// ptr4 can hold up to n elements of type T.
let ptr4: *mut T = MALLOC.malloc(size_of_t * n) as *mut T;
}

Using the pointers after they are allocated

Now, we know how to allocate and free pointers. But how do we use them?

There are three ways to use a pointer:

  1. Writing to a pointer with ptr::write(): this overwrites the data at the pointer with the given data. It will not free or destruct the old data, it will simply overwrite it.
  2. Moving data out of a pointer with ptr::read(): this will move out the data pointed to by the pointer and destroy/free that data.
  3. Getting a reference to data pointer to by a pointer: &*[name of your ptr]: this returns a reference to the data, it does not move out nor destroy it.

The difference between (2) and (3) is subtle: (3) leave the pointer unchanged: you can read the data again from that pointer later on and you will get the same data. (2) moves the data out, so if you try to read data from the pointer again after using it, there will be no data to read! (In fact, doing so will likely cause big problems and may result in nonsense outputs or errors).

Importantly, to use these operations correctly, you need to make sure these conditions are upheld:

  1. Never use ptr::read or &* on a pointer before writing with ptr::write() to that pointer (since there is no data yet).
  2. Never use ptr::read or &* on a pointer after ptr::read() (since the data is moved out), until you write to it again.
  3. If a pointer has data, you must first use ptr::read() to move it out, before using ptr::write() to write new data to it.

Rust cannot help you ensure that these conditions are met. Instead, you must do so yourself by thinking hard about your code. In fact, all of these operations are unsafe. These are special Rust operations that Rust allows us to execute to give us flexibility, but Rust cannot guarantee that they will not create problems (the technical term is undefined behavior). Instead, we must ensure that they will not create problems by carefully thinking about the code and ensuring it is correct.

To use these features, we must explicitly use the unsafe keyword, to tell Rust that we know what we are doing. If we do not use unsafe, the Rust compiler will give an error about these operations.

#![allow(unused)]
fn main() {
let my_pointer: *mut i32 = MALLOC.malloc(size_of::<i32>()) as *mut i32;

// This tells Rust we know what we are doing and we want to use unsafe
// operations.
unsafe {
    // First write.
    ptr::write(my_pointer, 5);  // Now, my_pointer points to 5.

    // Let us say we want to overide the data with 10.
    // We should first move the previous value out!
    // Then write to it.
    let _old_data = ptr::read(my_pointer);
    ptr::write(my_pointer, 10);


    let v: &i32 = &*my_pointer;
    println!("{v}");  // will print 10

    let v2: i32 = ptr::read(my_pointer);  // the data has been moved out of my_pointer
    // You should not try to read data from my_pointer again
    // (although it might still work with i32, but with more complicated types, it will not!)
    println!("{v2}");  // will print 10
}
}

What about when the pointer points to many elements? We can use add() to select which element we want to look at.

#![allow(unused)]
fn main() {
let my_pointer_2: *mut i32 = MALLOC.malloc(size_of::<i32>() * 10) as *mut i32;

unsafe {
    // This points to element at index 2, i.e. the third element.
    let ptr_2: *mut i32 = my_pointer_2.add(2);
    ptr::write(ptr2, 33);
    let this_is_33: i32 = ptr::read(ptr2);

    // This points to the element at index 9, i.e., the last element.
    let ptr_9: *mut i32 = my_pointer_2.add(9);
    ptr::write(ptr_9, 99);
    println!("{}", &*ptr_9);

    // add() is unsafe because if you misuse it, you might create problem,
    // what do you think will happen with this code?
    let ptr_10: *mut i32 = my_pointer_2.add(10);
    println1("{}", &*ptr_10);
}
}

main.rs and memory.rs

Just like in part 1, we provide fast_vec/src/main.rs and fast_vec/src/memory.rs to serve as a playground for you to experiment with MALLOC and with dealing with pointers. You can them using these commands:

cargo run --bin main
cargo run --bin memory

Take a look at main.rs, and specifically, the malloc_and_ptr() function. Run it and try to understand what it outputs. Feel free to modify it or add more code to it to experiment with other cases.

When you are confident that you understand the basics of MALLOC and pointers, move on to the next step.

Step 1 - Implement get

Student 1 Merge your submission1 branch from part 1 to the main branch, then, retrieve the changes from our course repository (the repository you forked your repo from). You must see both (1) your code from part 1 under slow_vec/ and the stencil code under for fast_vec/src/.

Both students should implement get on that main branch.

Start by assuming that the vector already has enough elements pushed to it. How would you use the pointer operations described in the background above to retrieve the element at index i from self.ptr_to_data?

Hint: You only want to get the data, you do not want to move out or destroy it. Users of your vector should be able to get the data again in the future if they want to. Consider using &*. Hint: You will need to use unsafe and you will need to use self.ptr_to_data.add([your index]).

You can try out your implementation using main.rs to see if it works.

After you make the basic version work, consider what would happen if the callers provided a bad index. E.g., if i is greater than or equal to self.len. Rather than returning random/garbage data or causing memory issues, it is best you create an error to inform users that they are using get wrong and providing a bad index.

Consider adding this code below to the top of your function implementation.

#![allow(unused)]
fn main() {
if i >= self.len {
    panic!("FastVec: get out of bounds");
}
}

After you are done, run the following test, and if it passes, move on to the next part.

cargo test get_strings -- --test-threads=1

Step 2 - Implement push and remove.

Each student should create their own separate branch, based on the main branch, and use it to do their implementation work.

Student 1 should implement remove. Unlike in part 1, you do not need to resize the vector, since FastVec can support having a capacity different than its length. Instead, you can simply remove the element at the given index, and then move every element after it one step backwards. For example, assume you had a vector with [1, 3, 5, EMPTY] and remove(1) is called, you can implement your code such that the vector becomes [1, 5, EMPTY, EMPTY] without having to allocate new memory or resize the vector.

Consider what should happen if callers provide an index that is outside the length of the vector. Similar to get, you should panic in this case using this error message:

#![allow(unused)]
fn main() {
panic!("FastVec: remove out of bounds");
}

Hint: Remember to first move out the element to be removed using ptr::read. Hint: For every index j greater than the index you want to remove, you should read the element at index j using ptr::read, then write it to index j-1 using ptr::write.

Student 2 should implement push. You should use the size doubling strategy we described above in the background.

Hint: Use MALLOC.malloc to allocate new memory of twice the size. Hint: Move over all the elements from the previous pointer to the new pointer using ptr::read and ptr::write Hint: Do not forget to write the new element using ptr::write and to update self.ptr_to_data, self.len, and self.capacity.

Both students should run the tests using

cargo test -- --test-threads=1

If your implementation of both push and remove is correct, all the tests should pass except one test called clear_tracker (leave that one for the last steps).

If other tests fail, look at their code (you can find it under tests/, or by using grep -R "[name of test]"). It might be not related to the function you are working on, and instead be testing the function your teammate is working on, in which case you can ignore it.

After both students are done, student1 should merge both of their branches into a new branch called submission2. Both students will use this branch to complete the rest of the assignment.

Step 3 - Fix bug in clear

Both students You will notice that the clear_tracker test fails even when you implement both push and remove correctly. This is because we have intentionally left a bug in the clear function we provided. You need to fix this bug.

Look at the output of running memory.rs. You will notice that some data is not free-ed even after calling clear(). You need to make sure that data is free-ed.

Hint: remember the rules of using pointers above. How can you destroy the data the pointer is pointing to? Hint: remember ptr::read()?

Step 4 - Run the provided experiment

Both students Use the following command to run the provided experiment:

cargo run --bin experiment --release

This will produce a plot under fast_vec/plot.png. Look at the plot. In this plot, the x-axis represents the size of the vector, and the y-axis represents the time needed to push one element to the vector with that size. For FastVec, the time is reported in microseconds, for SlowVec the time is in hundreds of microseconds.

Make sure you understand what you are seeing. E.g., which of the two implementations is faster, and what trends you see as vector sizes grow.

Step 5 - Submission

Student 1 should make sure all of your team’s code is in the submission2 branch and that you pushed it to your fork on GitHub. Then, student 1 should submit that code via Gradescope.