Author: Jörn Engel

This presentation will examine various data structures used by the Linux kernel, including linked lists, hash tables and several tree structures. Focus is on memory consumption and cache misses. Two data structures will be pointed out that, according to the author, are a poor choice, in spite of being widely used. While focusing on the Linux kernel, most of this presentation should apply equally well to other software, both userspace and kernelspace.