boostorg / sort Goto Github PK

View Code? Open in Web Editor NEW

51.0 51.0 42.0 3.4 MB

Boost.Sort

C++ 96.35% HTML 0.07% Perl 1.78% Shell 1.56% CMake 0.08% Starlark 0.15%

sort's People

Contributors

Stargazers

Watchers

sort's Issues

Compile failure when usign togerther with range/algorithm

The following code fails to compile:

#include <boost/range/algorithm.hpp>
#include <boost/sort/sort.hpp>
void main(){}

boost/sort/common/util/insert.hpp #includes itself

working on clang modules (as a proxy for C++20 header-units), I see that boost/sort/common/util/insert.hpp #includes itself. That seems unnatural.

boost-includes.txt

Failures on MSVC

testing.capture-output bin.v2\libs\sort\test\test_flat_stable_sort.test\msvc-14.1\debug\optimization-speed\threadapi-win32\threading-multi\test_flat_stable_sort.run
====== BEGIN OUTPUT ======
Running 1 test case...
unknown location(0): fatal error: in "test_main_caller(_argc,_argv_)": C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.11.25503\include\vector(140) : Assertion failed: vector iterator + offset out of range
*** 1 failure is detected in the test module "Test Program"
 
EXIT STATUS: 201 
====== END OUTPUT ======

See https://ci.appveyor.com/project/boostorg/boost/build/1.0.4436-develop/job/3iuoitpwo712t9l9#L268

Document that rightshift must discriminate between all elements

Hello,

from the documentation, it isn't clear to me whether I am allowed to float_sort a container of pair<float,void*> using a comparator that compares the first member and in case of equality disambiguates by complicated operations on the pointer, and a rightshift that only considers the float. In this case, rightshift does not provide the whole information, and the algorithm should finish by sorting elements with all identical rightshift using the comparator.

I convinced myself that it wasn't supported using the following program on this file (on x86_64-linux-gnu):
http://geometrica.saclay.inria.fr/team/Marc.Glisse/tmp/test.txt.gz

#include <boost/sort/sort.hpp>
#include <fstream>
#include <algorithm>
#include <cassert>

int main(){
  std::ifstream file ("test.txt");
  typedef std::pair<float,int> P;
  std::vector<P> v;
  struct C {
    bool operator()(P const&a, P const&b)const{
      if(a.first!=b.first){
        assert(a.first<b.first == a.second<b.second);
      }
      return a.second<b.second;
    }
  };
  float f; int i;
  while (file >> f >> i) v.emplace_back(f,i);
  boost::sort::spreadsort::float_sort(v.begin(),v.end(),
      [](P const&x, unsigned offset){ return boost::sort::spreadsort::float_mem_cast<float,int>(x.first)>>offset; },
      C());
  assert(std::is_sorted(v.begin(),v.end(),C()));
}

spreadsort() should work out-of-the-box for std::wstring

The following code sample fails:

int main()
{
    std::vector<std::wstring> vec(100000);
    boost::sort::spreadsort::string_sort(vec.begin(), vec.end());
}

It triggers the following static assertion:

sizeof(x[u]) == sizeof(Unsigned_char_type)

For some reason, when spreadsort is directly called with an std::wstring, it is forwarded to the string_sort overload that takes two iterators (until there, it seems normal) that forwards it to the overload that takes two iterators and a character but it always gives an unsigned char for the character. Shoudn't it do a dispatch with typename std::iterator_traits<RandomAccessIter>::value_type instead so that Unsigned_char_type can be wchar_t when needed?

Anyway, spreadsort says it works for std::wstring so I would expect to work out-of-the-box with std::wstring instead of triggering a compile-time error.

Missing documentation

Documentation

In the file https://github.com/boostorg/sort/blob/develop/include/boost/sort/common/merge_block.hpp I see around the line 175

    //-------------------------------------------------------------------------
    //  function :
    /// @brief
    /// @param
    /// @return
    //-------------------------------------------------------------------------
    void merge_range_pos(it_index itx_first, it_index itx_mid,
                         it_index itx_last);

missing information for the end user about the usage of the function
this will give problems with documentation generators due to missing information / incorrect information

For some other functions the documentation is also missing / incomplete whilst for a number of functions documentation is present.
I didn't check other files.

Edit just saw similar problems in https://github.com/boostorg/sort/blob/develop/include/boost/sort/flat_stable_sort/flat_stable_sort.hpp (e.g. line 107, 134).

Constants should be policy-based

Right now, boost/sort/spreadsort/detail/constants.hpp defines a bunch of performance-tuning constants for spreadsort. Why make these constants global? Because these constants live in a simple enum, they're impossible to change without changing the Boost headers, which is awkward when compiling against a Boost installed system-wide.

Instead, spreadsort should accept a struct containing these constants as a template argument. This way, users would be able to customize these parameters for specific invocations of spreadsort without changing the Boost headers themselves.

Missing parallel_stable_sort with comparator and thread count

The detail class contains parallel_stable_sort(Iter_t first, Iter_t last, Compare comp, uint32_t num_thread) but the callable wrappers at the end of parallel_stable_sort.h are missing this function.

Handle std::string_view in top-level spreadsort

The top-level spreadsort function has specific overloads targeting std::string and std::wstring specifically. With C++17 around the corner, these overloads could also accept std::string_view and std::wstring_view when they are available.

It notably helps std::string_view to be more of a "drop-in replacement for std::string" as much as possible.

By the way, is string_spread_sort also intended to sort collections of std::vector<char> or std::deque<char>, or is it not suited for these cases?

Potential undefined behavior in float_sort.hpp

This got flagged when I ran with UBSan. It looks like last - first in this code is doing a signed subtraction. Even though the result is being stored in an unsigned type, the subtraction itself is being done with singed integers. Overflow in signed arithmetic is undefined. This code should probably do the math as unsigned to be safe.

I can try to provide a repro if it helps. The code that flagged this issue was using a random input generator. So it will take me a while to come up with a minimal repo.

spinsort and flat_stable_sort don't compile with -fno-exceptions or -fno-operator-names GCC flags

Boost version: 1.72.0 (Arch Linux package version: boost 1.72.0-2).

The other two sorting methods I tested - spreadsort::float_sort and pdqsort - work just fine with these compiler flags.

These two flags are used by default in KDE: https://invent.kde.org/frameworks/extra-cmake-modules/-/blob/master/kde-modules/KDECompilerSettings.cmake. Possible workaround (which will hopefully work): create a tiny static library that disables these flags and calls spinsort or flat_stable_sort.

Using counting_sort to improve integer_spread_sort

Hi, it's me again :)

No bug or memory leak today, but I was benchmarking some sorting algorithms again and was surprised by how fast a simple counting sort. Here are the results of a benchmark testing several sorting algorithms against collections of one million of integer elements with several data distributions:

While not always the fastest, counting sort tends to be insanely fast and always beats spreadsort in the benchmarks. Of course, counting sort has its share of problems, but I believe that it can be used to improve the integer-only version of spreadsort that does not take any custom comparison or shift function. Basically, we could add the following implementation somewhere (this version uses C++11, but it can be done in C++03):

template<class ForwardIter, class T>
void counting_sort(ForwardIter first, ForwardIter last, T min, T max) {
  if (min == max) return;

  using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
  std::vector<difference_type> counts(max - min + 1, 0);

  for (auto it = first ; it != last ; ++it) {
    ++counts[*it - min];
  }

  for (auto count: counts) {
    first = std::fill_n(first, count, min++);
  }
}

Then we could modify the beginning of spreadsort_rec to use it as follows:

template <class RandomAccessIter, class Div_type, class Size_type>
inline void
spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
          std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
          , size_t *bin_sizes)
{
  //This step is roughly 10% of runtime, but it helps avoid worst-case
  //behavior and improve behavior with real data
  //If you know the maximum and minimum ahead of time, you can pass those
  //values in and skip this step for the first iteration
  RandomAccessIter max, min;
  if (is_sorted_or_find_extremes(first, last, max, min))
    return;

  if (*max - *min <= last - first) {
    counting_sort(first, last, *min, *max);
    return;
  }

  // Rest of the current implementation...
}

Thanks to is_sorted_or_find_extremes, we already know the minimum and maximum values of the range [first, last), so we don't have to compute them again in counting_sort. The check *max - *min <= last - first ensures that counting_sort will be called only if the std::vector it needs to allocate is no bigger than the original array, which means that spreadsort keeps a O(n) auxiliary memory guarantee (IIRC it is the current memory guarantee of spreadsort, right?). That check also ensures that the algorithm won't even run into the pathological worst cases of counting sort, so we only keep the good parts.

In other words, we can significantly speed up some scenarios at the cost of a single condition that shouldn't even weight too much when it fails. If I find the time, I will try to compare a version of spreadsort with this trick against the current one and share the benchmark results here.

tests take too long to complete on variant=debug

Typed b2 -j2 variant=debug threading=multi link=shared address-model=64 toolset=msvc-14.1 warnings=off libs/sort/test//test_parallel_stable_sort and it took about 5-7 minutes to complete (with variant=release it is done in seconds).

It does build with optimizations though:

     Usage requirements for test_parallel_stable_sort:  <include>.
     Build properties:  <abi>ms <address-model>64 <architecture>x86 <asynch-exceptions>off <binary-format>pe <context-impl>fcontext <debug-store>object <debug-symbols>on <deduced-address-model>32 <deduced-architecture>x86 <define>BOOST_ALL_NO_LIB=1 <doxygen.doxproc.index>no <doxygen.processor>xsltproc <embed-manifest>on <exception-handling>on <extern-c-nothrow>off <format>html <hardcode-dll-paths>true <host-os>windows <implicit-dependency>object(notfile-target)@9043 <include>. <include>.. <inlining>off <install-dependencies>off <link>shared <local-visibility>hidden <location-prefix>test_parallel_stable_sort.test <midl-robust>yes <midl-stubless-proxy>yes <optimization>speed <os>NT <pch>on <preserve-test-targets>on <profiling>off <python-debugging>off <python.interpreter>C:\Users\SERPENT\AppData\Local\Programs\Python\Python37\python <python>3.7 <relevant>build:<relevant>address-model <relevant>build:<relevant>architecture <relevant>build:<relevant>cxxstd <relevant>build:<relevant>cxxstd-dialect <relevant>build:<relevant>target-os <relevant>build:<relevant>toolset <relevant>build:<relevant>toolset-msvc:vendor <relevant>build:<relevant>toolset-msvc:version <relevant>define:<relevant>toolset <relevant>link:<relevant>toolset <relevant>python.interpreter:<relevant>address-model <relevant>python.interpreter:<relevant>python <relevant>python.interpreter:<relevant>target-os <relevant>threading:<relevant>runtime-link <relevant>threading:<relevant>toolset <relevant>toolset <rtti>on <runtime-debugging>on <runtime-link>shared <stdlib>native <strip>off <suppress-import-lib>false <symlink-location>project-relative <tag>@Jamfile<C:\Working\Repositories\boost>%Jamfile<C:\Working\Repositories\boost>.tag <target-os>windows <testing.execute>on <threadapi>win32 <threading>multi <toolset-msvc:version>14.1 <toolset>msvc <user-interface>console <variant>debug <vectorize>off <visibility>hidden <warnings-as-errors>off <warnings>off <windows-api>desktop <xsl:param>boost.defaults=Boost
     Usage requirements from test_parallel_stable_sort:  <include>. <relevant>address-model <relevant>architecture <relevant>asynch-exceptions <relevant>context-impl <relevant>cxxstd <relevant>cxxstd-dialect <relevant>debug-store <relevant>debug-symbols <relevant>deduced-address-model <relevant>deduced-architecture <relevant>embed-manifest <relevant>exception-handling <relevant>extern-c-nothrow <relevant>htm <relevant>inlining <relevant>instruction-set <relevant>known-warnings <relevant>link <relevant>numa <relevant>optimization <relevant>pch <relevant>pch-on:version <relevant>preserve-test-targets <relevant>rtti <relevant>runtime-debugging <relevant>runtime-link <relevant>segmented-stacks <relevant>target-os <relevant>testing.execute <relevant>threading <relevant>toolset <relevant>toolset-msvc:vendor <relevant>toolset-msvc:version <relevant>valgrind <relevant>variant <relevant>warnings <relevant>warnings-as-errors <relevant>wavetool <relevant>windows-api
common.mkdir bin.v2\libs\sort

        if not exist "bin.v2\libs\sort\\" mkdir "bin.v2\libs\sort"
    
common.mkdir bin.v2\libs\sort\test

        if not exist "bin.v2\libs\sort\test\\" mkdir "bin.v2\libs\sort\test"
    
common.mkdir bin.v2\libs\sort\test\test_parallel_stable_sort.test

        if not exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\\" mkdir "bin.v2\libs\sort\test\test_parallel_stable_sort.test"
    
common.mkdir bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1

        if not exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\\" mkdir "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1"
    
common.mkdir bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug

        if not exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\\" mkdir "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug"
    
common.mkdir bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64

        if not exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\\" mkdir "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64"
    
common.mkdir bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed

        if not exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\\" mkdir "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed"
    
common.mkdir bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi

        if not exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\\" mkdir "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi"
    

file bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.obj.rsp
"libs\sort\test\test_parallel_stable_sort.cpp" -Fo"bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.obj"    -TP /O2 /Z7 /Ob0 /W0 /GR /MDd /Zc:forScope /Zc:wchar_t /wd4996 /favor:blend /wd4675 /EHs -c 
-DBOOST_ALL_NO_LIB=1 
"-I." 
"-I.."
compile-c-c++ bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.obj

    call "bin.v2\standalone\msvc\msvc-14.1\address-model-64\architecture-x86\msvc-setup.bat"  >nul
 cl /Zm800 -nologo @"bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.obj.rsp" 

test_parallel_stable_sort.cpp

file bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe.rsp

"bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.obj"    
msvc.link bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe

        call "bin.v2\standalone\msvc\msvc-14.1\address-model-64\architecture-x86\msvc-setup.bat"  >nul
 link /NOLOGO /INCREMENTAL:NO /DEBUG /MACHINE:X64 /MANIFEST /subsystem:console /out:"bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe"   @"bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe.rsp"
        if %ERRORLEVEL% NEQ 0 EXIT %ERRORLEVEL%
    
msvc.manifest bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe

        if exist "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe.manifest" (
            call "bin.v2\standalone\msvc\msvc-14.1\address-model-64\architecture-x86\msvc-setup.bat"  >nul
 mt -nologo -manifest "bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe.manifest" "-outputresource:bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.exe;1"
        )
    
testing.capture-output bin.v2\libs\sort\test\test_parallel_stable_sort.test\msvc-14.1\debug\address-model-64\optimization-speed\threading-multi\test_parallel_stable_sort.run

Additional memory specification does not seem to consider the index for block indirect sort

Reading the paper about block indirect sort I was very puzzled of how one could manage the blocks indirectly without some sort of index, whose size would have been linear in the data (very small, like below 1%, but still depending on the data, not on the number of threads). Looking at the code, it seems to me that the variable std::vector<block_pos> index of the backbone is in fact a vector of additional usize values of length equal to the number of blocks. Am I correct?

Explicit calls to `std::swap` are made on user provided template types. This does not work for `C++20`.

Starting with C++20, fully specializing a function template in the std namespace is undefined behavior. This precludes implementing swap for user-defined types in the standard namespace. You can find the reasoning in this paper.

I am running into this issue while using boost::sort in a project using C++20. I have implemented a free function swap for my type in the type's namespace, but since the library code is explicitly calling std::swap, it cannot find it. If I implement the free function in std, the compiler chooses to ignore it, which is allowed under the standard.

I changed the sort code to use the "use std::swap and then call swap unqualified" idiom, and everything worked as expected. For example:

std::swap(*iter1, *iter2);

becomes,

using std::swap;
swap(*iter1, *ite2);

I can submit a PR for this change if that is appropriate.

Potential memory error in reverse_string_sort

As you might know, I work with a modified version of your spreadsort, by I believe that it is semantically equivalent, I just replaced the boost:: things with equivalent std:: entities without altering how the algorithm works in any way. I was toying with GCC and Clang's sanitizers when clang++'s address sanitizer reported what looks like a memory error when running reverse_string_sort. Once I strip the several abstraction layers, the faulty test looks roughly like this:

std::mt19937_64 engine(std::time(nullptr));

std::vector<std::string> vec;
for (int i = 0 ; i < 100'000 ; ++i)
{
    vec.push_back(std::to_string(i));
}

std::shuffle(std::begin(vec), std::end(vec), engine);
boost::sort::spreadsort::reverse_string_sort(std::begin(vec), std::end(vec), std::greater<>{});
assert(std::is_sorted(std::begin(vec), std::end(vec), std::greater<>{}));

Unfortunately, I randomize the vector based on an std::time seed, so I don't know the exact sequence that triggered the error; I tried to reproduce it didn't fire, so it probably depends on the input. I am trying to reproduce it again, meanwhile you can find the relevant error log. Since the seed uses std::time, it might be possible to find it again using the build time (to be honest, I think it's close to impossible though). I will update this post if I can deterministically reproduce the crash.

Ok, I managed to get a seed for std::mt19937_64 that triggers the memory error with the example above: 1459547468 (or 1459547467 or 1459547469 if I don't read my tests correctly, but I think I do). Just so that things are complete, you can still have the full error log, which is pretty much equivalent to the previous one.

segfault with parallel_stable_sort and 100000 entries

The following code snippet crashes for:

parallel_stable_sort
sorting 100000 entries

This is really obscure: the crash happens only for a certain number of items, 10000 works fine as well as 200000, the crash seems to happen in a certain range. I don't know if there is anything else in this setup that triggers this problem.

The example is a stripped down version from the original issue (KeyviDev/keyvi#215).

#include <ciso646>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <random>
#include <algorithm>
#include <boost/sort/parallel_stable_sort/parallel_stable_sort.hpp>
#include <boost/sort/spinsort/spinsort.hpp>
#include <boost/test/included/test_exec_monitor.hpp>
#include <boost/test/test_tools.hpp>

namespace bss = boost::sort;

template <typename KeyT, typename ValueT>
struct key_value_pair {
  key_value_pair() : key(), value() {}

  key_value_pair(const KeyT& k, const ValueT& v) : key(k), value(v) {}

  KeyT key;
  ValueT value;
};

struct ValueHandle final {
  ValueHandle() : ValueHandle(0, 0, false, false) {}
  ValueHandle(uint64_t value_idx, uint32_t weight, bool no_minimization, bool deleted)
      : value_idx_(value_idx), weight_(weight), no_minimization_(no_minimization), deleted_(deleted) {}

  uint64_t value_idx_;
  uint32_t weight_;
  bool no_minimization_;
  bool deleted_;
};

using key_value_t = key_value_pair<std::string, ValueHandle>;
using key_values_t = std::vector<key_value_t>;

inline bool compare_key_value_pair(const key_value_t& lhs, const key_value_t& rhs) {
  return lhs.key < rhs.key;
}

int test_main(int, char *[])
{
    std::vector<key_value_t> key_values;
    
    // works fine for 200000
    for (size_t i = 0; i < 100000; ++i) {
      ValueHandle handle(0, 0, false, true);
      key_values.push_back(key_value_t(std::to_string(i), handle));
    }

    bss::parallel_stable_sort(key_values.begin(), key_values.end(), compare_key_value_pair);
    
    // works fine using another sort
    //bss::spinsort(key_values.begin(), key_values.end(), compare_key_value_pair);

    return 0;
};

uname: Linux ...5.4.0-67-generic #75-Ubuntu SMP ... x86_64 x86_64 x86_64 GNU/Linux
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

pivot.hpp std::size_t fix

In applying clang implicit module machinery to boost headers I came across this problem (and by implication C++20 header-units will have the same problem). It prevents boost/sort/common/pivot.hpp being an importable header.

pivot.hpp refers to 'size_t', not std::size_t, thereby implicitly relying on its importers' contexts. Fixed thusly, it becomes a self-contained header and so a C++ 20 importable header.

--- c/1.77.0/src/boost_1_77_0/boost/sort/common/pivot.hpp
+++ w/1.77.0/src/boost_1_77_0/boost/sort/common/pivot.hpp
@@ -14,6 +14,7 @@
 #define __BOOST_SORT_COMMON_PIVOT_HPP
 
 #include <cstdint>
+#include <utility>
 
 namespace boost
 {
@@ -109,7 +110,7 @@ inline Iter_t mid9 (Iter_t iter_1, Iter_t iter_2, Iter_t iter_3, Iter_t iter_4,
 template < class Iter_t, class Compare >
 inline void pivot9 (Iter_t first, Iter_t last, Compare comp)
 {
-    size_t cupo = (last - first) >> 3;
+    std::size_t cupo = (last - first) >> 3;
     Iter_t itaux = mid9 (first + 1, first + cupo, first + 2 * cupo,
                          first + 3 * cupo, first + 4 * cupo, first + 5 * cupo,
                          first + 6 * cupo, first + 7 * cupo, last - 1, comp);

`doc/sort.idx` modified after fresh checkout

After a fresh checkout on Linux, doc/sort.idx appears modified and there's no way to un-modify it. This could be caused by the file having Windows line endings in the repository.

Document usage of pdqsort

In the documentation of pdqsort, I have trouble finding essential information for its use:

what header do I need to include?
what namespace is the function in?

I can guess that 1. is either boost/sort/sort.hpp or boost/sort/pdqsort/pdqsort.hpp, but I don't know if the second one is official and guaranteed not to move. I can also find the namespace in the source code (or just guess), but it would be nice if this information was more prominently advertised in the documentation.

spreadsort support for wider integers (e.g., (unsigned) __int128)

Hello, I am curious whether spreadsort is known to (or thought to) work with wider integer types using an appropriately written rightshift() method.

std::return_temporary_buffer

std::get_temporary_buffer and std::return_temporary_buffer that are used in this library are removed in c++20!

boost/sort/block_indirect_sort/block_indirect_sort.hpp doesn't compile under VS2017

Including #include "boost/sort/block_indirect_sort/block_indirect_sort.hpp" and using boost::sort::block_indirect_sort doesn't compile on VS2017 (C++17 compiler). There are following errors:

1>c:\views\conan\BoostHeaders\3.0.0+1.75.0\rs3\stable\package\5ab84d6acfe1f23c4fae0ab88f26e3a396351ac9\include\boost/sort/common/spinlock.hpp(72): error C2065: 'not': undeclared identifier
1>c:\views\conan\BoostHeaders\3.0.0+1.75.0\rs3\stable\package\5ab84d6acfe1f23c4fae0ab88f26e3a396351ac9\include\boost/sort/common/spinlock.hpp(72): error C2146: syntax error: missing ';' before identifier 'af'

Furthermore including: #include <boost/range/algorithm.hpp> along causes more errors since boost::sort is now template method and also internal namespace name used by block_indirect_sort.hpp header.

This is in boost 1.75.0, but I don't see it fixed in current version either (by brief look).

Warnings in float_sort_test

test\float_sort_test.cpp(86): warning C4146: unary minus operator applied to unsigned type, result still unsigned

test\float_sort_test.cpp(119): warning C4146: unary minus operator applied to unsigned type, result still unsigned

These are emitted by

  // Trying both positive and negative sorted and reverse sorted data.
  base_vec.clear();
  for (size_t i = 0; i < input_count; ++i) base_vec.push_back(-i);

The comment implies that negative values are supposed to be tested, but -i when i is size_t does not result in a negative number, but in a large positive one.

Looks like for (int i = 0; ... is intended.

Fix annoying warnings

Conversion from int64 to int in header file boost\sort\pdqsort\pdqsort.hpp, reported as warning per few screen and for almost every CPP in my project:

line 130

                limit += (int)(cur - sift);

line 265

        int unknown_left = (int)(last - first) - ((num_r || num_l) ? block_size : 0);

And in file boost\iostreams\filter\zstd.hpp:

line 94

    int error() const { return (int)error_; }

fatal error: 'boost/type_traits.hpp' file not found

Hi! I want to test these sorting algorithms, and I find that the readme says it is a include only lib. However, after #include "boost/sort/sort.hpp" in this repo, I got an error:

path/sort/include/boost/sort/spreadsort/spreadsort.hpp:26:10: fatal error: 'boost/type_traits.hpp' file not found
#include <boost/type_traits.hpp>
         ^~~~~~~~~~~~~~~~~~~~~~~
1 error generated.

error in common/spinlock.hpp

in boost/sort/common/spinlock.hpp, line 72, here is a "not", because of this, it couldn`t compile successfully.

bool try_lock ( ) noexcept { return not af.test_and_set (std::memory_order_acquire); };

Failing test case for spreadsort::float_sort

I was doing benchmarks for one of my libraries which happens to provide a wrapper for spreadsort. The benchmarks are always followed by a call to std::is_sorted so that they somehow double as unit tests. During one of the benchmarks, the assertion fired for spreadsort::float_sort. Here is a simple test case to reproduce the error:

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>
#include <boost/sort/sort.hpp>

int main()
{
    static constexpr std::size_t size = 1000000;

    std::vector<double> vec;
    for (int i = 0; i < size; ++i) vec.push_back(i);
    for (int i = 0; i < size; i += 2) vec[i] *= -1;

    boost::sort::spreadsort::float_sort(vec.begin(), vec.end());
    assert(std::is_sorted(vec.begin(), vec.end())); // fires
}

I got the error with the latest g++ and clang++, both under Windows and Linux. The error appears with both float and double. There is no error when long double is used, but I guess it's because spreadsort falls back to std::sort to sort collections of long double elements.

Broken boost::sort::spreadsort::string_sort

Below function

sort/include/boost/sort/spreadsort/detail/string_sort.hpp

Lines 696 to 705 in db798f6

 template <class RandomAccessIter, class Unsigned_char_type> 

 inline typename boost::disable_if_c< sizeof(Unsigned_char_type) <= 2, void 

 >::type 

 string_sort(RandomAccessIter first, RandomAccessIter last, 

 Unsigned_char_type) 

 { 

 //Warning that we're using boost::sort::pdqsort, even though string_sort was called 

 BOOST_STATIC_ASSERT( sizeof(Unsigned_char_type) <= 2 ); 

 boost::sort::pdqsort(first, last); 

 }

Will be disable if sizeof(Unsigned_char_type) <= 2, that means that function will be enabled when sizeof(Unsigned_char_type) > 2.

However, when sizeof(Unsigned_char_type) > 2, the BOOST_STATIC_ASSERT( sizeof(Unsigned_char_type) <= 2 ); will run into failure.

	template <class RandomAccessIter, class Unsigned_char_type>
	inline typename boost::disable_if_c< sizeof(Unsigned_char_type) <= 2, void
	>::type
	string_sort(RandomAccessIter first, RandomAccessIter last,
	Unsigned_char_type)
	{
	//Warning that we're using boost::sort::pdqsort, even though string_sort was called
	BOOST_STATIC_ASSERT( sizeof(Unsigned_char_type) <= 2 );
	boost::sort::pdqsort(first, last);
	}

boostorg / sort Goto Github PK

sort's People

Contributors

Stargazers

Watchers

Forkers

sort's Issues

Documentation

Recommend Projects

Recommend Topics

Recommend Org