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...