Fast linked lists(dygalo.dev) |
Fast linked lists(dygalo.dev) |
If you implemented your own parser for the schema and the JSON and only used an AST to validate + span information (which can just be a pair of u16s for start/end of a token) then you can collect your error messages very, very quickly and generate the error message once validation is finished.
Heavily optimized compilers will do this for semantic analysis and type checking, where the IR they use can be constructed quickly and then used with the input text to get helpful messages out, while the guts of the algorithm is only working with semantic information in a structure that's compact and easy to access/manipulate.
All that said, serde_json is incredibly convenient and giving up to write your own parser is a big hammer for a problem that probably doesn't need it.
I had a thought in my reply [0] on this that actually might let him eat his cake and have it too in this regard. I think you can heavily abuse serde::de::Visitor to schema validate without actually parsing (or with less parsing, at any rate). I went into more detail in my comment but I wanted to ping you (@duped).
Or, use sonic_rs::LazyValue if you want to parse json on demand as you traverse it.
struct Token {
token_type: u8,
type_info: u8,
token_start: u32, // offset into the source file.
token_len: u16
}
It's been developed for embedded systems (it was written originally for a NATS implementation in the Zephyr RTOS), so it's a bit limited and there's no easy way to know where some parsing/type validation error happened, but the information is there if one wants to obtain it: https://github.com/lpereira/lwan/blob/master/src/samples/tec...
The fewer bytes you can pack data into the more data that you can process per second. Computers may be the most complex machines ever built but the simple fact of having fewer things to touch means you can touch more things in the same amount of time remains true.
- almost no cost in the non-erroring path
- no extra data structures to manage
- a lot less code
I think the post would benefit from a better analysis of why this doesn't work for them.
This idea was added after I wrote the post and wasn't taken from my own optimization efforts in `jsonschema`. Originally, in `jsonschema` the output type is actually a badly composed iterator and I intended to simplify it to just a `Result<(), ValidationError>` for the article, but with this output, there are actually way better optimizations than I originally implemented.
If I'd discovered this idea earlier, I'd probably spend more time investigating it.
Two suggestions: it’s not immediately obvious whether subsequent benchmark result tables/rows show deltas from the original approach or from the preceding one (it’s the latter, which is more impressive). Maybe call that out the first couple of times?
Second, the “using the single Vec but mutating it” option would presumably benefit from a reserve() or with_capacity() call. Since in that approach you push to the vector in both erroring and non-erroring branches, it doesn’t have to be exact (though you could do a bfs search to find maximum depth, that doesn’t strike me as a great idea) and could be up to some constant value since a single block memory allocation is cheap in this context. (Additionally, the schema you are validating against defines a minimum depth whereas the default vec has a capacity of zero, so you’re guaranteed that it’s a bad choice unless you’re validating an empty, invalid object.)
But I agree with the sibling comment from @duped that actually parsing to JSON is the biggest bottleneck and simply parsing to the minimum requirements for validation would be far cheaper, although it depends on if you’ll be parsing immediately after in case it isn’t invalid (make the common case fast, assuming the common case here is absence of errors rather than presence of them) or if you really do just want to validate the schema (which isn’t that rare of a requirement, in and of itself).
(Edit: I do wonder if you can still use serde and serde_json but use the deserialize module’s `Visitor` trait/impl to “deserialize” to an enum { Success, ValidationError(..) }` so you don’t have to write your own parser, get to use the already crazy-optimized serde code, and still avoid actually fully parsing the JSON in order to merely validate it.)
If this were in the real world, I would use a custom slab allocator, possibly from storage on the stack rather than the heap, to back the Vec (and go with the last design with no linked lists whatsoever). But a compromise would be to give something like the mimalloc crate a try!
0 1 M / Nth node
[ N elem ] [.] -> [N elem] [.] -> .... -> [M - (M / N) elem] [null]
index (node i) :
acc = 0
while acc + N < i
acc += N
node = node.next
return node.array[j - acc]
For example say you have N = 8 and there are 1024 elements in the list, you would need 127 pointer dereferences to reach the end of the array. In a B-tree you only have 3. (double check my math, I might be off by one).
This is the typical implementation for immutable/persistent vector types. If you keep the links between leave nodes at the bottom of the tree, you've got a B+ tree and have fast iteration through it as well.
But you size the nodes dynamically, rather than using a fixed size.
I beg to disagree.
In kernels, drivers, and embedded systems they are very common.
The major slowness of linked lists is cache inconsistency. New nodes can be put all over the memory space. However, if you can make sure all or part of the list exists in contiguous blocks of memory, then there's a good chance that when the CPU loads up the next node it will also grab the next 3 nodes in a cache line.
The closer these node addresses are in memory, the faster things will be.
Yes, if you have a simple choice between a vector and a linked list, then the vector is vastly superior due to locality and (for non-intrusive linked lists) allocations. So much so that vectors often win even when you're doing lots of O(n) deletions that would be O(1) with a linked list.
But that doesn't mean that linked lists are useless! A vector gives you a single ordering. What if you need multiple? What if you need a free list, which you're never going to be iterating over but will just grab off an item at a time? I find it quite common to have one "natural" order, for which I will use a vector (or equivalently, a bump allocator of fixed-size items), and then one or several auxiliary orders like the entries belonging to a particular owner or the ones that will need to be visited for some sort of cleanup or an undo list or some sort of stack or queue of pending items to process. Your common iteration will be in memory order, but that doesn't mean you won't ever want to do different iterations.
It annoys me that this is always omitted, with the attitude that linked lists are obsolete and useless because vectors be moar better faster gooder, to the point that it's a waste of time to learn how to manipulate linked lists anymore.
I guess a lot of this is probably due to the popularity of high level languages, where you're just dealing with references to everything in the first place. But in those, the arguments in favor of vectors are often not valid because that blessed golden vector of Objects is giving you no more locality than giving your Object a `next` field: the vector of Objects is represented internally as a vector of pointers to the actual Object data, so your oh so nicely cached lookups are doing memory reads that are 100% pure overhead compared to following a `next` link from an Object that fits into a cache line. In both cases, your performance is going to be limited by the locality of your Object data, which is the same whether you have a vector of pointers or Object data with an intrusive pointer.
Also, if you have an existing setup and need to introduce a new list, it is sometimes far easier to drop in a `next` (and maybe `prev`) field than to refactor everything to accommodate a new vector. Especially since the vector will move all of your data when resizing the vector, which invalidates any pointers you might be using for other purposes. If you'll be iterating that list frequently, then the vector may very well be a good idea. If it's just for error cases or slow paths, then linked lists really aren't bad at all.
I'm not trying to argue for linked lists here so much as arguing against the blanket arguments against them.
</rant>
In general, use vecs until you absolutely can't.
Perhaps there are a few uses for LL's in limited circumstances.
It would be interesting to see the performance of a `Vec<&str>` where you reuse the vector, but also a `Vec<u8>` where you copy the path bytes directly into the vector and don't bother doing any pointer traversals. The example path sections are all very small - 'inner', 'another', 5 bytes, 7 bytes - less than the length of a pointer! storing a whole `&str` is 16 bytes per element and then you have to rebuild it again anyway in the invalid case.
---
This whole article is kinda bad, it's titled 'blazingly fast linked lists' which gives it some authority but the approach is all wrong. Man, be responsible if you're choosing titles like this. Someone's going to read this and assume it's a reasonable approach, but the entire section with Vec is bonkers.
Why are we designing 'blazingly fast' algorithms with rust primitives rather than thinking about where the data needs to go first? Why are we even considering vector clones or other crazy stuff? The thought process behind the naive approach and step 1 is insane to me:
1. i need to track some data that will grow and shrink like a stack, so my solution is to copy around an immutable Vec (???)
2. this is really slow for obvious reasons, how about we: pull in a whole new dependency ('imbl') that attempts to optimize for the general case using complex trees (???????????????)
You also mention:
> In some scenarios, where modifications occur way less often than clones, you can consider using Arc as explained in this video
I understand you're trying to be complete, but 'some scenarios' is doing a lot of work here. An Arc<[T]> approach is literally just the same as the naive approach but with extra atomic refcounts! Why mention it in this context?
You finally get around to mutating the vector + using it like a stack, but then comment:
> However, this approach requires more bookkeeping and somewhat more lifetime annotations, which can increase code complexity.
I have no idea why you mention 'code complexity' here (complexity introduced by rust and its lifetimes), but fail to mention how adding a dependency on 'imbl' is a negative.
> Two suggestions: it’s not immediately obvious whether subsequent benchmark result tables/rows show deltas from the original approach or from the preceding one (it’s the latter, which is more impressive). Maybe call that out the first couple of times?
Agree!
> Second, the “using the single Vec but mutating it” option would presumably benefit from a reserve() or with_capacity() call. Since in that approach you push to the vector in both erroring and non-erroring branches, it doesn’t have to be exact (though you could do a bfs search to find maximum depth, that doesn’t strike me as a great idea) and could be up to some constant value since a single block memory allocation is cheap in this context. (Additionally, the schema you are validating against defines a minimum depth whereas the default vec has a capacity of zero, so you’re guaranteed that it’s a bad choice unless you’re validating an empty, invalid object.)
Oh, this is a cool observation! Indeed it feels like `with_capacity` would help here
> But I agree with the sibling comment from @duped that actually parsing to JSON is the biggest bottleneck and simply parsing to the minimum requirements for validation would be far cheaper, although it depends on if you’ll be parsing immediately after in case it isn’t invalid (make the common case fast, assuming the common case here is absence of errors rather than presence of them) or if you really do just want to validate the schema (which isn’t that rare of a requirement, in and of itself).
My initial assumption was that usually the input is already parsed. E.g. validating incoming data inside an API endpoint which is then passed somewhere else in the same representation. But I think that is a fair use case too and I was actually thinking of implementing it at some point via a generic `Json` trait which does not imply certain representation.
> (Edit: I do wonder if you can still use serde and serde_json but use the deserialize module’s `Visitor` trait/impl to “deserialize” to an enum { Success, ValidationError(..) }` so you don’t have to write your own parser, get to use the already crazy-optimized serde code, and still avoid actually fully parsing the JSON in order to merely validate it.)
Now when I read the details, it feels like a really really cool idea!
> If this were in the real world, I would use a custom slab allocator, possibly from storage on the stack rather than the heap, to back the Vec (and go with the last design with no linked lists whatsoever). But a compromise would be to give something like the mimalloc crate a try!
Nice! In the original `jsonschema` implementation the `validate` function returns `Result<(), ErrorIter>` which makes it more complex to apply that approach, but I think it still should be possible.
Seems like the glaring exception to the rule!
Out of all the programmers in the world, what percentage of them do you think work in the kernel/driver/embedded spaces?
Second, linked lists are useful in a lot more places than that. Probably a better proxy would be low-level coders. You almost always want a linked list somewhere when you're dealing with memory addresses and pointers. Maybe not for the primary collections, but there are always secondary ones that need to maintain a collection with a different membership or ordering, and vectors of pointers don't have many clear advantages over intrusive linked lists for those secondary collections.
I did start to encounter some fresh grads with degrees that said "computer science" on them that couldn't answer some basic linked list questions. I was beginning to think it was a bad set of questions until I hit those kids. If you claim to know "computer science" and don't know what a linked list is, especially beyond some text books stuff, I'm probably not interested.
In embedded world, memory often needs to be exactly controlled, and allocation failures are fatal without a more complex MMU. In kernel world, I believe the main reason is that allocations can block.
In addition, a lot of data structures might be shared across multiple cores. Linked lists can be traversed and mutated concurrently (although with a bit of care).
I/e in a DMA-based ethernet driver, the ethernet MAC receives packets asynchronously from the processor, perhaps faster than the processor can ingest them. So the mac interrupts the processor to give it new packets, and the processor can't sit processing the packets in the interrupt context, so it needs to put them into some ordered list for processing later when it has downtime. In a true embedded system, the memory for this list is going to be fixed or statically allocated, but you still don't really want to have an array-style list with fixed indexing, as you'll have to manage what happens when the index wraps around back to 0 etc, so instead you just construct a linked list in that pre-allocated memory.
I wouldn't say linked lists aren't really used in high-level applications, as I said they're used all over the place whenever you have external asynchronous communication, it's just that modern high-level frameworks/libs totally abstract this away from most people writing high level code.
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.
Benchmarking is hard, and very often is done in ideal conditions, which never materialize in real use cases.
You can very much have a single vector owning the memory, and do all other ordering over auxiliary vectors of indices. Should be cheaper and faster than holding more linked lists.
If you want to remove elements, you can very much use tombstones to flag deleted elements and then clean up after some threshold.
Cheaper in space depends on the percentage of elements in the auxiliary list. An intrusive list has space for every element to be in the list, which is wasteful if few are. A vector that grows by doubling could waste nearly half of its elements. Indexes can often be smaller than pointers, though, which favors the vector approach.
Faster is debatable. Iterating the vector of indexes is quite fast, but indirecting into the data in a random order is still slow. An intrusive linked list doesn't need to do the former, only the latter. (Then again, it also bloats up the data slightly, which matters for small items since fewer fit in cache.)
The main reason why linked lists could still be at an advantage is if you don't want allocations in your auxiliary list manipulation path. Maybe you don't want the unpredictable timing, or maybe you can't handle failure.
I agree on tombstoning, but note that you're giving up some of the vector advantages by doing so. Your processing loop now has a much less predictable branch in it. (Though really, the vector probably still wins here, since the linked list is built out of data dependent accesses!)
Sometimes these auxiliary lists need to contain things that are no longer in the main list, too, as in the case of a free list. (And if you swap such things to the end, then you've just invalidated all of your indexes.) And non-intrusive linked lists can point to variable-size elements (though they lose most of the other benefits of an intrusive linked list.)
Anyway, it's the usual "use the right tool for the right job", I just claim that linked lists are sometimes the right tool.
(Random side note: I use "indexes" instead of "indices" these days, for a silly reason—"indices" is a fine word, I have no issue with it, but it seems to encourage some people to use the non-word "indice" which is an abomination.)
To me this is a self answering question.
The idea comes back to [0] which is similar to one of the steps in the article, and before adding `push` & `pop` I just cloned it to make things work. That's what Rust beginners do.
> This feels like you had a cool conclusion for your article, 'linked lists faster than vec', but you had to engineer the vec example to be worse. Maybe I'm being cynical.
Maybe from today's point in time, I'd think the same.
> It would be interesting to see the performance of a `Vec<&str>` where you reuse the vector, but also a `Vec<u8>` where you copy the path bytes directly into the vector and don't bother doing any pointer traversals. The example path sections are all very small - 'inner', 'another', 5 bytes, 7 bytes - less than the length of a pointer! storing a whole `&str` is 16 bytes per element and then you have to rebuild it again anyway in the invalid case.
Yeah, that makes sense to try!
> This whole article is kinda bad, it's titled 'blazingly fast linked lists' which gives it some authority but the approach is all wrong. Man, be responsible if you're choosing titles like this. Someone's going to read this and assume it's a reasonable approach, but the entire section with Vec is bonkers.
> Why are we designing 'blazingly fast' algorithms with rust primitives rather than thinking about where the data needs to go first? Why are we even considering vector clones or other crazy stuff? The thought process behind the naive approach and step 1 is insane to me:
> 1. i need to track some data that will grow and shrink like a stack, so my solution is to copy around an immutable Vec (???)
> 2. this is really slow for obvious reasons, how about we: pull in a whole new dependency ('imbl') that attempts to optimize for the general case using complex trees (???????????????)
That's clickbait-y, though none of the article's ideas aim to be a silver bullet. I mean, there are admittedly dumb ideas in the article, though I won't believe that somebody would come up with a reasonable solution without trying something stupid first. However, I might have used better wording to highlight that and mention that I've come up with some of these ideas when was working on `jsonschema` in the past.
> I understand you're trying to be complete, but 'some scenarios' is doing a lot of work here. An Arc<[T]> approach is literally just the same as the naive approach but with extra atomic refcounts! Why mention it in this context?
If you don't need to mutate the data and need to store it in some other struct, it might be useful, i.e. just to have cheap clones. But dang, that indeed is a whole different story.
> I have no idea why you mention 'code complexity' here (complexity introduced by rust and its lifetimes), but fail to mention how adding a dependency on 'imbl' is a negative.
Fair. Adding `imbl` wasn't a really good idea for this context at all.
Overall I think what you say is kind of fair, but I think that our perspectives on the goals of the article are quite different (which does not disregard the criticism).
Thank you for taking the time and answer!
- [0] - https://github.com/Stranger6667/jsonschema-rs/commit/1a1c6c3...
I'd be convinced once I see pure Rust kernels geared towards modern machines suddenly using linked lists everywhere. Otherwise I'm leaning towards it being a side-effect of the language choice and culture.
Also because I've seen the same kind of reasoning applied to compilers (e.g. "of course you need linked lists in compilers, they are extremely graph traversal heavy"). But one look at modern compilers implemented in Rust paint a very different picture, with index-based vectors, data-oriented design and flattened ASTs everywhere.
It can be solved (or worked around), but it's understandable that people don't _want_ to do that.
- My values represent runs of characters in the document.
- Inserts in the tree may split a run.
- Runs have a size - 0 if the run is marked as deleted or the number of characters otherwise. The size changes as we process edits
- Every inserted character has an ID. I need to be able to look up any run by its ID, and then edit it. (Including querying the run’s current position in the tree and editing the run’s size).
It’s an interesting data structure problem, and it took a few weeks to have a good solution (and a few weeks more later rewriting it in safe rust & improving performance in the process).
I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time!
SBCL:
* (defun hello-world () (write-string "hello world"))
HELLO-WORLD
* (disassemble #'hello-world)
; disassembly for HELLO-WORLD
; Size: 36 bytes. Origin: #x100311C85C ; HELLO-WORLD
; 5C: AA0A40F9 LDR R0, [THREAD, #16] ; binding-stack-pointer
; 60: 4A0B00F9 STR R0, [CFP, #16]
; 64: EAFDFF58 LDR R0, #x100311C820 ; "hello world"
; 68: 570080D2 MOVZ NARGS, #2
; 6C: 29EC80D2 MOVZ TMP, #1889
; 70: BE6B69F8 LDR LR, [NULL, TMP] ; WRITE-STRING
; 74: DE130091 ADD LR, LR, #4
; 78: C0031FD6 BR LR
; 7C: E00120D4 BRK #15 ; Invalid argument count trap
(write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.
Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers). Syntax isn't semantics.
The semantics is that a function write-string is called, with a string as its argument.
The second expression has linked list processing in its semantics because you stuck in a cdr, as well as a quote which makes a piece of the program available as run-time list datum. (This is semantics that could be easily optimized away in the executable form, but I would say that it has linked list processing in its abstract semantics.)
The % who have touched kernel bits, wrote a triangle engine scene renderer, wrote a compiler, touched server metal in production, have worked on ASICs, and can put together ML/AI building blocks shrinks way, way down to a handful of living humans.
This is about how many work in kernels/embedded systems/etc vs more common programming gigs. And that's less about how many are trained to do so, but rather how many are needed.
Absolutely! That is one of the places you want to use that style of programming. As the base classes and built in structs do not really cover it yet.
Also as a counterpoint sometimes the built in ones have some very interesting degenerate cases. I had one in an old library that basically doubled its memory footprint every time you exceeded its buffer. That was a point to change it to be a fixed allocation or something else. If i had no idea of the fundamentals I would have been totally in the weeds and no idea why it was doing it.
My experience in embedded, everything is hardcoded as a compile time constant, including fixed size arrays (or vectors of a fixed capacity)
A common way to implement these is to have an array of messages, sized for the worst case scenario and use this as the message pool.
You keep the unused messages in a single linked "free-list", and keep the used messages in a double linked queue or fifo structure.
That way you get O(1) allocation, de-allocation, enqueue and dequeue operations for your message queue.
Another example for this paradigm are job queues. You might have several actuators or sensors connected to a single interface and want to talk to them. The high level "business" logic enqueues such jobs and an interrupt driven logic works on these jobs in the background, aka interrupts.
And because you only move some pointers around for each of these operations it is perfectly fine to do so in interrupt handlers.
What you really want to avoid is to move kilobytes of data around. That quickly leads to missing other interrupts in time.
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...
We're looking at the same string and seeing different things. You're seeing `(write-string "hello world")` as a program, I'm seeing it as an expression.
It has linked list semantics, which you can preserve until runtime like this `'(write-string "hello world")`. Note that I didn't change the string, I changed its context. If the original were living in a string, and you called read on it, it would become a linked list. If you called eval on that list, it would become a function call. This is basic stuff which I'm well aware you know, so I'm not sure what all the quibbling is about.
You literally need a linked list to write a program in a language in which the code becomes linked lists. And you're going to have a bad time writing Lisp if you don't get the hang of cons cells, early and often.
Is "code is data" true, or false? You're trying to have it both ways here.
The "large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world" include approximately zero programmers who have wielded Lisp in anger, is my point. I thought that was pretty clear from context, but I guess not.
You're also likely provoking list manipulation by running C hello world. The C grammar has lists, like lists of parameter declarators in a function, or argument expressions in a function call.
By the time you've compiled your C program, you've likely "used", lists, trees and hash tables.
Classic line-numbered BASIC interpreters stored the lines as a linked list. For instance in
10 PRINT "Hello"
20 GOTO 10
So in addition to not being able to write C hello without linked lists, the same holds for BASIC.
The way you present your idea about Lisp is harmful because it is likely to be misinterpreted and become misinformation in the eyes of those who not so well informed.
The Lisp community still has to deal with nonsense like that the execution of Lisp programs is slow because linked lists are continuously being traversed, or that the only data structure is a list.
Think about how you might be playing into that. What do you think it looks like when you say that you can't write a hello world, without using linked lists.
Very good optimizing compilers existed before LLVM. Intel had one specifically for Itanium. It wasn't enough.
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
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
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)