Comment by cyberax | Hacker News Reader

Comment by cyberax | Hacker News Reader

Parent Full thread

I worked in Linux kernel-level land.

Calling it "optimized" is a stretch. A veeeery big one. The low-level code in some paths is highly optimized, but the overall kernel architecture still bears the scars of C.

The most popular data structure in the kernel land is linked list. AKA the most inefficient structure for the modern CPUs. It's so popular because it's the only data structure that is easy to use in C.

The most egregious example is the very core of Linux: the page struct. The kernel operates on the level of individual pages. And this is a problem in case you need _a_ _lot_ of pages.

For example, when you hibernate the machine, the hibernation code just has a loop that keeps grabbing swap-backed pages one by one and writing the memory to them. There is no easy way to ask: "give me a list of contiguous free page blocks". Mostly because these kinds of APIs are just awkward to express in C, so developers didn't bother.

There is a huge ongoing project to fix it (folios). It's been going for 5 years and counting.

> It's so popular because it's the only data structure that is easy to use in C.

Is this reasoning really true? A quick search reveals the availability of higher-level data structures like trees, flexible arrays, hashtables, and the like, so it's not as if the linux kernel is lacking in data structures.

Linked lists have a few other advantages - simplicity and reference stability come to mind, but they might have other properties that makes them useful for kernel development beyond how easy they are to create.

> Is this reasoning really true?

Well, yes. The kernel _now_ has all kinds of data structures, but you can look at the documentation from 2006 and see the horror of even the simplest rbtrees back then: https://lwn.net/Articles/184495/

A simple generic hashtable was added only in 2013!

> Linked lists have a few other advantages - simplicity and reference stability come to mind, but they might have other properties that makes them useful for kernel development beyond how easy they are to create.

The main property is that it's easy to use from C. Think about growable vectors as an exercise.

Where do I find a basic vector type? :)

Why, right here: https://elixir.bootlin.com/linux/v6.16.9/source/rust/kernel/... !

(XArray in regular C-based Linux also kinda qualifies)

there's a whole library inside linux and it's really good too!

> It's so popular because it's the only data structure that is easy to use in C.

I don't understand that statement. Linked lists are no easier or harder to use than other data structures. In all cases you have to implement it once and use it anywhere you want?

Maybe you meant that linked lists are the only structure that can be implemented entirely in macros, as the kernel likes to do? But even that wouldn't be true.

Think about a growable vector. Another basic structure that everyone uses in the userspace.

You can iterate through it fine, it's just an array after all. But then you want to add an element to it. At this point you need to handle reallocation. So you need to copy or move the elements from the old array. But this will break if the elements are not simple data structures.

So you need to have a copy function. There are copy constructors in C++, but not in C. So you need to reinvent them.

Reply on news.ycombinator.com