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

Question

我知道std::sort有很高的性能，据我所知它使用Introsort(quickSort+insertionSort+heapSort) ，但在我的测试中我发现："sorting an ascending array (1~99999) with std::sort() is faster than just using for loops 100,000 times"。 std::sort虽然快，但至少需要遍历整个数组。我认为这是不可能的（std::sort 比具有相同循环数和数组长度的循环更快）。很迷茫，谁能告诉我原理是什么

只在MacOS很难理解，我也在Linux (Centos 7.6)测试过，结果是expected.I想知道什么是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 s）。
  - 优化：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() return 作为数组的第一个元素，看看它是否有所作为。

根据你更新的问题，似乎没有真正的问题：

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

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

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

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

Why sorting an ascending array (1~100,000) with std::sort() is faster than just using for loop 100,000 times

c++

sorting

c++11

stl

arr