c++ - 为什么使用 std::sort() 对升序数组(1~100,000)进行排序比仅使用 for 循环 100,000 次要快

Question

我知道std::sort具有非常高的性能，据我所知它使用Introsort ( quickSort + insertionSort + heapSort )，但在我的测试中我发现:“使用 std::sort() 对升序数组(1~99999)进行排序比仅使用 for 循环 100,000 次要快”。虽然std::sort速度还是很快的，至少需要遍历整个数组。我认为这是不可能的( std::sort 比具有相同循环数和数组长度的循环更快)。我很困惑，谁能告诉我原理是什么。

仅在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::sort()对数组进行排序，这个时间不应该小于仅for循环(没有优化0.000203秒)。

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

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

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

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

  2. Centos7.6(g++):合理

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

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

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

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

Answer 1

这是一个可能的解释:

您不使用已排序数组的内容。 clang 内联扩展了初始化和模板代码，并且可以确定您正在丢弃该数组，因此它甚至不会生成对其进行排序的代码，从而比不丢弃显式空循环的替代方案花费更快的时间。

尝试让 main() 返回数组的第一个元素，看看是否有区别。

根据您更新的问题，似乎没有真正的问题:

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

您似乎对 MacOS 上已排序数组上 std::sort() 的性能感到惊讶。在已经排序的数组上排序可能非常有效，无论是按升序还是降序。初始扫描用于将数组分割成 block 。对于您的数据集，初始扫描很快会生成一个按原样保留或简单反转的 block 。

您可以尝试分析模板代码，该代码在两个平台上都可以直接在包含文件中或在开源库中使用。