4 ms·

Eh, you should probably test it either way. Performance can be very unpredictable. I ran into a weird case years ago when I was writing a program that needed

by Tommah 3y ago

Eh, you should probably test it either way. Performance can be very unpredictable. I ran into a weird case years ago when I was writing a program that needed to calculate popcount (number of 1 bits in a number). My method using a 256-entry lookup table turned out to be faster than using GCC's popcount intrinsic. (See [1] for a question from someone who encountered a similar situation. The solution provided there was to compile with -march=native, but I think I tried that without success.) I ran into a similar problem in another program where I needed 128-bit integers. I implemented them myself as a C struct containing two 64-bit integers. Then I discovered that GCC implemented its own 128-bit integer type. But that type was somehow slower than my implementation! [1] https://stackoverflow.com/questions/52161596/why-is-builtin-popcount-slower-than-my-own-bit-counting-function https://stackoverflow.com/questions/52161596/why-is-builtin-...

vardump 3y ago
Perhaps a wrong link? Your link shows a case where the compiler's implementation is better than a custom one.
- Thorrez 3y ago
  Has the link been edited? And are you taking about the question or the answers? In the question, __builtin_popcount is the slowest of the 3 options on both compilers.
o11c 3y ago
Was your problem perhaps because of the hardware bug where popcount unnecessarily stalled on the output as if it were an input? Later compilers added an explicit zero of the output to work around this issue.
- Tommah 3y ago
  Interesting... I hadn't heard about that bug. Here's my current theory about what was happening. Back then, I was using an Intel Atom notebook, and some research tells me that the early Atom processors don't have the popcount instruction. This would make GCC fall back to its implementation. I looked at GCC's current implementation, and it's using a 256-entry lookup table. My implementation was faster... so either (1) I was using a larger lookup table than I remembered, maybe 65536-entry, or (2) GCC was doing something different back then.
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 ago
  Regardless 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 ago
    Shift 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 ago
      Sure, 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 ago
  This 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.

by Tommah 3y ago

vardump 3y ago

Perhaps a wrong link? Your link shows a case where the compiler's implementation is better than a custom one.

Thorrez 3y ago
Has the link been edited? And are you taking about the question or the answers? In the question, __builtin_popcount is the slowest of the 3 options on both compilers.

o11c 3y ago

Was your problem perhaps because of the hardware bug where popcount unnecessarily stalled on the output as if it were an input? Later compilers added an explicit zero of the output to work around this issue.

Tommah 3y ago
Interesting... I hadn't heard about that bug. Here's my current theory about what was happening. Back then, I was using an Intel Atom notebook, and some research tells me that the early Atom processors don't have the popcount instruction. This would make GCC fall back to its implementation. I looked at GCC's current implementation, and it's using a 256-entry lookup table. My implementation was faster... so either (1) I was using a larger lookup table than I remembered, maybe 65536-entry, or (2) GCC was doing something different back then.

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 ago
Regardless 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 ago
  Shift 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 ago
    Sure, 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 ago
This 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.