• TLDR: The original Kotlin/Native memory management approach was very easy to implement, but it caused a number of problems for developers trying to share Kotlin code across different platforms.

Back in 2020, plans were announced to redesign the memory management approach in Kotlin/Native. The original post described the historical background, listed the problems now being faced, and explained why the approach had to change.

Now officials have updated the progress and shared some details about the memory management design. In addition, they plan to present a development preview by the end of summer 2021.

  • The basics of automatic memory management
  • Reference counting and trace garbage collection
  • Kotlin/Native garbage collector
  • New garbage collector infrastructure
  • Next steps

The basics of automatic memory management

The concept of automatic memory management is as old as programming languages. Early programming languages had no concept of a heap at all. All memory is statically or stack-allocated. The developer does not have to worry about memory allocation and deletion at run time because memory is always allocated (statically) or managed automatically (via the stack) and nothing needs to be done “manually”. This makes things easy, but it limits the software to work with data of a fixed size, and limits on the number of items to work with must be hard-coded in the source code.

PL/I and AlGol-68 in 1966 were the first two major languages to add to the concept of dynamically allocated memory as we know it today, establishing a tradition of manual memory management. This forces developers to write explicit code to allocate and free memory in the heap.

However, LISP is even older. In LISP, you can deal with dynamically sized data structures without having to pre-declare their size limits or write code to allocate and free underlying memory. This is all done automatically by the garbage collector. The concept of garbage collection as a form of automated management was invented by John McCarthy for LISP in 1959.

Since then, numerous garbage collection algorithms have been created and implemented in various systems. The goal of these algorithms is to automatically find and reclaim areas of memory that are no longer needed by garbage running programs.

Algorithms differ in the way they identify garbage and are generally divided into two categories.

  • The garbage collection algorithm for reference counting starts at the leaf of the object graph and tracks the number of references to a particular memory region. A live object that is still being used by the program will have a non-zero reference count.
  • The trace garbage collection algorithm starts at the root of the object graph and walks through the graph to identify all live objects. A dead object that is not used by the program will not be touched.

The science of garbage collection has a whole set of algorithms, many of which are hybrids of the two approaches. If you want to learn more, a good place to start is the Garbage Collection Manual, and the Garbage Collection Manual: The Art of Automatic Memory Management by Richard Jones et al.

Reference counting and tracking garbage collection

A common misconception is that garbage collection is completely different from reference counting. In fact, reference counting is a fair name for a broad family of garbage collection algorithms. In this context, garbage collection tends to refer more specifically to tracking garbage collection.

Another popular misconception is that the reference counting garbage collector reclaims free memory as soon as it is no longer needed. While it is possible to implement a reference counting garbage collector with this property, it is rarely done because immediate reference counting adds considerable overhead to reference-heavy code.

Choosing a garbage collector algorithm involves finding the right balance between the garbage collector’s throughput (its overhead in terms of the number of objects per allocated or reclaimed object) and the timeliness of memory collection (or how much more memory space it needs to operate on). Practical reference-counting garbage collection implementations typically use deferred counting and other similar techniques to improve runtime performance, while sacrificing memory usage in the process.

Kotlin/Native garbage collector

The original Kotlin/Native automatic memory manager used a garbage collector with deferred reference counting. It was chosen for its simplicity — not for its memory consumption. But this initial choice now stands in the way of improving Kotlin/Native’s performance and developer experience.

There is also the issue of collection pauses. Contrary to another popular myth, the reference-counting garbage collector is not pauses free in nature. Suggestive memory allocation and reclamation have low throughput and can result in significant allocation delays. In addition, these collectors cannot be easily moved to background threads to avoid blocking critical threads of the application. When trying to reduce the overhead of the overall reference count by delaying and grouping allocation, as Kotlin/Native currently does, pauses become fewer but longer.

Compared to reference counting, modern trace garbage collection algorithms are much more flexible and adjustable than reference counting garbage collectors, and more easily adapted to the needs of multithreaded applications. However, all trace garbage collectors have a common weakness — they require a fairly complex infrastructure from the programming language runtime and compiler.

New garbage collector infrastructure

Currently, new infrastructure is being studied. The first task is to determine the root — all the places in memory where references to dynamically allocated memory can be stored. This will allow us to start tracing an object graph. Roots lurk in global variables, thread locations and call stacks, and at the boundary with platform libraries.

In addition, a special infrastructure is required to implement concurrent garbage collection algorithms. Why so much trouble? Because the team’s primary usage scenario is running UI applications. UI applications have a delay-sensitive main thread, so a design that only supports stopping the world’s garbage collection is not feasible for Kotlin/Native.

As the program executes, the collection of roots that the tracing garbage collector must know changes. So you decided to use what’s known as the safe point approach, which labels compiled code as safe or unsafe based on whether all the roots are stored in predictable locations. These locations are known to the runtime, which means that garbage collection can run concurrently with code in a safe state.

Design of another goal is to realize the seamless interoperability and the platform of the library, the need to increase the automatic management of the handle to the memory leak to the management of the world track support, support for weak references, and the automatic management of Kotlin object has an additional platform specific objects run additional support to assign code.

To test the new infrastructure, the team is writing a simple stop-world tag and sweep garbage collector. This is not the algorithm used in production, but it takes advantage of all the infrastructure that any trace garbage collector implementation relies on. Through extensive testing of this implementation, we hope to find all potential errors in the underlying implementation (such as forgotten root references, or code with unmarked unsafe areas). The first implementation will not support multithreading and will only be used for testing purposes.

Next steps

The next step is to write a multithreaded garbage collection implementation, port the Kotlinx.coroutines library onto it, and test it. Their goal is to allow you to use multithreaded background scheduling queues on Darwin and start loops freely without freezing objects working in background threads. This will be the first public milestone, and Kotlin’s team plans to present it as a development preview in late summer 2021. It won’t be production-ready because it will focus on correctness rather than performance.

Once you have a proper implementation of the trace garbage collector, there will be a greater focus on performance and a more determined tradeoff between allocation, memory usage, and throughput. At this point, Kotlin will be able to use many different garbage collector implementations, including hybrid, because its underlying infrastructure is specifically designed to support pluggable garbage collection algorithms, including reference counting and tracing.

Kotlin plans to implement a production-ready garbage collection implementation that supports frictionless sharing of objects between threads and satisfies all other design goals. In the future, however, there may be supported garbage collection algorithms that are optimized for different usage situations.

Initially, the original Kotlin/Native memory management scheme will continue to be supported to simplify the migration of existing Kotlin/Native applications. When building your Kotlin/Native application, you will be able to choose your garbage collection implementation. The source code for your application will not change because the selection will be made through the compiler flag.

The original link: blog.jetbrains.com/kotlin/2021…