Looking for gcc source code

[Paul]

No matter how much googling I do, I can't find the source code for the gcc function __builtin_popcount for any version of gcc. Could anyone help? Thanks a lot. The more recent the compiler, the better.

My aim is to compare times of various popcount algorithms. This raises another problem in that the times fluctuate wildly between runs.

I use this type of methodology below.

Thanks a lot,

Paul

// high_resolution_clock example
#include <iostream>
#include <ctime>
#include <ratio>
#include <chrono>

int main ()
{
using namespace std::chrono;

high_resolution_clock::time_point t1 = high_resolution_clock::now();

std::cout << "printing out 1000 stars...\n";
for (int i=0; i<1000; ++i) std::cout << "*";
std::cout << std::endl;

high_resolution_clock::time_point t2 = high_resolution_clock::now();

duration<double> time_span = duration_cast<duration<double>>(t2 - t1);

std::cout << "It took me " << time_span.count() << " seconds.";
std::cout << std::endl;

return 0;
}

Paul

[Alf P. Steinbach]

On 12.11.2018 11:39, Paul wrote:
> code for the gcc function __builtin_popcount

I just googled the quoted phrase, clicked on the most likely hit,
clicked on relevant link in that hit, and was dispatched to <url:
https://gcc.gnu.org/viewcvs/gcc/trunk/libgcc/libgcc2.c?view=markup&pathrev=200506>,
which appears to have the current source for some support code for the
intrinsic, though not that function itself.



Cheers!,

- Alf

[Paul]

Alf,
When I saw the first two lines of your posting, I was confidently
expecting a reprimand of the form "But it's the very first hit.
How come you can't use google etc?."
But at the end, you say that we don't have support code for "that function
itself" and yet, "that function itself" is what I wanted.

So I'm still stuck.

Paul

[Paul]

On Monday, November 12, 2018 at 12:38:48 PM UTC, Alf P. Steinbach wrote:

Oh, I get it now.
I think you mean to piece it together from the popcount-related code
in the link you gave.
It hardcodes the answers in a table for x between 0 and 255 and uses bitmasking combined with look up for each set of 16 bits.

Paul

[Juha Nieminen]

Paul <peps...@gmail.com> wrote:
> My aim is to compare times of various popcount algorithms.
> This raises another problem in that the times fluctuate wildly
> between runs.

This is not something that's trivial to measure, because it depends a
bit on what exactly you want to measure. For example, it's difficult
to measure exactly how fast it is to count the number of 1-bits in
a 32-bit unsigned integer (although if you can use inline asm,
many/most CPU architectures have a way to count the exact clock
cycle count, which would be the best possible way, but it's not
something trivial to implement).

On the other hand, if you want to measure how fast the algorithm
can count the number of 1-bits in a bitset of 10 billion bits,
that's much easier to measure, but that task is quite different
and tells little about how fast the algorithm is for that previous
case. (In this case you would be traversing a huge array, and thus
constantly running into cache misses, which slow down the process,
adding thus time overhead that's unrelated to the popcount algorithm
itself into the mix.)

However, if what you are doing is measuring if algorithm A is
faster than algorithm B, then you could do something more like
the second option. Have like an array of a million bits, and
calculate in a loop its number of 1-bits several times, so that
the total time spent is in the order of several seconds, and
then compare the times. (Make sure that the compiler isn't doing
some overly smart optimizations that bypass the subsequent loops
or something, or bypassing the whole thing because it sees that
the result isn't used for anything. One way to ensure this last
thing is to print the result, for example, even if you aren't
interested in what the actual value is.)

[David Brown]

Intrinsics and builtins don't really have a function definition as such.
Depending on the target, the optimisation, the target-specific options,
the surrounding code, etc., __builtin_popcount can generate a "popcount"
instruction, inline code, or a call to a support library function. What
you have found is the source for the support library, which is probably
as good as it gets - and it includes versions using lookup tables as
well as versions with calculations.