Yes, Rust has Garbage Collection, and a Fast One

Rust is getting more and more popular. Thus, a group of colleagues, including myself, evaluated it for half a day to build up our own opinion, if Rust is of strategic interest for us or not. We did some coding following the standard introduction book, looked at some frameworks, and watched the presentation “Considering Rust”. The general conclusion was more or less in the line of: yeah, a nice new programming language, but without a full-grown ecosystem and without any garbage collection, it will be too cumbersome and unproductive for us in our projects. My gut feeling did not agree with the assessment regarding garbage collection. Thus, I did some more digging and testing and came up with my current conclusion: Rust does indeed garbage collection, but in a very clever way.

A Short History of Garbage Collection

When you look at the Web site of Rust and read the introduction, you quickly stumble about a proudly made statement that Rust has no garbage collector. If you are of my age, this raises some bad memories. There were times when you had to manually allocate memory, using malloc(), and to free it later again. If you freed it too soon, you got hit by something like an invalid memory access exception. If you forgot to free it, you created a memory leak that strangulated your application. Very seldom you got it right at the first time. This was something that was no fun at all.

Before looking at the approach Rust takes, let us look shortly what garbage actually means. In Wikipedia there is this nice definition: garbage includes data … which will not be used in any future computation by … a program running on it. This means only the developer can decide if a memory segment storing some data can be freed. But, the runtime of an application can automatically detect a subset of the garbage. If at some point of time, there exists no reference to a memory segment anymore, the program will not be able to access this segment. And, therefore it can be safely deleted.

To actually implement this support the runtime has to analyze all the active references in the application and has to check all allocated memory references, if they can be reached regarding the current application state. This is a very computationally intensive task. In the first days of Java it was common that the JVM suddenly freezes and had to do the garbage collection for a noticeable amount of time. Nowadays there are sophisticated algorithms for garbage collection running often concurrently to the application. But, the computational complexity is still the same.

On the plus side there is no need for the application developer to think about manually freeing memory segments. There will never be an invalid memory access exception. She still can create memory leaks by referencing data, that is not needed anymore. (The prime example IMHO are self-written cache implementations. The elderly advice: Never do this, use something like ehcache.) But, with the introduction of garbage collectors memory leaks were much more rarely seen.

How Rust Handles Memory Segments

Rust looks, at the first glance, a lot like C, especially with its referencing and dereferencing. But it has a unique approach of handling memory. Each memory segment is owned by one reference. From the developers perspective, there is always one variable owning the data. If this variable goes out of scope and is not reachable anymore, then either the ownership is transferred to some other variable or the memory is freed.

With this approach there is no need anymore, to compute the reachability for all your data. Instead, every time a naming context is closed, e.g. by returning from a function call, the reachability of the used memory is validated with a simple algorithm. This sounds so good, that probably in every experienced developer the question immediately arises: where is the catch?

The catch is, that the developer has to take care of the ownership. Instead of carelessly spreading references to data throughout the application, the developer has to mark the ownership. If the ownership is not clearly defined, the compiler prints an error and stops to work.

To evaluate, if this approach is actually helpful in comparison to a traditional garbage collector, I see two questions:

• How hard is it for a developer to mark the ownership while developing? If all her power is concentrated on fighting the compiler instead of solving the domain problems, this approach hurts more than helping.
• How much faster is the Rust solution in comparison to a traditional garbage collector? If the gain is not significant, why should we bother?

To answer these two questions I implemented a task in Rust and in Kotlin. The task is typical for an enterprise context and creates a lot of garbage. The first question is answered based on my personal experience and opinion, the second by concrete measurements.

The Task: Crunching the Database

The task I chose, is to simulate a typical database centric assignment, compute the average income of all employees. Every employee is loaded in memory and the average is computed in a loop. I am aware that you should never do this in real life, because databases can do this much faster on their own. But, firstly I saw this too often happening in real life, secondly with some NoSQL-Databases you have to do this in the application, and thirdly this is just some code to create lots of garbage that needs to be collected.

I chose Kotlin on the JVM as representative for the garbage collection based programming languages. The JVM has a highly optimized garbage collector and if you are used to Kotlin, using Java feels pretty much like working in the stone age.

You can find the code on GitHub: https://github.com/akquinet/GcRustVsJvm

Chrunching with Kotlin

The computation gets a sequence of employees, sums up their salaries, counts the number of employees, and finally divides these numbers:

fun computeAverageIncomeOfAllEmployees(
      employees : Sequence<Employee>
    ) : Double 
{
   val (nrOfEmployees, sumOfSalaries) = employees
       .fold(Pair(0L, 0L),
         { (counter, sum), employee ->
              Pair(counter + 1, sum + employee.salary)
         })
   return sumOfSalaries.toDouble() / 
          nrOfEmployees.toDouble()
 }

Nothing exciting here. (You may notice a functional programming style. This is, because I am a big fan of functional programming. But this is not the topic of this article. 🙂 ) The garbage is created while creating the employees. I create random employees here to avoid using a real database. But, would you use JPA , you would have the same amount of object creation.

 fun lookupAllEmployees(
        numberOfAllEmployees : Long
     ): Sequence<Employee>
{
   return (1L..numberOfAllEmployees)
            .asSequence()
            .map { createRandomEmployee() }
}

The creation of random objects is also pretty straight forward. The strings are created from a list of characters charPool.

fun createRandomEmployee(): Employee =
   Employee(
     createRandomStringOf80Chars(),
     createRandomStringOf80Chars(),
     ... // code cut Out
   )
fun createRandomStringOf80Chars() =
   (1..80)
      .map { nextInt(0, charPool.size) }
      .map(charPool::get)
      .joinToString("")

A little surprise in the Rust version was how I had to handle the before mentioned list of characters. Because I only need one singleton I stored it in a companion object. Here its outline:

class EmployeeServices {

    companion object {
        private val charPool: List<Char> 
           = ('a'..'z') + ('A'..'Z') + ('0'..'9')

        fun lookupAllEmployees(...) ...
        fun createRandomEmployee(): Employee ...
        fun computeAverageIncomeOfAllEmployees(...) ...
    }
}

Now, Crunching it the Rust way

The first thing I stumbled about was, where to put this singleton list of characters. Rust supports static data, directly embedded in the binary, and constant data, which can be inlined by the compiler. Both alternatives only support a small subset of expressions to compute the value of the singleton. My solution to calculate the pool of allowed characters was this:

let char_pool = ('a'..'z').collect::<Vec<_>>();

Because the computation of the vector is based on type inference, it is not possible to specify it as constant or static. My current understanding is that the idiomatic way to do this in Rust is to add all the objects, a function needs to work on, as parameters. Thus the main call to compute the average salaries in Rust looks like this:

let average = 
  compute_average_income_of_all_employees(
    lookup_all_employees(
            nr_of_employees, &char_pool,
  ) );

With this approach all the dependencies are clear. Developers with experience in C immediately recognize the address operator &, that returns the memory address as a pointer and is the basis for efficient and potentially unmaintainable code. When many of my colleagues played with Rust, this C-based negative experience was projected to Rust.

In my opinion this is not fair. The problems C suffers from the design of the & operator is that there always can be unpredictable side effects, because every part of the application can store a pointer to a memory block. Additionally every part can free the memory causing potentially all other parts to raise an exception.

In Rust the & operator works differently. Every data is always owned by one variable. If a reference to a data is created using & this ownership is transferred to the scope of the reference. Only the owner can access the data. If the owner goes out of scope, the data can be freed.

In our example the ownership of char_pool is transferred to the parameter of the function using the & operator. When the function returns the ownership is given back to the variable char_pool. Thus, it is kind of an address operator similar to C but it adds the concept of ownership resulting in much cleaner code.

Domain Logic in Rust

The main function in Rust looks more or less the same as in Kotlin. It feels a little bit more basic because of the cryptic number types, such as f64 for a 64 bit floating point number. But, this is something you can get accustomed to pretty quickly.

fn compute_average_income_of_all_employees(
     employees: impl Iterator<Item=Employee>
   )  -> f64
{
    let (num_of_employees, sum_of_salaries) =
        employees.fold(
          (0u64, 0u64),
          |(counter, sum), employee| {
              return (counter + 1, 
                      sum + employee.salary);
          });
    return (sum_of_salaries as f64) / 
           (num_of_employees as f64);
}

IMHO, this is a good example to prove that Rust is a very modern clean programming language with a good support for functional programming style.

Creating Garbage in Rust

Now let us take a look at the part of the program, where lots of objects are created and have to be collected later:

fn lookup_all_employees<'a>(
     number_of_all_employees: u64,
     char_pool: &'a Vec<char>
   ) -> impl Iterator<Item=Employee> + 'a 
{
    return
     (0..number_of_all_employees)
       .map(move | _ | {
         return create_random_employee(char_pool); 
        })
       .into_iter();
}

At the first look, this looks pretty similar to Kotlin. It uses the same functional style to create random employees in a loop. The return type is an Iterator, which is, similar to a sequence in Kotlin, a lazily evaluated list.

At the second look, the types look strange. What the heck is this 'a? It solves the problem of the lazy evaluation. Because the Rust compiler can not know when the return value is actually evaluated and the return value depends on a borrowed reference, it has now the problem to determine when the borrowed value char_pool can be freed. The 'a annotation specifies that the lifetime of char_pool must be at least as long as the lifetime of the returned value.

This is a new concept for a developer used to classical garbage collection. In Rust she sometimes has to explicitly specify lifetimes of objects. Something, which is not needed when a garbage collector does all the clean up.

At the third look, you could discover the move keyword. It enforces the closure to take ownership of all the variables it uses. This is necessary because of char_pool (again). Map is executed lazily, thus, from the perspective of the compiler the closure may outlive the variable char_pool. Therefore the closure has to take ownership of it.

The remainder of the code is pretty straightforward. The structures are created from randomly created strings:

fn create_random_employee(
     char_pool: &Vec<char>
   ) -> Employee 
{
  return Employee {
    first_name: 
      create_random_string_of_80_chars(char_pool),
    last_name: 
      create_random_string_of_80_chars(char_pool),
    address: Address
    { // cut out .. },
        salary: 1000,
    };
}

fn create_random_string_of_80_chars(
     char_pool: &Vec<char>
   ) -> String 
{
    return (0..80)
        .map(|_| { 
          char_pool[
            rand::thread_rng()
               .gen_range(0,
                          char_pool.len())]
         })
        .into_iter().collect();
}

So, HOw Hard is Rust?

Implementing this tiny test program was surprisingly complicated. Rust is a modern programming languages that enables the developer to quickly and cleanly maintainable code. But, its concept of memory management is directly reflected through all the elements of the language and is something a developer has to understand.

The tool support is IMHO very good. Most of the time, you just have to do what the compiler tells you to do. But sometimes you have to actually decide how you want your data being handled.

Now, Is it worthwhile?

Even if something sounds convincing, I am a big fan of doing some measurements to see if the reality is convinced too. Therefore I ran the Rust and Kotlin applications for four different input sizes, measured the time, and put the results in a logarithmically scaled diagram:

Looking at the numbers I made a pretty long face. Rust is always slower; for 10^6 elements a pretty bad factor of 11. This can not be. I checked the code and found no errors. Then, I checked for optimizations and discovered the --release flag that switches from dev mode to prod. Now, the results looked much better:

This is much better. Rust is now always faster than Kotlin and provides a linear performance. Looking at Kotlin we see the typical performance improvements for longer running code, probably caused by just-in-time-compilations. From input sizes of 10^4 Rust is roughly a factor of 3 faster than Kotlin. This is pretty impressive, considering the maturity of the JVM and the resources invested in the infrastructure over the last decades (The first version of Java was released in 1995).

For me, it is surprising how much slower the development profile is in comparison to the production profile. A factor of 40 is so big, that you never ever should use the development profile for releases.

The Conclusion

Rust is a modern programming language with all the comfort you got used to nowadays. It has a new approach to memory handling that puts a little extra burden on the shoulder of the developer but also provide for excellent performance.

And, to answer the initial question of the title, you do not have to manually take care of your garbage in Rust. This garbage collection is done by the runtime-system, but it is not called garbage collector anymore.

ADDED:
In the meantime I wrote two follow-ups on this article:
Kotlin/JVM, Rust, and Randy Random
Haskell is Faster Than Rust! … Wait A Sec!