Better linked-list traversal in BPF [LWN.net]

Better linked-list traversal in BPF

Posted Mar 8, 2024 16:25 UTC (Fri) by pj (subscriber, #4506)
In reply to: Better linked-list traversal in BPF by atnot
Parent article: Better linked-list traversal in BPF

Indeed, it's my understanding that it's more efficient for traversal to allocate an array of node records and then make a linked list based on array indices. This may also shrink the memory footprint because the array index (aka 'pointer') may be smaller (u16 or even u8) than a machine pointer.

to post comments

Better linked-list traversal in BPF

Posted Mar 8, 2024 16:52 UTC (Fri) by atnot (guest, #124910) [Link]

If you're creating a dependency between the next address to access and the contents of the previous address, that's going to be bad regardless of whether you use indexes or pointers. BPF wouldn't like that either. You really just want a count and some data; that's trivial to analyze.

Allocating stuff together does make a big difference and you should definitely do it. But at that point you may as well just use the length and capacity values you have to store anyway to do a proper dynamic array. Then just swap elements in place or, if you must, have a separate table of indexes sorted by some other value, like in a hashtable. Or just use a well implemented tree or hash table outright. But really most of the time you don't need any of that.

Better linked-list traversal in BPF

Posted Mar 8, 2024 16:54 UTC (Fri) by willy (subscriber, #9762) [Link] (7 responses)

Demonstration code:

https://www.infradead.org/~willy/linux/scan.c

That doesn't actually do linked-list-by-index-instead-of-pointer. Someone who's interested can make that modification. But it's about 10x as fast to walk an array of random pointers as it is to walk a list of random pointers, depending on your CPU.

Better linked-list traversal in BPF

Posted Mar 8, 2024 17:48 UTC (Fri) by epa (subscriber, #39769) [Link] (6 responses)

Perhaps a useful optimization would be to define a magic pointer value which means “next one in memory”. You could even use null for that if you have some other way to signal end of list. Then your code would be like

if (curr->next == MAGIC) ++curr;
else curr = curr->next;

If the linked list is laid out mostly continuously in memory most of the time (perhaps not completely contiguous all of the time, because then you’d be using an array or vector instead) then the branch predictor should be able to learn the first case is more common and the code can run almost as fast as an ordinary loop over an array.

Better linked-list traversal in BPF

Posted Mar 8, 2024 18:14 UTC (Fri) by mb (subscriber, #50428) [Link] (2 responses)

You don't need magic for that:

if (curr->next == curr + 1) ++curr;
else curr = curr->next;

But I don't get why that would help.
You can just say curr = curr->next, because you need to load the next pointer anyway.

I wouldn't be surprised if the compiler would optimize it into that.

Better linked-list traversal in BPF

Posted Mar 9, 2024 6:36 UTC (Sat) by epa (subscriber, #39769) [Link] (1 responses)

You need to load the next pointer but the processor can learn that it’s usually the following address and load it speculatively. Whereas if you simply dereference it the processor might not be able to look so far ahead. That’s my thinking.

If the flag to say “just increment” were included in a part of the data structure you have to load anyway, then it might save some memory access too.

Better linked-list traversal in BPF

Posted Mar 9, 2024 18:08 UTC (Sat) by Baughn (subscriber, #124425) [Link]

Correct, so it would be faster on average, and a lot of the time the next location will be loaded whether or not it’s useful, regardless of list design — cache lines can only be loaded as a whole.

This isn’t a new approach, by the way. LISP famously uses lists a lot, and LISP machines needed to process them quickly. Even with memory latency at the time being much lower relative to CPU speeds, laying them out contiguously in memory was a standard trick. One way to do that is to use a copying garbage collector, which if coded correctly will automatically defragment the lists when they’re copied.

Better linked-list traversal in BPF

Posted Mar 8, 2024 18:59 UTC (Fri) by atnot (guest, #124910) [Link] (2 responses)

There's hash tables that do this. But I think in reality that's kind of just otherthinking it. Very few C programs use linked lists for good reasons and want or need any of the very few positive properties of them. It's mostly just used because it's the first thing you learn in school and perhaps more importantly the only datastructure that's easy to implement and use in C without macro hell. That and not nearly enough people tell programmers it's a bad idea.*

* this goes beyond just performance implications but architectural decisions too. One of the "advantages" of linked lists is that list items rarely move once they get created. This inevitably leads to things like structures getting bloated with information really only needed by one user and people stashing long-lived pointers to objects on lists somewhere without really worrying about how long they'll stay valid for, which ossifies into the familiar pointer hell codebase where you're scared of changing anything because something might still be holding a pointer to it and 5% of your CPU time is refcounting. But I digress.

Better linked-list traversal in BPF

Posted Mar 9, 2024 15:51 UTC (Sat) by adobriyan (subscriber, #30858) [Link] (1 responses)

How would you structure (pardon the repetition) data structures?

Userspace have a luxury of kernel doing equivalent of vmalloc for their std::vector's, but kernel have to deal with fragmentation.

Better linked-list traversal in BPF

Posted Mar 9, 2024 20:24 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link]

There's no real reason the kernel can't allocate its internal data in a contiguous virtual RAM. It's just that right now the kernel has one simple 1-to-1 mapping.