为什么这三个排序函数有不同的运行时间？

我实现了Insertion以3种不同的方式在C++中排序。一个使用基本的C数组，一个使用载体，和一种使用迭代：为什么这三个排序函数有不同的运行时间？

void insertionsort_array(int *arr, size_t length) 
{ 
    for (int i = 1; i < length; i++) 
     for (int k = i; k > 0 && arr[k] < arr[k-1]; k--) 
      swap(arr[k], arr[k-1]); 
} 

template<typename T> 
void insertionsort_vector(vector<T>& arr) 
{ 
    for (int i = 1; i < arr.size(); i++) 
     for (int k = i; k > 0 && arr[k] < arr[k-1]; k--) 
      swap(arr[k], arr[k-1]); 
} 

template<class IterType> 
void insertionsort_iterator(IterType iter, IterType end) 
{ 
    for (IterType edge = iter + 1; edge != end; ++edge) 
     for (IterType ptr = edge; ptr != iter && *ptr < *(ptr-1); --ptr) 
      swap(*ptr, *(ptr-1)); 
}

我期望运行时间用于这些功能的一些常数不同。然而，这是不是这种情况（使用GCC -O0计时）：

// array 
Sorting 1000000 lists of length 10: 2605531 usec 
Sorting 50000 lists of length 100: 1268442 usec 
Sorting  500 lists of length 1000: 787731 usec 
Sorting  5 lists of length 10000: 759133 usec 

// vector 
Sorting 1000000 lists of length 10: 2888354 usec 
Sorting 50000 lists of length 100: 2031675 usec 
Sorting  500 lists of length 1000: 1604312 usec 
Sorting  5 lists of length 10000: 1603279 usec 

// iterator 
Sorting 1000000 lists of length 10: 3003877 usec 
Sorting 50000 lists of length 100: 4150561 usec 
Sorting  500 lists of length 1000: 3829943 usec 
Sorting  5 lists of length 10000: 3766683 usec

对于长度为10的名单，他们都有着相同的性能，但对于长度为10的阵列，迭代器是比C更糟糕的近五倍阵列。怎么会这样？

编辑：我重新测试它使用-O3和效果似乎消失。很高兴知道我可以使用编译器优化来避免这个问题，但我仍然想要了解这种在-O0发生的奇怪行为。

// array 
Sorting 1000000 lists of length 10: 802136 usec 
Sorting 50000 lists of length 100: 300472 usec 
Sorting  500 lists of length 1000: 185330 usec 
Sorting  5 lists of length 10000: 179851 usec 

// vector 
Sorting 1000000 lists of length 10: 955003 usec 
Sorting 50000 lists of length 100: 302232 usec 
Sorting  500 lists of length 1000: 185034 usec 
Sorting  5 lists of length 10000: 181459 usec 


// iterator 
Sorting 1000000 lists of length 10: 811077 usec 
Sorting 50000 lists of length 100: 230852 usec 
Sorting  500 lists of length 1000: 112885 usec 
Sorting  5 lists of length 10000: 105739 usec

我在GCC中编译了-O0或-O3，并且没有使用其他编译器标志。

来源

2013-05-01 Michael Dickens

发布您的基准测试代码。并且告诉我们，是Debug还是Release版本？或者，在GCC中，您是否使用了诸如“-O4”之类的优化标志？ – Nawaz 2013-05-01 05:10:48

优化开启了吗？ – 2013-05-01 05:11:36

你没有打开优化，所以第一组基准是没有意义的。第二组基准对我来说似乎很正常。 – Mysticial 2013-05-01 05:32:32

没有优化，最大的差异可能来自调用函数如operator[]。当调用函数there is a lot that happens会导致开销，并且在循环调用时特别显着。但是，打开优化后，所有这些函数调用都是inlined，这就是您看到差异消失的原因。请注意，无论您使用std::vector还是普通数组，现在的任何编译器都应该能够提供几乎相同的性能。

来源

2013-05-01 05:40:27

为什么这三个排序函数有不同的运行时间？

回答

相关问题