6 ms·
Compilers are too smart
- FrankWilhoit 2y agoSo you need to do a binary search but you don't want to use division instructions. The funny thing is that DEC's assembler for the PDP-10 did a very similar thing to set up the binary search of its symbol table, which was its critical path. The JFFO instruction (Jump on Find First One) was added to the PDP-10 instruction set for this purpose.
- fanf2 2y agoBinary search is easy because division by two is just a shift. It doesn’t need any division or even multiplication instructions. I can guess why they might have used JFFO but it seems needlessly complicated. I wonder why libcxx doesn’t use multiplication for modular reduction. https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...
- FrankWilhoit 2y agoThe trick is quickly finding the largest power of two that is less than the size of the table. It was done with two instructions: the second was the JFFO, the first was an FADD with a purposely denormalized operand. The symbol table was kept sorted on every insert.
- fanf2 2y agoThat was my guess :-) But binary search doesn’t need explicit powers of two. I wonder if maybe the PDP10 is much faster at loops with explicit counters instead of comparing the search upper and lower bounds.
- FrankWilhoit 2y agoNo, the loop would have been slower. That is why they found the starting point with that bizarre two-instruction sequence. For any table size between (2^^n)+1 and 2^^(n+1), inclusive, it returned 2^^n as the starting point. Then of course it had to loop after that.
- petermcneeley 2y agoLooks like this is the week we talk about the performance of hash function binning. https://news.ycombinator.com/item?id=40553541 https://news.ycombinator.com/item?id=40553541 Most of the issue here comes from the mistaken belief that computers do mathematical (and more specifically arithmatic) operations as first class citizens.
- deleted 2y ago[deleted]
- shikaan 2y agoI know it's probably hyperbole, but why > yes, I know, friends don’t let friends use STL, but that is a topic for another discussion ? Are there known shortcomings with the standard library in C++?
- deleted 2y ago[deleted]
- mrcode007 2y agoNo. It’s a trope. Most people can’t tell the difference. It’s highly context and application specific.
- olliej 2y agoYeah the bulk of the time it doesn’t matter. The only places it really matters are if you have stronger perf requirements, or dislike stupid amounts of UB.
- unwind 2y agoI noticed the post was tagged with 'gamedev' which might be relevant, STL used to be hard to optimize due to it doing lots of heap allocations. It has been a while since I was in gamedev so perhaps not true anymore but sometimes these things change slowly with people/culture.
- fyrn_ 2y agoIt has some pretty bad containers, specifically unordered_map and map, and set. There are some good talks on why from ccp con and other varius developer cons. They are still usable mind you, just it's also true that unordered_map is slower then JS or Python hashmaps in some situations because of some really questionable design choices (exposing bucket nodes, overly restrictive iterator invalidation requirements, etc..)
- krackers 2y agoWhat's the recommended drop-in replacement? absl::flat_map?
- mrcode007 2y agoIt uses SWAR technique for counting bits because target platform wasn’t specified in compiler flags properly. popcnt and family are specific family extensions and without specifying the target flags the compiler generates lowest common denominator among available instructions Edit: add -msse4 and you will see popcnt appear because popcnt is the SSE4 extension
- deleted 2y ago[deleted]
- fyrn_ 2y agoThe article says all of this?
- upon_drumhead 2y ago> It was a Clang compiler, ARM-based platform > I do think it is a bug in this case, native popcnt could maybe be defended, but should not be used if compiling for architecture that does not support it.
- mrcode007 2y ago> If you would like to experiment yourself, Compiler Explorer snippet can be found here https://gcc.godbolt.org/z/qGzWo39b6 https://gcc.godbolt.org/z/qGzWo39b6 Which is an x86-64 sample
- upon_drumhead 2y agoIt's a little impossible to show the difference between using popcnt and the expanded emulation code on a platform that doesn't support popcnt. It doesn't change the fact that the actual program itself was being complied on a platform that doesn't support popcnt, so no amount of compiler arguments would fix that.
- mrcode007 2y agoNEON extension on ARM comes with CNT instruction that counts set bits.
- Findecanor 2y agoI have come across a related compiler issue with popcnt before. I was trying to prototype a "population count" routine in C before rewriting it in 64-bit ARM assembly. ARMv8.0 64-bit doesn't have a "popcnt" instruction in its scalar set. I was curious to how well Clang would map my C statements into the ARM assembly I had been thinking of using, so I tested it on Compiler Explorer. I noticed that in the output my routine was oh so slightly different, using an inverted constant. I then rewrote my routine with another algorithm ... but got the same compiler output. Apparently Clang can recognise that "Oh, this is a population count routine" and replace it with a `llvm.ctpop.i32` intrinsic. I have found no way to use compiler flags to suppress specifically this optimisation without turning off optimisations completely.
- matthews2 2y agoYou can use -mno-popcnt for this. Godbolt: https://godbolt.org/z/raszoEedr https://godbolt.org/z/raszoEedr Reference: https://clang.llvm.org/docs/ClangCommandLineReference.html#cmdoption-clang-mpopcnt https://clang.llvm.org/docs/ClangCommandLineReference.html#c...
- tialaramex 2y agoThis is called Idiom Recognition, and it was already needed in some compilers in the 1960s. So, unless you're now writing C from a retirement home probably all the non-toy compilers you've used had this feature.
- 2y ago
- mgaunard 2y agojust use a hashmap implementation that always uses power-of-two buckets.
- nikic 2y agoThe background here is that "ctpop < 2" or "ctpop == 1" (depending on zero behavior) is LLVM's canonical representation for a "power of two" check. It is used on the premise that the backend will expand it back into a cheap bitwise check and not use an actual ctpop operation. However, due to complex interactions in the backend, this does not actually happen in this case (https://github.com/llvm/llvm-project/issues/94829 https://github.com/llvm/llvm-project/issues/94829).
- diffxx 2y agoGreat title. I feel like in some sense we've lost our way with compiler design. Languages do not help us write code that require minimal optimizations to run fast enough on most workloads. Instead, we overoptimize with -O[23] everywhere which slows down our development process and makes all of our code inscrutable. Better would be a faster -O0 experience and good profilers/observability so that we only optimize the hot spots (which could mean isolating specific subcomponents and compiling only those with optimizations on). Of course it's much easier to just globally turn on release mode and optimize everything whether it matters or not. This both slows down the development process considerably and leads to bizarre issues like this.
- fch42 2y agoAn "unrolled" popcnt is not that badly performing; I haven't seen numbers for a current server class CPU. Results for older CPUs for different implementation can be found easily, for example at https://news.ycombinator.com/item?id=11277891 https://news.ycombinator.com/item?id=11277891
- gergo_barany 2y agoThe use case in the article here is for a single 8-byte (one size_t) popcount at a time. The comparison in your source is for when you want to compute many popcounts in parallel. The smallest size it compares is 32 bytes, where the scalar popcount instruction beats even the fastest other variants by a factor of almost 2x. The AVX2 lookup variant only starts beating it starting at 256 or 512 bytes, depending on the exact CPU. And even then, that variant is not equivalent to (a parallel version of) the scalar code shown in this article. So, good that the parallel version exists, but it's really apples and oranges compared to this article's problem.
- valicord 2y agoImpressively, chatgpt was able to tell that the assembly snippet is computing popcnt on the first try without any hints.
- mhh__ 2y agoIt is impressive but keep in mind that compilers follow relative familiar patterns with this kind of thing in that they specifically either emit the same pattern from an intrinsic or emit the same pattern from manually spotting a loop in the input source code i.e. it's not going in blind
- zamalek 2y ago> you need SSE4 on x64 for popcnt This is a strong argument for moving to x86_64-v2 (or at least having an entire package ecosystem build for it) because popcnt shows up all over the place.
- GnarfGnarf 2y agoWhat’s wrong with STL?
- ratmeadow 2y agoLooks like the author is into game development, and STL is often avoided in that context. I think one of the reasons is performance - STL has made some design decisions which prioritise general use over performance. Often cited example is `std::unordered_map`, whose spec necessitates an implementation using separate chaining (or similar). Depending on the use case, in high performance applications, a different implementation can be much faster. Although I don't understand why some people hate all of STL so much. Like sure, use your custom hash map, makes sense. But is anyone really replacing basics like `std::find` or `std::sort`?
- GnarfGnarf 2y agoThanks for the clarification. I think STL is the greatest thing since sliced bread. The time I have wasted in the 90’s debugging malloc/realloc/free rat’s nests for dynamic arrays, I could have put to better use. Thank god for vector/deque etc. I work isolated. I didn’t learn about STL until years later,
- daemin 2y agoProbably also because Game Developers had to deal with the MS STL implementation which for many years both the compiler and standard library were behind the times and not that optimal. Case in point when using a std::deque with MS STL it's not really efficient because it has a very small buffer size, so it pretty much degrades into a linked list if the element is big enough. See: https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=108587 https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=10... Then there's the case of std::unordered_map which has been benchmarked recently, and for all the flak that boost gets I am considering using it for its hash map. https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/ https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/
- GeertB 2y agoA smart compiler would have used the test (x & (x - 1)) == 0 to verify that x (assumed non-zero) is a power of two. Don't know why Clang didn't do that here.
- fooker 2y agoThe tricky part is doing this without knowing the value of x! This is why compilers have to rely on static analysis.