摘要
本文深入探索 GCC 钦定的西半球最快的排序算法。
说明
下文中提到的 STL 都是指 libstdc++ 的具体实现。
流程分析 1-policy
STL 的 sort 实现是使用一种内省式排序（introspective sort）的算法，也就是大范围（使用快排 + 递归过深使用堆排）+ 最终使用完整的插入排序来完成：
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
// 实际调用
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
}
template<typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2, // ##flag #2
__comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}
流程分析 2-插入排序
出于可读性的考虑，首先看 __final_insertion_sort：
/**
* @doctodo
* This controls some aspect of the sort routines.
*/
enum { _S_threshold = 16 };
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
if (__last - __first > int(_S_threshold))
{
std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
__comp); // ##flag #1
}
else
std::__insertion_sort(__first, __last, __comp);
}
STL 实现的插入排序是带有优化的，它把区间分为两部分：
- 第一部分
[first, first + _S_threshold)，进行完整的插入排序（里面的技巧后面会提）。 - 第二部分
[first + _S_threshold, last)，进行不含边界检查的插入排序。
下面展式这两种插入排序的微妙区别。
完整的插入排序：
template<typename _RandomAccessIterator, typename _Compare>
void
__insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
if (__first == __last) return;
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
if (__comp(__i, __first)) // ##flag #0
{
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);
}
else
std::__unguarded_linear_insert(__i,
__gnu_cxx::__ops::__val_comp_iter(__comp));
}
}
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void
__unguarded_linear_insert(_RandomAccessIterator __last,
_Compare __comp)
{
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__last);
_RandomAccessIterator __next = __last;
--__next; // 前一个迭代器
while (__comp(__val, __next))
{
*__last = _GLIBCXX_MOVE(*__next);
__last = __next;
--__next;
}
*__last = _GLIBCXX_MOVE(__val);
}
unguarded 的插入排序：
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i,
__gnu_cxx::__ops::__val_comp_iter(__comp));
} // 同样用到__unguarded_linear_insert
__insertion_sort 相对于常见的实现，只多了一步 ##flag #0 处的预先判断 *i < *first。
常规的实现是从 i 一直往前直到 first 逐个判断是否需要 swap 来实现插入，但是 STL 这里的预判如果为 true，则直接可以移动整个 [first, i] 区间往后偏移一位，减少 i-first+1 次判断。
如果为 false 就是常规的线性遍历 __unguarded_linear_insert，这里虽然保证了 *first < *i，但是 [first+1, i) 与 i 是否有序还是需要接着判断的，之所以使用 unguarded 是因为 first 必然是 [first, i) 区间最小的值，while (__comp(__val, __next)) 必不满足，因此不需要每次确认 __last != __first，同样是减少了 i-first+1 次判断成本，另外，__val 是固定不变的，而不是每次都取迭代器上的值，可以说是连一点访问成本都抠下来了。
问题出现在 __unguarded_insertion_sort，内部是直接从 first 到 last（的开区间）都调用 __unguarded_linear_insert，从前面的分析可以看出，使用 __unguarded_linear_insert 要求在 first 前面（不包含 first）要有一个比 [first,last) 都小的值才能保证安全（因为它根本没有边界保护），回到 __final_insertion_sort 的 ##flag #1 处，也就是要求 [__first, __first + _S_threshold) 中必然存在整个区间 [first, last) 的最小值，我们必须回去分析 __introsort_loop 的流程来获得答案。
流程分析 3-轴点划分
__introsort_loop 的流程如下：
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
（所以说每个函数都标注 This is a helper function 有啥意义，又没说是干嘛的）
首先分析 __depth_limit，这是一个限制递归深度的参数，由于快排存在间歇性拉垮的性能表现，有必要在超过一定阈值限制后把它转为另一种排序算法来避免最坏情况。
在 __sort 的 ##flag #2 可以看到它的玄学参数为 std::__lg(__last - __first) * 2，从结论上来说，就是限制快排的递归深度为 \(2 \cdot log_2(last - first)\)。
别问 std::__lg 是怎么实现的，我也没看懂。（update: 看懂了，留意返回值类型，是下取整）
inline _GLIBCXX_CONSTEXPR unsigned long long
__lg(unsigned long long __n)
{ return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
接着了解 __unguarded_partition_pivot，从上面的代码形式和命名就可以得知是一个返回轴点的划分算法：
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
__comp);
return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}
它的划分值挑选挺简单粗暴的，就是挑选 first+1, mid, last-1 三个数的中值，然后 std::swap 到 first 位置上去，所以说关键就是最后一行的 __unguarded_partition：
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_RandomAccessIterator __pivot, _Compare __comp)
{
while (true)
{
while (__comp(__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, __last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
整个流程是非常标准的，把大于等于 piviot 的 first 和小于等于 pivot 的 last 进行交换并逼近中间，直到两个迭代器交错或相等，从结果上来说，就是保证 [first, return_iter) 的任意迭代器 iter 都满足 *iter<=*pivot，这里返回的位置 return_iter 并不严格等于 *__pivot，因为这样可以减少一次 std::swap(*__pivot, *__first) 的成本。
流程分析 4-堆排序
当 __depth_limit == 0 时，__introsort_loop 调用 __partial_sort，这个过程实际就是堆排序：
template<typename _RandomAccessIterator, typename _Compare>
inline void
__partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last,
_Compare __comp)
{
std::__heap_select(__first, __middle, __last, __comp);
std::__sort_heap(__first, __middle, __comp);
}
这一部分并不打算接着分析下去。
流程分析 5-内省式排序
再次贴上内省式排序的框架：
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut; // ##flag #4
}
}
我们已经分析了上述所有细节，重新来看整体的流程：
__introsort_loop只处理区间大小大于_S_threshold的子区间，否则直接忽略，因此它不具有完整排序的功能。- 只要到达
__depth_limit下限，将会强行使用堆排来结束流程，此时排序的区间是确保有序的。 __introsort_loop使用##flag #4处的__last = __cut来替代掉尾递归__introsort_loop(__first, __cut, __depth_limit, __comp)，可能对不聪明的编译器有优化效果。
那么重新回到 __unguarded_insertion_sort 的问题。
在 __sort 的流程中，__introsort_loop 完成后接着就是 __final_insertion_sort，先是对前 _S_threshold 个元素进行完整的插入排序，剩下的绝大部分是不受保护的 __unguarded_insertion_sort，这里要求 [__first, __first + _S_threshold) 满足一个隐含的要求：[__first, __last) 的最小值必须落在里面。
那么 __introsort_loop 是怎么做到的？似乎我前面的分析完全没有提及这个问题，确实需要推理，而不是流程上的讲解。
在调用 __unguarded_insertion_sort 之前，区间的情况有多种可能：
- 整个区间不足
_S_threshold的大小，直接跳过了introsort - 进行了
introsort，但是没有达到depth_limit下限就结束了 - 进行了
introsort，到达depth_limit下限强制结束了
在这里我们考虑 [first, last) 区间的最左端，因为 introsort 肯定会划分出一个最左边的轴点 pivot（或者叫 cut），那么这个范围就是 [first, pivot)。
对于情况一，不足大小限制，在插入排序流程中并不会进行 __unguarded_insertion_sort，而是完整的插入排序流程，因此是安全的。
对于情况二，没有到达下限就结束，意味着 pivot 落在 (first, first + _S_threshold]，由划分算法的性质可知，[first, pivot) 肯定小于等于 (pivot, last)，间接实现了最小值落在 [__first, __first + _S_threshold) 区间的需求。
对于情况三，能进入该分支意味着 pivot 在 depth_limit 次机会中都没有落到 (first, first + _S_threshold] 里面，因此切换为堆排，按照堆排的特性，最左端的区间的最小值必然落在 first 这个位置，而这个最左端区间是划分算法得来的，因此最左端肯定是整个 [first, last) 区间的最小值。
也就是说，introsort 是隐式地维护了这一条性质：最小值必然落在 [__first, __first + _S_threshold) 区间，从而保证后面的 __unguarded_insertion_sort 流程是安全的。
THE END
完整的分析可以见我的 github： Caturra000/RTFSC。
虽然解释都是一样的啦。