From the article: Lookup tables are always faster than calculation - is that true? I'd think that while in the distant past maybe today due to memory being much slower than CPU the picture is different nowadays. If you're calculating a very expensive function over a small domain so the lookup fits in L1 Cache then I can see it would be faster, but you can do a lot of calculating in the time needed for a single main memory access.
3. https://www.intel.com/content/www/us/en/developer/articles/t... - shows you whether the above is matching the reality (besides the CPU alone, more often than not your bottleneck is actually memory accesses; at least on the first access which wasn’t triggered by a hardware prefetcher or a hint to it. On Linux it would be staring at “perf top” results.
So, the answer is as is very often - “it depends”.
...and we always circle back to "premature optimization is the root of all evil", since processors are a wee bit more intelligent with our instructions than we thought. :)
Not that intelligent. If you have two loads and one store per cycle, then that’s it. (Recall that we have SSDs with 14 GB/s sequential reads now, yet CPU clocks are below 6 GHz.) Most of the computational power of a high-performance CPU is in the vector part; still the CPU won’t try to exploit it if you don’t, and the compiler will try but outside of the simplest cases won’t succeed. (Most of the computational power of a high-performance computer is in the GPU, but I haven’t gotten that deep yet.)
I don’t mean to say that inefficient solutions are unacceptable; they have their place. I do mean to say that, for example, for software running on end-users’ computers (including phones), the programmer is hardly entitled to judge the efficiency on the scale of the entire machine—the entire machine does not belong to them.
> We should forget about small inefficiences, say 97% of the time; premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.
D. E. Knuth (1974), “Structured Programming with go to Statements”, ACM Comput. Surv. 6(4).
> Lookup tables are always faster than calculation - is that true?
Maybe on the Z80. Contemporary RAM was quite fast compared to it, by our sad standards.
A table lookup per byte will see you hit a pretty hard limit of about 1 cycle per byte on all x86 CPUs of the last decade. If you’re doing a state machine or a multistage table[1] where the next table index depends on both the next byte and the previous table value, you’ll be lucky to see half that. Outracing your SSD[2] you’re not, with this approach.
If instead you can load a 64-bit chunk (or several!) at a time, you’ll have quite a bit of leeway to do some computation to it before you’re losing to the lookup table, especially considering you’ve got fast shifts and even multiplies (another difference from the Z80). And if you’re doing 128- or 256-bit vectors, you’ve got even more compute budget—but you’re also going to spend a good portion of it just shuffling the right bytes into the right positions. Ultimately, though, one of your best tools there is going to be ... an instruction that does 16 resp. 32 lookups in a 16-entry table at a time[3].
So no, if you want to be fast on longer pieces of data, in-memory tables are not your friend. On smaller data, with just a couple of lookups, they could be[4]. In any case, you need to be thinking about your code’s performance in detail for these things to matter—I can’t think of a situation where “prefer a lookup table” is a useful heuristic. “Consider a lookup table” (then measure), maybe.
Depends on the hardware and what you are making with that hardware. Some processors can do complicated things stupidly fast (e.g. when SIMD done right), and for some hardware platforms, a mundane operation can be very costly since they are designed for other things primarily.
My favorite story is an embedded processor which I forgot its ISA. The gist was, there was a time budget, and doing a normal memory access would consume 90% of that budget alone. The trick was to use the obscure DMA engine to pump data into the processor caches asynchronously. This way, moving data was only ~4% of the same budget, and they have beaten their performance targets by a large margin.
In this case, the lookup table is used for popcount, and there's a comment in the Z80 assembly that says "One lookup vs eight bit tests." If the code could make use of a hardware popcount instruction, the lookup table would lose, but if that isn't available, a 256-byte lookup table could be faster. So it's less "lookup tables are always faster" and more "lookup tables can be faster, this is one such case."
probably fastest popcount in z80 that does not use aligned table, would be shift A through flag, then conditional INC C, unrolled, still slower than ld l,a: ld b,(hl).
On the Z80 any memory access had a fixed cost of 3 clock cycles (in reality the memory system could inject wait cycles, but that was an esoteric case). Together with the instruction fetch of 4 clock cycles the fastest instruction to load an 8-bit value from an address that's already in a 16-bit register (like LD A,(HL)) takes 7 clock cycles.
The fastest instructions that didn't access memory (like adding two 8-bit registers) were 4 clock cycles, so there's really not much room to beat a memory access with computation.
Today "it depends", I still use lookup tables in some places in my home computer emulators, but only after benchmarking showed that the table is actually slightly faster.
The article does mention cache friendly access patterns in the same context.
But yes, you're right. Back when I started with optimizations in the mid 90s memory _latencies_ were fairly minor compared to complex instructions so most things that wasn't additions (and multiplications on the Pentium) would be faster from a lookup table, over time memory latencies grew and grew as clock speeds and other improvements made the distance to the physical memory an actual factor and lookup tables less useful compared to recomputing things.
Still today there are things that are expensive enough that can be fit in a lookup table that is small enough that it doesn't get evicted from cache during computation, but they're few.
I'm a sometimes CPU architect and came here to argue just this - modern CPUs have far far slower memory access (in clocks) than z80 memory access. To be fair you can probably fit any z80 table you're using into modern L1 cache, but even so you're looking at multiple clocks rather than 1.
Optimizing code on MMU-less processor versus MMU and even NUMA capable processor is vastly different.
The fact that the author achieves only a 3 to 6 times speedup on a processor running at a frequency 857 faster should have led to the conclusion that old optimizations tricks are awfully slow on modern architecture.
To be fair, execution pipeline optimization still works the same, but not taking into account the different layers of cache, the way the memory management works and even how and when actual RAM is queried will only lead to suboptimal code.
Seems like, You've got it backwards — and that makes it so much worse. ^_^
I ported from ABAP to Z80. Modern enterprise SAP system → 1976 processor.
The Z80 version is almost as fast as the "enterprise-grade" ABAP original. On my 7MHz ZX Spectrum clone, it's neck-and-neck. On the Agon Light 2, it'll probably win.
Think about that: 45-year-old hardware competing with modern SAP infrastructure on computational tasks.
This isn't "old tricks don't work on new hardware." This is "new software is so bloated that Paleolithic hardware can keep up." (but even this is nonsense - ABAP is not designed for this task =)
Turns out "I want a burger" beats "we have equivalent burger at home" every time—even when the home solution is objectively better.
So yes, this reads like "What my goldfish taught me about microservices." But unlike those posts, this story has no moral—just nerdy fun with enterprise software roasting.
Sometimes you gotta speak the language they actually read there +)).
Two reasons: 1) English is not my native tongue, 2) I hate LinkedIn article style -> let LLM convert my hadrcore-oldschool style into something like "You won't believe what my grandmother's cat taught me about ..."
My comment was a reaction to the fact that you called out your experience/wisdom on the topic no less than five distinct times in a short (otherwise great!) post.
I would argue that by doing so, you made it the unintended central theme of the post.
I'm not saying this to hurt your feelings. That you didn't perceive the obvious sarcasm in my late-night comment suggests that you might not want to be perceived as pompous in your writing style.
My suggestion is that one explicit "I'm an expert" reminder per post is a perfectly good number.
From the article: Lookup tables are always faster than calculation - is that true? I'd think that while in the distant past maybe today due to memory being much slower than CPU the picture is different nowadays. If you're calculating a very expensive function over a small domain so the lookup fits in L1 Cache then I can see it would be faster, but you can do a lot of calculating in the time needed for a single main memory access.
You will need to first sit and ballpark, and then sit and benchmark, and discover your ballpark was probably wrong anyhow:-)
Some (for me) useful pointers to that regard for both:
1. https://www.agner.org/optimize/instruction_tables.pdf - an extremely nice resource on micro architectural impacts of instructions
2. https://llvm.org/docs/CommandGuide/llvm-mca.html - tooling from Intel that allows to see some of these in real machine code
3. https://www.intel.com/content/www/us/en/developer/articles/t... - shows you whether the above is matching the reality (besides the CPU alone, more often than not your bottleneck is actually memory accesses; at least on the first access which wasn’t triggered by a hardware prefetcher or a hint to it. On Linux it would be staring at “perf top” results.
So, the answer is as is very often - “it depends”.
...and we always circle back to "premature optimization is the root of all evil", since processors are a wee bit more intelligent with our instructions than we thought. :)
Not that intelligent. If you have two loads and one store per cycle, then that’s it. (Recall that we have SSDs with 14 GB/s sequential reads now, yet CPU clocks are below 6 GHz.) Most of the computational power of a high-performance CPU is in the vector part; still the CPU won’t try to exploit it if you don’t, and the compiler will try but outside of the simplest cases won’t succeed. (Most of the computational power of a high-performance computer is in the GPU, but I haven’t gotten that deep yet.)
I don’t mean to say that inefficient solutions are unacceptable; they have their place. I do mean to say that, for example, for software running on end-users’ computers (including phones), the programmer is hardly entitled to judge the efficiency on the scale of the entire machine—the entire machine does not belong to them.
> We should forget about small inefficiences, say 97% of the time; premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.
D. E. Knuth (1974), “Structured Programming with go to Statements”, ACM Comput. Surv. 6(4).
> Lookup tables are always faster than calculation - is that true?
Maybe on the Z80. Contemporary RAM was quite fast compared to it, by our sad standards.
A table lookup per byte will see you hit a pretty hard limit of about 1 cycle per byte on all x86 CPUs of the last decade. If you’re doing a state machine or a multistage table[1] where the next table index depends on both the next byte and the previous table value, you’ll be lucky to see half that. Outracing your SSD[2] you’re not, with this approach.
If instead you can load a 64-bit chunk (or several!) at a time, you’ll have quite a bit of leeway to do some computation to it before you’re losing to the lookup table, especially considering you’ve got fast shifts and even multiplies (another difference from the Z80). And if you’re doing 128- or 256-bit vectors, you’ve got even more compute budget—but you’re also going to spend a good portion of it just shuffling the right bytes into the right positions. Ultimately, though, one of your best tools there is going to be ... an instruction that does 16 resp. 32 lookups in a 16-entry table at a time[3].
So no, if you want to be fast on longer pieces of data, in-memory tables are not your friend. On smaller data, with just a couple of lookups, they could be[4]. In any case, you need to be thinking about your code’s performance in detail for these things to matter—I can’t think of a situation where “prefer a lookup table” is a useful heuristic. “Consider a lookup table” (then measure), maybe.
[1] https://www.unicode.org/versions/latest/ch05.pdf
[2] https://lemire.me/en/talk/perfsummit2020/
[3] http://0x80.pl/notesen/2008-05-24-sse-popcount.html
[4] https://tia.mat.br/posts/2014/06/23/integer_to_string_conver...
Depends on the hardware and what you are making with that hardware. Some processors can do complicated things stupidly fast (e.g. when SIMD done right), and for some hardware platforms, a mundane operation can be very costly since they are designed for other things primarily.
My favorite story is an embedded processor which I forgot its ISA. The gist was, there was a time budget, and doing a normal memory access would consume 90% of that budget alone. The trick was to use the obscure DMA engine to pump data into the processor caches asynchronously. This way, moving data was only ~4% of the same budget, and they have beaten their performance targets by a large margin.
In this case, the lookup table is used for popcount, and there's a comment in the Z80 assembly that says "One lookup vs eight bit tests." If the code could make use of a hardware popcount instruction, the lookup table would lose, but if that isn't available, a 256-byte lookup table could be faster. So it's less "lookup tables are always faster" and more "lookup tables can be faster, this is one such case."
probably fastest popcount in z80 that does not use aligned table, would be shift A through flag, then conditional INC C, unrolled, still slower than ld l,a: ld b,(hl).
On the Z80 any memory access had a fixed cost of 3 clock cycles (in reality the memory system could inject wait cycles, but that was an esoteric case). Together with the instruction fetch of 4 clock cycles the fastest instruction to load an 8-bit value from an address that's already in a 16-bit register (like LD A,(HL)) takes 7 clock cycles.
The fastest instructions that didn't access memory (like adding two 8-bit registers) were 4 clock cycles, so there's really not much room to beat a memory access with computation.
Today "it depends", I still use lookup tables in some places in my home computer emulators, but only after benchmarking showed that the table is actually slightly faster.
The article does mention cache friendly access patterns in the same context.
But yes, you're right. Back when I started with optimizations in the mid 90s memory _latencies_ were fairly minor compared to complex instructions so most things that wasn't additions (and multiplications on the Pentium) would be faster from a lookup table, over time memory latencies grew and grew as clock speeds and other improvements made the distance to the physical memory an actual factor and lookup tables less useful compared to recomputing things.
Still today there are things that are expensive enough that can be fit in a lookup table that is small enough that it doesn't get evicted from cache during computation, but they're few.
> Lookup tables are always faster than calculation - is that true?
I know it's not always true on the Nintendo 64, because it shared a single bus between the RAM and "GPU": https://youtu.be/t_rzYnXEQlE?t=94, https://youtu.be/Ca1hHC2EctY?t=827
You are correct and I've even ran into a situation where build-time evaluation was slower than runtime calculation, thanks to code size.
I'm a sometimes CPU architect and came here to argue just this - modern CPUs have far far slower memory access (in clocks) than z80 memory access. To be fair you can probably fit any z80 table you're using into modern L1 cache, but even so you're looking at multiple clocks rather than 1.
Optimizing code on MMU-less processor versus MMU and even NUMA capable processor is vastly different.
The fact that the author achieves only a 3 to 6 times speedup on a processor running at a frequency 857 faster should have led to the conclusion that old optimizations tricks are awfully slow on modern architecture.
To be fair, execution pipeline optimization still works the same, but not taking into account the different layers of cache, the way the memory management works and even how and when actual RAM is queried will only lead to suboptimal code.
Seems like, You've got it backwards — and that makes it so much worse. ^_^
I ported from ABAP to Z80. Modern enterprise SAP system → 1976 processor. The Z80 version is almost as fast as the "enterprise-grade" ABAP original. On my 7MHz ZX Spectrum clone, it's neck-and-neck. On the Agon Light 2, it'll probably win. Think about that: 45-year-old hardware competing with modern SAP infrastructure on computational tasks. This isn't "old tricks don't work on new hardware." This is "new software is so bloated that Paleolithic hardware can keep up." (but even this is nonsense - ABAP is not designed for this task =)
The story has no moral, it is just for fun.
It's amusing that the writing style is akin to a LinkedIn what XYZ taught me about B2B sales.
Guilty as charged—and totally intentional.
Turns out "I want a burger" beats "we have equivalent burger at home" every time—even when the home solution is objectively better.
So yes, this reads like "What my goldfish taught me about microservices." But unlike those posts, this story has no moral—just nerdy fun with enterprise software roasting.
Sometimes you gotta speak the language they actually read there +)).
Writing style and length of paragraphs strongly suggest that this is AI generated in full.
Not yet in full, it is ~45% generated.
Two reasons: 1) English is not my native tongue, 2) I hate LinkedIn article style -> let LLM convert my hadrcore-oldschool style into something like "You won't believe what my grandmother's cat taught me about ..."
I have only one question: does the author know anything about coding ABAP like it's a Z80? I wish that they'd addressed this.
yes, it is addressed in another repo https://github.com/oisee/zvdb
and another article about zvdb-abap from ~1.5 years ago.
My comment was a reaction to the fact that you called out your experience/wisdom on the topic no less than five distinct times in a short (otherwise great!) post.
I would argue that by doing so, you made it the unintended central theme of the post.
I'm not saying this to hurt your feelings. That you didn't perceive the obvious sarcasm in my late-night comment suggests that you might not want to be perceived as pompous in your writing style.
My suggestion is that one explicit "I'm an expert" reminder per post is a perfectly good number.
oh!, now I got it =) will increase "Shy" parameter and decrease "Braggart" parameters in my "Normal speech" to "LinkedInese" translator +)
Thank you for feedback =)
(I was thinking that it is not MY wisdom i am talking, but about "Z80" wisdom - all the code I have seen on demoscene and e-zines.)
Nice recursive joke!