Re: __inplace_stable_sort improvement

["François Dumont" <frs.dumont@gmail.com>]

On 24/11/21 7:48 pm, David de Kloet wrote:
> On Wed, Nov 24, 2021 at 7:33 PM François Dumont <frs.dumont@gmail.com> wrote:
>>
>> On 18/11/21 1:58 pm, David de Kloet via Libstdc++ wrote:
>>> Hello libstdc++,
>>>
>>> Apologies if this is the wrong list for my message. I believe I have an
>>> improvement for __inplace_stable_sort and I'm wondering if this is worth
>>> pursuing and if so how to proceed.
>> Of course, anyone interested in enhancing the library is welcome.
>>
>> The best way to do so would be to provide a patch on the current library
>> code. I'm the last one to have touch to this algo and it would be easier
>> for me to understand if you try to implement it directly on the library.
> _my_merge_without_buffer below preprocesses exactly to
> __merge_without_buffer from the library if you undefine NEW_ALGO so
> you can see exactly what my changes are.
>
> I currently don't have much time, but when I do I'd be happy to
> provide it as a patch. If you find time before me, you're also more
> than welcome to use the code.
>
>> The good news is that you are trying to enhance a piece of code rarely
>> used as it is only when the buffer allocation fails. So it is less
>> critical and so perhaps more open to modifications.
>>
>> During my last work on it I've added a performance test:
>> performance/25_algorithms/inplace_merge.cc. It is also supposed to check
>> performance when we fail to get a buffer and so use
>> __merge_without_buffer. Use 'make check-performance' to run it, see
>> library manual guide. Do not hesitate to change it if you think that
>> your benches are better.
> I don't currently have the environment to `make check-performance`. I
> just copied the code from the web and adjusted it. But (again) when I
> have time, I'll look into that.
>
> If you know of any "contributing to stdlibc++" guides, that would be great too.

https://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html


>
>>> __inplace_stable_sort does a merge sort where in each recursive step the 2
>>> sublists are merged in-place. The merge step is itself also recursive. In order
>>> to merge [A, B) and [B, C), a tail section S1 of [A, B) and a head section S2
>>> of [B, C) are found such that all elements in S1 are greater than all elements
>>> in S2 and then those sections are swapped/rotated and the shorter sections are
>>> merged recursively. This is done by the function __merge_without_buffer.
>>>
>>> In the current implementation, __merge_without_buffer takes the half point of
>>> the longer section and does a binary search (via lower_bound or upper_bound) to
>>> find the corresponding cut point on the other section. Then it rotates the
>>> sections.
>>>
>>> My proposal is to find the cut points such that both rotated sections have the
>>> same length such that they can always simply be swapped.
>> What do you mean by swapped ?
> I mean the first element of section 1 gets swapped with the first
> element of section 2. The second element of section 1 gets swapped
> with the second element of section 2. Etc. for each index.
>
>> I see in the code below that you are just
>> changing how the cut positions are computed and then call the same
>> std::rotate algo. I cannot see any reason why changing the position
>> would make the rotate faster.
> The implementation of rotate does a series of such section swaps. But
> if both section have the same length, it's only a single swap of
> sections which makes rotate about 1.5-2 times faster.

Ok, I see now, you try to use as much as possible the std::swap_ranges 
in __rotate for random access iterator. Maybe it means that this 
optimization should be limited to this type of iterator. We'll see 
depending on benches.

I'll have a try then when I have time.

Thanks

>
> The purpose of the code I added is to choose the cut positions such
> that the rotated sections are of equal length, which makes rotate
> faster by doing fewer element swaps, resulting in fewer calls to the
> copy/assignment constructor.
>
>>>    I have implemented
>>> this and it seems to perform better in general and in the special cases that
>>> I've tried.
>>>
>>> Unfortunately, since we are no longer guaranteed to halve the longer section in
>>> each step, there is a possibility for a stack overflow. To avoid this, the new
>>> algorithm falls back to the old behavior whenever the sections have
>>> significantly different lengths.
>>>
>>> Also, where the current algorithm performs the binary search implicitly via
>>> lower_bound/upper_bound, the new algorithm has to implement the binary search
>>> explicitly because it has to look at both sections to determine the next step
>>> in the search.
>>>
>>> I have created wrappers for my value objects as well as my iterators to count
>>> the number of operations performed by the current and my algorithm and run
>>> benchmarks on various distributions. My code is at the bottom but below is the
>>> output as run on my machine. For each operation it outputs the ratio between
>>> the number of operations performed by my algorithm over the number performed by
>>> the current algorithm.
>>>
>>> Thanks for your attention,
>>> David
>>>
>>>
>>> Distribution: random_unique(100000)
>>> Example: [19, 13, 5, 0, 10, 6, 15, 11, 16, 9, 14, 18, 4, 17, 1, 7, 8, 12, 3, 2]
>>>
>>> move: 0.588026 = 3331848 / 5666154
>>> moveAssign: 0.594789 = 6852819 / 11521431
>>> compare: 0.914997 = 2028977 / 2217469
>>> iteratorDeref: 0.718466 = 11001863 / 15312994
>>> iteratorCopy: 0.791332 = 33977189 / 42936712
>>> iteratorEquals: 2.27841 = 5174606 / 2271143
>>> iteratorInc: 1.2143 = 7697971 / 6339449
>>> iteratorDec: 0.0833529 = 473556 / 5681340
>>> iteratorDiff: 0.444865 = 1362598 / 3062950
>>> iteratorSub: 0.0200683 = 6272 / 312533
>>> iteratorAdd: 0.0695467 = 57149 / 821736
>>> iteratorAddAssign: 1.36491 = 3141949 / 2301950
>>> iteratorArithmetic: 0.861623 = 17914101 / 20791101
>>> micros: 0.663704 = 650825 / 980596
>>>
>>> Distribution: random_dupes(100000)
>>> Example: [4, 4, 1, 3, 0, 3, 2, 2, 4, 4, 0, 3, 1, 0, 3, 2, 0, 2, 1, 1]
>>>
>>> move: 0.570041 = 2949623 / 5174401
>>> moveAssign: 0.577736 = 6087819 / 10537375
>>> compare: 0.845419 = 1530877 / 1810790
>>> iteratorDeref: 0.678233 = 9232869 / 13613114
>>> iteratorCopy: 0.742699 = 25652244 / 34539225
>>> iteratorEquals: 2.41643 = 4123881 / 1706601
>>> iteratorInc: 1.15617 = 6554374 / 5669028
>>> iteratorDec: 0.101004 = 539991 / 5346219
>>> iteratorDiff: 0.417093 = 959972 / 2301580
>>> iteratorSub: 0.0350046 = 8882 / 253738
>>> iteratorAdd: 0.0972571 = 64122 / 659304
>>> iteratorAddAssign: 1.2279 = 2247197 / 1830107
>>> iteratorArithmetic: 0.81605 = 14498419 / 17766577
>>> micros: 0.699386 = 554426 / 792732
>>>
>>> Distribution: increasing_unique(100000)
>>> Example: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>>
>>> move: 1 = 91808 / 91808
>>> moveAssign: 1 = 91808 / 91808
>>> compare: 0.573591 = 224558 / 391495
>>> iteratorDeref: 0.722385 = 540924 / 748803
>>> iteratorCopy: 0.298175 = 976735 / 3275708
>>> iteratorEquals: 0.522302 = 116383 / 222827
>>> iteratorInc: 0.715444 = 132750 / 185549
>>> iteratorDec: 1 = 91808 / 91808
>>> iteratorDiff: 0.217455 = 40956 / 188342
>>> iteratorAdd: 1 = 16383 / 16383
>>> iteratorAddAssign: 0.299523 = 81884 / 273381
>>> iteratorArithmetic: 0.49082 = 480164 / 978290
>>> micros: 0.479792 = 22935 / 47802
>>>
>>> Distribution: increasing_dupes(100000)
>>> Example: [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]
>>>
>>> move: 1 = 91808 / 91808
>>> moveAssign: 1 = 91808 / 91808
>>> compare: 0.573591 = 224558 / 391495
>>> iteratorDeref: 0.722385 = 540924 / 748803
>>> iteratorCopy: 0.298175 = 976735 / 3275708
>>> iteratorEquals: 0.522302 = 116383 / 222827
>>> iteratorInc: 0.715444 = 132750 / 185549
>>> iteratorDec: 1 = 91808 / 91808
>>> iteratorDiff: 0.217455 = 40956 / 188342
>>> iteratorAdd: 1 = 16383 / 16383
>>> iteratorAddAssign: 0.299523 = 81884 / 273381
>>> iteratorArithmetic: 0.49082 = 480164 / 978290
>>> micros: 0.449154 = 20675 / 46031
>>>
>>> Distribution: mostly_increasing(100000)
>>> Example: [3, 2, 3, 4, 5, 5, 6, 7, 9, 9, 11, 13, 12, 14, 15, 17, 17, 18, 21, 20]
>>>
>>> move: 0.681093 = 814725 / 1196203
>>> moveAssign: 0.703421 = 1809563 / 2572519
>>> compare: 0.924016 = 965320 / 1044700
>>> iteratorDeref: 0.847765 = 3802634 / 4485480
>>> iteratorCopy: 0.804068 = 11859111 / 14748894
>>> iteratorEquals: 1.59826 = 1388752 / 868913
>>> iteratorInc: 1.25659 = 1818421 / 1447111
>>> iteratorDec: 0.383738 = 537108 / 1399674
>>> iteratorDiff: 0.486488 = 562273 / 1155779
>>> iteratorSub: 0.0638659 = 6666 / 104375
>>> iteratorAdd: 0.184194 = 55586 / 301780
>>> iteratorAddAssign: 1.30369 = 1105439 / 847932
>>> iteratorArithmetic: 0.893672 = 5474245 / 6125564
>>> micros: 0.790603 = 233953 / 295917
>>>
>>> Distribution: decreasing_unique(100000)
>>> Example: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>>
>>> move: 0.40597 = 995312 / 2451688
>>> moveAssign: 0.45785 = 2459840 / 5372592
>>> compare: 0.489247 = 151631 / 309927
>>> iteratorDeref: 0.524798 = 3415934 / 6509043
>>> iteratorCopy: 0.563628 = 5971275 / 10594360
>>> iteratorEquals: 1.18395 = 843533 / 712475
>>> iteratorInc: 0.864454 = 1460463 / 1689462
>>> iteratorDec: 0.373125 = 1606976 / 4306800
>>> iteratorDiff: 0.495226 = 235930 / 476409
>>> iteratorSub: 0.248254 = 13824 / 55685
>>> iteratorAdd: 0.590877 = 135839 / 229894
>>> iteratorAddAssign: 0.421852 = 119646 / 283621
>>> iteratorArithmetic: 0.569514 = 4416211 / 7754346
>>> micros: 0.543145 = 167865 / 309061
>>>
>>> Distribution: decreasing_dupes(100000)
>>> Example: [4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0]
>>>
>>> move: 0.741695 = 1455276 / 1962096
>>> moveAssign: 0.736048 = 2826598 / 3840238
>>> compare: 0.641679 = 282851 / 440798
>>> iteratorDeref: 0.740565 = 3386062 / 4572271
>>> iteratorCopy: 0.628798 = 5008472 / 7965150
>>> iteratorEquals: 1.50206 = 794354 / 528843
>>> iteratorInc: 1.39602 = 2164546 / 1550510
>>> iteratorDec: 0.336639 = 837728 / 2488504
>>> iteratorDiff: 0.313457 = 88552 / 282501
>>> iteratorSub: 0.165388 = 3880 / 23460
>>> iteratorAdd: 0.377644 = 27139 / 71864
>>> iteratorAddAssign: 0.551364 = 182383 / 330785
>>> iteratorArithmetic: 0.776766 = 4098582 / 5276467
>>> micros: 0.71282 = 160398 / 225019
>>>
>>> Distribution: mostly_decreasing(100000)
>>> Example: [20, 19, 20, 18, 18, 15, 13, 13, 14, 13, 10, 9, 10, 8, 5, 7,
>>> 6, 4, 3, 2]
>>>
>>> move: 0.760602 = 2197435 / 2889075
>>> moveAssign: 0.768473 = 4591313 / 5974593
>>> compare: 0.932913 = 977678 / 1047984
>>> iteratorDeref: 0.838641 = 6633169 / 7909424
>>> iteratorCopy: 0.829028 = 15447960 / 18633830
>>> iteratorEquals: 1.7009 = 2000686 / 1176251
>>> iteratorInc: 1.52771 = 3788203 / 2479657
>>> iteratorDec: 0.363843 = 1369990 / 3765332
>>> iteratorDiff: 0.489186 = 595472 / 1217270
>>> iteratorSub: 0.0877827 = 10925 / 124455
>>> iteratorAdd: 0.201991 = 69640 / 344767
>>> iteratorAddAssign: 1.32756 = 1133512 / 853830
>>> iteratorArithmetic: 0.900303 = 8968428 / 9961562
>>> micros: 0.846298 = 377504 / 446065
>>>
>>> Distribution: sawtooth_unique(100000)
>>> Example: [0, 3, 6, 9, 12, 15, 18, 1, 4, 7, 10, 13, 16, 19, 2, 5, 8, 11, 14, 17]
>>>
>>> move: 0.569953 = 2912465 / 5110007
>>> moveAssign: 0.577701 = 6012427 / 10407511
>>> compare: 0.824488 = 1604387 / 1945920
>>> iteratorDeref: 0.678979 = 9299794 / 13696724
>>> iteratorCopy: 0.72546 = 26157352 / 36056250
>>> iteratorEquals: 2.00683 = 4131766 / 2058856
>>> iteratorInc: 1.10728 = 6498257 / 5868688
>>> iteratorDec: 0.111225 = 552519 / 4967557
>>> iteratorDiff: 0.405328 = 988144 / 2437889
>>> iteratorSub: 0.026249 = 6327 / 241038
>>> iteratorAdd: 0.089034 = 55918 / 628052
>>> iteratorAddAssign: 1.18737 = 2297233 / 1934717
>>> iteratorArithmetic: 0.801143 = 14530164 / 18136797
>>> micros: 0.706282 = 583937 / 826776
>>>
>>> Distribution: sawtooth_dupes(100000)
>>> Example: [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]
>>>
>>> move: 0.547721 = 2348873 / 4288447
>>> moveAssign: 0.543252 = 4613817 / 8492965
>>> compare: 0.664642 = 841503 / 1266099
>>> iteratorDeref: 0.599656 = 6292282 / 10493159
>>> iteratorCopy: 0.60663 = 15336816 / 25281976
>>> iteratorEquals: 2.24803 = 2859760 / 1272118
>>> iteratorInc: 1.07142 = 4999546 / 4666276
>>> iteratorDec: 0.0490551 = 205953 / 4198405
>>> iteratorDiff: 0.314518 = 473157 / 1504390
>>> iteratorSub: 0.0371951 = 5998 / 161258
>>> iteratorAdd: 0.0875684 = 34672 / 395942
>>> iteratorAddAssign: 0.900009 = 1233077 / 1370072
>>> iteratorArithmetic: 0.72316 = 9812163 / 13568461
>>> micros: 0.610891 = 353102 / 578011
>>>
>>> Distribution: increasing_with_swap(100000)
>>> Example: [19, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 0]
>>>
>>> move: 1 = 291782 / 291782
>>> moveAssign: 1 = 491779 / 491779
>>> compare: 0.57449 = 225064 / 391763
>>> iteratorDeref: 0.819553 = 941922 / 1149312
>>> iteratorCopy: 0.377964 = 1392386 / 3683915
>>> iteratorEquals: 0.525758 = 117408 / 223312
>>> iteratorInc: 0.863708 = 333050 / 385605
>>> iteratorDec: 0.999753 = 291716 / 291788
>>> iteratorDiff: 0.224408 = 42528 / 189512
>>> iteratorSub: 0.888889 = 104 / 117
>>> iteratorAdd: 0.997151 = 16801 / 16849
>>> iteratorAddAssign: 0.302604 = 82864 / 273836
>>> iteratorArithmetic: 0.640448 = 884471 / 1381019
>>> micros: 0.616124 = 36233 / 58808
>>>
>>> Distribution: increasing_fast_slow(100000)
>>> Example: [0, 4, 8, 12, 0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18]
>>>
>>> move: 0.640348 = 825772 / 1289568
>>> moveAssign: 0.627081 = 1559792 / 2487384
>>> compare: 0.714235 = 431286 / 603843
>>> iteratorDeref: 0.694913 = 2421875 / 3485151
>>> iteratorCopy: 0.637176 = 5645877 / 8860786
>>> iteratorEquals: 1.7552 = 953880 / 543458
>>> iteratorInc: 1.08941 = 1676609 / 1539005
>>> iteratorDec: 0.135904 = 154533 / 1137073
>>> iteratorDiff: 0.388132 = 192787 / 496705
>>> iteratorSub: 0.00577964 = 141 / 24396
>>> iteratorAdd: 0.207287 = 17272 / 83324
>>> iteratorAddAssign: 0.849015 = 431320 / 508024
>>> iteratorArithmetic: 0.790987 = 3426542 / 4331985
>>> micros: 0.777699 = 153552 / 197444
>>>
>>>
>>>
>>> #include <iostream>
>>> #include <stdio.h>
>>> #include <vector>
>>> #include <cstdlib>
>>> #include <algorithm>
>>> #include <functional>
>>> #include <ranges>
>>> #include <chrono>
>>> #include <cmath>
>>> #include <numeric>
>>>
>>> using namespace std;
>>>
>>> #define LINE0 0
>>> #define cout_line (cout << "line " << __LINE__ - LINE0 << ": ")
>>> #define vout(v) #v << " = " << (v)
>>> #define print1(v) cout_line << vout(v) << endl
>>> #define print2(v1, v2) cout_line << vout(v1) << ", " << vout(v2) << endl
>>> #define print3(v1, v2, v3) cout_line << vout(v1) << ", " << vout(v2)
>>> << ", " << vout(v3) << endl
>>> #define GET_MACRO(_1,_2,_3,NAME,...) NAME
>>> #define print(...) GET_MACRO(__VA_ARGS__, print3, print2, print1)(__VA_ARGS__)
>>>
>>> template <class Ch, class Tr, class Container>
>>> basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os,
>>> Container const& x);
>>>
>>> template <class X, class Y>
>>> ostream & operator << (ostream & os, pair <X, Y> const& p) {
>>> return os << p.first << ":" << p.second;
>>> }
>>>
>>> template <class Ch, class Tr, class Container>
>>> basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os,
>>> Container const& x) {
>>>       os << "[";
>>>       bool first = true;
>>>       for(auto const& y : x) {
>>>           if (!first) os << ", ";
>>>           os << y;
>>>           first = false;
>>>       }
>>>       return os << "]";
>>> }
>>>
>>>
>>> struct Counter {
>>>     int construct = 0;
>>>     int copy = 0;
>>>     int assign = 0;
>>>     int move = 0;
>>>     int moveAssign = 0;
>>>     int compare = 0;
>>>     int iteratorDeref = 0;
>>>     int iteratorCopy = 0;
>>>     int iteratorEquals = 0;
>>>     int iteratorInc = 0;
>>>     int iteratorDec = 0;
>>>     int iteratorDiff = 0;
>>>     int iteratorSub = 0;
>>>     int iteratorAdd = 0;
>>>     int iteratorAddAssign = 0;
>>>     int iteratorArithmetic = 0;
>>>     int micros = 0;
>>> };
>>>
>>> int next_element_id = 0;
>>>
>>> class Element {
>>>     Counter* counter;
>>> public:
>>>     int val;
>>>     int id;  // Distinguis identical values to verify stability.
>>>     Element(int val, Counter* counter)
>>>         : val(val), counter(counter), id(++next_element_id) {
>>>       ++counter->construct;
>>>     }
>>>
>>>     Element(Element const& other)
>>>         : val(other.val), counter(other.counter), id(other.id) {
>>>       ++counter->copy;
>>>     }
>>>
>>>     Element& operator=(Element const& other) {
>>>       val = other.val;
>>>       counter = other.counter;
>>>       id = other.id;
>>>       ++counter->assign;
>>>       return *this;
>>>     }
>>>
>>>     Element(Element&& other) noexcept
>>>         : val(move(other.val)), counter(other.counter), id(other.id) {
>>>       ++counter->move;
>>>     }
>>>
>>>     Element& operator=(Element&& other) noexcept {
>>>       val = move(other.val);
>>>       counter = other.counter;
>>>       id = other.id;
>>>       ++counter->moveAssign;
>>>       return *this;
>>>     }
>>>
>>>     bool operator<(Element const& other) const {
>>>       ++counter->compare;
>>>       return val < other.val;
>>>     }
>>>
>>>     bool operator==(Element const& other) const {
>>>       return val == other.val && id == other.id;
>>>     }
>>> };
>>>
>>> ostream & operator << (ostream & os, Element const& e) {
>>> return os << e.val << "(" << e.id << ")";
>>> }
>>>
>>>
>>> class RandomIterator {
>>>     typedef vector<Element>::iterator It;
>>>     It it;
>>>     Counter* counter;
>>>
>>> public:
>>>     using iterator_category = std::random_access_iterator_tag;
>>>     using difference_type   = std::ptrdiff_t;
>>>     using value_type        = Element;
>>>     using pointer           = value_type*;
>>>     using reference         = value_type&;
>>>
>>>     RandomIterator(It it, Counter* counter) : it(it), counter(counter) {
>>>     }
>>>
>>>     RandomIterator(RandomIterator const& other) : it(other.it),
>>> counter(other.counter) {
>>>       counter->iteratorCopy += 1;
>>>     }
>>>
>>>     bool operator== (RandomIterator other) {
>>>       counter->iteratorEquals += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return it == other.it;
>>>     }
>>>
>>>     RandomIterator operator++ () {
>>>       counter->iteratorInc += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return RandomIterator(++it, counter);
>>>     }
>>>
>>>     RandomIterator operator-- () {
>>>       counter->iteratorDec += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return RandomIterator(--it, counter);
>>>     }
>>>
>>>     Element& operator* () {
>>>       counter->iteratorDeref += 1;
>>>       return *it;
>>>     }
>>>
>>>     difference_type operator- (RandomIterator other) {
>>>       counter->iteratorDiff += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return it - other.it;
>>>     }
>>>
>>>     RandomIterator operator- (difference_type diff) {
>>>       counter->iteratorSub += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return RandomIterator(it - diff, counter);
>>>     }
>>>
>>>     RandomIterator operator+ (difference_type diff) {
>>>       counter->iteratorAdd += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return RandomIterator(it + diff, counter);
>>>     }
>>>
>>>     RandomIterator operator+= (difference_type diff) {
>>>       counter->iteratorAddAssign += 1;
>>>       counter->iteratorArithmetic += 1;
>>>       return RandomIterator(it += diff, counter);
>>>     }
>>> };
>>>
>>>
>>> class TestCase {
>>>     Counter counter;
>>>     vector<Element> elements;
>>>
>>> public:
>>>     TestCase(vector<int> const& data) {
>>>       elements.reserve(data.size());
>>>       for (int i: data) {
>>>         elements.push_back(Element(i, &counter));
>>>       }
>>>     }
>>>
>>>     Counter sort(
>>>         void algo(RandomIterator, RandomIterator),
>>>         vector<Element>::iterator begin,
>>>         vector<Element>::iterator end) {
>>>       counter = Counter();
>>>       auto t0 = std::chrono::system_clock::now();
>>>
>>>       algo(RandomIterator(begin, &counter), RandomIterator(end, &counter));
>>>
>>>       auto t1 = std::chrono::system_clock::now();
>>>       counter.micros =
>>> std::chrono::duration_cast<std::chrono::microseconds>(t1 -
>>> t0).count();
>>>       return counter;
>>>     }
>>>
>>>     pair<Counter,Counter> benchmark(
>>>         void new_algo(RandomIterator, RandomIterator),
>>>         void cur_algo(RandomIterator, RandomIterator)) {
>>>       vector<Element> toSort1 = elements;
>>>       Counter counter1 = sort(new_algo, toSort1.begin(), toSort1.end());
>>>
>>>       vector<Element> toSort2 = elements;
>>>       Counter counter2 = sort(cur_algo, toSort2.begin(), toSort2.end());
>>>
>>>       if (toSort1 != toSort2) {
>>>         cout << "INCORRECT RESULT!" << endl;
>>>         exit(1);
>>>       }
>>>
>>>       return make_pair(counter1, counter2);
>>>     }
>>> };
>>>
>>>
>>> void relative_metric(string name, int m1, int m2) {
>>>     if (m1 == 0 && m2 == 0) return;
>>>     if (m2 == 0) {
>>>       cout << name << ": inf = " << m1 << " / " << m2 << endl;
>>>     } else {
>>>       cout << name << ": " << m1 / (double) m2 << " = " << m1 << " / "
>>> << m2 << endl;
>>>     }
>>> }
>>>
>>>
>>> void relative_report(Counter const& c1, Counter const& c2) {
>>>     cout << endl;
>>>     relative_metric("construct", c1.construct, c2.construct);
>>>     relative_metric("copy", c1.copy, c2.copy);
>>>     relative_metric("assign", c1.assign, c2.assign);
>>>     relative_metric("move", c1.move, c2.move);
>>>     relative_metric("moveAssign", c1.moveAssign, c2.moveAssign);
>>>     relative_metric("compare", c1.compare, c2.compare);
>>>     relative_metric("iteratorDeref", c1.iteratorDeref, c2.iteratorDeref);
>>>     relative_metric("iteratorCopy", c1.iteratorCopy, c2.iteratorCopy);
>>>     relative_metric("iteratorEquals", c1.iteratorEquals, c2.iteratorEquals);
>>>     relative_metric("iteratorInc", c1.iteratorInc, c2.iteratorInc);
>>>     relative_metric("iteratorDec", c1.iteratorDec, c2.iteratorDec);
>>>     relative_metric("iteratorDiff", c1.iteratorDiff, c2.iteratorDiff);
>>>     relative_metric("iteratorSub", c1.iteratorSub, c2.iteratorSub);
>>>     relative_metric("iteratorAdd", c1.iteratorAdd, c2.iteratorAdd);
>>>     relative_metric("iteratorAddAssign", c1.iteratorAddAssign,
>>> c2.iteratorAddAssign);
>>>     relative_metric("iteratorArithmetic", c1.iteratorArithmetic,
>>> c2.iteratorArithmetic);
>>>     relative_metric("micros", c1.micros, c2.micros);
>>>     cout << endl;
>>> }
>>>
>>>
>>> /// This is a helper function for the merge routines.
>>> template<typename _BidirectionalIterator, typename _Distance, typename _Compare>
>>> void _my_merge_without_buffer(
>>> _BidirectionalIterator __first,
>>> _BidirectionalIterator __middle,
>>> _BidirectionalIterator __last,
>>> _Distance __len1, _Distance __len2,
>>> _Compare __comp) {
>>>
>>> if (__len1 == 0 || __len2 == 0)
>>> return;
>>>
>>> if (__len1 + __len2 == 2) {
>>>     if (__comp(__middle, __first))
>>>       std::iter_swap(__first, __middle);
>>>     return;
>>> }
>>>
>>> _BidirectionalIterator __first_cut = __first;
>>> _BidirectionalIterator __second_cut = __middle;
>>> _Distance __len11 = 0;
>>> _Distance __len22 = 0;
>>>
>>>
>>> #define NEW_ALGO 1
>>>
>>> #ifdef NEW_ALGO
>>>     // Prevent stack overflow
>>> if (__len1 > 4 * __len2 || __len2 > 4 * __len1) {
>>> #endif
>>>       if (__len1 > __len2)
>>>         {
>>>           __len11 = __len1 / 2;
>>>           std::advance(__first_cut, __len11);
>>>           __second_cut
>>>             = std::__lower_bound(__middle, __last, *__first_cut,
>>>                __gnu_cxx::__ops::__iter_comp_val(__comp));
>>>           __len22 = std::distance(__middle, __second_cut);
>>>         }
>>>       else
>>>         {
>>>           __len22 = __len2 / 2;
>>>           std::advance(__second_cut, __len22);
>>>           __first_cut
>>>             = std::__upper_bound(__first, __middle, *__second_cut,
>>>                __gnu_cxx::__ops::__val_comp_iter(__comp));
>>>           __len11 = std::distance(__first, __first_cut);
>>>         }
>>> #ifdef NEW_ALGO
>>>     } else
>>>     {
>>>       _Distance __cut_range;
>>>       // __cut_len is always equal to __middle - __first_cut (and eventually to
>>>       // __second_cut - __middle) but we keep track of it to avoid calculating it
>>>       // later which can be expensive for bidirectional iterators.
>>>       _Distance __cut_len;
>>>
>>> if (__len1 > __len2)
>>> {
>>> std::advance(__first_cut, __len1 - __len2);
>>> __cut_range = __len2;
>>> }
>>> else
>>> {
>>> __cut_range = __len1;
>>> }
>>>       __cut_len = __cut_range;
>>>
>>> while (__cut_range > 0) {
>>> _Distance __half_cut_range = __cut_range / 2;
>>> _BidirectionalIterator __mid_first_cut = __first_cut;
>>> std::advance(__mid_first_cut, __cut_range - __half_cut_range - 1);
>>> _BidirectionalIterator __mid_second_cut = __second_cut;
>>> std::advance(__mid_second_cut, __half_cut_range);
>>>
>>> if (__comp(__mid_second_cut, __mid_first_cut)) {
>>> __cut_range -= __half_cut_range + 1;
>>> __second_cut = __mid_second_cut;
>>> ++__second_cut;
>>> } else {
>>>           __cut_len -= __cut_range - __half_cut_range;
>>> __cut_range = __half_cut_range;
>>> __first_cut = __mid_first_cut;
>>> ++__first_cut;
>>> }
>>> }
>>> __len22 = __cut_len;
>>>       __len11 = __len1 - __cut_len;
>>> }
>>> #endif
>>>
>>>     _BidirectionalIterator __new_middle
>>>         = std::rotate(__first_cut, __middle, __second_cut);
>>>     _my_merge_without_buffer(__first, __first_cut, __new_middle,
>>>         __len11, __len22, __comp);
>>>     _my_merge_without_buffer(__new_middle, __second_cut, __last,
>>>         __len1 - __len11, __len2 - __len22, __comp);
>>> }
>>>
>>> /// This is a helper function for the stable sorting routines.
>>> template<typename _RandomAccessIterator, typename _Compare>
>>>     void
>>>     _my_inplace_stable_sort(_RandomAccessIterator __first,
>>>         _RandomAccessIterator __last, _Compare __comp)
>>>     {
>>>
>>>       if (__last - __first < 15)
>>>         {
>>>           std::__insertion_sort(__first, __last, __comp);
>>>           return;
>>>         }
>>>       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
>>>       _my_inplace_stable_sort(__first, __middle, __comp);
>>>       _my_inplace_stable_sort(__middle, __last, __comp);
>>>       _my_merge_without_buffer(__first, __middle, __last,
>>>           __middle - __first,
>>>           __last - __middle,
>>>           __comp);
>>>     }
>>>
>>>
>>> template<typename Iterator>
>>> void my_inplace_stable_sort(Iterator start, Iterator end) {
>>>     _my_inplace_stable_sort(start, end, __gnu_cxx::__ops::__iter_less_iter());
>>> }
>>>
>>> template<typename Iterator>
>>> void std_inplace_stable_sort(Iterator start, Iterator end) {
>>>     std::__inplace_stable_sort(start, end, __gnu_cxx::__ops::__iter_less_iter());
>>> }
>>>
>>> void benchmark(string const& dist_name,
>>>       vector<int> dist_func(int),
>>>       int n) {
>>>     vector<int> v = dist_func(n);
>>>     cout << "Distribution: " << dist_name << "(" << n << ")" << endl;
>>>     cout << "Example: " << dist_func(20) << endl;
>>>     TestCase testCase(v);
>>>
>>>     pair<Counter, Counter> counter_pair =
>>>         testCase.benchmark(
>>>             my_inplace_stable_sort
>>>             , std_inplace_stable_sort
>>>             );
>>>     Counter cKloet = counter_pair.first;
>>>     Counter cInplace = counter_pair.second;
>>>
>>>     relative_report(cKloet, cInplace);
>>> }
>>>
>>>
>>> vector<int> random_unique(int n) {
>>>     vector<int> v(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i;
>>>     }
>>>     for (int i = n - 1; i >= 0; --i) {
>>>       swap(v[i], v[rand() % (i + 1)]);
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> random_dupes(int n) {
>>>     vector<int> v(n);
>>>     int r = (int)sqrt(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i / r;
>>>     }
>>>     for (int i = n - 1; i >= 0; --i) {
>>>       swap(v[i], v[rand() % (i + 1)]);
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> increasing_unique(int n) {
>>>     vector<int> v(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i;
>>>     }
>>>     return v;
>>> }
>>>
>>>
>>> vector<int> increasing_dupes(int n) {
>>>     vector<int> v(n);
>>>     int r = (int)sqrt(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i / r;
>>>     }
>>>     return v;
>>> }
>>>
>>>
>>> vector<int> mostly_increasing(int n) {
>>>     vector<int> v(n);
>>>     int r = (int)sqrt(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i + rand() % r;
>>>     }
>>>     return v;
>>> }
>>>
>>>
>>> vector<int> decreasing_unique(int n) {
>>>     vector<int> v(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = n - 1 - i;
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> decreasing_dupes(int n) {
>>>     vector<int> v(n);
>>>     int r = (int)sqrt(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = (n - 1 - i) / r;
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> mostly_decreasing(int n) {
>>>     vector<int> v(n);
>>>     int r = (int)sqrt(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = n - 1 - i + rand() % r;
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> sawtooth_unique(int n) {
>>>     int r = (int)sqrt(n);
>>>     while (gcd(r, n) != 1) ++r;
>>>     vector<int> v(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[(i * r) % n] = i;
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> sawtooth_dupes(int n) {
>>>     int r = (int)sqrt(n);
>>>     vector<int> v(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i % r;
>>>     }
>>>     return v;
>>> }
>>>
>>> vector<int> increasing_with_swap(int n) {
>>>     vector<int> v(n);
>>>     for (int i = 0; i < n; ++i) {
>>>       v[i] = i;
>>>     }
>>>     swap(v[0], v[n - 1]);
>>>     return v;
>>> }
>>>
>>> vector<int> increasing_fast_slow(int n) {
>>>     int r = (int)sqrt(n);
>>>     vector<int> v(n);
>>>     for (int i = 0; i < r; ++i) {
>>>       v[i] = i * r;
>>>     }
>>>     for (int i = r; i < n; ++i) {
>>>       v[i] = (i - r) * n / (n - r);
>>>     }
>>>     return v;
>>> }
>>>
>>>
>>> #define BENCHMARK(dist, n) benchmark(#dist, dist, n)
>>>
>>> int main() {
>>>     int n = 100000;
>>>     BENCHMARK(random_unique, n);
>>>     BENCHMARK(random_dupes, n);
>>>     BENCHMARK(increasing_unique, n);
>>>     BENCHMARK(increasing_dupes, n);
>>>     BENCHMARK(mostly_increasing, n);
>>>     BENCHMARK(decreasing_unique, n);
>>>     BENCHMARK(decreasing_dupes, n);
>>>     BENCHMARK(mostly_decreasing, n);
>>>     BENCHMARK(sawtooth_unique, n);
>>>     BENCHMARK(sawtooth_dupes, n);
>>>     BENCHMARK(increasing_with_swap, n);
>>>     BENCHMARK(increasing_fast_slow, n);
>>>
>>>     return 0;
>>> }
>>