Comment by shiomiru | Hacker News Reader

Comment by shiomiru | Hacker News Reader

> As any good programmer knows, division is slow, it’s a serializing instruction, and we want to avoid it as much as possible. The favourite programmer tricks to avoid division are to use bit shifts (for division by multiples of two) or flip it into a multiplication — for example, to multiply by 0.333 instead of dividing by 3. In this case though, we are dividing by the alpha, so we can’t know what number we will be dividing by in advance.

> However, because the channels are 8-bit, we will only ever be dividing numbers from 1 to 255 (yes, some values will be zero — but we sure won’t be dividing by them then!) That means there are only about 65K possible combinations, so we can use another classic solution: a lookup table! This is a perfect place to use constexpr to bake the array directly into the compiled result.

Interestingly, when I benchmarked this same problem, three integer divisions would easily beat the LUT on my computer. Maybe because the it's easier on the cache? (Or I did something wrong.)

I think, on a modern processor, a lookup table of 65k is way too big to be worthwhile for something as simple as a division

memory access is relatively very slow; OP probably should have benchmarked it

Depends on the use and context, benchmarking can hint at the "truth", that it is faster to just divide: ultimately the benchmark would have to have the two implementations and run them thru all possible inputs to know for sure.

It may clearly state that memoization is slower, until you plop it into a benchmark that inlines division explicitly without using a given hardware accelerate.

division by a constant input can be solved faster still, so there can be optimizations on top of memoization that would beat raw division on most peocessors/runtime environments.

Chances are only a small portion of the lookup table is used. It's conceivable that this is almost entirely L1 access.

But I'm also very skeptical that this is actually faster. Would have been nice to see some numbers

I think an l2 cache hit is about the same number of cycles as a single byte divide, might as well save the cache for something else

but yeah, this is just my speculation

Instead of compiling and running code, just replace all of your code with composable functions that are each small enough to lookup the results for in a precomputed hardware dictionary. In this way you have a Turing complete cpu with only one instruction.

I started this comment as a tongue in cheek satire of yours, but now I’m honestly wondering if it could be a viable idea for a radically simplified cpu (I’m not a computer engineer). I suppose the lookup tables rapidly become too large, possibly before they are useful?

For an 8-bit CPU you could maybe do it. For a 64 bit cpu, the lookup table for addition alone would be massive. (You can of course do addition in smaller increments, like adding one digit at a time and keeping track of the carry, but then you just have a normal full adder).

The biggest issue is that this CPU would be conceptually simple, but very difficult to make fast. Memory is slow, and accessing a 64k lookup table uses more transistors than just doing the addition

Again, I'm no expert here but find this stuff fascinating. Could the simplicity possibly allow some radically different CPU design that makes the lookups alone nearly instantaneous? I could imagine some types of optical/photonic physical 3D hash table structures - even ones where the same physical structure could support a large number of read operations in parallel if pre-arranged by a compiler to not physically interfere. I imagine a cpu with only one instruction could be physically miniscule, and therefore pack a lot of cores in a small space.

Hypothetically, if it were orders of magnitude faster than a normal CPU, one could still perform rapid computation on larger numbers as needed while keeping the cpu physically 8 bit- yet be able to revert to even higher performance when less precision is needed.

If you're interested in One Instruction Computers, check out: https://en.m.wikipedia.org/wiki/One-instruction_set_computer

Thanks! I half expected to be told one instruction computers were impossible.

Just build 4 of them and chain them together to get 64-bits.

(Beyond just being a joke, it is often how things like this get scaled. 1-Bit Adders become 2-Bits with a Carry Line between, then 3-bits with another Carry Line, and so forth, ad infinitum and beyond. The real joke is the complexity involved in however you "just" chain them together.)

CPUs do use a ton o LUTs under the hood.

I wonder if this was inspired by this discussion, but this just made the front page. I didn’t realize the famous Pentium fdiv bug was due to an error in a lookup table used for division: https://news.ycombinator.com/item?id=42391079

I've been (very slowly) working on this for a 4-bit CPU. Not for any practical reason, just for fun.

Any more details you could share? Is this a physical cpu design, or a VM/assembler?

There are packages for those things in npm, but they you'll have to start using javascript...

https://www.npmjs.com/package/@samuelmarina/is-even

The javascript crowd. They are always one step ahead!

Haha, a 100mb library, it doesn't say so but is this really a dictionary of numbers with even/odd as values? I love that they have an entirely separate is-odd package.

//edit: looked at the code, it's literally 100mb of if else statements- and a bunch of them are wrong! The github pull requests to add additional integers are hilarious.

AI powered version: https://github.com/rhettlunn/is-odd-ai

It also depends a lot on your CPU. Operations can be made faster by dedicating more resources to them. Most CPUs go for a slowish division operation that isn’t too expensive in terms of resources, or lower-end ones don’t provide it at all and make you do it in software. Apple seems to have decided that integer division is pretty important, so they dedicated a lot of resources to it and the M1 does a divide in something like two cycles. Even thinking about loading from memory is probably slower than that.

A 256-item float32 LUT for 8-bit sRGB -> linear conversion is definitely still faster than doing the division live (I re-benchmarked it on Zen4 and Apple M3 last month), however floating point division with the newer microarchs is not as slow as it was on processors 10 years ago or so, so I can imagine using a much larger LUT cache is not worth it.

does this include vectorized code? I stopped using LUTs for anything “trivial” probably 20 years ago because I rarely see any improvements (in particular where it would benefit the overall runtime noticeably).

With all the discussion of lookup tables here it is worthwhile to remember the https://en.wikipedia.org/wiki/Pentium_FDIV_bug from the mid 1990s.

I was a little kid the age my son is now when I went with my dad to buy a 486 cpu and motherboard… he said he wasn’t getting the pentium because he did scientific computing and was worried about this bug. It’s funny that I only now understand what the significance of that was due to this thread.

Reply on news.ycombinator.com