December 20, 2019

198 words 1 min read

Replacing the Radix Tree

Replacing the Radix Tree

Last year I gave a talk extolling the benefits of the Linux radix tree. This year I am talking about its shortcomings, what I did to improve things, and how I came to the conclusion that it had to be …

Talk Title Replacing the Radix Tree
Speakers Matthew Wilcox (Programmer, Oracle)
Conference Open Source Summit Europe
Conf Tag
Location Prague, Czech Republic
Date Oct 21-27, 2017
URL Talk Page
Slides Talk Slides
Video

Last year I gave a talk extolling the benefits of the Linux radix tree. This year I am talking about its shortcomings, what I did to improve things, and how I came to the conclusion that it had to be replaced. The new XArray is easier to use than the radix tree. Conceptually, it is an array of 16 quintillion pointers, all of which are initially NULL. Just like an array, its basic operations are ‘load’ and ‘store’, unlike a tree’s ‘lookup’, ‘insert’ and ‘delete’. It provides some more advanced operations, and enables users to build their own operations. This talk covers general aspects of API design for C programmers, as well as particular considerations for kernel API design due to the constrained environment.

comments powered by Disqus