Collections

Arrays, vectors, structs, tuple-structs, tuples, and enums are data types whose objects may contain several other objects. However, for structs, tuple-structs, tuples, and enums, for each contained object a specific clause must be specified both in the type declaration and in the object construction, so they are not usable to contain hundreds of objects. Instead, arrays and vectors are data types that may contain many objects, even if they are defined and instantiated with simple formulas. The objects of such kinds are named collections.

Arrays and vectors are optimal collections in many cases: they use memory efficiently, they are fast to scan, they use CPU caches efficiently, and they allow fast direct access through an integer offset (or index). Yet, for some operations, they are definitely inefficient, so in such cases it is appropriate to use other kinds of collections. The Rust standard library provides various kinds of them: VecDeque<T>, LinkedList<T>, BinaryHeap<T>, BTreeSet<T>, BTreeMap<K,V>, HashSet<T>, and HashMap<K,V>.

Speaking of collections, arrays are a separate case, because they are entirely stack allocated, and they have a size defined at compile time. All the other collections, including vectors, contain a variable number of items; and they store a fixed-length header in the stack, while the data, if there is some, is allocated in the heap. We will name them dynamically sized collections.

Measuring Execution Time

Because the choice of a collection depends much on its performance, here we take a detour, where we see how we can measure with precision the time spent by different portions of Rust code.

Performance is important for all software developers. However, those who program in a high-level language typically reason about how many milliseconds or how many seconds are spent by a command, while those who program in a low-level language, like Rust, often reason about how many microseconds or even nanoseconds are spent by a single function.

This program first will print all the integer numbers from 0 to 9999, and then it will print the time spent to print such numbers. A possible content of the last line is: 20.695631ms. It means that the time taken to run the loop has been a bit more than 20 milliseconds.

Such time depends mainly on the power of the computer used, on the operating system, and on the terminal emulator program. It depends little on the optimization level used by the Rust compiler, as most time is used by library code and operating system code.

However, some programs perform a lot of computations, and for such programs the level of optimizations performed by the compiler can dramatically affect the time to run a command.

At the beginning of the book, we saw that to compile a Rust program it was enough to write the rustc command, followed by the name of the source file, with no need for any other arguments. Yet, such a command does not activate the compiler optimizations, so it generates machine code that is good for debugging but not as efficient as it could be.

If you are interested in performance, you should activate the compiler optimizations. These are activated using the command-line option -O (it’s an uppercase letter, not a zero). If that option is omitted, every optimization is disabled.

If you go back to the previous example, you will notice that first the Instant type has been included from the standard library. It represents time instants with a resolution smaller than a microsecond.

To measure a time, you should invoke the now function of the Instant type . Every invocation of now returns an object of type Instant, representing the current time instant. Then, the elapsed method of the Instant type returns an object of type std::time::Duration, which represents the time elapsed from the creation time of the Instant object to the current time. If a Duration is printed for debug (using the {:?} placeholder), the nearest unit of measurement is automatically chosen, and the symbol of such unit is output as suffix.

Performing Arbitrary Insertions and Removals

Now let’s get back to the operations on the collections.

Remember to compile it specifying the -O option.

This program will print three numbers that depend on the computer, on the operating system, and possibly even on the version of the compiler.

A possible result is: 3.517μs 449.095194ms 61.93267ms.

That means that to create a vector that allocates room for one hundred million usize objects , which in a 64-bit system occupies 800 MB, few microseconds are spent; to put one hundred million values in such space, without ever allocating memory, less than half a second is spent; and to remove all such numbers, one at a time, proceeding from the last one, less than one tenth of a second is spent.

It could print: 6.663μs 1.151939082s 1.015383097s.

First of all, notice that this time only one hundred thousand items are processed, which is one thousandth of those processed by the previous example.

To create the 800KB-large vector, few microseconds are spent, but to insert one hundred thousand items from the beginning of the vector, more than one second is spent, and as much time is spent to remove them by proceeding from the first one. So, such an insertion operation appears to be more than two thousand times slower than that of the previous example, and such a deletion operation appears to be more than sixteen thousand times slower than that of the previous example.

The reason for such times is easy to explain.

To add an item at the end of a vector having enough capacity, all you need to do is to check that there is enough space, to copy the item into the vector buffer, and to increment the item count. That, for a usize, in the computer used to measure those times, takes less than five nanoseconds, including the time to move the iterator to the next item.

To remove an item from the end of a nonempty vector, all you need to do is to check that the vector is not empty, and to decrement the item count. That takes less than one nanosecond.

To insert an item at the beginning of a vector, first you need to shift by one place all the items already in the vector, to free the first place for the new item. At the start of the loop, the shift operation is fast, but as the item count grows, the time spent to insert an item at the beginning of the vector grows as much.

Similarly, to remove the first item, you must shift all the items but the first one, which will be overwritten by the second item.

Using the notation of the theory of computational complexity, we can say that the insertion and the removal of an item at the end of a vector have a O(K) complexity, which is constant complexity, while the insertion and the removal of an item at the beginning of a vector already containing N items have O(N) complexity, which is linear complexity.

If the insertions and removals are not really at the beginning, but in an intermediate position, the performance will be better, but still much slower than insertion and removal at the end.

Queues

If you need to insert and remove items only at the beginning of a vector, it is enough to redesign the vector in inverted order, so that such operations will be applied at the end.

It could print: 330.812316ms 163.214733ms.

The first timed code portion creates an empty vector, and then, for forty thousand times, it inserts three numbers at the end of the vector and it extracts two items from the beginning. The second code portion extracts from the beginning all the remaining items. The first portion spends about a third of a second, and the second portion about a sixth of a second. Actually, almost all the time is spent for the extractions, because insertions are extremely fast.

It could print: 505.627254ms 211ns.

Now the insertions are slow, and the removals spend virtually zero time. However, the sum of the two times hasn’t improved at all.

It could print: 994.255μs 47.34μs.

The difference from the previous times is abysmal. Indeed, the whole program spends less than one millisecond, compared with around 500 milliseconds spent by the versions using a vector.

Notice that while the Vec type is automatically imported in the current namespace, the VecDeque type, like the types of the other collections, must be explicitly qualified.

The VecDeque name is shorthand for vector-based double-ended queue. Here, the queue word means: sequential collection, into which items are inserted at one end and from which items are extracted at the other end. The fact of being double-ended means that the items can be inserted at both ends and extracted from both ends, with no penalty. Finally, the fact of being vector-based means that it is implemented storing its items in a vector, and that its items can be accessed using an integer offset, similarly to arrays and vectors.

To insert or remove items at the end of a vector, you can use the simple words push and pop, without specifying the point of insertion or extraction; it is understood that such point is the end, which is the only point where such operations are mostly efficient. Instead, VecDeque collections handle both ends equally well; so, the recommended functions to insert items at the beginning and at the end are, respectively, push_front and push_back; and the recommended functions to remove items from the beginning and from the end are, respectively, pop_front and pop_back. The VecDeque type also supports the insert and remove functions , similarly to vectors, but such functions are not recommended because they can be inefficient.

Given that queues are so efficient, why shouldn’t we always use them, instead of vectors?

It could print: 1599960000 495.299μs 466.374μs 16.642μs 89.7μs.

The count is printed just to force the compiler to do the actual computation. Otherwise, the optimizer could skip it all.

The times mean that to insert each item at the end of a collection, the Vec and the VecDeque collection types have almost the same performance, but for scanning the whole collection, Vec is five as fast.

Linked Lists

For some applications, there is the need to frequently insert and remove items in intermediate positions. In such cases, both vectors and queues perform such operations inefficiently, so, if you have such a need, you can resort to another kind of collection, LinkedList. Though, there are really few cases in which the usage of a LinkedList is justified.

Binary Heaps

It will print: 18 35 13 12 33 27 16 50 29 42 39 17 20 48 .

The data vector is used as an item provider. Its 14 objects are processed, two each iteration, in the seven iterations of the first loop. At each iteration, two items of the data vector are passed to the add function, which inserts them at the end of the v vector. Then, the last item is extracted from the v vector and printed. The last statement of the program repeatedly extracts and prints the last items of the vector, until the vector becomes empty.

The result is not the desired one, as the last inserted item will be always extracted, even if the collection contains an item bigger than it. For example, after having inserted the numbers 48 and 18, the first extracted number is 18, even though the number 48 is greater than it.

In both cases, the program will print: 48 35 20 39 42 33 50 29 27 18 17 16 13 12 .

In the first case, each time a value is added to the v vector, that vector is sorted again so that the values are always in ascending order. In the second case, the vector is sorted just before a value is extracted from the v vector. Both techniques guarantee that the extracted value is always the largest among those contained in the collection.

Both correct versions have the drawback of quite often invoking the sort function , which has a significant cost.

As you can see, binary heaps are used by invoking the push and pop functions , similarly to vectors. Though, while in these last collections the pop function extracts the last inserted item among those still contained in the collection, in binary heaps the pop function extracts the item having the largest value among those still contained in the collection.

Regarding the implementation, here we can say that both when an item is added and when an item is removed, some items are moved, so that the last item is always the largest; however, the other items are not necessarily in ascending order.

Ordered Sets and Unordered Sets

Another way to use a collection is to insert an item only if it is not already contained in the collection. That realizes the concept of mathematical set. Indeed, in mathematics it makes no sense to say that an item is contained several times in a set.

A way to implement this kind of insertion using a vector would be to scan the whole vector at every insertion, and insert the item only if it is not found. Of course, such an algorithm would be inefficient.

There are several techniques to create a collection that efficiently inserts an item only if it is not already contained, which is a collection that implements the concept of a set without duplicates.

The most efficient technique to search for arbitrary objects uses a kind of data structure named hashtable, so such a type of collection is named HashSet .

As you can see, the Vec collection contains all the ten inserted items, in insertion order; instead, the Hashset collection and the BTreeSet collection contains only seven items, as there is only one of the two 6 numbers, and only one of the three 8 numbers . Moreover, the BTreeSet collection is sorted, while the Hashset collection is in random order. A different run can generate a different order.

To insert a four-byte number at the end of a Vec, 8 nanoseconds are taken, while inserting it into a HashSet or BTreeSet takes around 15 times as long.

To sequentially search that forty-thousand-items vector for an existing number, around 9,000 nanoseconds are taken. Then, the vector is sorted (actually it was already sorted, so two items are swapped beforehand, to make timing more realistic), in 116 microseconds. To search that sorted vector using the binary search algorithm, an item is found in less than 40 nanoseconds on average. It turns out that, if searches are at least 13 times as frequent as insertions, it is more efficient to sort the array after every insertion and then use binary search.

To search the HashSet for a number, about 24 nanoseconds are taken; and to search the BTreeSet for a number, about 40 nanoseconds are taken. So they are orders of magnitude faster than a vector; the only case in which a sorted Vec with binary search is competitive with a BTreeSet is when first there are all the insertions into the vector, then the vector is sorted once, and then there are only searches.

All this happens in a particular platform, with a particular type of item, with a particular number of items, and with a particular sequence of operations. If you change something of these, the algorithm that used to be slower can become the fastest one.

The best way to optimize a data structure whose performance is critical is as follows. First declare a trait having all the operations that your data structure will offer to the rest of the application. Then create the simplest possible implementation of such trait and use that trait and its methods in the rest of the program. Then you measure if the performance of such methods is good enough. If it is good enough, there is no need to optimize it. Otherwise, you keep changing the implementation of the trait, and you measure the performance of the application until you find a satisfying implementation.

Ordered Dictionaries and Unordered Dictionaries

Another commonly used kind of collection is the dictionary, which is a collection accessible by a search key.

Dictionaries can be considered sets of key-value pairs, with the peculiarity that the look-up is performed using only the key. As a consequence, a dictionary cannot contain two pairs having the same key, even if their values are different.

An array containing five pairs is used as a source of data. Three other containers are declared and initialized as empty: a Vec, a HashMap, and a BtreeMap . Then, each pair of the array is inserted into such containers.

In fact, all of them will be inserted into the Vec, but only four of them will be inserted into the HashMap and into the BtreeMap, because they do not admit duplicate keys. When the pair (917, 'L') is inserted, it replaces the pair (917, 'C') already contained in the dictionary. Instead, duplicate values are allowed.

Notice that in the vector the items are in insertion order, in the BTreeMap collection they are in key order, and in the HashMap collection they are in random order.

Their performance is similar to that of the corresponding HashSet and BTreeSet collections.

Collections in C++ and in Rust

Those who know the C++ standard library will find useful the following table that corresponds C++ collections with Rust collections.