Proposing statsort for Boost.Sort
On Wed, 11 Mar 2026, Peter Taraba via Boost wrote:
I'm Peter Taraba, and I've been developing a new sorting algorithm called statsort that I'd love to explore adding to Boost.Sort. [...] **Benchmarks** (GCC -O3, x86-64 Linux, vs std::sort):
Wouldn't it make sense to run benchmarks against the other functions in Boost.Sort first? -- Marc Glisse
I'm Peter Taraba, and I've been developing a new sorting algorithm called statsort that I'd love to explore adding to Boost.Sort.
Hello Peter, I've made use of boost::sort in the past, and contributed some minor things to that over time. In recent projects I've been particularly interested in sorting very large (1 to 10 billion) std::vector of uint32_t or uint64_t using multiple threads and minimal memory overhead. I think this data is broadly uniform-ish, but often with multiple dense clusters of similar values. (3D point clouds) Might be interesting to see how well the bucketing approach applies to that? The key developer for boost::sort is Francisco Tapia, his email address is available via the fjtapia github profile page. The main maintainer of boost::sort tends to be responsive to boost::sort github issues and pull requests. As mentioned previously I'd be interested in broader benchmarking results including what boost::sort provides. Also of interest is the relative memory overhead - quicksort has the advantage of essentially being in-place, after all. One thing I'd mention is that with std::sort and boost::sort the formulation is in terms of a bool comparator function, std::less by default. But in this scheme what's needed is a "to scalar float/double reflecting the required order" function? Question is how "lumpy" a scalar it takes to go slower than the other approaches? Does it make sense to subsample the scalar and adjust the function to make it more uniform? Perhaps boost::sort ought to be extended to generating various datasets that we can use for benchmarking more systematically. Such as sampling from multiple weighted guassians, for example. - Nigel Stewart
Hello everyone, I'm Francisco Tapia, one of the developers of Boost Sort. I've been testing statsort, I used the official Boost Sort code. In the benchmarks folder, there's a test program to measure the execution times of all single-threaded algorithms, and another for parallel algorithms. In the program for single-threaded algorithms, I added statsort. All algorithms use the same dataset and measure times in the same way. There is a shell script to run it with GCC and another to run it with CLANG. I’ve attached the results of both on Ubuntu 25.10 ================================================================== == B E N C H M A R K N U M B E R S == == == == G C C C O M P I L E R == ================================================================== ************************************************************ ** ** ** B O O S T S O R T ** ** S I N G L E T H R E A D ** ** I N T E G E R B E N C H M A R K ** ** ** ** SORT OF 100 000 000 NUMBERS OF 64 BITS ** ** ** ************************************************************ [ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort [ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort [7] statsort | | | | | | | | | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]| [ 7 ]| --------------------+------+------+------+------+------+------+------+ random | 8.13 | 3.64 |10.56 |10.82 |11.93 | 5.26 | 5.85 | | | | | | | | | sorted | 1.68 | 0.14 | 2.96 | 0.07 | 0.07 | 0.07 | 2.70 | sorted + 0.1% end | 5.75 | 2.65 | 2.98 | 0.57 | 0.36 | 3.97 | 3.04 | sorted + 1% end |10.58 | 3.11 | 3.08 | 0.76 | 0.52 | 4.27 | 3.08 | sorted + 10% end | 7.37 | 3.83 | 3.98 | 1.62 | 1.53 | 5.13 | 3.74 | | | | | | | | | sorted + 0.1% mid | 3.48 | 2.68 | 3.28 | 2.24 | 2.71 | 2.74 | 3.07 | sorted + 1% mid | 3.30 | 2.88 | 3.32 | 2.41 | 3.28 | 2.90 | 3.33 | sorted + 10% mid | 4.04 | 3.75 | 4.20 | 3.63 | 4.99 | 3.68 | 3.85 | | | | | | | | | reverse sorted | 1.22 | 0.27 | 3.22 | 0.14 | 0.14 | 1.70 | 2.98 | rv sorted + 0.1% end| 6.72 | 2.72 | 3.30 | 0.71 | 0.43 | 3.97 | 3.21 | rv sorted + 1% end| 4.71 | 3.06 | 3.38 | 0.86 | 0.58 | 4.31 | 3.28 | rv sorted + 10% end| 4.52 | 3.86 | 4.27 | 1.74 | 1.58 | 5.30 | 3.81 | | | | | | | | | rv sorted + 0.1% mid| 6.00 | 2.67 | 3.49 | 2.73 | 3.25 | 2.48 | 3.20 | rv sorted + 1% mid| 3.81 | 2.91 | 3.59 | 2.92 | 3.83 | 2.73 | 3.33 | rv sorted + 10% mid| 4.51 | 3.69 | 4.41 | 4.13 | 5.29 | 3.72 | 3.93 | --------------------+------+------+------+------+------+------+------+ ================================================================== == B E N C H M A R K N U M B E R S == == == == C L A N G C O M P I L E R == ================================================================== ************************************************************ ** ** ** B O O S T S O R T ** ** S I N G L E T H R E A D ** ** I N T E G E R B E N C H M A R K ** ** ** ** SORT OF 100 000 000 NUMBERS OF 64 BITS ** ** ** ************************************************************ [ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort [ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort [7] statsort | | | | | | | | | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]| [ 7 ]| --------------------+------+------+------+------+------+------+------+ random | 7.98 | 3.88 | 8.92 | 7.45 | 8.92 | 4.74 | 5.44 | | | | | | | | | sorted | 1.67 | 0.15 | 5.35 | 0.07 | 0.07 | 0.08 | 3.06 | sorted + 0.1% end | 5.45 | 2.72 | 5.37 | 0.73 | 0.41 | 3.69 | 3.24 | sorted + 1% end | 9.53 | 3.23 | 5.47 | 1.25 | 0.62 | 3.92 | 3.27 | sorted + 10% end | 6.98 | 4.05 | 6.27 | 1.53 | 1.38 | 4.72 | 3.82 | | | | | | | | | sorted + 0.1% mid | 3.13 | 2.77 | 7.42 | 5.82 | 3.02 | 2.24 | 3.24 | sorted + 1% mid | 3.10 | 3.01 | 7.88 | 6.30 | 4.24 | 2.41 | 3.33 | sorted + 10% mid | 3.90 | 3.84 | 9.16 | 7.33 | 6.26 | 3.11 | 3.88 | | | | | | | | | reverse sorted | 1.18 | 0.28 | 5.59 | 0.14 | 0.14 | 1.33 | 3.30 | rv sorted + 0.1% end| 6.29 | 2.80 | 5.86 | 0.92 | 0.48 | 3.33 | 3.48 | rv sorted + 1% end| 4.41 | 3.18 | 5.90 | 1.41 | 0.70 | 3.65 | 3.50 | rv sorted + 10% end| 4.37 | 4.07 | 6.68 | 1.72 | 1.45 | 4.74 | 3.99 | | | | | | | | | rv sorted + 0.1% mid| 5.61 | 2.80 | 7.65 | 6.30 | 3.78 | 1.78 | 3.58 | rv sorted + 1% mid| 3.67 | 3.12 | 8.10 | 6.87 | 5.06 | 2.14 | 3.63 | rv sorted + 10% mid| 4.71 | 4.11 | 9.58 | 8.23 | 7.06 | 3.15 | 4.14 | --------------------+------+------+------+------+------+------+------+ In my opinion, looking at the results, statsort is a good algorithm, but it doesn’t add anything significant to the library, as can be seen in the results tables. I must say I’m glad to see people doing new things and trying to improve on what we already know. Coming up with a new algorithm is a task that’s equally hard, demanding, and exciting, which is why I encourage Peter to keep coming up with new ideas and new algorithms. Good things rarely work out on the first try But this is like Formula 1: before the season starts, all the cars look magnificent, and with the new upgrades, they’re going to be the best. Reality sets in as soon as the races begin, and we start measuring lap times. Best regards, Francisco Tapia El dom, 15 mar 2026 a las 5:12, Nigel Stewart via Boost (< boost@lists.boost.org>) escribió:
I'm Peter Taraba, and I've been developing a new sorting algorithm called statsort that I'd love to explore adding to Boost.Sort.
Hello Peter,
I've made use of boost::sort in the past, and contributed some minor things to that over time.
In recent projects I've been particularly interested in sorting very large (1 to 10 billion) std::vector of uint32_t or uint64_t using multiple threads and minimal memory overhead. I think this data is broadly uniform-ish, but often with multiple dense clusters of similar values. (3D point clouds) Might be interesting to see how well the bucketing approach applies to that?
The key developer for boost::sort is Francisco Tapia, his email address is available via the fjtapia github profile page. The main maintainer of boost::sort tends to be responsive to boost::sort github issues and pull requests.
As mentioned previously I'd be interested in broader benchmarking results including what boost::sort provides. Also of interest is the relative memory overhead - quicksort has the advantage of essentially being in-place, after all.
One thing I'd mention is that with std::sort and boost::sort the formulation is in terms of a bool comparator function, std::less by default. But in this scheme what's needed is a "to scalar float/double reflecting the required order" function? Question is how "lumpy" a scalar it takes to go slower than the other approaches? Does it make sense to subsample the scalar and adjust the function to make it more uniform?
Perhaps boost::sort ought to be extended to generating various datasets that we can use for benchmarking more systematically. Such as sampling from multiple weighted guassians, for example.
- Nigel Stewart _______________________________________________ Boost mailing list -- boost@lists.boost.org To unsubscribe send an email to boost-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost@lists.boost.org/message/2VK7VP63...
Hi Francisco, What is the generative process for the data submitted to the benchmark ? Because if I understood correctly, stat sort is supposed to outperform in quite specific distribution patterns. If you benchmark on other distributions, I would actually take it as a stress tests for stat sort, and a good thing that the difference in performance is minimal. The next question would be “what data distribution could maximize statsort perfs while minimize other algos perfs” and then benchmark on that distribution. As suggested before, a mixture of k Gaussian distributions could be a fair judge (but that would require investigating k, mu_k and sigma_k). I haven’t seen that in the presented benchmarks but maybe I misunderstood :) Apologies if I did, Best wishes, Arnaud
Hi people, After giving it more thought, maybe this is worth considering: - Injectable heavy type: if statsort best argument is to avoid comparisons through interpolation, it could mean that its dream target applications are distributions of data types that are actually costly to compare, for example boost::multiprecision::cpp_dec_float<N>. But this would require statsort not to gate its data type on std::is_arithmetic. A trait-based approach (e.g., sortable_numeric<T> or something) would let users opt-in while maintaining type safety. - Injectable interpolation function: Users in physics/finance/ML often know their data distribution or can estimate it, so why not allow users to supply a CDF estimate that actually match their actual data distribution? For Gaussian mixture, you would inject the mixture CDF. This would extend statsort from "works on smooth distributions" to "works on any distribution the user can model", and make it (hopefully) competitive on multimodal distributions. Keeping linear as the default makes sense. - Injectable bucket policy: the sqrt(n) buckets thing is hardcoded. But injectable interpolation would open the door the gaussian mixtures, lognormal mixtures and others naturally arising distributions where a "natural" number of buckets would be the number of modes in the distribution (often known in advance). I am not sure this would make anything faster though, if more intuitive, so this would require some benchmark. With these extensions, statsort could shine compared to boost::sort on benchmarks of billions of non-trivially (non uniform) generated heavy data types. And I expect those patterns (mixtures etc) to be sufficiently popular in physics and stuff to warrant inclusion in boost. But 1) Im no Boost.Sort guy 2) all of this is conditional on extensions + benchmarks Or maybe I completely misunderstood ;) Best wishes, Arno On Sun, Mar 15, 2026 at 5:12 PM Arnaud Becheler <arnaud.becheler@gmail.com> wrote:
Hi Francisco,
What is the generative process for the data submitted to the benchmark ?
Because if I understood correctly, stat sort is supposed to outperform in quite specific distribution patterns. If you benchmark on other distributions, I would actually take it as a stress tests for stat sort, and a good thing that the difference in performance is minimal.
The next question would be “what data distribution could maximize statsort perfs while minimize other algos perfs” and then benchmark on that distribution. As suggested before, a mixture of k Gaussian distributions could be a fair judge (but that would require investigating k, mu_k and sigma_k).
I haven’t seen that in the presented benchmarks but maybe I misunderstood :) Apologies if I did,
Best wishes, Arnaud
On Mar 16, 2026, at 10:21, Arnaud Becheler via Boost <boost@lists.boost.org> wrote:
why not allow users to supply a CDF estimate that actually match their actual data distribution? For Gaussian mixture, you would inject the mixture CDF.
My understanding is that this family of methods of sorting optimally relies on knowledge of inverse CDF. I am not aware of a closed form expression for inverse CDF for mixture of gaussians. I have toyed with the idea of creating a sort routine that could do live estimation of the inverse CDF as it is traversing the list. In my mind, the difficult part is making sure that partially pre-sorted input would not produce much worse performance than unsorted. Also, I wander what happens to performance when the data is slightly different from assumed distribution? Peter? Cheers, Kostas
On Mar 17, 2026, at 16:40, Kostas Savvidis <kotika98@yahoo.com> wrote:
On Mar 16, 2026, at 10:21, Arnaud Becheler via Boost <boost@lists.boost.org> wrote:
why not allow users to supply a CDF estimate that actually match their actual data distribution? For Gaussian mixture, you would inject the mixture CDF.
My understanding is that this family of methods of sorting optimally relies on knowledge of inverse CDF. I am not aware of a closed form expression for inverse CDF for mixture of gaussians.
I have toyed with the idea of creating a sort routine that could do live estimation of the inverse CDF as it is traversing the list. In my mind, the difficult part is making sure that partially pre-sorted input would not produce much worse performance than unsorted.
Also, I wander what happens to performance when the data is slightly different from assumed distribution? Peter?
Cheers, Kostas
Delete that message :-) indeed you need the CDF, not inverse. I dont know what I was thinking when I was typing....
Algorithms have two sides, just like coins. On one side is the end user, who wants an algorithm that’s fast and uses few resources. And on the other side are we, the algorithm developers. In my previous message, I spoke from the user’s perspective. I see you’re talking about statistical methods and interpolation. I’m not a mathematician or a data scientist, so I don’t have enough knowledge to contribute anything to statsort. But I encourage you to keep searching and trying. No one gets different results by doing the same thing as everyone else. In my experience, good results come after a fair number of attempts. In any case, if what you’re working on is a sorting algorithm, you know it will be judged by its speed and the resources it consumes. If it’s something else, I’ll keep quiet. I’d like for you to feel valued for what you’ve done and encouraged for having tried by the end of all this. This is difficult and very demanding. Sincerely, Francisco Tapia El mar, 17 mar 2026 a las 15:44, Kostas Savvidis via Boost (< boost@lists.boost.org>) escribió:
On Mar 17, 2026, at 16:40, Kostas Savvidis <kotika98@yahoo.com> wrote:
On Mar 16, 2026, at 10:21, Arnaud Becheler via Boost < boost@lists.boost.org> wrote:
why not allow users to supply a CDF estimate that actually match their actual data distribution? For Gaussian mixture, you would inject the mixture CDF.
My understanding is that this family of methods of sorting optimally relies on knowledge of inverse CDF. I am not aware of a closed form expression for inverse CDF for mixture of gaussians.
I have toyed with the idea of creating a sort routine that could do live estimation of the inverse CDF as it is traversing the list. In my mind, the difficult part is making sure that partially pre-sorted input would not produce much worse performance than unsorted.
Also, I wander what happens to performance when the data is slightly different from assumed distribution? Peter?
Cheers, Kostas
Delete that message :-) indeed you need the CDF, not inverse. I dont know what I was thinking when I was typing.... _______________________________________________ Boost mailing list -- boost@lists.boost.org To unsubscribe send an email to boost-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost@lists.boost.org/message/Q6IY5CEU...
Dear Boost C++ community,
StatSort function for fast sorting is ready to be reviewed / commented on, etc. https://github.com/drpt78/statsort
Questions:
Q1: Is statsort suitable for Boost C++ Library?
Q2: What optiomization you usually use -O2 or -O3 and why?
Q3: What is missing?
Q4: What is wrong? Best, Peter
tend to use O3 because its a higher number than O2, so it feels like it would be better.
Hello Peter, I took a fresh look just now, indeed the polishing work is evident. I had some thoughts I'd like to share. One thing I think is great about boost::sort is the multi-threading. For some workloads sorting can definitely be a bottleneck and throwing more cores at that is beneficial. In rendering for example, knowing the order of things towards or away from the current viewpoint, can be useful. It does seem like this algorithm is amenable to multi-threading, and think would be a requirement for production use. If I had a precomputed bucket per item, that would likely fit into a 16-bit unsigned integer. And if evaluating that is costly, or not all the items are changing, would be an additional performance advantage. So consider a variant of statsort accepting a seperate array of buckets, rather than always "lazily" evaluated. One other advantage of decoupling the bucket evaluation is that non-uniform distributions can be dealt with as a seperate concern. (Such as percentile via CDF by some good enough method) I'm curious to know if sqrt(n) buckets is somehow optimal, or if the performance has been evaluated for other powers such as 0.4 or 0.6? One reason I'm curious is if 5 billion items works fine for 16-bit bucket index, to spare the memory expense of 32-bit bucket index. One code suggestion is to nest statsort namespace inside detail, rather than prefixing the function names there. Best regards, Nigel Stewart
Hello, I’ve been reviewing the new version of the algorithm. My stance remains the same as in previous messages. My vision for the library is to include new algorithms only when they offer a clear advantage over existing ones. The goal isn’t to have a catalog of algorithms, but to have the best ones. I myself have several algorithms that aren’t in the library because they don’t offer anything significant compared to what’s already there. I’ve tested Statsort on my desktop and laptop, and in both cases the algorithm doesn’t improve upon what’s already there. With the O2 and O3 optimization options, the differences are very small. In older compilers, you could sometimes see that optimization with O2 was faster than optimization with O3, but I haven’t seen that again in recent years. Obviously, this is just my opinion. There are three authors in the Sprt library. We’ll have to see what my colleagues think. Sincerely, Francisco Tapia El mar, 7 abr 2026 a las 13:18, Nigel Stewart via Boost (< boost@lists.boost.org>) escribió:
Hello Peter,
I took a fresh look just now, indeed the polishing work is evident. I had some thoughts I'd like to share.
One thing I think is great about boost::sort is the multi-threading. For some workloads sorting can definitely be a bottleneck and throwing more cores at that is beneficial. In rendering for example, knowing the order of things towards or away from the current viewpoint, can be useful. It does seem like this algorithm is amenable to multi-threading, and think would be a requirement for production use.
If I had a precomputed bucket per item, that would likely fit into a 16-bit unsigned integer. And if evaluating that is costly, or not all the items are changing, would be an additional performance advantage. So consider a variant of statsort accepting a seperate array of buckets, rather than always "lazily" evaluated. One other advantage of decoupling the bucket evaluation is that non-uniform distributions can be dealt with as a seperate concern. (Such as percentile via CDF by some good enough method)
I'm curious to know if sqrt(n) buckets is somehow optimal, or if the performance has been evaluated for other powers such as 0.4 or 0.6? One reason I'm curious is if 5 billion items works fine for 16-bit bucket index, to spare the memory expense of 32-bit bucket index.
One code suggestion is to nest statsort namespace inside detail, rather than prefixing the function names there.
Best regards,
Nigel Stewart _______________________________________________ Boost mailing list -- boost@lists.boost.org To unsubscribe send an email to boost-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost@lists.boost.org/message/FQ2QICJK...
participants (7)
-
Arnaud Becheler -
Francisco José Tapia -
Jakob Lövhall -
Kostas Savvidis -
Marc Glisse -
Nigel Stewart -
Peter Taraba