It's the memory latency, stupid
pivotlake.io
pivotlake.io
On the other hand, in my team I wrote my custom C++ STL containers that allocate inline, SAX-style processing libraries and an object pool with links that use index+generations like 2000s video games... on a STM32H5 with less than a megabyte of RAM.
Mechanical sympathy feels like a lost art to people I demonstrate it to... and I had to demonstrate to the first team with benchmark numbers that I would not be the bottleneck between us by orders of magnitudes.
I kinda get the commodification of games engines and Unreal. I am sure a lot of us saw the gaming revolution unfold, watching gaming companies one-up each other in graphics and interactivity. But once you get to the point of UE5, Unity, or Godot there is little need or value to make a game engine from scratch anymore.
Don't get me wrong, if you want to write an engine, go for it. But if you just want to make a game then an existing engine is good enough.
There was also a heavy emphasis on games being "cinematic" which necessitates photorealistic rendering.
AAA games have been pretty artless for a while now baring a couple exceptions.
Crysis 3 is over a decade old, still looks great and ran on hardware that wouldn't suffice for web browsing today. I haven't seen anything in games since then that justified a significant increase in system requirements.
I was unable to see any site that used webgl, which is almost all games site and many charting and graphing apps.
So your argument is that game engines will just decay.
The vast majority of programmers today don't even understand the basics of how-computer-work - not just microarchitecural considerations but even how to interface with the kernel efficiently / understand the performance considerations of their target platform.
Ask your average programmer how to say, simply perform I/O efficiently as possible on NT given some workload characteristics. One needs to first understand this before they can begin making concessions in favour of other demands (abstraction, flexibility, ect) and very few programmers can even get beyond the starting line.
This was on a team and at a time where Clean Code was very popular. I somewhat wonder if the problem is that, in the 2010s, many people became convinced that certain aesthetic standards were both objectively, provably correct, and more important than anything else.
A "real performance bottleneck that I observed during testing" is a little bit unclear whether it occurred outside of test conditions, or whether speeding up that particular bit improves anything anyone cares about.
I think cache friendly code also tends to be reason about friendly and debugger friendly. None of that is remotely premature optimization.
Not sure what examples you have in mind, but the very first things I think of when I hear cache friendly code are cache-blocking and cache-oblivious algorithms, which are quite the opposite of that. See also B-trees vs. binary search trees, etc.
It’s predominantly a way to shut down thinking, which is why it’s so often misquoted. Knuth’s version is more nuanced. Theirs is not at all.
As a compromise I got really good at doing optimizations that also improved readability. Things like hoisting and better variable naming combined together can be mistaken for just code cleanup.
I also discovered that keyhole optimizations are more palatable. Which is to say, move the slow bit yo a separate function with a single responsibility. Then do the optimization in a separate commit. Then the other devs don’t have to look at your changes and if they turn out to have a bug, we can always revert the change later. They almost never do, but having the option seems to grease the wheels.
To you, 2x faster means 2x the work done in the same time, but 25% faster means 1.33x the work done in the same time.
I see this a lot - in software people interpret 50% faster as a 50% reduction in time taken.
If a car is 50% faster, I hope people would universally interpret that as e.g. 20 to 30 mph. But if I asked people how long would a 1 hour journey take if it were 50% faster, I bet a lot would say 30 mins, because it kind of seems like that's what I mean.
Time domain also works for Little's Law, which is the more prevalent measure these days anyway. If you double the throughput of a server you can halve the cluster size and retain the same level of service. Which isn't 200%, it's 50%.
> Which isn't 200%, it's 50%.
Okay.
You're going to report in the time domain. In which case 1/2 off the time is 50%.
One of the benchmarking tools I used to use reported 50k ops/sec -> 200k ops/sec as 75% faster. Which definitely IS wrong but I know how he got there. You see you don't count operations per second, you run the loop ?? thousand times and see how many milliseconds it takes. Then you convert that to ops/sec. If you compare before and after while still in the time domain, that's 75%. But if you report throughput right next to a ratio in the time domain you're gonna have a bad time.
When that tool stopped being maintained, the person who replaced it wisely switched to reporting in multipliers. 4x faster is hard to misinterpret. Though "1.1x slower" is still open to misinterpretation.
It would be even better, in your example, to report "4x ops/sec" or "0.9x ops/sec" rather than faster or slower.
My rule of thumb is that as long as it doesn’t really complicate or convolute the code, write with performance in mind.
My expertise is in C# and sometimes this is as simple as using a hash set or dictionary instead of a plain list.
Other times it’s having a decent understanding of how EF (an ORM) actually works (the static typing benefits of them in C# makes ORMs very valuable when used appropriately) and the cost of round trips to any network host (including a DB).
As I think back to the people who fought me, the same group didn't like when you refactored code either because now they didn't have the code memorized. But I've found in the intervening years that making code discoverable is much more useful than trying to keep it static because coworkers are always going to need to change shit anyway to implement new features even if that feature is neither Correctness nor Performance. What you don't want is for people to hide logic from you. So if you move logic to a function call, that's fine, because it's still in the same neighborhood. But if you hoist it all the way up into a much earlier part of the call tree, you need to announce that in meetings and maybe in the documentation so people know what's what.
Once I got very confused when exactly this kind of 10k x speed up I demonstrated for a problem introduced to me as a business bottleneck then got ignored (I wasn’t on this team, though, but it’s still hard to understand the mentality and incentives there).
Then he could not get an interview anywhere. After some backchannel communication it turned out he had to remove that experience from his CV, as all employers assumed he was just lying.
I'm sure I've found factorial complexity code, at least in the design phase, but that's the worst one I've encountered in the wild.
I see what you did there
This is not the right choice for everything, just as using Python is not the right choice for everything. The question to ask is: what are we trying to do in the first place? Then take it from there.
You did that by making sure the speed-up was business relevant. I'm mostly putting this out to force people to think about whether that also applies to their specific thing.
"Unclean" code for this is putting objects in a table, giving objects a generation (that increments whenever you create/delete one) and storing pairs of (index, generation) numbers everywhere you need a link. Link is live only if the generations matches and since only odd generations are live objects, default construction means no link. Lifted straight from 2000s video game tricks and with modern C++ it's basically all encapsulated away.
I've made that refactoring in a codebase, not because of speed but because of maintenance and memory fragmentation concerns. Sometimes, the clean solution really isn't the right one and it's really sad that compsci only ever teaches classical data structures, like we're still coding in the 1970s on computers with no caches that don't suffer from pointer chasing.
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.
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)]
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
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.
Programs should express the solution, not the problem.
cos...everyone seems still 'unreal busy'...or mentioning doom (3) ^^
I would estimate that a single digit percentage of my colleagues are aware that, according to `top`, sitting around picking at your fingernails while you wait on the memory controller to run across town and back counts as working your ass off.
You could install an entire Windows system, emulated in cache of a modern CPU, including the hard disk, and modern computers are still slow, partly because the CPU does nothing while waiting for RAM to fetch data, and partly because decades of people prioritizing abstractions over efficient coding have made software totally inefficient.
The good news is that with LLMs, we can make software efficient again, much more cheaply!
Then I go back to Cursor’s agent chat window and spend another day endlessly struggling to keep LLMs from inserting needless complexity and N+1 queries into the code at a faster rate than mere humans could ever hope to achieve.
Now isn’t even the first time people got so excited about an automatic proof finder that they declared that it’s already here.
"A direct search on the CDC 6600 yielded 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵ as the smallest instance in which four fifth powers sum to a fifth power. This is a counterexample to a conjecture by Euler that at least n nth powers are required to sum to an nth power, n > 2."
https://projecteuclid.org/journals/bulletin-of-the-american-...
So yeah, computers have been slaughtering math tentpoles since forever ago, but I don't think I've seen so many big ones taken down so quickly. Although if Euler had been alive when the 1966 paper was published, he might've crashed out the way Terence Tao is doing now.
Has anyone rewritten this for 2026?
The problem is that it's basically a book and deep-dive. You don't get much out of it by skimming. I doubt that CPU architectures have changed enough to matter. I admit I'm not up-to-date, but CPUs are not the web ecosystem. What has changed is that nobody has the attention span to read something like this any more.
And the title was wrong when it came out - not every programmer needs to know those details. Many programmers work on some CRUD app with frontend and REST API and should learn about CREATE INDEX or start to measure performance in the first place. And some performance work has moved to GPUs instead of CPUs (not always for a good reason IMO).
Still not orders of magnitude better.
Microcosm of Pivot itself I guess. I just don't get why this project exists when DuckDB and Clickhouse both exist.
I don't think they were claiming it was novel. Seemed just like an article explaining a performance optimization
I like flamegraphs
I know folks use perf to help generate them
But in the future, now that Llm is here, get and agent to check assembly, PMUs and also see what you’re doing in assembly.
My 2c and happy coding to everyone :)