4 ms·
> 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 on
by 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.
- rjeli 10y agoI would expect `bitcount` to mean sizeof(x)*8. Population count or Hamming weight is the canonical name for this operation.
- to3m 10y agoErm - ``sizeof x*CHAR_BIT'' ;)
- andreasvc 10y agoA bit is a binary digit, with a value of 0 or 1. Popcount counts the number of 1-bits; and, as said, population count actually is the canonical name. You can apply __builtin_popcount in a loop if you want to count bits in multiple words. The point of exposing this particular operation for an unsigned int is that a recent CPU will likely have an efficient operation for it. Operating on larger units is something better left to your own code or a library. You're definitely not "back to square 1", because the intrinsic offers you an operation that would otherwise only be accessible with inline assembly.
- WalterBright 10y ago> a general mechanism for expressing high-level concepts functions > that a compiler can now about and optimize directly. For that, C is completely hopeless. This has been done with C for generations, i.e. memcpy, strlen, sqrt, and even printf are recognized by the C compiler and custom code is generated. The only problem is the C community has been slow to standardize on additional functions.
- lisper 10y agoNo, that's not the only problem, it's one of many problems. But even by itself it's a pretty frickin' substantial problem.
- WalterBright 10y agoIt means a new language is not required. Even without a Standard update, the various C compiler vendors could get together and agree on a set of them, making a "technical report". Anyhow, what other problems?
- lisper 10y ago> the various C compiler vendors could get together and agree on a set of them, making a "technical report". Yes, they could. But they don't. > Anyhow, what other problems? The lack of a real multi-dimensional array type is probably the biggest problem with regards to the goal of making code run fast. The fact that strings are required to be zero-terminated arrays of signed 8-bit integers is another huge problem. It means that you can't have native unicode strings, and that to create a substring you have to make a copy. The lack of exceptions and automatic memory management means that you need weird calling conventions if you want to return composite types, or if a function can fail. The lack of generics and namespacing means that you need to use weird naming conventions to avoid collisions, and there is a significant cognitive load placed on the programmer to figure out the right operation to use for a particular set of operand types (except for native arithmetic, but that can't be extended to any non-native types).
- theseoafs 10y ago> The right name for a function that counts bits is "bitcount", not "popcount" "Population count" is what this function is typically called. > (and certainly not __builtin_popcount!) C doesn't have namespacing and naming the function "bitcount" would almost certainly collide with user code. > 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. Not really? Just use __builtin_popcount in a loop.
- lisper 10y ago> "Population count" is what this function is typically called. I didn't know that. Thanks. > C doesn't have namespacing That I did know. I even pointed that out in the comment you're responding to :-) > Just use __builtin_popcount in a loop. But that just brings you back to the original problem when some day someone builds a machine that has hardware support for popcount on multiple words.
- theseoafs 10y ago> But that just brings you back to the original problem when some day someone builds a machine that has hardware support for popcount on multiple words. Is that really a problem? We've already seen that compilers are clever enough to recognize these patterns. Meanwhile any loop using __builtin_popcount will look more or less like this: for (int i = X; i < Y; i++) { total += __builtin_popcount(a[i]); } ... which is a substantially easier pattern to recognize than the one that clang is already using to recognize popcount.
- lisper 10y ago> Is that really a problem? I think it is if you consider wasted effort a problem. But apparently not everyone does. > compilers are clever enough Yes, but only because someone did a lot of work to make them clever. And they only had to do that work because someone else did a lot of work to write a clever algorithm. If we as an industry had just done the Right Thing to begin with both of those people could have used that time to do something more productive.