4 ms·
Lookup tables can be insanely fast, if kept entirely in L[1|2] cache. We found this out, when we were optimizing image processing pipelines (image processing u
by ChrisMarshallNY 3y ago
Lookup tables can be insanely fast, if kept entirely in L[1|2] cache.
We found this out, when we were optimizing image processing pipelines (image processing uses lots of lookup tables).
We found that the best way to optimize was to avoid moving out of cache, so we had to rewrite a lot of our stuff, so it never broke cache.
That meant a lot of copy-and-paste repetition, strict (small) static functions, and hardcoded values, instead of properties or even constants.
I don't remember all the stuff we learned, but it wasn't pretty (and applied only to x86 architecture. Not sure how well it would work, these days, on ARM).
- fluoridation 3y agoRegardless of the arguments this article makes, it can be surprising. One time back in the Core 2 days I was optimizing an alpha blend in software and I had something like x * y / 255. That operation was a tiny bit slower than table[(x << 8) | y].
- hajile 3y agoShift is one cycle. Or is one cycle. If your table is using a fast algorithm, it’s going to add a few more cycles and a couple very predictable branches. Meanwhile, divide is insanely slow. If your table is in L1 or L2 cache, it should be faster than the divide, but if not, I’d guess it would be slower. As the article says, that’s why you test then hope it doesn’t change later.
- fluoridation 3y agoSure, but my point is, how fast does the operation need to be and how slow does accessing the table need to be for the LUT to not be worth it, if a multiplication and a division is too slow?
- HappyDaoDude 3y agoThis was a big thing in video game development in the mid 90's/early 2000's. So long as you can keep the code and data or at least manageable chunks of it in cache, that would give huge performance gains. Things like the Ps2 VPU1 16KByte cache and the much more limited VPU0 with 4Kbyte cache. There were many titles that just did not use VPU0 for anything high performant simply because the cache limit killed its potential.
- djmips 3y agoThe Gamecube had a 'locked-cache' feature. You were able to reserve 16 KB of L1 data cache to use as scratchpad.
- petermcneeley 3y agoLookup tables can be competitive with SIMD https://darkcephas.blogspot.com/2018/10/validating-utf8-strings-with-lookup.html https://darkcephas.blogspot.com/2018/10/validating-utf8-stri...
- kwhitefoot 3y ago> hardcoded values, instead of properties or even constants. What's the difference in the object code between a hardcoded value and a constant? Surely they should be the same?
- ChrisMarshallNY 3y agoI don’t remember, exactly. It was C++ (LLVM, I think). It was important that the PC never leave the cache address pool, and constants may have been in a table, somewhere. With macros, it was almost the same.