upvote
Looking at the specs: 32 KiB of L1, 256 KiB of L2, in-order and partial dual-issue.

That's the least forgiving kind of chip when it comes to performance: fast enough to outpace main memory by two orders of magnitude, yet the slightest speed bump (branch misprediction, cache miss) stalls it without any ability to reorder around it.

reply
What is a cache friendly version of linked lists?
reply
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.

reply
reply
Similarly, if you squint at B-trees, they are just unrolled linked lists with "skipping".
reply
B+ tree if you want unrolling, B-tree if you just want the faster random access.
reply
deleted
reply
Cdr-coding?
reply