std::sort的流程分析

本文深入探索g++钦定的西半球最快的排序算法

背景

我也没想过要特意为std::sort写一篇文章，但是不写又太对不起我的工作量了，我真的看了一天

当然里面充满技巧性的实现确实值得一提（可以说是为了性能愿意变态到连可读性都不放过的那种）

分析过一遍可以明白什么样的代码实现才算是真正的性能优化

说明

下文中提到的STL都是指GNU ISO C++ Library（既libstdc++）下的具体实现

由于源文件就是tab+空格混用，因此可能排版不太好看（upd.是vscode乱改tab占位，有空换一下排版）

流程分析1-policy

STL的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是怎么实现的，我也没看懂（upd. 看懂了，留意返回值类型，是下取整）

  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

虽然解释都是一样的啦