3 ms·

> Most software doesn’t read random addresses. Is there any literature or studies to back this? I thought one of the downfalls of modern software is a ridicul

> Most software doesn’t read random addresses. Is there any literature or studies to back this? I thought one of the downfalls of modern software is a ridiculous number of tiny dynamic allocations, often deliberately randomized in space. Lots of pointer chasing and hard-to-predict access patterns. And some people work really hard to make their access patterns cache friendly, which is far from trivial and for most software, not a cost they can justify. Sometimes changing the access patterns means reorganizing all vital data structures and going SoA to AoS (or vice versa) and due to limited language support, that can mean sweeping changes across the entire code base. It doesn't help that as new features are added, requirements on these data structures and access patterns can change a lot.

Const-me 5y ago
> Lots of pointer chasing and hard-to-predict access patterns. They’re hard to predict individually, but statistically I think they’re rather predictable. Many programs indeed use tons of small allocations and chase quite a few of these pointers. Still, after the program runs for a while, the data is distributed appropriately across caches (e.g. my CPU has 32kb L1D, 512kb L2 and 32MB L3) and it sometimes becomes not terribly bad. > work really hard to make their access patterns cache friendly, which is far from trivial and for most software Depends on the goal. If the goal is approaching the numbers listed in CPU specs, FLOPS or RAM bandwidth, indeed, it can be prohibitively expensive to do. If the goal is more modest, to make software that’s reasonably fast, for many statically typed languages it’s not that bad. Prefer arrays/vector over the rest of the containers, prefer B+ trees over red-black ones, prefer value types over classes, reduce strings to integer IDs when possible, and it might be good enough without going full-HPC with these structs-of-arrays and the complexity overhead.

Const-me 5y ago

> Lots of pointer chasing and hard-to-predict access patterns. They’re hard to predict individually, but statistically I think they’re rather predictable. Many programs indeed use tons of small allocations and chase quite a few of these pointers. Still, after the program runs for a while, the data is distributed appropriately across caches (e.g. my CPU has 32kb L1D, 512kb L2 and 32MB L3) and it sometimes becomes not terribly bad. > work really hard to make their access patterns cache friendly, which is far from trivial and for most software Depends on the goal. If the goal is approaching the numbers listed in CPU specs, FLOPS or RAM bandwidth, indeed, it can be prohibitively expensive to do. If the goal is more modest, to make software that’s reasonably fast, for many statically typed languages it’s not that bad. Prefer arrays/vector over the rest of the containers, prefer B+ trees over red-black ones, prefer value types over classes, reduce strings to integer IDs when possible, and it might be good enough without going full-HPC with these structs-of-arrays and the complexity overhead.