[cfe-dev] Potential optimization for std::inplace_merge

[Morwenn Ed via cfe-dev]

Sure, I guess I can use the _LIBCPP_UNREACHABLE macro from <cstdlib> even though it looks like it'll be yet another incude for the already pretty big <algorithm>.


If I understand the process correctly, I only have to submit an SVN patch to the cfe-commits mailing list. Are there any other legalese I should be aware of besides knowing the project's license?


Thanks in advance.


Morwenn


________________________________
De : Eric Fiselier <eric at efcs.ca>
Envoyé : dimanche 30 octobre 2016 18:27
À : Morwenn Ed
Cc : cfe-dev at lists.llvm.org
Objet : Re: [cfe-dev] Potential optimization for std::inplace_merge

Thanks for all of this hard work. It looks like a promising optimization.

Would you be interested in submitting a patch?

/Eric


On Thu, Oct 27, 2016 at 1:12 PM, Morwenn Ed via cfe-dev <cfe-dev at lists.llvm.org<mailto:cfe-dev at lists.llvm.org>> wrote:

I have been working on a sorting library for a while, and it happens to contain reimplementations of many standard algorithms borrowed from libc++ (mostly because I needed to add a few more features to standard algorithms, akin to those in range-v3). I was working on a top-down in-place mergesort implementation, and I believe that I have found a potential albeit small optimization for std::inplace_merge, specifically in the helper function half_inplace_merge. Here is the original function borrowed from libc++ (coding style has been changed, don't pay attention to that):


    template<typename Compare, typename InputIterator1,
             typename InputIterator2, typename OutputIterator>
    auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, InputIterator2 last2,
                            OutputIterator result, Compare comp)
        -> void
    {
        for (; first1 != last1 ; ++result) {
            if (first2 == last2) {
                std::move(first1, last1, result);
                return;
            }

            if (comp(*first2, *first1)) {
                *result = std::move(*first2);
                ++first2;
            } else {
                *result = std::move(*first1);
                ++first1;
            }
        }
        // first2 through last2 are already in the right spot.
    }


I made a simple observation: at every loop iteration, we check whether first1 is different from last1 and whether first2 is equal to last2. However, we know that we will loop at least min(last1 - first1, last2 - first2) times before actually needing to check whether first1 == last1 or first2 == last2, so why not take advantage of that by comparing against an integer counter and skipping a few iterator comparisons? Moreover, the value min(last1 - first1, last2 - first2) is already known when half_inplace_merge is called, so we can directly pass them to the function? The modified function looked like this:


    template<typename Compare, typename InputIterator1,
             typename InputIterator2, typename OutputIterator,
             typename Size>
    auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, InputIterator2 last2,
                            OutputIterator result, Size min_len,
                            Compare comp)
        -> void
    {
        for (; min_len != 0 ; --min_len) {
            if (comp(*first2, *first1)) {
                *result = std::move(*first2);
                ++first2;
            } else {
                *result = std::move(*first1);
                ++first1;
            }
            ++result;
        }

        for (; first1 != last1 ; ++result) {
            if (first2 == last2) {
                std::move(first1, last1, result);
                return;
            }

            if (comp(*first2, *first1)) {
                *result = std::move(*first2);
                ++first2;
            } else {
                *result = std::move(*first1);
                ++first1;
            }
        }
        // first2 through last2 are already in the right spot.
    }


However, at this point, the new "optimization" made the code dramatically slower than it was before when sorting a vector of one million integers with a mergesort built on the top of std::inplace_merge. It kind of baffled me until I finally noticed that the second loop had some information that the first didn't have: the second loop knows that first1 != last1 and first2 != last2 while it runs. However, it is apparently possible to give that information to the first loop too. I defined the following macro:


    #define ASSUME(cond) do { if (!(cond)) __builtin_unreachable(); } while(0)


Then I changed the first loop (the "optimization") as follows:


    for (; min_len != 0 ; --min_len) {

        ASSUME(first1 != last1);
        ASSUME(first2 != last2);

        if (comp(*first2, *first1)) {
            *result = std::move(*first2);
            ++first2;
        } else {
            *result = std::move(*first1);
            ++first1;
        }
        ++result;
    }


This additional information solved the "dramatically slower" problem, and then running the benchmarks again showed that the mergesort based on the modified half_inplace_merge was generally slightly faster than the old one (sometimes the difference is lost in the noise, but there are also cases where the difference is neat albeit small). I guess that the ASSUME macro actually solved an aliasing problem which wasn't present in the second loop due to its loop conditions.


Anyway, I benchmarked that code using MinGW GCC 6.2, so the results might be different with Clang. I wanted to tell that small optimization story, and felt that I needed to share it here since I borrowed the original code from libc++. Now, you can use it as you want if you feel that the small performance gain proves to be consistent and worth it (IIRC you have benchmarks for some standard algorithms).


The code used for the benchmark is a modified version of the following: https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/bench.cpp

Here is a graph with the results I got; merge_sort-new uses the modified half_inplace_merge (the names on the left correspond to different data distributions used to test the sorting algorithms): https://i.imgur.com/hwzJ84U.<https://i.imgur.com/hwzJ84U.png>


With plenty of love <3


Morwenn


[https://i.imgur.com/hwzJ84U.png]

_______________________________________________
cfe-dev mailing list
cfe-dev at lists.llvm.org<mailto:cfe-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20161031/a257fb3b/attachment.html>