6 ms·
There is an often-missed elephant in the compiler optimization living room in the form of poor language design leading to a tremendous amount of wasted human ef
by lisper 10y ago
There is an often-missed elephant in the compiler optimization living room in the form of poor language design leading to a tremendous amount of wasted human effort. First, effort is demanded of the programmer to write the clever optimized C code in the first place, and then effort is demanded of the compiler writers to recognize the clever optimized C code and compile it down to the native instruction that does the Right Thing.
All of this effort could be eliminated simply by adding a function to the standard library called bitcount. This would make life easier for both the programmer, who could now count bits by calling bitcount, and the compiler writers, who no longer have to write and maintain code that recognizes clever hacks.
This (counting bits) is not an isolated incident either. There is an entire field of academic endeavor devoted to this sort of thing, focusing particularly on recognizing common idioms involved in vector and array processing. All of this could be eliminated at a stroke through better language design. Instead, an entire academic field dons the ball-and-chain of a poorly designed language and then pats itself on the back for getting to the finish line panting and sweating, and people like me who say, "Um, why not just take off the extra weight and use a better designed language?" get marginalized at best and vilified at worst.
- adrianN 10y agoBetter language design unfortunately doesn't eliminate the other elephant in the room: legacy code. Compilers do provide intrinsics for some of these hacks, counting bits for sure. But old code doesn't use them and yet the compiler should create optimal instructions.
- lisper 10y agoTrying to make legacy code run faster through horrible compiler hacks rather than fixing the legacy code is a deal with the devil. The net result of that strategy is a horrible pile of hacks, many of which are there fore no reason other than to undo the deleterious effects of previous hacks. The long-term cost of maintaining all that complexity is far greater than the cost of just doing the Right Thing in the first place. Nowadays there is absolutely no excuse for continuing to use languages with built-in design compromises that were put in simply because the compiler had to fit in 64k of RAM. People keep doing it because doing the Right Thing front-loads the cost. But another name for "front loading costs" is "making an investment" which is generally considered a Good Thing in other walks of life. But for some reason, not in software.
- gpderetta 10y agoLegacy code is working code. Arguably time is better spent making old code go faster than optimizing yet to be written code. And this is not confined to compilers. Most general purpose high performance CPUs are actually optimized to make existing code go fast and do not require recompilation to take advantage of many optimizations. Some go as far as recognizing common sequences of instructions and internally converting them to more optimized sequences (for example POWER8 conditional conversion of short jumps to conditional execution).
- sliverstorm 10y agoOption A: Maybe it's acceptable for legacy code to be compiled less-optimally? If it was fast enough on a Pentium 4, it should run fine on modern chips even without some optimizations Option B: How often is legacy code recompiled, anyway? Option C: Why not compile legacy code with legacy compilers? Sure the hack was removed upstream, but that doesn't stop you from using a copy of gcc circa 1995 Option D: If it needs to be maximally fast, and is routinely recompiled on a wide range of systems with a variety of compilers (e.g. Linux kernel), maybe it's worth rewriting.
- cremno 10y ago>Please don't bait other users by inviting them to downvote you or announce that you expect to get downvoted. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- lisper 10y agoIronically, I see you're getting downvoted, but you shouldn't be because you're right: I violated HN guidelines, so I edited my comment to remove the offending passage. Thanks for pointing this out.
- mikeash 10y agogcc and clang both provide a builtin for this, __builtin_popcount. There are a bunch of other useful things like that too: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html Of course, that doesn't save you from writing the long version if you need portable code, but it's a step in the direction you describe.
- psuter 10y agoMake sure to use __builtin_popcountl to count bits in a uint64_t, or you may miss half of them (yes it happened to me).
- nightcracker 10y agoI love this example. Even though you are aware how error-prone this is, you still get it wrong. long is 32-bits on GCC 32-bit. So it will still give the wrong result with `uint64_t`. You should be using __builtin_popcountll. (don't get me wrong - you're not stupid, it happened to me too: https://github.com/orlp/libop/issues/1 https://github.com/orlp/libop/issues/1)
- psuter 10y agoGood catch, thanks. (It has been a while since I've been on a 32bit platform.)
- lisper 10y ago> it's a step in the direction you describe. Well, sort of. This is not about any one particular optimization. This is about the general pattern of having one human take a high-level concept (like counting bits) and reducing it to a low-level implementation, and then having a second human writing a compiler which tries to reverse-engineer the work that the first human did in order to figure out that they were trying to count bits so that it can emit code that actually does the Right Thing. So yes, __builtin_popcount does improve the situation a little bit, but it perpetuates a whole host of other problems. For example: 1. It has the wrong name. The right name for a function that counts bits is "bitcount", not "popcount" (and certainly not __builtin_popcount!) The __builtin is there because C doesn't have a proper name spacing system, and so using __builtin_popcount perpetuates that problem in the same way that clever compiler optimizations perpetuate other bad aspects of C's design. 2. __builtin_popcount only works on unsigned ints. If you want to count bits in anything else (a string, say, or a bignum) you're back to square 1. To really fix this problem you need a general mechanism for expressing high-level concepts that a compiler can now about and optimize directly. For that, C is completely hopeless. You need a new language.
- trishume 10y agoRust does exactly this in many cases. All the integer types have methods like 'count_ones' for popcount and 'trailing_zeros' for ctz, things that are intrinsics in other languages. See http://doc.rust-lang.org/1.8.0/std/primitive.u64.html#method.count_ones http://doc.rust-lang.org/1.8.0/std/primitive.u64.html#method...
- kibwen 10y agoThough note that these methods are really just thin abstractions over intrinsics, since Rust doesn't want to stabilize intrinsics directly for reasons of compiler backend portability. For example, the `count_ones` method currently resolves directly to LLVM's `ctpop` intrinsic, defined at https://github.com/rust-lang/rust/blob/master/src/libcore/intrinsics.rs#L548 https://github.com/rust-lang/rust/blob/master/src/libcore/in... .
- nirvdrum 10y agoFYI, when you're on a GitHub page you can press the 'y' key to have the URL changed to one that includes a particular blob reference. It helps prevent bit rot. Curently, your linked line doesn't point to the `ctpop` intrinsic. I think you wanted https://github.com/rust-lang/rust/blob/34fd68668152530dcd1d00865fa8514461b895d7/src/libcore/intrinsics.rs#L558 https://github.com/rust-lang/rust/blob/34fd68668152530dcd1d0...
- greglindahl 10y agoYour point on vectors and array processing is not a good one: Some significant numerical algorithms can be easily expressed with nested loops, and are a pain to express with array operations. Fortran has both, and some of the best compilers turn array operations into loops, to ensure that they get both forms right. Maybe you could spend more time understanding other points of view, rather than feeling marginalized or vilified?
- lisper 10y ago> Some significant numerical algorithms can be easily expressed with nested loops Like for example? Just to clarify, I'm (obviously) not suggesting that nested loops be eliminated from the language, or that common optimizations on nested loops be eliminated from compilers. But having specialized code to recognize a clever idiom for counting bits is IMHO going way too far. It's true that I'm not intimately familiar with numerical algorithms, so I could be wrong about this, but my impression is that the number of "significant numerical algorithms" that can be easily expressed as nested loops is not that large: dozens, not hundreds. Unless I'm wrong about that, I stand by my position that the best way to handle these is to enumerate them and then allow them to be expressed directly.
- greglindahl 10y agoSuch as any code that applies a 1D operator against each of 3 dimensions in turn. That's done in the commonly-used PPM hydrodynamics algorithm, which is used in astrophysics and nuclear weapon simulations.
- amelius 10y agoOne big problem I see, is that these tricks make the compiler unpredictable in terms of performance. Add a line somewhere in the middle, and the compiler might no longer recognize the construct, and suddenly your code runs 10x slower. Try debugging that :)
- JBReefer 10y agoYeah, you can't print that halfway through and get the killer performance (not that printf is fast)
- DerekL 10y agoThere's a proposal to add them to the C++ standard, but I don't know its current status. “A constexpr bitwise operations library for C++”: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3864.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n386...
- SilasX 10y agoGreat thinking! So that way, if you need to leftpad a string, you could just import the well-maintained leftpad function ...
- gravypod 10y agoThe principle is sound. Would you rather there be 500 non standard implementations of left-pad or should there be one fast and optimized implementation of left pad? The only issue that leftpad demonstrated was that there was NO method for dependency resolution of removed libraries.
- SilasX 10y agoOh, agreed, just calling back to the outrage over "dude, why would you need a library for that?"