通用可重复值的排序数组的二分法检索

爻易

实测O3优化下，楼主的代码(test1)最慢，STL(test2)快一点，C新写函数（test3）更快，手写的内嵌汇编(test4)则是最快
#c++ -std=c++11 test.cpp -O3
#./a.out
Test1 result: 8001 Duration: 8333434
Test2 result: 8001 Duration: 5173997
Test3 result: 8001 Duration: 4464493
Test4 result: 8001 Duration: 4057710

yulihua49

爻易 发表于 2016-11-08 15:23
实测O3优化下，楼主的代码(test1)最慢，STL(test2)快一点，C新写函数（test3）更快，手写的内嵌汇编(test4) ...

有心人，赞一个。不管怎么说，通用的C库函数是最慢的，因为编译器无法优化它。内存访问的聚集性也不行。在比较函数里访问用户数据，在函数调用过程中清除了cache，造成访问效率低。
你的test1也是有inline优化的。如果把函数入库，那么比较函数彻底不能inline了，速度还要慢。

爻易

回复 62# yulihua49

静态库安全独立性好，动态库尺寸小，要想速度快，汇编丢不了

lxyscls

回复 24# windoze

int main() {
        generate_test_data();
        // Warm up
        for(size_t i=0; i<100; i++) {
                test1();
                test2();
        }
        std::cout << "Test1 ";
        time_it(100000, test1);
        std::cout << "Test2 ";
        time_it(100000, test2);
}

猫哥，我弱问一句，这里的warm up有啥用？还是写Java写习惯了顺手就写下了

windoze

回复 65# lxyscls


做benchmark的惯例，先把会碰到的内存反复刷几遍，防止它们被交换出去，同时也尽量让cache都准备好。
这样可以减少测试时环境的干扰。