ONGOING DEVELOPMENT

Linux uses some complex data structures to track its internal state. Much time and effort has been spent optimising the choice of algorithms and the structures in memory that they operate upon. Yet there’s always room for improvement, particularly when it comes to contended structures that don’t scale well in today’s multi-core world.

Readers may be familiar with popular data structures such as a hash, dict or a map. These are containers used to store data in a way that’s more efficient to index or search than just a simple list. In the latter case, a naive algorithm may have to iterate through every piece of data to find the one of interest, while structures enable data to be organised in a way more conducive to fast lookups.

Trees may be less familiar data structures to many, but they are common, particularly in high-performance code that must rapidly traverse a large amount of data. In a tree structure, each entry contains a value as well as pointers (links) to children and parent nodes. Traversing a tree is faster than going through a list because an algorithm only needs to traverse a few nodes before finding the one it needs. One type of tree is a redblack tree, so named because it’s formed from nodes that are “coloured” either red or black. These “rbtrees” are used within the Linux Virtual Memory subsystem to keep track of Virtual Memory Areas (VMAS).

VMAS are how the kernel tracks which regions of a program’s memory have been mapped (allocated). But rbtrees have scaling limits because locks must be acquired when manipulating them. The “Maple” Tree is an effort to remove the contended locks required by the existing red-black tree implementation. It models another tree known as a B-tree (common in databases). While initial performance numbers show modest improvement, it’s expected to be more readily optimised for scale.