3 ms·
Well in the articles case, it's the linked list `next` pointers: https://mazzo.li/posts/value-speculation.html#value-speculation-bailing-us-out https://mazzo.l
by dmoy 2y ago
Well in the articles case, it's the linked list `next` pointers:
https://mazzo.li/posts/value-speculation.html#value-speculation-bailing-us-out https://mazzo.li/posts/value-speculation.html#value-speculat...
In a happy case, those will be laid out sequentially in memory so you can guess the value of the pointer easily.
(That said your comment still stands, since using linked lists in the first place is much more rare). But I suppose there's probably a lot of other domains where you might have a performance critical loop where some hacky guessing might work.
- account42 2y agoNot only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.
- gpderetta 2y agothe optimization could be vaguely interesting if you are implementing a lisp (or some other list heavy language) and don't want to perform too aggressive non-local optimizations to optimize the layout of lists.
- twoodfin 2y agoAs I recall, at least one of the Lisp machine Lisps used a bit in the cons pair to declare if the cdr (tail element) was immediately following. EDIT: https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding
- kevin_thibedeau 2y agoMemory pools are commonly allocated in a contiguous block and sliced into nodes placed onto a free list. They will be sequential until the pattern of allocations mixes them up.
- kazinator 2y agoGarbage collection is good at consolidating swaths of adjacent free objects into ordered allocation.
- saagarjha 2y agoThe point here is that this isn't guaranteed, it's that it is likely. And as the other commenters mention, it's likelier than you think.
- kazinator 2y agoThe Linux kernel is full of links, and so are many (probably most) C programs in the GNU/Linux userland.