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.
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)
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.
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.
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.
Anyhow, what other problems?
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).
> strings are required to be zero-terminated arrays of signed 8-bit integers
This is incorrect. C's char type is optionally signed, not required to be signed. The implementations I know of make them unsigned, because signed characters make no sense.
Unless you can produce an actual counter-argument I guess we'll just have to agree to disagree about that.
> signed characters make no sense
I could not agree more. And yet...
[ron@mighty:~] gcc -v
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 6.0 (clang-600.0.51) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin13.4.0
Thread model: posix
[ron@mighty:~] cat test.c
int main(int argc, char** argv) {
unsigned char* x = "baz";
}
[ron@mighty:~] gcc test.c
test.c:3:18: warning: initializing 'unsigned char *' with an expression of type
'char [4]' converts between pointers to integer types with different sign
[-Wpointer-sign]
unsigned char* x = "baz";
^ ~~~~~
1 warning generated.There's no problem having a function called popcnt(), and having the C compiler recognize it just like it recognizes memcpy(), strlen(), sqrt(), etc., and generate optimal code for it.
"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.
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.
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]);
}
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.
You haven't considered 2 things: marginal returns and opportunity cost.
Your solution to this "wasted effort" is to build a better C (or a better language). But this overlooks the millions of hours spent in C systems, C code, C compilers, learning, and all that would have to be done once again...
If the better language already existed, and was a drop in replacement (meaning everything just works) then your argument would indeed mean an end to wasted effort if adopted.
But as it is, it means tons of EXTRA effort, which is not clear is if better than the current wasted effort because of C deficiencies.
Yes, I have.
> this overlooks the millions of hours spent in C systems
No, it doesn't. You are assuming that I am advocating re-writing existing C code in this hypothetical new language. I'm not. The hypothetical new language should be backwards-compatible with C, either a superset of C (like C++) or with a C (and C++) FFI (just about every other language out there today).
But even that is not strictly necessary. It is already common practice for programs written in different languages to interact with each other via language-independent mechanisms like pipes and sockets.
> If the better language already existed, and was a drop in replacement (meaning everything just works) then your argument would indeed mean an end to wasted effort if adopted.
Many such languages exist. The one I like to use, Common Lisp (and specifically Clozure Common Lisp) not only has a C FFI, it has an Objective-C FFI, which allows me to easily write Cocoa applications and leverage all of the power of both C and ObjC libraries on OS X with all of the efficiency of C. No wheel-reinventing required. And yes, everything Just Works. (With QuickLisp it really Just Works!)
> But as it is, it means tons of EXTRA effort
No, it doesn't. If you think it does, then you're doing it wrong.
Not sure in what parallel universe starting to write software in CL, and getting hundreds of thousands of C programmers to adopt it doesn't mean "tons of EXTRA effort".
Heck, even the re-training required is millions of man-hours.
Even worse for the other proposed solution, to have legacy programs (that is: 99.9999% of available software that's not in the "NEW LANGUAGE") written in different languages to interact with each other via language-independent mechanisms like pipes and sockets.
And all that to gain what?
Supposedly it was to have a language where compilers could take advantage of the superior design to be even faster and more optimized than C, and you propose CL, which, after 30+ years, is slower or at best equal-ish to C.
> And all that to gain what?
The ability to write future software with less effort (and that is more reliable and secure) than past software.
> equal-ish to C.
Equal-ish is good enough given the big win in security, reliability and development effort.
I don't think anybody doubted that. At least not anybody who ever heard of the C calling conventions and FFIs.
But you started this thread advocating for something much stronger, which I read (correct me if I'm wrong) as: working around C is wasting so much effort, people should adopt a better language design for better compiler optimizations, etc.
Unless this adoption is actually a mass phenomenon (even a replacement), then instead of improving things, it only split all the effort and worsened things.
>The ability to write future software with less effort (and that is more reliable and secure) than past software (...) Equal-ish is good enough given the big win in security, reliability and development effort.
At the start of this thread you were all about compiler optimizations for speed -- not about more reliability and security. Now "equal-ish" to C is good enough?
Well, you wrote:
> this overlooks the millions of hours spent in C systems, C code, C compilers, learning, and all that would have to be done once again...
and you are wrong -- on two counts. I didn't overlook these things, and they would not have to be done again. It's a little unclear to me how you could possibly think that they would have to be done again if you didn't doubt that this problem could be solved with an FFI.
> But you started this thread advocating for something much stronger, which I read (correct me if I'm wrong) as: working around C is wasting so much effort, people should adopt a better language design for better compiler optimizations, etc.
Yes, that's right.
> Unless this adoption is actually a mass phenomenon (even a replacement), then instead of improving things, it only split all the effort and worsened things.
No, that's not right. Different tools are good for different tasks. There's nothing wrong with split efforts.
Furthermore, even if you're right and there should be only the One True Language, don't you think it would be better if it were actually a well designed one?
> At the start of this thread you were all about compiler optimizations for speed
Not quite. I was lamenting the way in which compilers are evolving: people write clever algorithms in C, and compiler writers then write compilers to try to reverse-engineer those clever algorithms, and neither of those efforts would be necessary if we had a language that could directly express the things that people want to run fast and compiler writers could just directly compile those things to run fast. Life would be better for everyone.
The problem with C is that it's a low-level language masquerading as a high-level one. It's a macro assembler for a machine that was common in the 1970s but is no longer common today. The general idea of having a high-level assembler is a good one, but it needs to be an assembler for the actual target machine, otherwise you waste a lot of effort dealing with the impedance mismatch.
A portable way of determining how many bits are in an object is sizeof(object) * CHAR_BIT. No reason to use the 8 version.