измерить время для функции popcount в c ++ - PullRequest
Новая
       15

измерить время для функции popcount в c ++

0 голосов
/ 14 ноября 2011

Меня интересует, как поставить его в цикл, чтобы получить реальное время, затрачиваемое процессором для выполнения каждой отдельной операции. 

#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;
}

пишет на терминале всегда ноль, независимо от того, какой тест числа я ввожудля меня понятно почему, потому что операции 10 или даже 20 и 100 не являются чем-то для современного компьютера, но как я могу расставить точки так, чтобы получить, если не точный ответ, приближение хотя бы? большое спасибо

Ответы [ 2 ]

5 голосов
/ 14 ноября 2011

Просто повторите все тесты большое количество раз.

Следующее повторяется 1 Mio (1024 * 1024) 2 ^ 25 раз для каждого теста.Возможно, вы захотите разделить время, чтобы получить время в наносекундах, но для сравнения общее число будет в порядке (и его легче читать). 

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;
}

Примечание также исправлено start-end до (end-start):)

3 голосов
/ 14 ноября 2011

Вы хотите выполнить микробенчмарк очень дешевой операции. Вам необходимо:

  • Сделайте петлю вокруг дешевых операций; тот, который занимает достаточно много времени, чтобы разумно; например около секунды.
  • Убедитесь, что вы используете результат одной итерации цикла в следующей , чтобы компилятор не пропускал полностью тело.
  • Обернуть весь цикл в функции, пометить функцию как неотключаемую атрибутом, специфичным для компилятора (опять же, чтобы компилятор не просто пропустил вызов), и вызвать эта функция от вашей функции синхронизации. В качестве альтернативы , верните значение в зависимости от всех итераций цикла и фактически используйте это возвращаемое значение (например, напечатайте его или сохраните в переменной volatile) в вашей основной программе, чтобы обеспечить компилятор не могу просто оптимизировать программу и удалить ее.
  • Кроме того, вы должны использовать таймеры высокого разрешения , а не clock(). В Windows это будет QueryPerformanceCounter(&tick_count), в Unix clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timespec_var), а в Macos посмотрите mach_absolute_time(). Другое преимущество (некоторых из) этих методов состоит в том, что они измеряют время процессора, а не время настенных часов, и, таким образом, немного менее изменчивы перед лицом других действий в системе.

Опять же, абсолютно важно , чтобы убедиться, что вы на самом деле используете значения, вычисленные либо путем сохранения их в переменной volatile, их печати или возврата из не встроенная функция, чтобы компилятор не мог просто оптимизировать их. И вы не хотите пометить ваш основной метод как не встраиваемый, так как накладные расходы на вызов функции вполне могут затопить такие микробенчмарки; по тем же причинам вам следует избегать random. Вот почему вы должны тестировать функцию, содержащую цикл, вызывающий (встроенную) функцию, которая вас действительно интересует.

Например: 

#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;
}

Например, простое пропускание volatile приводит к тому, что GCC 4.6.3 и MSC 10.0 на моем компьютере сообщают о потраченных 0с. Я использую лямбду, так как указатели на функции не указываются этими компиляторами, а лямбда -.

На моей машине вывод этого теста на GCC: 

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

и на 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
...