Better linked-list traversal in BPF

Posted Mar 9, 2024 6:36 UTC (Sat) by epa (subscriber, #39769)
In reply to: Better linked-list traversal in BPF by mb
Parent article: Better linked-list traversal in BPF

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.

to post comments

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.