为什么用std :: sort()对上升阵列(1〜100,000)排序比仅使用100,000次使用的速度要快

Question

我知道std::sort的性能很高，据我所知，它使用Introsort(quickSort insertionSort heapSort(，但是在我的测试中，我发现："对上升数组进行排序(1〜99999(使用std::sort()比仅使用100,000次使用的循环更快。尽管std::sort很快，但至少需要遍历整个数组。我认为这是不可能的(STD ::排序比仅适用于具有相同数量的循环和数组长度的循环(。我很困惑，谁能告诉我什么是原则。

很难仅在MacOS中理解，我还在Linux (Centos 7.6中对其进行了测试，并且结果是预期的。我想知道Mac和Xcode对此做了什么。

• 环境：

  1. MacBook Pro(Macos Mojave 10.14.6(，Xcode
  2. x86_64(centos7.6(，clang

• 测试代码：

  #include <iostream>
  #include <sys/time.h>
  #define LENGTH 100000
  int *  order_arr(int lo, int hi, int reverse) {
      int *arr=(int *)malloc(hi<<2);
      if (reverse==0) {
          for (int i = lo; i < hi; ++i) {
              arr[i]=i;
          }
      return arr;
      }else{
          for (int i = lo; i < hi; ++i) {
              arr[i]=hi-1-i;
          }
          return arr;
      }
  }
  int main(int argc, const char * argv[]) {
      // ---- Create an ascending array: 0~99999
      int * order_array = order_arr(0, LENGTH, 0);
      //------------------------------------------------------------------
      timeval starttime,endtime;
      gettimeofday(&starttime,0);
      //----------------------------------------------------------------------start_time
      // ---- STL sort
  //    std::sort(order_array, order_array+LENGTH);
      // ---- Only for loop 100000 times
  //    for (int i = 0; i < LENGTH; ++i) ;
      //----------------------------------------------------------------------end_time
      gettimeofday(&endtime,0);
      double timeuse = 1000000*(endtime.tv_sec - starttime.tv_sec) + endtime.tv_usec - starttime.tv_usec;
      std::cout<< (timeuse/=1000000) <<std::endl;
      return 0;
  }  
  

• 运行结果：

  1. macOS(xcode(：不合理，有无优化，std :: stort((对数组的排列，这次不应仅小于循环(没有优化0.000203 s(。

     • 优化：clang++ test.cpp -std=c++11 -o -O3 test

       1. for (int i=0; i<LENGTH; ++i) ;：0 S
       2. std::sort(order_array, order_array+LENGTH);：0.000118 S

     • 无优化：clang++ test.cpp -std=c++11 -o test

       1. for (int i=0; i<LENGTH; ++i) ;：0.000203 S
       2. std::sort(order_array, order_array+LENGTH);：0.000123 S

  2. centos7.6(g (：合理

     • 优化：clang++ test.cpp -std=c++11 -o -O3 test

       1. for (int i=0; i<LENGTH; ++i) ;：0 S
       2. std::sort(order_array, order_array+LENGTH);：0.001654 S

     • 无优化：clang++ test.cpp -std=c++11 -o -O3 test

       1. for (int i=0; i<LENGTH; ++i) ;：0.0002745 S
       2. std::sort(order_array, order_array+LENGTH);：0.002354 S

Answer 1

这是一个可能的解释：

您不使用排序阵列的内容。clang扩展了初始化和模板代码内联，可以确定您要丢弃数组，因此它甚至不会生成代码进行排序的代码，从而比不丢弃明确的空循环的替代方案更快。p>尝试使main()返回数组的第一个元素，以查看是否有所不同。

有了您更新的问题，似乎没有真正的问题：

• 优化构建的时间是一致的，没有时间在空循环中花费时间，并且花了很短的时间对已经排序的数组进行排序。
• 未优化构建的时间基本上是无关紧要的，因为模板代码的核心可能仍可以优化，而简单的循环被编译到幼稚的无效代码中。

您似乎对MACOS上已经分类的数组的std::sort()的性能感到惊讶。在已经排序的数组上，无论是增加还是减小顺序，分类都可能非常有效。初始扫描用于将数组分成大块。使用您的数据集，初始扫描很快就会产生一个单一的块，该块是按照或简单地反转的。

您可以尝试分析模板代码，这可以直接在Include Files或开源库中的两个平台上可用。