4 ms·
A linked list is almost certainly not what you want either. They're so deeply cache-unfriendly that their appearance in kernel code should be viewed as suspect.
by grabcocque 9y ago
A linked list is almost certainly not what you want either. They're so deeply cache-unfriendly that their appearance in kernel code should be viewed as suspect.
- justinhj 9y agoThe article indicates use of a slab cache which means that all the socket structures will be together in memory.
- deleted 9y ago[deleted]
- UK-AL 9y agoI was under the impression, that linked lists are quite common in the Linux kernel.
- huhtenberg 9y agoThey indeed are.
- forgotpwtomain 9y ago> They're so deeply cache-unfriendly There a number of variations on linked lists, which are cache friendly (e.g. unrolled linked lists)
- panic 9y agoWhat would you use instead?
- Johnny_Brahms 9y agoHave you looked at the Linux source? It is full of linked lists everywhere.
- tropo 9y agoThey are cache-friendly in normal Linux kernel usage. There are not distinct allocations for list links; the pointers are embedded (via a small struct) in the struct that is being dealt with. In walking the list, you normally need to look at that stuff anyway, and with everything together you can share cache lines. It isn't normal to run down the entire length of a list without looking at the data. Since you need to look at the data anyway, it is best that the data share cache lines with the linked list info.