I thought up a RAM that paired every data word, with an address word, pointing to its "next" word. ListRAM.
Reduces usable RAM in half, but speed is speed.
The idea being the RAM buses could be designed to provide fast pipelines of chained data to the cache, despite arbitrarily scattering in RAM.
There is no way this could compete with a single batch read of actually adjacent data. But it could speed up "Random" accessed data, which often is not - in fact - actually random from the program's or the data structure's point of view, just not adjacent.
And it would do one thing better: Reading a null terminated string wouldn't over read. The null next-address would stop every small string read from becoming a page read.
Even more flexible, send little read-chain algorithms to RAM. A little address math chaining and branching on in-RAM values, on little distributed address-math cores (RAM embedded APU cores!), could avoid a lot slow turnarounds.
These kinds of ideas seem even better to me now, by orders of magnitude, than they did originally. RAM really needs help.
If you don't need insert/remove in middle, only at the end, there are more optimal data structures for list like RAOTS[1].
Btrees are O(log n) random access, O(log n) cons and use O(log n) excess space.
Unrolled linked lists are still O(n) random access because we ignore the constant factor of block size. They also use O(n) excess space for pointers, but have O(1) cons.
RAOTS are O(1) random access, O(1) amortized cons [O(√n) worse case], and use O(√n) excess space.
RAOTS is basically a tree of depth 1. The root is an "index block" of pointers to data blocks which grow in size proportional to the square root of the data length (similar to Hashed Array Trees, but doesn't require restructuring on each power of 2). The index block has length ~√n.
The square root is an approximation - the structure grows in "superblocks" where each superblock has `~√n` blocks of size `~√n` The pattern is: [1x1, 1x2, 2x2, 2x4, 4x4, 4x8, 8x8, 8x16, 16x16, 16x32, ...] Even indexed superblocks double the data block size, odd indexed superblocks double the number of blocks per superblock. It doesn't use an actual `sqrt()` call uses but some bit tricks via `clz`.
A simpler trick, which has no single name but have been known as "segmented lists", is where the index block points to blocks increasing in size geometrically essentially like a dynamic array but where we don't need to `realloc`. The index block is length 1+log₂n and each index i points to a block of length 2⁽ⁱ⁻¹⁾. These have O(1) random access, O(1) amortized cons [O(n) worst case] and waste O(n) space [with constant factor of 1/2]. The random access is very efficient as it's only two dereferences and a few bit tricks:
index_block[bit_width(idx)][idx - bit_floor(idx)]
This is more cache friendly than the other approaches.
There's also Bagwell's VList[2] which is like a mashup of the "segmented list" and an unrolled list - the blocks grow geometrically in size, but still contain the pointer the the next block rather than them being in a separate index block.
I thought up a RAM that paired every data word, with an address word, pointing to its "next" word. ListRAM.
Reduces usable RAM in half, but speed is speed.
The idea being the RAM buses could be designed to provide fast pipelines of chained data to the cache, despite arbitrarily scattering in RAM.
There is no way this could compete with a single batch read of actually adjacent data. But it could speed up "Random" accessed data, which often is not - in fact - actually random from the program's or the data structure's point of view, just not adjacent.
And it would do one thing better: Reading a null terminated string wouldn't over read. The null next-address would stop every small string read from becoming a page read.
Even more flexible, send little read-chain algorithms to RAM. A little address math chaining and branching on in-RAM values, on little distributed address-math cores (RAM embedded APU cores!), could avoid a lot slow turnarounds.
These kinds of ideas seem even better to me now, by orders of magnitude, than they did originally. RAM really needs help.
https://en.wikipedia.org/wiki/Unrolled_linked_list
Similarly, if you squint at B-trees, they are just unrolled linked lists with "skipping".
If you don't need insert/remove in middle, only at the end, there are more optimal data structures for list like RAOTS[1].
Btrees are O(log n) random access, O(log n) cons and use O(log n) excess space.
Unrolled linked lists are still O(n) random access because we ignore the constant factor of block size. They also use O(n) excess space for pointers, but have O(1) cons.
RAOTS are O(1) random access, O(1) amortized cons [O(√n) worse case], and use O(√n) excess space.
RAOTS is basically a tree of depth 1. The root is an "index block" of pointers to data blocks which grow in size proportional to the square root of the data length (similar to Hashed Array Trees, but doesn't require restructuring on each power of 2). The index block has length ~√n.
The square root is an approximation - the structure grows in "superblocks" where each superblock has `~√n` blocks of size `~√n` The pattern is: [1x1, 1x2, 2x2, 2x4, 4x4, 4x8, 8x8, 8x16, 16x16, 16x32, ...] Even indexed superblocks double the data block size, odd indexed superblocks double the number of blocks per superblock. It doesn't use an actual `sqrt()` call uses but some bit tricks via `clz`.
A simpler trick, which has no single name but have been known as "segmented lists", is where the index block points to blocks increasing in size geometrically essentially like a dynamic array but where we don't need to `realloc`. The index block is length 1+log₂n and each index i points to a block of length 2⁽ⁱ⁻¹⁾. These have O(1) random access, O(1) amortized cons [O(n) worst case] and waste O(n) space [with constant factor of 1/2]. The random access is very efficient as it's only two dereferences and a few bit tricks:
This is more cache friendly than the other approaches.
There's also Bagwell's VList[2] which is like a mashup of the "segmented list" and an unrolled list - the blocks grow geometrically in size, but still contain the pointer the the next block rather than them being in a separate index block.
[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
[2]:https://dl.acm.org/doi/10.5555/1756972.1756975
B+ tree if you want unrolling, B-tree if you just want the faster random access.
Cdr-coding?