measure time for popcount function in c++

Question

i am interested how to put it in loop so that get real time which is taken by cpu to execute each different operation

#include<iostream>
#include<cstdlib>
#include<time.h>

using namespace std;
typedef unsigned __int64 uint64;
const uint64 m1=0x5555555555555555;
const uint64 m2=0x3333333333333333;
const uint64 m4=0x0f0f0f0f0f0f0f0f;
const uint64 m8=0x00ff00ff00ff00ff;
const uint64 m16=0x0000ffff0000ffff;
const uint64 m32=0x00000000ffffffff;
const uint64 hff=0xffffffffffffffff;
const uint64 h01=0x0101010101010101;

uint64 popcount_1(uint64 x)
{
    x=(x&m1)+((x>>1)&m1);
    x=(x&m2)+((x>>2)&m2);
    x=(x&m4)+((x>>4)&m4);
    x=(x&m8)+((x>>8)&m8);
    x=(x&m16)+((x>>16)&m16);
    x=(x&m32)+((x>>32)&m32);
    return (uint64)x;
}

//This uses fewer arithmetic operations than any other known
//implementation on machines with slow multiplication.
//It uses 17 arithmetic operations.
int popcount_2(uint64 x)
{
    x-=(x>>1)&m1;//put count of each 2 bits into those 2 bits
    x=(x&m2)+((x>>2)&m2);//put count of each 4 bits into those 4 bits
    x=(x+(x>>4))&m4; //put count of each 8 bits into those 8 bits
    x+=x>>8;//put count of each 16 bits into their lowest 8 bits
    x+=x>>16;
    x+=x>>32;
    return x&0x7f;
}
////This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
int popcount_3(uint64 x)
{
    x-=(x>>1)&m1;
    x=(x&m2)+((x>>2)&m2);
    x=(x+(x>>4))&m4;
    return (x*h01)>>56;
}
uint64 popcount_4(uint64 x)
{
    uint64  count;
    for(count=0; x; count++)
    {
        x&=x-1;
    }
    return count;
}
uint64 random()
{
    uint64 r30=RAND_MAX*rand()+rand();
    uint64 s30=RAND_MAX*rand()+rand();
    uint64  t4=rand()&0xf;
    uint64 res=(r30<<34 )+(s30<<4)+t4;
    return res;
}
int main()
{
    int testnum;
    while (true)
    {
        cout<<"enter number of test "<<endl;
        cin>>testnum;
        uint64 x= random();
        switch(testnum)
        {
            case 1: {
                    clock_t start=clock();
                    popcount_1(x);
                    clock_t end=clock();
                    cout<<"execution time of first method"<<start-end<<" "<<endl;
                }
                break;
            case 2: {
                    clock_t start=clock();
                    popcount_2(x);
                    clock_t end=clock();
                    cout<<"execution time of first method"<<start-end<<" "<<endl;
                }
                break;
            case 3: {
                    clock_t start=clock();
                    popcount_3(x);
                    clock_t end=clock();
                    cout<<"execution time of first method"<<start-end<<" "<<endl;
                }
                break;
            case 4: {
                    clock_t start=clock();
                    popcount_4(x);
                    clock_t end=clock();
                    cout<<"execution time of first method"<<start-end<<" "<<endl;
                }
                break;
            default:
                cout<<"it is not correct number "<<endl;
                break;
        }
    }
    return 0;
}

it writes on terminal always zero inspite of which number test i enter,it is clear for me why because 10 or even 20 and 100 operation is not anything for modern computer,but how could i dot such that get if not exact answer,approximation at least?thanks a lot

Answer 1

Just repeat all the tests a large number of times.

The following repeats 1 Mio (1024*1024)2^25 times for each test. You might want to divide the times to get the time in nanoseconds, but for comparison the total numbers would be fine (and easier to read).

int main()
{
    int testnum;
    while (true)
    {
        cout<<"enter number of test "<<endl;
        cin>>testnum;
        uint64 x= random();

        clock_t start=clock();
        switch(testnum)
        {
            case 1: for(unsigned long it=0; it<=(1ul<<26); ++it) popcount_1(x); break;
            case 2: for(unsigned long it=0; it<=(1ul<<26); ++it) popcount_2(x); break;
            case 3: for(unsigned long it=0; it<=(1ul<<26); ++it) popcount_3(x); break;
            case 4: for(unsigned long it=0; it<=(1ul<<26); ++it) popcount_4(x); break;
            default:
                cout<<"it is not correct number "<<endl;
                break;
        }
        clock_t end=clock();
        cout<<"execution time of method " << testnum << ": " << (end-start) <<" "<<endl;
    }
    return 0;
}

Note also fixed start-end to (end-start) :)

Answer 2

You want to perform a microbenchmark of a very cheap operation. You need to:

• Make a loop around the cheap operations; one that takes long enough to time reasonably; e.g. around a second.
• Ensure that you use the result from one loop iteration in the next to avoid the compiler just omitting the body entirely.
• Wrap the entire loop in a function, mark the function as not-inlinable with a compiler-specific attribute (again, to ensure the compiler doesn't just omit the call) and call this function from your timing function. Alternatively, return a value depending on all loop iterations and actually use that return value (e.g. print it or store it in a volatile variable) in your main program to ensure the compiler can't just optimize the program and remove it.
• Additionally, you should use high-resolution timers and not clock(). On windows this would be QueryPerformanceCounter(&tick_count), on unix clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timespec_var), and on macos have a look at mach_absolute_time(). Another advantage of (some of) these methods is that they measure CPU time, not wall-clock time, and are thus slightly less variable in the face of other activity on the system.

Again, it's absolutely critical to make sure you actually use the values computed either by storing them in a volatile variable, printing them or by returning them from a non-inlined function to ensure the compiler can't just optimize them away. And you do not want to mark your core method non-inlinable, since function call overhead may well swamp such microbenchmarks; for similar reasons you should probably avoid random. This is why you should benchmark a function containing a loop calling the (inlinable) function you're actually interested in.

For example:

#include <iostream>
#include <time.h>
typedef unsigned __int64 uint64;

inline uint64 popcount_1(uint64 x)// etc...

template<typename TF>
uint64 bench_intfunc_helper(TF functor, size_t runs){//benchmark this
    uint64 retval = 0;
    for(size_t i=0; i<runs; ++i) retval += functor(i); 
    // note that i may not have a representative distribution like this
    return retval;//depends on all loop iterations!
}
template<typename TF>
double bench_intfunc(TF functor, size_t runs){
    clock_t start=clock();//hi-res timers would be better
    volatile auto force_evalution = bench_intfunc_helper(functor,runs);
    clock_t end=clock();
    return (end-start)/1000.0;
}
#define BENCH(f) do {std::cout<<"Elapsed time for "<< RUNS <<" runs of " #f \
    ": " << bench_intfunc([](uint64 x) {return f(x);},RUNS) <<"s\n"; } while(0)

int main() {
    BENCH(popcount_1);
    BENCH(popcount_2);
    BENCH(popcount_3);
    BENCH(popcount_4);
    return 0;
}

Simply omitting volatile, for example, causes GCC 4.6.3 and MSC 10.0 on my machine to report 0s spent. I'm using a lambda since function pointers aren't inlined by these compilers but lambda's are.

On my machine the output of this benchmark on GCC is:

Elapsed time for 1073741824 runs of popcount_1: 3.7s
Elapsed time for 1073741824 runs of popcount_2: 3.822s
Elapsed time for 1073741824 runs of popcount_3: 4.091s
Elapsed time for 1073741824 runs of popcount_4: 23.821s

and on MSC:

Elapsed time for 1073741824 runs of popcount_1: 7.508s
Elapsed time for 1073741824 runs of popcount_2: 5.864s
Elapsed time for 1073741824 runs of popcount_3: 3.705s
Elapsed time for 1073741824 runs of popcount_4: 19.353s