This event has ended. Visit the official site or create your own event on Sched.
September 11-14, 2017 - Los Angeles, CA
Click Here For Information & Registration
Back To Schedule
Wednesday, September 13 • 11:00am - 11:40am
Replacing the Radix Tree - Matthew Wilcox, Microsoft

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
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.


Matthew Wilcox

Mr, Microsoft
Matthew has been a Linux kernel hacker since 1998 when he made a minor modification to the isofs filesystem. Since then, he's worked on many parts of the kernel including the ARM, PA-RISC, Itanium, x86 and powerpc architectures, file locking, the PCI and SCSI subsystems, semaphores... Read More →

Wednesday September 13, 2017 11:00am - 11:40am PDT
Georgia I/II
  LinuxCon Tracks