5 ms·
> 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 t
by shiomiru 2y ago
> 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.)
- Palomides 2y agoI 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
- Jerrrry 2y agoDepends 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.
- wongarsu 2y agoChances 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
- Palomides 2y agoI 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
- wat10000 2y agoIt 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.
- _yb2s 2y agoInstead 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?
- wongarsu 2y agoFor 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
- _yb2s 2y agoAgain, 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.
- spencerflem 2y agoIf you're interested in One Instruction Computers, check out: https://en.m.wikipedia.org/wiki/One-instruction_set_computer https://en.m.wikipedia.org/wiki/One-instruction_set_computer
- bluGill 2y agoWith all the discussion of lookup tables here it is worthwhile to remember the https://en.wikipedia.org/wiki/Pentium_FDIV_bug https://en.wikipedia.org/wiki/Pentium_FDIV_bug from the mid 1990s.
- _yb2s 2y agoI 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.
- berkut 2y agoA 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.
- fp64 2y agodoes 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).