A C++ implementation of timsort

I've implemented a verification patch on top of this pull request: 0001-Verify-is_sorted-audit-off-by-default.patch.txt. But I am not sure it is worth commiting. If it is, please let me know whether to push a second commit into this pull request or create a separate future pull request.

Hi, I seem to be having an issue with pairs. I start with a vector with 4 elements (1,a) (3,c) (4,d) (2,b) But then when I try to sort them I get 'd' being repeated and 'b' is gone (1,a) (2,d) (3,c) (4,d) This doesn't happen when the second value in the pair is a string (I want a string&). Here is the code I use

int main() {
  typedef std::pair<int, std::string&> KV;
  std::vector<KV> keys;
  keys.reserve(8);
  std::vector<std::string> vals;
  vals.reserve(8);
  vals.push_back("a");
  keys.push_back(static_cast<KV>(KV(1, vals.back())));
  vals.push_back("c");
  keys.push_back(static_cast<KV>(KV(3, vals.back())));
  vals.push_back("d");
  keys.push_back(static_cast<KV>(KV(4, vals.back())));
  vals.push_back("b");
  keys.push_back(static_cast<KV>(KV(2, vals.back())));
  std::cout << std::endl;
  for (auto s : keys) {
    std::cout << "(" << s.first << "," << s.second << ") ";
  }
  std::cout << std::endl;
  timsort(keys.begin(),
                 keys.end(),
                 [](const KV& a, const KV& b) {
                   return a.first < b.first;
                 });
  for (auto s : keys) {
    std::cout << "(" << s.first << "," << s.second << ") ";
  }
  std::cout << std::endl;
  return 0;
}

Because I am not using C++ in production anymore, I'd like to transfer this project to another organization with new maintainers.

However, there're security incidents these days in which attackers inject malware to modules by new maintainers:

• https://blog.npmjs.org/post/180565383195/details-about-the-event-stream-incident

So I'd like to review the org to be transferred carefully, so please tell me the details.

Background:

Like any well-behaved C++ template algorithm, gfx::timsort takes a comparison functor in the form of std::less(a, b) -- i.e. take two objects and return a bool indicating if a<b

For most of the algorithm this works well, the exception being gallopLeft() with its calls to gt()/le() These have to be implemented by two calls to the comparison functor. For a simple value type like int the compiler will easily optimize this into a single branch. However for something more complicated (and more expensive to compare!) like std::string this can end up doing two comparisons of the same elements.

For algorithms like this a qsort()-like comparison functor (i.e. strcmp()/memcmp()/std::string::compare()/etc) is actually more efficient since it gives you more than a simple bool result. Since the comparison functor gives you more information you can call it fewer times.

Proposal:

It's good that the standard interface of gfx::timsort matches std::stable_sort and takes a std::less-based function. However, since your code already abstracts these comparisons via the template <typename Value, typename LessFunction> class Compare helper class, why not provide an alternate function that takes a qsort-like functor instead? Just as a proof of concept I tried this:

diff --git a/timsort.hpp b/timsort.hpp
index 77dd7a2..e6230c0 100644
--- a/timsort.hpp
+++ b/timsort.hpp
@@ -126,12 +126,46 @@ template <typename Value, typename LessFunction> class Compare {
     func_type less_;
 };

-template <typename RandomAccessIterator, typename LessFunction> class TimSort {
+template <typename Value, typename TristateFunction> class CompareFromTristate {
+  public:
+    typedef Value value_type;
+    typedef TristateFunction func_type;
+
+    CompareFromTristate(TristateFunction f) : tristate_(f) {
+    }
+    CompareFromTristate(const CompareFromTristate<value_type, func_type> &other) : tristate_(other.tristate_) {
+    }
+
+    bool lt(value_type x, value_type y) {
+        return tristate_(x, y) < 0;
+    }
+    bool le(value_type x, value_type y) {
+        return tristate_(x, y) <= 0;
+    }
+    bool gt(value_type x, value_type y) {
+        return tristate_(x, y) > 0;
+    }
+    bool ge(value_type x, value_type y) {
+        return tristate_(x, y) >= 0;
+    }
+
+    // Allow this to be passed to APIs like std::lower_bound
+    CompareFromTristate &less_function() {
+        return *this;
+    }
+    bool operator()(value_type x, value_type y) {
+        return lt(x, y);
+    }
+
+  private:
+    func_type tristate_;
+};
+
+template <typename RandomAccessIterator, typename compare_t> class TimSort {
     typedef RandomAccessIterator iter_t;
     typedef typename std::iterator_traits<iter_t>::value_type value_t;
     typedef typename std::iterator_traits<iter_t>::reference ref_t;
     typedef typename std::iterator_traits<iter_t>::difference_type diff_t;
-    typedef Compare<const value_t &, LessFunction> compare_t;

     static const int MIN_MERGE = 32;

@@ -245,7 +279,7 @@ template <typename RandomAccessIterator, typename LessFunction> class TimSort {
         return n + r;
     }

-    TimSort(compare_t c) : comp_(c), minGallop_(MIN_GALLOP) {
+    TimSort(const compare_t& c) : comp_(c), minGallop_(MIN_GALLOP) {
     }

     void pushRun(iter_t const runBase, diff_t const runLen) {
@@ -661,6 +695,7 @@ template <typename RandomAccessIterator, typename LessFunction> class TimSort {

     // the only interface is the friend timsort() function
     template <typename IterT, typename LessT> friend void timsort(IterT first, IterT last, LessT c);
+    template <typename IterT, typename TristateT> friend void timsort_tristate(IterT first, IterT last, TristateT c);
 };

 template <typename RandomAccessIterator>
@@ -671,7 +706,18 @@ inline void timsort(RandomAccessIterator const first, RandomAccessIterator const

 template <typename RandomAccessIterator, typename LessFunction>
 inline void timsort(RandomAccessIterator const first, RandomAccessIterator const last, LessFunction compare) {
-    TimSort<RandomAccessIterator, LessFunction>::sort(first, last, compare);
+    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
+    typedef typename gfx::Compare<const value_type &, LessFunction> compare_type;
+    compare_type const compare_from_less(compare);
+    TimSort<RandomAccessIterator, compare_type>::sort(first, last, compare_from_less);
+}
+
+template <typename RandomAccessIterator, typename TristateFunction>
+inline void timsort_tristate(RandomAccessIterator const first, RandomAccessIterator const last, TristateFunction compare_tristate) {
+    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
+    typedef typename gfx::CompareFromTristate<const value_type &, TristateFunction> compare_type;
+    compare_type const compare_from_tristate(compare_tristate);
+    TimSort<RandomAccessIterator, compare_type>::sort(first, last, compare_from_tristate);
 }

 } // namespace gfx

On a quick test of 10^7 integers from rand() (so lots of duplicates but no sorted runs in the input) this caused about a 1.1% drop in the number of comparisons needed... so for an "expensive to compare, cheap to move" data type you might get a ~1% improvement in overall sort speed (although I didn't do extensive benchmarking of this). Not a huge improvement, but it's something.

I am still using your timsort implementation in a project, but recently noticed that Valgrind sometimes complained when trying to sort an std::deque with timsort. Here is my reduced test case:

std::deque<double> collection(35);
std::iota(std::begin(collection), std::end(collection), -47.0);
std::mt19937 engine(std::time(nullptr));
std::shuffle(std::begin(collection), std::end(collection), engine);

gfx::timsort(std::begin(collection), std::end(collection));
assert(std::is_sorted(std::begin(collection), std::end(collection)));

The actual test case is slightly more complicated than that since I am using Catch, but nothing really different. Unfortunately, Valgrind's error is way too big for me to include it here, but you can find the full error log here. Now, note that it is a log obtained with the test compiled by g++ in release mode, so it lacks some information about where exactly the error happens.

I will try to find a sequence of numbers that makes Valgrind report errors for sure, and edit this issue when I have one. Currently I don't really have many ideas about what can cause the error. I got similar errors when trying to sort an std::deque with another sorting algorithm: apparently, std::deque is less cool than std::vector when it comes to accessing out-of-bound iterators (not even dereferencing them), so that might be the culprit.

Update: some things in the original testcase such as the shuffling or the fact that I used double were a bit dumb/unneeded. I managed to find a sequence of integers that always triggers the Valgrind errors and cleaned the minimal testcase a bit:

std::deque<int> collection = {
    15, 7, 16, 20, 25, 28, 13, 27, 34, 24, 19, 1,
    6, 30, 32, 29, 10, 9, 3, 31, 21, 26, 8, 2, 22,
    14, 4, 12, 5, 0, 23, 33, 11, 17, 18
};

gfx::timsort(std::begin(collection), std::end(collection));
assert(std::is_sorted(std::begin(collection), std::end(collection)));

Now that we have an initial sequence that always triggers the Valgrind error, here are the corresponding error logs for the program compiler in debug mode with clang++ and g++. Most of them seem to come from mergeHi but I also remember having seen errors coming from mergeAt and gallopRight in older logs.

As discussed in issue #24, the implemetnations of Compare::le() and Compare::gt() were more expensive than they needed to be. As long as LessFunction provides the strict weak ordering that std::sort() requires, we can safely synthesize all four lt/gt/le/gt options with a single call.

While the simple fix would be to just change their definitions, I went a bit further and removed the Compare class entirely. I don't really think that it provides much, but it does take space in the TimSort object whether it's needed or not -- this could be addressed by some application of the Empty Base Class optimization, but it's a bit awkward)

I think it was probably done with the intention that having the comparator as a member of this for the core algorithm would be better because it would cut down on the number of function parameters. However, the normal way that the STL's sorting algorithms are implemented is to just pass the comparator down as a parameter to the functions so that the optimizer can just remove it when it's a pure functor. I think if anything forcing it to be an instance member makes this harder.

I looked at some other tricks to add some syntactic sugar to keep the gt()/lt()/le()/ge() function names (either with some namespaced inline functions or even just with macros) but it just seemed ugly. So instead I just replaced all of the comaprisons with direct calls to the comparator functor.

In C++11, std::sort is supposed to be able to sort collections of mve-only types. This patch adds support for move-only types to timsort. Here is what it changes:

• More GFX_TIMSORT_MOVE instead of simple copy-assignments.
• Introduce GFX_TIMSORT_MOVE_RANGE to use the C++11 iterators version of std::move if required and us std::copy instead.
• Introduce GFX_TIMSORT_MOVE_BACKWARD to use either std::move_backward or std::copy_backward.
• I also fixed a mistake in an assert message, but that's trivial :p

However, here is the big deal: I am not 100% sure that the algorithm never reads from a moved-from value. I read the algorithm and checked everywhere that whenever a value was moved-from the algorithm made sure that the iterators point to other non-moved-from values before being dereferenced, but this method has its limits. I also used a derived version of the benchmarks from my sorting library with a move-only type that keeps track of whether it has been moved-from and asserts if we try to read from it if it has been moved-from. Here is the type I used:

template<typename T>
struct move_only
{
    // Constructors

    move_only() = delete;
    move_only(const move_only&) = delete;

    move_only(const T& value):
        can_read(true),
        value(value)
    {}

    move_only(move_only&& other):
        can_read(true),
        value(std::move(other.value))
    {
        if (not std::exchange(other.can_read, false))
        {
            std::cerr << "illegal read from a moved-from value\n";
            assert(false);
        }
    }

    // Assignment operators

    move_only& operator=(const move_only&) = delete;

    auto operator=(move_only&& other)
        -> move_only&
    {
        if (&other != this)
        {
            if (not std::exchange(other.can_read, false))
            {
                std::cerr << "illegal read from a moved-from value\n";
                assert(false);
            }
            can_read = true;
            value = std::move(other.value);
        }
        return *this;
    }

    // Whether the value can be read
    bool can_read;
    // Actual value
    T value;
};

The benchmark runs several times on arrays of one million element with several data patterns to cover common and not-so-common cases, including arrays filled with random values. After every call to a sort method, it also checks that the resulting array is indeed sorted.

So, while I couldn't be 100% sure that it never reads from moved-from value (it would require a formal analysis), check the algorithm by hand and running all those tests make me pretty confident that it is safe :)

I didn't write a proper test case though since all of your tests seem to work with C++03, and such a test would explicitly require C++11 support to run and I don't know whether it would integrate seamlessly in the testsuite.

I am investigating why after sorting some entries in my array get overwritten with duplicates. Basically, if I start out with an array of size 500k and no duplicates (well there maybe duplicates from a key perspective), it appears that after running I end up with the same array size, but some entries have been duplicated and others are gone.

I caught the problem with a sanity check where I ran through the array checking that each element was greater than or equal to its predecessor. I have tried running in debug mode and did not see any assert failures.

My use case is a little complicated, but not terribly. I have an array of plain old data objects and an array of ints which are to be a sorted index of the data in the data array. The int array is filled with the index of each data object in the main array. Using a custom compare I would like to sort the int array.

It may still turn out to be a bug in my code, but the fact that it works with std::sort, std::stable_sort, and a version of SmoothSort made me think it worth asking if you think this may be a bug in the timsort impl.

Below is some psuedo code.

// this seems to work
std::sort( index_array.begin(), index_array.end(), compareHelper(data_array));  

// this seems to consistently run into problems
gfx::timsort( index_array.begin(), index_array.end(), compareHelper(data_array)); 

-------------------------------------
class data {
    int  col1;
    int  col 2; 
    int  col 3;
}

std::vector< data >  data_array;
std::vector< uint32_t >      index_array;

insert_data ( data d )
{
       data_array.push_back(d);
       index_array.push_back( data_array.size()-1);
}

struct  compareHelper
{
   const std::vector< data >& mArray;
   compareHelper( const data_array& aArray )
      :  mArray( aArray) {};

   bool operator()(const uint32_t x, const uint32_t y) const
   {
      const data& a = mArray[x];
      const data& b = mArray[y];

      if (  a.col1 == b.col1 )
      {
         return a.col2 < b.col2;
      }
      return a.col1 < b.col1;
   };
}

The following line seems incorrect.

Since MIN_MERGE is 32, the loop would end with n containing the 5 most significant bits instead of 6 most significant bits. Therefore, the function would return [0, 32], which is less than what Python is doing here

The Python detailed description of Timsort in the readme here also corresponds to returning a size of [32, 64] when possible.

Yes, "goto considered harmful" and all that. However, it really is the most direct way of breaking out of multiple levels of loops.

Using a temporary boolean like this code had been doing actually requires more work at the assembly level. An if statement that just has a break or goto as its contents will likely compile down to a single branch instruction. However, if you have to do anything else in the body, you now have a code block that needs to be branched around in the false case. So in pseudo-assembly instead of:

  beq FOO

you could have:

  bne FALSE
  mov %r1, TRUE
  jmp FOO
FALSE:

It's possible that the compiler's flowgraph optimizer will manage to pull out the temporary variable and do this transformation itself... but it's really asking a lot. I don't think it's any less readable to just change to a goto and express directly where we want controlflow to go

Additional checks on compiler move/type-trait compliance, check for move capability of element type (these checks are compile-time and should be optimized out by compiler), fallback to copy for non-move-capable types.

I just realized that the namespace gfx has two million hits on GitHub alone: it is most likely a common abbreviation for "graphics" and it's used in big engines (it notably appears in the Fuchsia source code).

I'm not sure what to do about this. We could probably play it safe and use namespace timsort instead, which apparently doesn't exist. That would give a timsort::timsort(...) function, a timsort/timsort.hpp header to include and a timsort::timsort CMake target. It doesn't feel like the coolest solution, but it's probably pragmatic enough.

First, sorry that this PR contains more than one thing. I have a few other changes I want to propose for timsort and I'll try to keep those in standalone PRs. Because of the need for C++11 support to test this I ended up having to fix that bug as part of this performance work. I can break the libc++ changes out into a different PR if you'd rather merge that as a separate PR first.

In my application I need to sort a vector of pointers. I was profiling timsort and was surprised at how much time was being spent in copy_to_tmp() This method was implemented as:

tmp_.clear();
tmp_.reserve(len);
GFX_TIMSORT_MOVE_RANGE(begin, begin + len, std::back_inserter(tmp_));

Unfortunately this performs badly on simple types like pointers. The GFX_TIMSORT_MOVE_RANGE() macro itself can reduce to a single memmove() but using std::back_inserter (which is required for move-only types) breaks this optimization. Instead of a nice SSE-optimized memory copy you end up with an element-by-element loop with a vector capacity check each time.

As an experiment I did some metaprogramming so that TriviallyCopyable types would just do:

tmp_.assign(begin, begin + len);

This basically fixed the problem, but it's still not quite perfect, since the non-trivial case still is doing extra capacity checks that aren't required. I did a more aggressive fix that replaced the std::vector use entirely with a custom data structure (since we don't really need a general purpose vector here, just a managed array) which bought another couple percent in speed.

First I had to make two preparatory changes, though:

1. The C++11 support was broken on libc++ (which is the default STL for most clang installs, including Xcode) The changes @mattreecebentley made to auto-detect C++11 were mostly good but they specifically rejected anything with _LIBCPP_VERSION set. Not sure why.

Rather than one large binary expression I instead used a larger (but hopefully easier to understand) ifdef decision tree. This can also be overridden on the command-line with -DGFX_TIMSORT_USE_CXX11=[0|1] As before we default to using C++11 constructs unless we see some evidence that it won't work. However we now let modern versions of clang/libc++ pass.

2. The parts of the TimSort class that don't very based on LessFunction are now in their own set of classes such as TimSortState

This is partially just a cleanup I needed to make some template metaprogramming less gross. However, it's a good idea in any case. It's not unusual for a program to need to sort a type of data multiple ways, which means expanding the TimSort<RandomAccessIterator,LessFunction> template multiple times. With this change, the compiler can reuse the expansion of TimSortState<RandomAccessIterator> between them. If nothing else, this should compile faster.

Now with those things out of the way, I could get to the meat of the change: replacing the std::vector<value_t> tmp_; with a custom TimSortMergeSpace<> type.

This class allocates itself like a vector, but the only "setter" is a move_in() method that replaces its contents via move construction (similar to what the std::back_inserter loop was doing) We don't construct elements before they're needed (even if we allocated them) so it will work even for non-default-constructable types. The move-loop is faster than before since we don't need to re-check for capacity at every insertion.

However, on C++11 we do even better: we use template-specialization to provide an alternate implementation of this data type for types that pass std::is_trivially_copyable<>. The big advantage is that we can just use std::memcpy() to refill the merge buffer. The code is also simpler in general since we don't need to worry about construction/destruction of the buffer elements.

Since a lot of the overall cost of the timsort algorithm is spent merging, making this data structure as fast as possible is important. This change makes sorting randomized sequences about 10% faster when working with trivially-copyable types.

While I was there I also replaced the std::vector<run> pending_ with my own TimSortRunStack<> type. This doesn't have the same importance for performance, but it's another place where we don't really need the full STL vector support... just a simple resizable stack. Since I was replacing one vector I thought it was more consistent to just replace both. This also removes the header dependency on <vector>

RESULTS: "make bench" on Xcode 10.1, Mac Pro:

• RANDOMIZED SEQUENCE [int] size=100K Before: 0.851 After: 0.745

• RANDOMIZED SEQUENCE [std::string] size=100K Before: 5.389 After: 3.735

The improvement with int is due to the vector replacement. The bigger improvement with std::string is making C++11 work with the libc++ STL so that move optimizations get applied.