algo/detail/pdqsort.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Orson Peters  2017.
0004 // (C) Copyright Ion Gaztanaga 2017-2018.
0005 // Distributed under the Boost Software License, Version 1.0.
0006 // (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/move for documentation.
0010 //
0011 //////////////////////////////////////////////////////////////////////////////
0012 //
0013 // This implementation of Pattern-defeating quicksort (pdqsort) was written
0014 // by Orson Peters, and discussed in the Boost mailing list:
0015 // http://boost.2283326.n4.nabble.com/sort-pdqsort-td4691031.html
0016 //
0017 // This implementation is the adaptation by Ion Gaztanaga of code originally in GitHub
0018 // with permission from the author to relicense it under the Boost Software License
0019 // (see the Boost mailing list for details).
0020 //
0021 // The original copyright statement is pasted here for completeness:
0022 //
0023 //  pdqsort.h - Pattern-defeating quicksort.
0024 //  Copyright (c) 2015 Orson Peters
0025 //  This software is provided 'as-is', without any express or implied warranty. In no event will the
0026 //  authors be held liable for any damages arising from the use of this software.
0027 //  Permission is granted to anyone to use this software for any purpose, including commercial
0028 //  applications, and to alter it and redistribute it freely, subject to the following restrictions:
0029 //  1. The origin of this software must not be misrepresented; you must not claim that you wrote the
0030 //     original software. If you use this software in a product, an acknowledgment in the product
0031 //     documentation would be appreciated but is not required.
0032 //  2. Altered source versions must be plainly marked as such, and must not be misrepresented as
0033 //     being the original software.
0034 //  3. This notice may not be removed or altered from any source distribution.
0035 //
0036 //////////////////////////////////////////////////////////////////////////////
0037
0038 #ifndef BOOST_MOVE_ALGO_PDQSORT_HPP
0039 #define BOOST_MOVE_ALGO_PDQSORT_HPP
0040
0041 #ifndef BOOST_CONFIG_HPP
0042 #  include <boost/config.hpp>
0043 #endif
0044 0045 ">#
0046 #if defined(BOOST_HAS_PRAGMA_ONCE)
0047 #  pragma once
0048 #endif
0049
0050 #include <boost/move/detail/config_begin.hpp>
0051
0052 #include <boost/move/detail/workaround.hpp>
0053 #include <boost/move/utility_core.hpp>
0054 #include <boost/move/algo/detail/insertion_sort.hpp>
0055 #include <boost/move/algo/detail/heap_sort.hpp>
0056 #include <boost/move/detail/iterator_traits.hpp>
0057
0058 #include <boost/move/adl_move_swap.hpp>
0059 #include <cstddef>
0060
0061 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0062 #pragma GCC diagnostic push
0063 #pragma GCC diagnostic ignored "-Wsign-conversion"
0064 #endif
0065
0066 namespace boost {
0067 namespace movelib {
0068
0069 namespace pdqsort_detail {
0070
0071    //A simple pair implementation to avoid including <utility>
0072    template<class T1, class T2>
0073    struct pair
0074    {
0075       pair()
0076       {}
0077
0078       pair(const T1 &t1, const T2 &t2)
0079          : first(t1), second(t2)
0080       {}
0081
0082       T1 first;
0083       T2 second;
0084    };
0085
0086     enum {
0087         // Partitions below this size are sorted using insertion sort.
0088         insertion_sort_threshold = 24,
0089
0090         // Partitions above this size use Tukey's ninther to select the pivot.
0091         ninther_threshold = 128,
0092
0093         // When we detect an already sorted partition, attempt an insertion sort that allows this
0094         // amount of element moves before giving up.
0095         partial_insertion_sort_limit = 8,
0096
0097         // Must be multiple of 8 due to loop unrolling, and < 256 to fit in unsigned char.
0098         block_size = 64,
0099
0100         // Cacheline size, assumes power of two.
0101         cacheline_size = 64
0102
0103     };
0104
0105     // Returns floor(log2(n)), assumes n > 0.
0106     template<class Unsigned>
0107     Unsigned log2(Unsigned n) {
0108         Unsigned log = 0;
0109         while (n >>= 1) ++log;
0110         return log;
0111     }
0112
0113     // Attempts to use insertion sort on [begin, end). Will return false if more than
0114     // partial_insertion_sort_limit elements were moved, and abort sorting. Otherwise it will
0115     // successfully sort and return true.
0116     template<class Iter, class Compare>
0117     inline bool partial_insertion_sort(Iter begin, Iter end, Compare comp) {
0118         typedef typename boost::movelib::iterator_traits<Iter>::value_type T;
0119         typedef typename boost::movelib:: iter_size<Iter>::type  size_type;
0120         if (begin == end) return true;
0121
0122         size_type limit = 0;
0123         for (Iter cur = begin + 1; cur != end; ++cur) {
0124             if (limit > partial_insertion_sort_limit) return false;
0125
0126             Iter sift = cur;
0127             Iter sift_1 = cur - 1;
0128
0129             // Compare first so we can avoid 2 moves for an element already positioned correctly.
0130             if (comp(*sift, *sift_1)) {
0131                 T tmp = boost::move(*sift);
0132
0133                 do { *sift-- = boost::move(*sift_1); }
0134                 while (sift != begin && comp(tmp, *--sift_1));
0135
0136                 *sift = boost::move(tmp);
0137                 limit += size_type(cur - sift);
0138             }
0139         }
0140
0141         return true;
0142     }
0143
0144     template<class Iter, class Compare>
0145     inline void sort2(Iter a, Iter b, Compare comp) {
0146         if (comp(*b, *a)) boost::adl_move_iter_swap(a, b);
0147     }
0148
0149     // Sorts the elements *a, *b and *c using comparison function comp.
0150     template<class Iter, class Compare>
0151     inline void sort3(Iter a, Iter b, Iter c, Compare comp) {
0152         sort2(a, b, comp);
0153         sort2(b, c, comp);
0154         sort2(a, b, comp);
0155     }
0156
0157     // Partitions [begin, end) around pivot *begin using comparison function comp. Elements equal
0158     // to the pivot are put in the right-hand partition. Returns the position of the pivot after
0159     // partitioning and whether the passed sequence already was correctly partitioned. Assumes the
0160     // pivot is a median of at least 3 elements and that [begin, end) is at least
0161     // insertion_sort_threshold long.
0162     template<class Iter, class Compare>
0163     pdqsort_detail::pair<Iter, bool> partition_right(Iter begin, Iter end, Compare comp) {
0164         typedef typename boost::movelib::iterator_traits<Iter>::value_type T;
0165
0166         // Move pivot into local for speed.
0167         T pivot(boost::move(*begin));
0168
0169         Iter first = begin;
0170         Iter last = end;
0171
0172         // Find the first element greater than or equal than the pivot (the median of 3 guarantees
0173         // this exists).
0174         while (comp(*++first, pivot));
0175
0176         // Find the first element strictly smaller than the pivot. We have to guard this search if
0177         // there was no element before *first.
0178         if (first - 1 == begin) while (first < last && !comp(*--last, pivot));
0179         else                    while (                !comp(*--last, pivot));
0180
0181         // If the first pair of elements that should be swapped to partition are the same element,
0182         // the passed in sequence already was correctly partitioned.
0183         bool already_partitioned = first >= last;
0184
0185         // Keep swapping pairs of elements that are on the wrong side of the pivot. Previously
0186         // swapped pairs guard the searches, which is why the first iteration is special-cased
0187         // above.
0188         while (first < last) {
0189             boost::adl_move_iter_swap(first, last);
0190             while (comp(*++first, pivot));
0191             while (!comp(*--last, pivot));
0192         }
0193
0194         // Put the pivot in the right place.
0195         Iter pivot_pos = first - 1;
0196         if(begin != pivot_pos)   //Avoid potential self-move
0197             *begin = boost::move(*pivot_pos);
0198         *pivot_pos = boost::move(pivot);
0199
0200         return pdqsort_detail::pair<Iter, bool>(pivot_pos, already_partitioned);
0201     }
0202
0203     // Similar function to the one above, except elements equal to the pivot are put to the left of
0204     // the pivot and it doesn't check or return if the passed sequence already was partitioned.
0205     // Since this is rarely used (the many equal case), and in that case pdqsort already has O(n)
0206     // performance, no block quicksort is applied here for simplicity.
0207     template<class Iter, class Compare>
0208     inline Iter partition_left(Iter begin, Iter end, Compare comp) {
0209         typedef typename boost::movelib::iterator_traits<Iter>::value_type T;
0210
0211         T pivot(boost::move(*begin));
0212         Iter first = begin;
0213         Iter last = end;
0214
0215         while (comp(pivot, *--last));
0216
0217         if (last + 1 == end) while (first < last && !comp(pivot, *++first));
0218         else                 while (                !comp(pivot, *++first));
0219
0220         while (first < last) {
0221             boost::adl_move_iter_swap(first, last);
0222             while (comp(pivot, *--last));
0223             while (!comp(pivot, *++first));
0224         }
0225
0226         Iter pivot_pos = last;
0227         *begin = boost::move(*pivot_pos);
0228         *pivot_pos = boost::move(pivot);
0229
0230         return pivot_pos;
0231     }
0232
0233
0234    template<class Iter, class Compare>
0235    void pdqsort_loop( Iter begin, Iter end, Compare comp
0236                     , typename boost::movelib:: iter_size<Iter>::type bad_allowed
0237                     , bool leftmost = true)
0238    {
0239         typedef typename boost::movelib:: iter_size<Iter>::type size_type;
0240
0241         // Use a while loop for tail recursion elimination.
0242         while (true) {
0243             size_type size = size_type(end - begin);
0244
0245             // Insertion sort is faster for small arrays.
0246             if (size < insertion_sort_threshold) {
0247                 insertion_sort(begin, end, comp);
0248                 return;
0249             }
0250
0251             // Choose pivot as median of 3 or pseudomedian of 9.
0252             size_type s2 = size / 2;
0253             if (size > ninther_threshold) {
0254                 sort3(begin, begin + s2, end - 1, comp);
0255                 sort3(begin + 1, begin + (s2 - 1), end - 2, comp);
0256                 sort3(begin + 2, begin + (s2 + 1), end - 3, comp);
0257                 sort3(begin + (s2 - 1), begin + s2, begin + (s2 + 1), comp);
0258                 boost::adl_move_iter_swap(begin, begin + s2);
0259             } else sort3(begin + s2, begin, end - 1, comp);
0260
0261             // If *(begin - 1) is the end of the right partition of a previous partition operation
0262             // there is no element in [begin, end) that is smaller than *(begin - 1). Then if our
0263             // pivot compares equal to *(begin - 1) we change strategy, putting equal elements in
0264             // the left partition, greater elements in the right partition. We do not have to
0265             // recurse on the left partition, since it's sorted (all equal).
0266             if (!leftmost && !comp(*(begin - 1), *begin)) {
0267                 begin = partition_left(begin, end, comp) + 1;
0268                 continue;
0269             }
0270
0271             // Partition and get results.
0272             pdqsort_detail::pair<Iter, bool> part_result = partition_right(begin, end, comp);
0273             Iter pivot_pos = part_result.first;
0274             bool already_partitioned = part_result.second;
0275
0276             // Check for a highly unbalanced partition.
0277             size_type l_size = size_type(pivot_pos - begin);
0278             size_type r_size = size_type(end - (pivot_pos + 1));
0279             bool highly_unbalanced = l_size < size / 8 || r_size < size / 8;
0280
0281             // If we got a highly unbalanced partition we shuffle elements to break many patterns.
0282             if (highly_unbalanced) {
0283                 // If we had too many bad partitions, switch to heapsort to guarantee O(n log n).
0284                 if (--bad_allowed == 0) {
0285                     boost::movelib::heap_sort(begin, end, comp);
0286                     return;
0287                 }
0288
0289                 if (l_size >= insertion_sort_threshold) {
0290                     boost::adl_move_iter_swap(begin,             begin + l_size / 4);
0291                     boost::adl_move_iter_swap(pivot_pos - 1, pivot_pos - l_size / 4);
0292
0293                     if (l_size > ninther_threshold) {
0294                         boost::adl_move_iter_swap(begin + 1,         begin + (l_size / 4 + 1));
0295                         boost::adl_move_iter_swap(begin + 2,         begin + (l_size / 4 + 2));
0296                         boost::adl_move_iter_swap(pivot_pos - 2, pivot_pos - (l_size / 4 + 1));
0297                         boost::adl_move_iter_swap(pivot_pos - 3, pivot_pos - (l_size / 4 + 2));
0298                     }
0299                 }
0300
0301                 if (r_size >= insertion_sort_threshold) {
0302                     boost::adl_move_iter_swap(pivot_pos + 1, pivot_pos + (1 + r_size / 4));
0303                     boost::adl_move_iter_swap(end - 1,                   end - r_size / 4);
0304
0305                     if (r_size > ninther_threshold) {
0306                         boost::adl_move_iter_swap(pivot_pos + 2, pivot_pos + (2 + r_size / 4));
0307                         boost::adl_move_iter_swap(pivot_pos + 3, pivot_pos + (3 + r_size / 4));
0308                         boost::adl_move_iter_swap(end - 2,             end - (1 + r_size / 4));
0309                         boost::adl_move_iter_swap(end - 3,             end - (2 + r_size / 4));
0310                     }
0311                 }
0312             } else {
0313                 // If we were decently balanced and we tried to sort an already partitioned
0314                 // sequence try to use insertion sort.
0315                 if (already_partitioned && partial_insertion_sort(begin, pivot_pos, comp)
0316                                         && partial_insertion_sort(pivot_pos + 1, end, comp)) return;
0317             }
0318
0319             // Sort the left partition first using recursion and do tail recursion elimination for
0320             // the right-hand partition.
0321             pdqsort_loop<Iter, Compare>(begin, pivot_pos, comp, bad_allowed, leftmost);
0322             begin = pivot_pos + 1;
0323             leftmost = false;
0324         }
0325     }
0326 }
0327
0328
0329 template<class Iter, class Compare>
0330 void pdqsort(Iter begin, Iter end, Compare comp)
0331 {
0332    if (begin == end) return;
0333    typedef typename boost::movelib:: iter_size<Iter>::type size_type;
0334    pdqsort_detail::pdqsort_loop<Iter, Compare>(begin, end, comp, pdqsort_detail::log2(size_type(end - begin)));
0335 }
0336
0337 }  //namespace movelib {
0338 }  //namespace boost {
0339
0340 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0341 #pragma GCC diagnostic pop
0342 #endif
0343
0344 #include <boost/move/detail/config_end.hpp>
0345
0346 #endif   //BOOST_MOVE_ALGO_PDQSORT_HPP