c++ - Fair timing of two equivalent functions with -O3 -
a coworker sent me interesting code calculates index of lsb of integer:
unsigned int v; // 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]; i curious see if beat (with equivalent function runs more quickly) , wrote code test it:
#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 strange thing //------------------------------------------------------------------------------------------------------------------- bool equivalent = true; (unsigned int = 0; < 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 faster strange thing //------------------------------------------------------------------------------------------------------------------- clock_t start; start = clock(); (unsigned int = 0; < num_iterations; ++i) alexidea(i); std::cout << std::setprecision(51) << "alex's idea time: " << (double(clock() - start) / clocks_per_sec) << std::endl; start = clock(); (unsigned int = 0; < num_iterations; ++i) strangething(i); std::cout << std::setprecision(51) << "strange thing's time: " << (double(clock() - start) / clocks_per_sec) << std::endl; return 0; } i had strange results, seemed strange function impossibly fast:
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 i tried adding conditional (that not true during run time) try force both calculated. timing section of main changed this:
//------------------------------------------------------------------------------------------------------------------- // see if alex's idea faster strange thing //------------------------------------------------------------------------------------------------------------------- clock_t start; start = clock(); (unsigned int = 0; < num_iterations; ++i) if (alexidea(i) == 31) // never happen, don't optimize out calculation std::cout << "this 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(); (unsigned int = 0; < num_iterations; ++i) if (strangething(i) == 31) // never happen, don't optimize out calculation std::cout << "this never happen" << std::endl; std::cout << std::fixed << std::setprecision(8) << "strange thing's time: " << (double(clock() - start) / clocks_per_sec) << std::endl; resulting in:
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 is second timing valid? there better way time functions?
create variable dummy , initialize argc. in each loop increment dummy return of function. return dummy. should stop compiler eliding function calls.
Comments
Post a Comment