Rendered at 10:47:11 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
boricj 2 days ago [-]
I work with another team at work that uses lots of message passing, C++ virtual methods in deeply nested class hierarchies, large DOMs and off-the-shelf C++ STL containers... on a STM32MP1, which has an in-order Cortex-A7 and a pittance of cache.
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.
bunderbunder 2 days ago [-]
I’ve had code review pushback against reorganizing data structures to be more cache-friendly on the grounds that it was “premature optimization” even though I pre-emotively justified the decision with benchmark results indicating that the performance difference was large and business relevant, and addressed a real performance bottleneck that I observed during testing.
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.
hinkley 2 days ago [-]
A lot of my poor opinion on developer opinions dates back to a couple projects where Product and Marketing were begging us for substantial performance improvements and the teams pushed back saying this was as fast as you could expect. I got 2x in the first six months on both projects, and delivered 25% per quarter on one for almost 2 years (that maths to around 8x) before I started to scrape the bottom of my barrel.
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.
nomel 1 days ago [-]
My general rule of thumb is that if you see you can 2x it easily, you can actually get somewhere around 10x with effort, since the presence of that easy 2x means nobody really spent any time on performance.
vrighter 1 days ago [-]
i got over 800 this way. O(n^2) everywhere and n+1 queries
jonathanlydall 1 days ago [-]
This sounds like being completely performance oblivious, like an extreme opposite of premature optimisation.
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).
hinkley 14 hours ago [-]
"Premature optimization" became a battle cry of the Don't Make Me Think crowd.
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.
vrighter 1 days ago [-]
a hashset was used... then ".Where(x=>x == key).Count() == 0"
hinkley 15 hours ago [-]
Long long ago I filed a bug against TogetherJ, where I determined empirically that they had a bug with monorepo/separate compilation units that resulted in n^5 time complexity for loading multiple project files at once. For the last data point I started loading it at 5pm one day and then it finished at 11 am the following morning. They gave us a workaround that got it down to around 20 minutes, the patch made it a little bit better than that but that was still a long time.
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.
andyferris 24 hours ago [-]
It can go to extremes. Like 100x by going from a dynamic to static language then 100x more adjusting the data structures/algorithm…
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).
hyperman1 20 hours ago [-]
I've known about a student, long ago in the '90s, who got to speed up a batch codebase in some bigcorp, as a summer job. The original did basically everything wrong, up to bubblesort. So student diligently cleaned up the mess and got a speedup from multiple hours to a few minutes.
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.
kevsamuel 18 hours ago [-]
To be fair, I would have assumed that too. Occam's razor: in a sea of lying candidates, the next one is probably lying too.
rowanG077 1 days ago [-]
Nitpick but 25% improvement over 8 quarters is 1.25^8, almost a runtime in 1/6th of the time.
hinkley 1 days ago [-]
25% faster is 1.33x work done in the same time. What you want is 0.75^7 (almost 2 years) gives you 13.3% of the original time, which is 1/7.5. Only it was more like 25-30% so I rounded up.
kaashif 1 days ago [-]
Interesting how people interpret the word faster differently.
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.
hinkley 15 hours ago [-]
Performance is for the user. If the user has told you that we have an SLA that requires this operation to complete in 10s, but it currently runs in 30 seconds, and your first set of changes gets it to 15s, what improvement are you going to report to the user?
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.
kaashif 43 minutes ago [-]
My only conclusion from this is that "faster" will be interpreted in different ways by different people. This is actually just a fact and can't be disputed, the evidence is too strong.
It would be even better, in your example, to report "4x ops/sec" or "0.9x ops/sec" rather than faster or slower.
smolder 23 hours ago [-]
50 percent faster is 2/3 time, but yes, prominent people have made this error and even doubled down on it publicly.
hinkley 15 hours ago [-]
When you're asked to meet a time limit, that's time domain, not rate, and so improvements will be reported in the time domain.
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%.
3 hours ago [-]
smolder 3 hours ago [-]
If an object moves across a space 50% faster, it finishes in 2/3 of the time. It's not up for debate, it's not ambiguous. To say anything else is wrong.
> Which isn't 200%, it's 50%.
Okay.
15 hours ago [-]
plasticchris 2 days ago [-]
That’s just pattern matching. Most people don’t do this level of prep so they assume you didn’t either. There’s usually no ill intent, and people are maybe a little embarrassed when you point it out, but if you are tactful it’s fine.
1 days ago [-]
smolder 23 hours ago [-]
Something like this happened to me on a very high budget java project. I said I didn't want to make high memory pressure code that performed badly, and the senior guy said the optimization was premature. It didn't matter in the end because they didn't adopt our solution. (They stuck with mainframes, and I don't blame them.)
dnautics 1 days ago [-]
> objectively
I see what you did there
tomjen3 1 days ago [-]
All types of architecture have advantages and disadvantages. Clean code might not be very cache-friendly, but it does a pretty good job of making sure you don't have to hunt in too many places to update things and It also makes it pretty simple to split things up so that you can write unit test for most everything.
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.
boricj 1 days ago [-]
"Clean" code for modelling links between objects would be to store pointers within them. But that means dangling pointers when deleting objects, so you need to either update manually everywhere (easy to forget somewhere) or use shared/weak pointers (extra bookkeeping and allocations).
"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.
Gibbon1 2 days ago [-]
Processors I mostly write firmware for have little cache at all.
I think cache friendly code also tends to be reason about friendly and debugger friendly. None of that is remotely premature optimization.
dataflow 2 days ago [-]
> I think cache friendly code also tends to be reason about friendly and debugger friendly.
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.
bunderbunder 1 days ago [-]
I usually start with simpler things like paying attention to locality of reference and adjusting data so that it takes up less space in memory.
jacquesm 1 days ago [-]
Even CPUs like the ARM cores have caches, usually 16K, occasionally 32K, and even larger L2 caches (512K).
imtringued 21 hours ago [-]
Well, MCUs tend to have a buffer for execute in place from flash, but often they just have SRAM as main memory which can be accessed with a fixed latency and there is not much point in having a cache.
sick_of_slop 2 days ago [-]
Before AI, nobody has been responsible for more psychic damage against software developers than Bob Martin.
teddyh 1 days ago [-]
From what I understand, it is mostly the very rigid and prescriptive attitude which the average reader gets from his book, which, if you listen to him talk, was not his intent. He even published a new 2025 edition of “Clean Code” to try and fix this, by making the text less self-assured. So while he may or may not be responsible, he did not intend it.
okeuro49 1 days ago [-]
I liked the book, so did my colleagues, and we even had a meetup to discuss the book on how to improve the legacy codebase we had inherited.
maccard 21 hours ago [-]
The exact same can be about agile, and all the arguments against that are the same.
teddyh 18 hours ago [-]
The same applies there, except he hasn’t made a second book.
gjvc 1 days ago [-]
think you mean "psychological damage". Can you give some examples of what you mean?
zbentley 1 days ago [-]
I’m not who you were replying to, but there was a thread here a couple of years ago in which many people chimed in with examples. I added my two cents here, but the whole discussion is much more worth reading than my gripes: https://news.ycombinator.com/item?id=43166836
bigstrat2003 1 days ago [-]
Psychic is a damage type in D&D (and probably other RPGs too), so that is most likely a reference.
gjvc 1 days ago [-]
[flagged]
gjvc 1 days ago [-]
[flagged]
AnimalMuppet 1 days ago [-]
"Can you give examples?" was perfectly reasonable. "Are you high?" is not.
Calling everyone who downvotes you "incels" is very much against site rules. You've certainly been here long enough to know that. Knock it off.
gjvc 6 hours ago [-]
incels on the rise
gjvc 6 hours ago [-]
incels on the rise. also fuck off with your white-knighting, cunt.
AlexeyBelov 36 seconds ago [-]
I see only one incel in this thread. Normal people don't talk to others like that.
gjvc 1 days ago [-]
[flagged]
cffan2 22 hours ago [-]
Absolute nonsense, people claiming that on here are usually hiding their deep political biases and as liberal lefties dont like it when someone in their space calls a spade a spade, especially someone with a lot more reach and respect. Slightly different playbook than calling everything you disagree with racist. Yawn spells are spent. This is how they attack Bob now because they realize being a leftie is ridiculous and this “im a centralist” crap carries no weight, so they hide that and try to attack him on his contributions to software engineering.
sick_of_slop 15 hours ago [-]
[dead]
clivedup 2 days ago [-]
There's not enough context for me (or other commenters) to really evaluate this, but every change has risk, and some projects aren't in a position to be accepting that risk.
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.
1 days ago [-]
jordand 2 days ago [-]
I work in the games industry with exceptionally skilled system programmers that can do that too. They're getting on in age, and there's fewer programmers in the younger generations that are interested in any of it. Technology is sadly increasingly homogenising around Unreal Engine 5
MisterTea 2 days ago [-]
> Technology is sadly increasingly homogenising around Unreal Engine 5
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.
mananaysiempre 22 hours ago [-]
A popular refrain in gaming circles when Oblivion Remastered released was “it’s awesome if you have the hardware, but it’s Unreal so of course it runs like shit”. So it’s far from obvious that customer sentiment agrees with you. Having seen what Decima can do, I don’t think I agree that Unreal is the pinnacle of game tech either.
Jtarii 2 days ago [-]
If everyone stops writing game engines then who is going to program unreal engine/unity/godot?
bunderbunder 2 days ago [-]
I’ll admit I lost the plot a long time ago, but there’s a part of me that wonders if the main purpose behind the game engine and graphics card treadmill is to line the pockets of people who sell games engines and graphics cards. My subjective sense of the connection between technology and enjoyment as a player started to degrade about a decade back.
Jtarii 2 days ago [-]
I think it was just studios competing with each other in the 2010s to see who could make the biggest most ambitious game worlds. Leading to ballooning dev costs and then a feedback loop of higher production costs leading to safer design decisions.
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.
bunderbunder 1 days ago [-]
It’s especially the “cinematic” bit that got me. It’s technically impressive, but isn’t as visually interesting as what lower budget games have been doing with less polygons and more inspiration.
unrented7977 2 days ago [-]
[dead]
alpaca128 2 days ago [-]
I'd it's more a convenient outcome of maximizing profits than premeditated. Not optimizing is cheaper for studios while Nvidia doesn't mind extra popularity for their DLSS feature.
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.
ses1984 1 days ago [-]
What about hardware that could run crysis3 wouldn’t suffice for web browsing?
lelanthran 1 days ago [-]
Well, it ran on my 9600GT, which I used in a desktop from 2016 and recently used that desktop with 16GB RAM for the last few weeks.
I was unable to see any site that used webgl, which is almost all games site and many charting and graphing apps.
immibis2 2 days ago [-]
The people working for Unreal/Unity/Godot. Nobody writes search engines any more - except for Google et al. Nobody writes advertising systems - except for all the advertising businesses.
fasterik 2 days ago [-]
Games are a bit different in that the game engine is a core part of the product. There aren't many projects with $100M budgets building directly on top of a search engine. A lot of small and medium sized companies will use off the shelf game engines, but you'll never see Rockstar switching over to Unity/Unreal.
Jtarii 1 days ago [-]
Okay, but google search has only gotten worse for decades.
So your argument is that game engines will just decay.
Emjayen 1 days ago [-]
Not unique to gamedev; during the boom at the turn of the millennium the bar to entry to programming was dropped on the floor to fill demand.
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.
nxobject 1 days ago [-]
Around the time Mantle/Vulkan-type APIs entered the scene, I ended up hearing a lot of "yes, these APIs much more complicated to use, but fewer people need to touch D3D/your graphics API anymore with these freely available engines." Was my impression correct?
fwlr 1 days ago [-]
Someone asked me why Zig programmers seem to genuinely enjoy passing the allocator around as an argument. I didn’t have a good answer at the time, but I think I do now, thanks to your comment - feeling the “weight” of allocations is an example of mechanical sympathy, and having to pass around and use an allocator explicitly makes your code-effort more closely resemble the chip-effort it is asking for.
kibwen 1 days ago [-]
Heap allocations aren't really the culprit of the waste that the root comment is talking about. Indirection in general is, and passing around an allocator doesn't guard you against that. Virtual dispatch occurs even for objects on the stack.
fwlr 1 days ago [-]
Yes, I was suggesting allocation as another example of the same principle.
jacquesm 1 days ago [-]
I recently spent three weeks paring down a piece of software until it could run entirely in the L1 cache of the processor it was running on. The performance was - to put it mildly - impressive. And this was 1970's technology running on a modern CPU. This stuff can do miracles if you use it right.
immibis2 2 days ago [-]
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 2 days ago [-]
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 2 days ago [-]
What is a cache friendly version of linked lists?
Nevermark 2 days ago [-]
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.
Similarly, if you squint at B-trees, they are just unrolled linked lists with "skipping".
sparkie 22 hours ago [-]
If you don't need insert/remove in middle, only at the end, there are more optimal data structures for Lists 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.
cos...everyone seems still 'unreal busy'...or mentioning doom (3) ^^
swiftcoder 1 days ago [-]
I remember have a very long argument with a team I worked on, who were mostly convinced our service couldn't handle requests any faster because the CPUs were already at 100%. In the end we tripled the requests-per-second by cleaning up the service's memory access patterns...
bunderbunder 23 hours ago [-]
This is the kind of thing that needs a “things every programmer should know about…” blog post.
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.
squirrellous 9 hours ago [-]
Similarly, someone told me the memory consumption of a certain data structure couldn't be smaller because it had to store the full day's history of a thing rather than the snapshot state. We reduced it by about 30% in the end just by optimizing memory layouts and removing redundant data.
bugake 1 days ago [-]
Modern CPUs have hundreds of megabytes of cache. That's more than the entire hard disk space required by Windows in the 1990s.
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.
bitwize 1 days ago [-]
Software has gotten vastly more complex over the intervening decades, and unfortunately it has historically been beyond human capacity and/or institutional time/money availability to keep everything running super efficiently.
The good news is that with LLMs, we can make software efficient again, much more cheaply!
bunderbunder 23 hours ago [-]
I go to Hacker News to hear people say that LLMs will automagically make software clean and efficient again.
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.
alpaca128 12 hours ago [-]
In the end LLMs were also trained on all the incorrect and suboptimal solutions and examples.
aravpanwar 19 hours ago [-]
LLMs helping with efficiency comes long after AGI.
bitwize 14 hours ago [-]
Dude, LLMs are finding algorithmic efficiency solutions where humans have long assumed there were none. We're inside the singularity now.
bunderbunder 13 hours ago [-]
I’ve been studying and working in AI for almost 3 decades now, and made at least an amateur’s study of the field’s 70-ish year history. Much has changed, including the word we use for this concept, but one immutable constant is that we have always been teetering on the brink of the singularity.
Now isn’t even the first time people got so excited about an automatic proof finder that they declared that it’s already here.
bitwize 8 hours ago [-]
Strangely enough, one of the shortest math papers ever published is another computer disproof of a long-standing conjecture, by Lander and Parkin (1966):
"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."
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.
solyin 13 hours ago [-]
Which definition of singularity are you using? I'm still doing my own laundry and taking out the trash, though I could hire a human to do that job if I had the money for it.
wolvesechoes 3 hours ago [-]
Complexity has nothing to do with memory access patterns.
ozgrakkurt 14 hours ago [-]
This blog post and some other pages in the website are really great. Just useful information without padding, even when writing about the product.
inoknowtoask 18 hours ago [-]
Hi, i just have 2 questions. Are your machines priorizing Space over Processing ? In terms to save a few bytes, cos "Rendering" (for example) is done by the clients machine as an example? Or have i missunderstood something? I am asking, cos the first answer in the posting seem to miss: "commenting the code good enough than anyone may 'understood, what heck this typed line may be for...'" just asking...thanks
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).
bugake 7 hours ago [-]
Today, it exists PIM "processing in memory" RAM modules, but they are Xeon and Linux-only. Still kind of a niche product.
tsoukase 12 hours ago [-]
Clean code is beautiful, like a convenient lie enjoys us. Cache aware code is ugly, like a truth that hurts. Morality suggests to be honest from the beginning, there is no prematurity in aiming for cache locality.
drivebyhooting 2 days ago [-]
I feel like the solution presented is just a clustered hashmap or “locality sensitive” if you’d like it.
Still not orders of magnitude better.
quotemstr 1 days ago [-]
Uh, isn't this just radix-partitioned aggregation? Hierarchical (fixed two level) aggregation is old. What's novel here?
Microcosm of Pivot itself I guess. I just don't get why this project exists when DuckDB and Clickhouse both exist.
fluffyllemon 1 days ago [-]
From the article: "To do this, we'll use a method called radix partitioning."
I don't think they were claiming it was novel. Seemed just like an article explaining a performance optimization
northes 1 days ago [-]
I didn't get the sense that this was the end-all, just a relatively simple way to show how much impact cache-friendly data structures can have for somewhat little effort over the naive solution and give readers a sense for how to think through the problem.
zittturkkpon 1 days ago [-]
[flagged]
1 days ago [-]
happyPersonR 1 days ago [-]
Shout out to the author, it seems coherent.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Calling everyone who downvotes you "incels" is very much against site rules. You've certainly been here long enough to know that. Knock it off.
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 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.
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.
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:
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
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 :)