3 ms·
A technique commonly used in C, for example in the Linux kernel. You embed "links" to other nodes in your structs, and find the struct from the link based on of
by exDM69 11y ago
A technique commonly used in C, for example in the Linux kernel. You embed "links" to other nodes in your structs, and find the struct from the link based on offsetof. Linux kernel uses linked lists and red-black trees this way. Probably other data structures too.
Intrusive containers are cache friendly and typically require no dynamic allocations (in addition to allocating the data itself).
See the link in the post above for more about linked lists in the linux kernel.
- charlieflowers 11y agoInteresting. At first I thought you were claiming this technique made linked lists cache friendly. After looking at it, I have concluded you meant merely that the next and prev pointers are near your data. Am I understanding you correctly?
- krakensden 11y agoThat's my understanding too. Instead of going to your data structure, and then dereferencing a pointer to your data, after going to your data structure, you're already there.
- exDM69 11y agoYes, there's one pointer chase less when you don't have a pointer from the link node to the data, but you can get it with offsetof. This can save a significant number of cache misses in some algorithms.