ярмарка время двух эквивалентных функций с -O3

Question

Коллега прислал мне какой-нибудь интересный код в исчисляет индекс LSB целого числа:

unsigned int v; // the input number 
int r;   // result goes here 
static const int MultiplyDeBruijnBitPosition[32] = 
{ 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27]; 

мне было интересно посмотреть, смогу ли я победить его (с эквивалентная функция, которая, надеюсь, работает более быстро), и изначально я писал этот код, чтобы проверить:

#include <ctime> 
#include <iomanip> 
#include <iostream> 

//----------------------------------------------------------------------------------------------------------------------- 
unsigned int alexIdea(unsigned int i) 
{ 
    switch (i & -i) 
    { 
    case 0x0u: 
    case 0x1u: 
     return 0; 
    case 0x2u: 
     return 1; 
    case 0x4u: 
     return 2; 
    case 0x8u: 
     return 3; 
    case 0x10u: 
     return 4; 
    case 0x20u: 
     return 5; 
    case 0x40u: 
     return 6; 
    case 0x80u: 
     return 7; 
    case 0x100u: 
     return 8; 
    case 0x200u: 
     return 9; 
    case 0x400u: 
     return 10; 
    case 0x800u: 
     return 11; 
    case 0x1000u: 
     return 12; 
    case 0x2000u: 
     return 13; 
    case 0x4000u: 
     return 14; 
    case 0x8000u: 
     return 15; 
    case 0x10000u: 
     return 16; 
    case 0x20000u: 
     return 17; 
    case 0x40000u: 
     return 18; 
    case 0x80000u: 
     return 19; 
    case 0x100000u: 
     return 20; 
    case 0x200000u: 
     return 21; 
    case 0x400000u: 
     return 22; 
    case 0x800000u: 
     return 23; 
    case 0x1000000u: 
     return 24; 
    case 0x2000000u: 
     return 25; 
    case 0x4000000u: 
     return 26; 
    case 0x8000000u: 
     return 27; 
    case 0x10000000u: 
     return 28; 
    case 0x20000000u: 
     return 29; 
    case 0x40000000u: 
     return 30; 
    case 0x80000000u: 
     return 31; 
    } 

    return 0; 
} 

//----------------------------------------------------------------------------------------------------------------------- 
const int multiplyDeBruijnBitPosition[32] = { 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 

unsigned int strangeThing(unsigned int i) 
{ 
    return multiplyDeBruijnBitPosition[((unsigned int)((i & -i) * 0x077cb531u)) >> 27]; 
} 

//----------------------------------------------------------------------------------------------------------------------- 
int main() 
{ 
    const unsigned int NUM_ITERATIONS = 1000000000; 

    //------------------------------------------------------------------------------------------------------------------- 
    // Compare Alex's idea to the strange thing 
    //------------------------------------------------------------------------------------------------------------------- 
    bool equivalent = true; 
    for (unsigned int i = 0; i < NUM_ITERATIONS; ++i) 
     if (alexIdea(i) != strangeThing(i)) { 
      equivalent = false; 
      break; 
     } 
    std::cout << (equivalent ? "Equivalent functions" : "Alex screwed up") << std::endl; 


    //------------------------------------------------------------------------------------------------------------------- 
    // See if Alex's idea is faster than the strange thing 
    //------------------------------------------------------------------------------------------------------------------- 
    clock_t start; 

    start = clock(); 
    for (unsigned int i = 0; i < NUM_ITERATIONS; ++i) 
     alexIdea(i); 
    std::cout << std::setprecision(51) << "Alex's idea time:  " << (double(clock() - start)/CLOCKS_PER_SEC) << std::endl; 

    start = clock(); 
    for (unsigned int i = 0; i < NUM_ITERATIONS; ++i) 
     strangeThing(i); 
    std::cout << std::setprecision(51) << "Strange thing's time: " << (double(clock() - start)/CLOCKS_PER_SEC) << std::endl; 

    return 0; 
} 

у меня были некоторые странные результаты, казалось, что странная функция была невероятно быстро:

Alexanders-MBP:Desktop alexandersimes$ !g 
g++ foo.cpp -O3 
Alexanders-MBP:Desktop alexandersimes$ ./a.out 
Equivalent functions 
Alex's idea time:  9.99999999999999954748111825886258685613938723690808e-07 
Strange thing's time: 0 
Alexanders-MBP:Desktop alexandersimes$ ./a.out 
Equivalent functions 
Alex's idea time:  1.99999999999999990949622365177251737122787744738162e-06 
Strange thing's time: 9.99999999999999954748111825886258685613938723690808e-07 
Alexanders-MBP:Desktop alexandersimes$ ./a.out 
Equivalent functions 
Alex's idea time:  3.00000000000000007600257229123386082392244134098291e-06 
Strange thing's time: 9.99999999999999954748111825886258685613938723690808e-07 

Я попытался добавить условие (которое не будет истинным во время выполнения), чтобы попытаться заставить оба они были рассчитаны. Раздел сроков основных изменен следующим образом:

//------------------------------------------------------------------------------------------------------------------- 
// See if Alex's idea is faster than the strange thing 
//------------------------------------------------------------------------------------------------------------------- 
clock_t start; 

start = clock(); 
for (unsigned int i = 0; i < NUM_ITERATIONS; ++i) 
    if (alexIdea(i) == 31) // This will never happen, but don't optimize out the calculation 
     std::cout << "This will never happen" << std::endl; 
std::cout << std::fixed << std::setprecision(8) 
      << "Alex's idea time:  " << (double(clock() - start)/CLOCKS_PER_SEC) << std::endl; 

start = clock(); 
for (unsigned int i = 0; i < NUM_ITERATIONS; ++i) 
    if (strangeThing(i) == 31) // This will never happen, but don't optimize out the calculation 
     std::cout << "This will never happen" << std::endl; 
std::cout << std::fixed << std::setprecision(8) 
      << "Strange thing's time: " << (double(clock() - start)/CLOCKS_PER_SEC) << std::endl; 

Результирующее в:

Alexanders-MBP:Desktop alexandersimes$ ./a.out 
Equivalent functions 
Alex's idea time:  0.00000200 
Strange thing's time: 1.53144700 
Alexanders-MBP:Desktop alexandersimes$ ./a.out 
Equivalent functions 
Alex's idea time:  0.00000300 
Strange thing's time: 1.44950600 
Alexanders-MBP:Desktop alexandersimes$ ./a.out 
Equivalent functions 
Alex's idea time:  0.00000200 
Strange thing's time: 1.57773800 

ли второе время действительны? Есть ли лучший способ своевременно выполнять функции?

Answer 1

Создайте переменную dummy и инициализируйте ее до argc. Затем в каждом приращении цикла dummy по возврату функции. Затем верните dummy. Это должно остановить компилятор от вызова функций.