If it has a pittance of cache, then mechanical sympathy might not mean cache-friendliness. Linked lists were mechanically sympathetic on uncached systems - it cost the same to access any byte of memory, so you might as well go directly to the one you wanted.

▲

boricj 26 minutes ago | parent | next [-]

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.

▲

brcmthrowaway an hour ago | parent | prev [-]

What is a cache friendly version of linked lists?

	▲	Nevermark 41 minutes ago \| parent [-]
		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.