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

Better linked-list traversal in BPF

Posted Mar 8, 2024 18:14 UTC (Fri) by mb (subscriber, #50428)
In reply to: Better linked-list traversal in BPF by epa
Parent article: Better linked-list traversal in BPF

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.

to post comments

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.