tail sharing makes a good candidate for locality of reference/caching
I'd love to hear about how that is implemented contemporarily, I'd really appreciate if you gave me a poke if you find/write a nice article about that.
AFAIK: In statically typed languages where the linked list is part of core/stdlib,
(as opposed to some kind of JS where you implement it as nested length-2 arrays ([4,[3,[2,[1]]]]))
they are actually stored as arrays of significant size with pointer to next slice.
(And previous, as since the data structure is already quite large, they are often a doubly-linked list. What's another pointer?)
This makes them still more expensive to index into than a contiguous/dense array but makes both indexing AND iteration several orders of magnitude faster.
Pretty much the same thing that turned binary trees into massively wide trees used today.
There's more complexity, especially since this cancels some size optimizations of structural sharing, but that's what the compiler is for.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
I'd love to hear about how that is implemented contemporarily, I'd really appreciate if you gave me a poke if you find/write a nice article about that.
AFAIK: In statically typed languages where the linked list is part of core/stdlib,
(as opposed to some kind of JS where you implement it as nested length-2 arrays (
[4,[3,[2,[1]]]]))they are actually stored as arrays of significant size with pointer to next slice.
(And previous, as since the data structure is already quite large, they are often a doubly-linked list. What's another pointer?)
This makes them still more expensive to index into than a contiguous/dense array but makes both indexing AND iteration several orders of magnitude faster.
Pretty much the same thing that turned binary trees into massively wide trees used today.
There's more complexity, especially since this cancels some size optimizations of structural sharing, but that's what the compiler is for.