To have a good chance that there is space near the other nodes, you’d have to reserve memory up front for each list you’d want to do that with, though, and that will kill cache locality before that optimization sets in. Corrections welcome, but I don’t see that (easily) being a net win. But hey, with a sufficiently smart compiler at hand, you can do wonders. (Edit: when looking at pure functions, it many times may not be that hard to discriminate between “this allocation will be returned” and “this allocation is temporary”. For example, if you use map to apply a function to all elements in a list, and that function is pure, detecting that only the return values of that function will be visible after the function returns isn’t that hard)
An easier win is that lisp garbage collectors tend to move memory, and thus can try to move nodes that reference each other close together. You get that for free with a semispace collector, but that has quite a few disadvantages, so you don’t want to use that. A generational collector also will do it a bit, though (say you create a few million nodes of garbage to build a list of a few hundred results. Then, after generational collection, those few hundred cells will be closer together than before)
While there is a natural encoding of this process into a pointer to the target value, and a pointer to the next node, it is not the only encoding possible by any means.
A good exercise if you are having trouble with this is to implement a little linked list that performs those operations on something that simply backs to an array, including the blind O(n) copy when appending another list. It should be quite short. But that is not the only alternate implementation, either, and you can easily build others where the interface is maintained but you pay only log n additional factors maximum for operations, easily recovered from the constant factors which on modern hardware are often staggering.
Once you break the entanglement between memory representation and the API a data structure offers in your mind, many ways become obvious as to how to possibly improve this structure while maintaining the same operations, many of which of course already exist and have names.
But just because Lisp has cons and cdr does not mean the compiler is obligated to only and exactly use things that structurally look like linked lists in the actual implementation. You need to break the relationship between memory layout and API to understand what is going on here. You may choose later to put them back together; the naive memory layout is often a good one. (Linked lists nowadays are arguably one of the larger exceptions to that, but there are still circumstances even so where that may not be an issue; see Erlang's memory management for instance and ponder how that impacts linked list locality.) But you can't understand what compilers may be doing if you do not realize that there is a distinction.
If your argument is that a linked-list-like data structure can be implemented using something other than a linked list, then I agree with you. Vector tries (for example) are great for that use case.
But a vector trie isn't a linked list, it's a vector trie. As such, it will be faster for some usage patterns, equal for some, and completely degenerate for some others. Just like any other data structure that isn't a linked list.
It wouldn't really be an "optimization" to implement my linked list code with something other than a linked list - it would be rewriting my code.
That worked surprisingly well, but there were lots of edge cases since I am a professional bassoonist and not a compiler guy.
I generalized it and made all lists allocated in chunks of 16 and then let the GC truncate it. I spent a stupid amount of work doing the first thing and the second thing was done in an afternoon.
Then there are all kinds of
From my understanding this is what led to the recent 'unpatchable' exploit in Apple's M1, but rather then trying to guess it by some heuristic, why not just give compilers option to make that optimization?
It turns out programmers, or rather their employers, don't really care about using hardware efficiency. They care about shipping things yesterday, because that's how business deals get closed, and making software efficient is secondary to money changing hands. Performance never really matters to business people after the checks are cashed.
Multicore computers have been ubiquitous for more than a decade, yet the overwhelming majority of software built today is single-threaded microservices, where in they spend most of their time serializing and deserializing message payloads.
This is all really to say that most performance is already being left on the table for the majority of what computers are used for today.
And it's not like the companies arent trying this idea (again, M1 exploit). But for whatever reason they want to keep cpus as black box, perfect abstract machines, even though we know they aren't
Very good optimizing compilers existed before LLVM. Intel had one specifically for Itanium. It wasn't enough.
But for all the crazy optimizations modern compiler do, I don't see how marking pointers for more then couple of them in a raw is that crazy
And unrolling loop for traversing linked lists can be done, if you use a sentinel node instead of nullptr to signal then end:
beqz a0, .end
.loop:
ld a1, 0(a0) ; a1 = curr->data
ld a0, 8(a0) ; curr = curr->next
; do something with payload in a1 here
bnez a1, .loop
.end:
la s1, sentinel
beq a0, s1, .end
ld a1, 0(a0)
ld a2, 8(a0)
ld a3, 0(a2)
ld a4, 8(a2)
ld a5, 0(a4)
ld a6, 8(a4)
beq a6, s1, .trail
.loop:
ld t0, 0(a6)
ld t1, 8(a6)
ld t2, 0(t1)
ld t3, 8(t1)
ld t4, 0(t3)
ld t5, 8(t3)
; do something with three payloads in a1, a3, a5 here
mv a1, t0
mv a2, t1
mv a3, t2
mv a4, t3
mv a5, t4
mv a6, t5
bne t5, s1, .loop
mv a0, a2
beq a2, s1, .end
.trail:
ld a1, 0(a0)
ld a0, 8(a0)
; do something with payload in a1 here
bne a0, s1, .trail
.end:
Oh, and if you want to see something really crazy, look at e.g. splitting the branch instruction into prediction and resolution instructions [0].
[0] https://zilles.cs.illinois.edu/papers/branch_vanguard_isca_2...
Benchmarking is hard, and very often is done in ideal conditions, which never materialize in real use cases.