I have written a sorting algorithm which is way faster than std::sort for all array size. The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost. Regards, Fenil Mehta
On Mon, 24 Dec 2018, Fenil Mehta via Boost wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size. The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Compare with Boost.Sort then contact its maintainer. -- Marc Glisse
On 12/23/18 9:56 PM, Fenil Mehta via Boost wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size. The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
One of the steps would be to license your contribution under the Boost Software License 1.0. GPL is not acceptable. Other guidelines are described here: https://www.boost.org/development/requirements.html Also, since the contribution is better suited as part of Boost.Sort, maintainers of Boost.Sort may add some requirements as well. I would say, your submission should include comparison with existing algorithms in Boost.Sort.
I have written a sorting algorithm which is way faster than std::sort for all array size.
Could you give more insights on what you did to make it work so fast? The doc is rather small. Also, when comparing with std::sort, could you say which implementation of the standard library you use and which compiler? Regards, F
On Sat, 29 Dec 2018 at 08:24, Frédéric via Boost <boost@lists.boost.org> wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
Could you give more insights on what you did to make it work so fast? The doc is rather small. Also, when comparing with std::sort, could you say which implementation of the standard library you use and which compiler?
It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use]. degski [1] https://github.com/skarupke/ska_sort -- *“If something cannot go on forever, it will stop" - Herbert Stein*
On Sat, 29 Dec 2018 at 11:16, degski <degski@gmail.com> wrote:
It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use].
Some write-up on "how it works"[2] degski [1] https://github.com/skarupke/ska_sort [2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ -- *“If something cannot go on forever, it will stop" - Herbert Stein*
Hi, I am Fenil Mehta, a 3rd year Computer Science and Engineering student. In response to the past suggestions I have added the comparison graphs of ir_sort::integer_sort for different size of integers and various array lengths with various sorting algorithms of boost to my GitHub[1]. I have also added the explanation of basic working to my GitHub[1] For arrays of large objects, I have made an improvement which is more efficient as compared to any sorting algorithm I have ever tried (including ska_sort, std::sort, boost::sort::spreadsort::integer_sort, boost::sort::pdqsort, boost::sort::spinsort, boost::sort::flat_stable_sort). It is about two times faster than ska_sort, spreadsort, pdqsort and five times faster than std::sort, spinsort, flat_stable_sort.
From my knowledge and the learning's of past six months by working on this sorting project(ir_sort), I have few more optimizations in mind which would improve the sorting speed even more.
I would like to contribute to this organization in view of GSoC(Google Summer of Code) 2019. It would be great if someone could mentor me regarding the improved sorting algorithm that I have written in C++14. [1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort Regards, Fenil Mehta On Sat, Dec 29, 2018 at 2:59 PM degski via Boost <boost@lists.boost.org> wrote:
On Sat, 29 Dec 2018 at 11:16, degski <degski@gmail.com> wrote:
It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use].
Some write-up on "how it works"[2]
degski [1] https://github.com/skarupke/ska_sort [2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ -- *“If something cannot go on forever, it will stop" - Herbert Stein*
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, Jan 20, 2019 at 12:22 PM Fenil Mehta via Boost <boost@lists.boost.org> wrote:
Hi,
I am Fenil Mehta, a 3rd year Computer Science and Engineering student.
In response to the past suggestions I have added the comparison graphs of ir_sort::integer_sort for different size of integers and various array lengths with various sorting algorithms of boost to my GitHub[1]. I have also added the explanation of basic working to my GitHub[1]
For arrays of large objects, I have made an improvement which is more efficient as compared to any sorting algorithm I have ever tried (including ska_sort, std::sort, boost::sort::spreadsort::integer_sort, boost::sort::pdqsort, boost::sort::spinsort, boost::sort::flat_stable_sort). It is about two times faster than ska_sort, spreadsort, pdqsort and five times faster than std::sort, spinsort, flat_stable_sort.
From my knowledge and the learning's of past six months by working on this sorting project(ir_sort), I have few more optimizations in mind which would improve the sorting speed even more.
I would like to contribute to this organization in view of GSoC(Google Summer of Code) 2019. It would be great if someone could mentor me regarding the improved sorting algorithm that I have written in C++14.
[1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort
Regards, Fenil Mehta
On Sat, Dec 29, 2018 at 2:59 PM degski via Boost <boost@lists.boost.org> wrote:
On Sat, 29 Dec 2018 at 11:16, degski <degski@gmail.com> wrote:
It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use].
Some write-up on "how it works"[2]
Your numbers are impressive, but how can you have a sort algorithm that is O(n) complexity? I know that I could go and analyse your code, but it would be easier if you just explained it.
On Sun, Jan 20, 2019 at 12:22 PM Fenil Mehta via Boost <boost@lists.boost.org> wrote:
Hi,
I am Fenil Mehta, a 3rd year Computer Science and Engineering student.
In response to the past suggestions I have added the comparison graphs of ir_sort::integer_sort for different size of integers and various array lengths with various sorting algorithms of boost to my GitHub[1]. I have also added the explanation of basic working to my GitHub[1]
For arrays of large objects, I have made an improvement which is more efficient as compared to any sorting algorithm I have ever tried (including ska_sort, std::sort, boost::sort::spreadsort::integer_sort, boost::sort::pdqsort, boost::sort::spinsort, boost::sort::flat_stable_sort). It is about two times faster than ska_sort, spreadsort, pdqsort and five times faster than std::sort, spinsort, flat_stable_sort.
From my knowledge and the learning's of past six months by working on this sorting project(ir_sort), I have few more optimizations in mind which would improve the sorting speed even more.
I would like to contribute to this organization in view of GSoC(Google Summer of Code) 2019. It would be great if someone could mentor me regarding the improved sorting algorithm that I have written in C++14.
[1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort
Regards, Fenil Mehta
On Sat, Dec 29, 2018 at 2:59 PM degski via Boost <boost@lists.boost.org> wrote:
On Sat, 29 Dec 2018 at 11:16, degski <degski@gmail.com> wrote:
It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use].
Some write-up on "how it works"[2]
degski
Your numbers are impressive, but how can you have a sort algorithm that is O(n) complexity? I know that I could go and analyse your code, but it would be easier if you just explained it. Adrian
Fenil, niedz., 20 sty 2019 o 18:22 użytkownik Fenil Mehta via Boost < boost@lists.boost.org> napisał:
[1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort
Would you care to explain how you algorithm sorts in a linear number of comparisons as you claim in the repository description? Isn't it the case that you have to perform at least O(n * logn) comparisons? Best, Marcin
Regards, Fenil Mehta
On Sat, Dec 29, 2018 at 2:59 PM degski via Boost <boost@lists.boost.org> wrote:
On Sat, 29 Dec 2018 at 11:16, degski <degski@gmail.com> wrote:
It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use].
Some write-up on "how it works"[2]
degski [1] https://github.com/skarupke/ska_sort [2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ -- *“If something cannot go on forever, it will stop" - Herbert Stein*
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, Jan 20, 2019 at 1:13 PM Marcin Copik via Boost <boost@lists.boost.org> wrote:
Fenil,
niedz., 20 sty 2019 o 18:22 użytkownik Fenil Mehta via Boost < boost@lists.boost.org> napisał:
[1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort
Would you care to explain how you algorithm sorts in a linear number of comparisons as you claim in the repository description? Isn't it the case that you have to perform at least O(n * logn) comparisons?
Best, Marcin
Hmmm. Looks like this user is using two different email accounts. "degski" and "Fenil Mehta". The answer is in the post from "degski":
[2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
Still looking through it but looks ingenious. A
On Sun, 20 Jan 2019 at 20:30, Jack Adrian Zappa via Boost < boost@lists.boost.org> wrote:
Hmmm. Looks like this user is using two different email accounts.
No way, Jose! Are you the real Zappa? :-] "degski" and "Fenil Mehta". The answer is in the post from "degski":
[2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
The above link is the description of the development of ska_sort [a radix-sorting algo], over which the OP claims a 2 times speed-up [the graphs on GH don't include ska_sort nor any numbers, though]. My 2 cents is that the measuring method is flawed, 2 different things are being compared or the test-cases favor one over the other. degski -- *“If something cannot go on forever, it will stop" - Herbert Stein*
On 1/20/19 10:11 AM, Marcin Copik via Boost wrote:
Fenil,
niedz., 20 sty 2019 o 18:22 użytkownik Fenil Mehta via Boost < boost@lists.boost.org> napisał:
[1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort
Would you care to explain how you algorithm sorts in a linear number of comparisons as you claim in the repository description? Isn't it the case that you have to perform at least O(n * logn) comparisons?
It is very common knowledge that there are many sorting algorithms which do not require O(n * log n) comparisons. In fact, there are many - including the proposed integer sort - which do no comparisons at all. It's very easy to find information on this. Just google radix sort, postman's sort, among other search terms. Robert Ramey
Best, Marcin
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost <boost@lists.boost.org> wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan https://en.wikipedia.org/wiki/Sagan_standard
The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
Hi Fenil, I am Francisco Tapia, one of the maintainers of the Sort Library. I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code. Yours Francisco Tapia El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost <boost@lists.boost.org
wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan
https://en.wikipedia.org/wiki/Sagan_standard
The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Fenil, Based on the description, this looks like spreadsort without the worst case analysis, and with a new swapping optimization (I know there is room for improvement in the swapping). I expect this algorithm will perform significantly worse than std::sort (or pdqsort) in the worst-case situations, without applying similar worst-case analysis. spreadsort is comparable to std::sort in the worst case distribution for spreadsort because of careful analysis and threshold optimization. If you tweaked the spreadsort constants <https://github.com/boostorg/sort/blob/master/include/boost/sort/spreadsort/detail/constants.hpp> I think you should be able to get comparable performance to your algorithm, minus the impact of your swapping optimization. How does your swapping optimization perform on mostly-sorted data? spreadsort does well in this common case relative to std::sort, which is somewhat tricky with in-place radix sorting. You should try seeing how your algorithm performs on the distributions in https://github.com/boostorg/sort/blob/master/example/alrbreaker.cpp and https://github.com/boostorg/sort/blob/master/example/binaryalrbreaker.cpp, tweaking those to hit your worst case. What's the memory overhead? What's the threshold size at which it starts becoming faster than std::sort and pdqsort? comparison-based sorting is surprisingly fast on small lists of integers that fit on L1 cache. How well does it handle common prefixes in string sorting? string_sort is optimized to handle that case extremely quickly. It's a serious performance issue if you don't optimize for it. I wish more people realized the generality of these algorithms; if you really want a fast sort, you can use spreadsort (or an equivalent algorithm), you just need to define a way to index into the key. This was published a while ago in Engineering Radix Sort, but most people use comparison sorts because they're easier to use (and for most applications, sorting compute time is minor). On Mon, Jan 21, 2019, 3:29 AM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I am Francisco Tapia, one of the maintainers of the Sort Library.
I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code.
Yours
Francisco Tapia
El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost < boost@lists.boost.org
wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan
https://en.wikipedia.org/wiki/Sagan_standard
The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I communicate with this E-mail account only: fenilgmehta@gmail.com I have no other E-mail account. Please forgive me for my mistyped time complexity, I have corrected it to O(nk). I am not quite good at calculating the time complexity. Hence there may be an error in my time complexity but the sorting idea is good. I have been working on my project for the past 6 months and it was for the first time I heard about ska_sort. When I read its implementation, it had already implemented what I was planning to do in the near future. I could not find ska_sort in the Boost library which I had recently installed. If someone could throw some light on this, then it would be greatly appreciated. I completely agree that ska_sort is highly optimized. For all arrays of primary data types(like int, float, char) or small objects(like pair<int,int>) ska_sort performance is the best. However, for arrays of large objects, ir_sort is better. The test cases are generated completely randomly. I do not know the test cases at all when I make the comparison. The source code for test case generation is there on the GitHub[1], you can scrutinize it and a snippet is as follows: // here I pass a vector for arr template<typename T> void fillRandArray(T &arr, const int64_t &low, const int64_t &high, const int64_t &randStart, const int64_t &randEnd) { std::random_device rd; std::mt19937_64 gen(rd()); std::uniform_int_distribution<ArrayIndexType> dis(randStart, randEnd); for (int64_t i = low; i <= high; i++) arr[i] = dis(gen); } As of my claims, let me give the clear details of the input. ir_sort is faster when I tested it for an array of objects of size = 1000*64 bits, and array length = 2000 only. I have to test it for other conditions. Steven, at present I have only implemented the swapping optimization for integers only. ir_sort is in the beginning phase. Once it finalized for integers, I will plan a solution for other data types. I have not looked much at the worst case distribution. At present, I am testing it for random distributions. I will have a look at the worst scenario and mostly sorted data. For memory overhead, it will require two integer arrays of size "n", and probably it can be reduced to a single array of size "n". I agree that these algorithms have been designed keeping generality as the focus. However, generally, objects are indexed based on integers, keeping this in mind I decided to write ir_sort. The reason it is way faster for large object arrays is that I only make "n" swaps to sort the array. I use indexes to reduce the overhead of swapping. I believe the swapping optimization I have written is not limited to ir_sort, it can be used along with other sorting algorithms to improve their running speed for large objects. Francisco, thank you for your quick response. I wait for your feedback. [1] https://github.com/fenilgmehta/Fastest-Integer-Sort/blob/b11ae9ddb3c9cc7e9d1... [2] https://github.com/fenilgmehta/Fastest-Integer-Sort/ Regards, Fenil Mehta On Mon, Jan 21, 2019 at 8:18 PM Steven Ross via Boost <boost@lists.boost.org> wrote:
Fenil,
Based on the description, this looks like spreadsort without the worst case analysis, and with a new swapping optimization (I know there is room for improvement in the swapping). I expect this algorithm will perform significantly worse than std::sort (or pdqsort) in the worst-case situations, without applying similar worst-case analysis. spreadsort is comparable to std::sort in the worst case distribution for spreadsort because of careful analysis and threshold optimization. If you tweaked the spreadsort constants < https://github.com/boostorg/sort/blob/master/include/boost/sort/spreadsort/d...
I think you should be able to get comparable performance to your algorithm, minus the impact of your swapping optimization. How does your swapping optimization perform on mostly-sorted data? spreadsort does well in this common case relative to std::sort, which is somewhat tricky with in-place radix sorting. You should try seeing how your algorithm performs on the distributions in https://github.com/boostorg/sort/blob/master/example/alrbreaker.cpp and https://github.com/boostorg/sort/blob/master/example/binaryalrbreaker.cpp, tweaking those to hit your worst case. What's the memory overhead? What's the threshold size at which it starts becoming faster than std::sort and pdqsort? comparison-based sorting is surprisingly fast on small lists of integers that fit on L1 cache. How well does it handle common prefixes in string sorting? string_sort is optimized to handle that case extremely quickly. It's a serious performance issue if you don't optimize for it.
I wish more people realized the generality of these algorithms; if you really want a fast sort, you can use spreadsort (or an equivalent algorithm), you just need to define a way to index into the key. This was published a while ago in Engineering Radix Sort, but most people use comparison sorts because they're easier to use (and for most applications, sorting compute time is minor).
On Mon, Jan 21, 2019, 3:29 AM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I am Francisco Tapia, one of the maintainers of the Sort Library.
I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code.
Yours
Francisco Tapia
El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost < boost@lists.boost.org
wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan
https://en.wikipedia.org/wiki/Sagan_standard
The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Tue, Jan 22, 2019 at 4:09 AM Fenil Mehta via Boost <boost@lists.boost.org> wrote:
I communicate with this E-mail account only: fenilgmehta@gmail.com I have no other E-mail account.
Please forgive me for my mistyped time complexity, I have corrected it to O(nk). I am not quite good at calculating the time complexity. Hence there may be an error in my time complexity but the sorting idea is good.
I have been working on my project for the past 6 months and it was for the first time I heard about ska_sort. When I read its implementation, it had already implemented what I was planning to do in the near future. I could not find ska_sort in the Boost library which I had recently installed. If someone could throw some light on this, then it would be greatly appreciated. I completely agree that ska_sort is highly optimized. For all arrays of primary data types(like int, float, char) or small objects(like pair<int,int>) ska_sort performance is the best. However, for arrays of large objects, ir_sort is better.
The test cases are generated completely randomly. I do not know the test cases at all when I make the comparison. The source code for test case generation is there on the GitHub[1], you can scrutinize it and a snippet is as follows: // here I pass a vector for arr template<typename T> void fillRandArray(T &arr, const int64_t &low, const int64_t &high, const int64_t &randStart, const int64_t &randEnd) { std::random_device rd; std::mt19937_64 gen(rd()); std::uniform_int_distribution<ArrayIndexType> dis(randStart, randEnd);
for (int64_t i = low; i <= high; i++) arr[i] = dis(gen); }
As of my claims, let me give the clear details of the input. ir_sort is faster when I tested it for an array of objects of size = 1000*64 bits, and array length = 2000 only. I have to test it for other conditions.
I test using this random number generation approach (in addition to the worst-case analysis): https://github.com/boostorg/sort/blob/master/example/randomgen.cpp So that I can vary the range in both the top and bottom 2 bytes of a 4-byte integer. The same data can be cast to 8-byte if you wish. I use this script to run through the various combinations of distributions and different data types: https://github.com/boostorg/sort/blob/master/tune.pl tune.pl is also capable of tuning constants to the processor with the -tune option. The optimal sorting approach varies based on input array size, data distribution, processor, and data type. 2000 randomly-distributed elements should fit in L1 cache and be split evenly by a single radix pass; the optimal approach for more complicated distributions and millions of elements, sorted data, or for 256 elements may be quite different. spreadsort is optimized to provide good performance across all these cases (for 256 elements it just uses pdqsort).
Steven, at present I have only implemented the swapping optimization for integers only. ir_sort is in the beginning phase. Once it finalized for integers, I will plan a solution for other data types. I have not looked much at the worst case distribution. At present, I am testing it for random distributions. I will have a look at the worst scenario and mostly sorted data. For memory overhead, it will require two integer arrays of size "n", and probably it can be reduced to a single array of size "n".
Spreadsort uses just the input array and kilobytes of RAM overhead for the bins. For large amounts of data the RAM overhead can be important. Your swapping approach would probably need to change if you sorted in-place.
I agree that these algorithms have been designed keeping generality as the focus. However, generally, objects are indexed based on integers, keeping this in mind I decided to write ir_sort.
The reason it is way faster for large object arrays is that I only make "n" swaps to sort the array. I use indexes to reduce the overhead of swapping. I believe the swapping optimization I have written is not limited to ir_sort, it can be used along with other sorting algorithms to improve their running speed for large objects.
Francisco, thank you for your quick response. I wait for your feedback.
[1] https://github.com/fenilgmehta/Fastest-Integer-Sort/blob/b11ae9ddb3c9cc7e9d1... [2] https://github.com/fenilgmehta/Fastest-Integer-Sort/
Regards, Fenil Mehta
On Mon, Jan 21, 2019 at 8:18 PM Steven Ross via Boost <boost@lists.boost.org> wrote:
Fenil,
Based on the description, this looks like spreadsort without the worst case analysis, and with a new swapping optimization (I know there is room for improvement in the swapping). I expect this algorithm will perform significantly worse than std::sort (or pdqsort) in the worst-case situations, without applying similar worst-case analysis. spreadsort is comparable to std::sort in the worst case distribution for spreadsort because of careful analysis and threshold optimization. If you tweaked the spreadsort constants < https://github.com/boostorg/sort/blob/master/include/boost/sort/spreadsort/d...
I think you should be able to get comparable performance to your algorithm, minus the impact of your swapping optimization. How does your swapping optimization perform on mostly-sorted data? spreadsort does well in this common case relative to std::sort, which is somewhat tricky with in-place radix sorting. You should try seeing how your algorithm performs on the distributions in https://github.com/boostorg/sort/blob/master/example/alrbreaker.cpp and https://github.com/boostorg/sort/blob/master/example/binaryalrbreaker.cpp, tweaking those to hit your worst case. What's the memory overhead? What's the threshold size at which it starts becoming faster than std::sort and pdqsort? comparison-based sorting is surprisingly fast on small lists of integers that fit on L1 cache. How well does it handle common prefixes in string sorting? string_sort is optimized to handle that case extremely quickly. It's a serious performance issue if you don't optimize for it.
I wish more people realized the generality of these algorithms; if you really want a fast sort, you can use spreadsort (or an equivalent algorithm), you just need to define a way to index into the key. This was published a while ago in Engineering Radix Sort, but most people use comparison sorts because they're easier to use (and for most applications, sorting compute time is minor).
On Mon, Jan 21, 2019, 3:29 AM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I am Francisco Tapia, one of the maintainers of the Sort Library.
I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code.
Yours
Francisco Tapia
El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost < boost@lists.boost.org
wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan
https://en.wikipedia.org/wiki/Sagan_standard
The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi Fenil, I examined and ran your code. About it we have two perspectives - Internal, about the algorithm. The Steven’s opinion is the most qualified about the algorithm. He signed several lacks that must be resolved, before any serious consideration. - External. Test the algorithm and measure the speed, the memory used, The documentation and the code. I had seen a couple of questions 1.- The documentation is really poor. You need to explain questions about the worst case, the memory used. The goal of any documentation is help to the user to understand and run the code. If you write a documentation where explain something, and the final user don’t understand. It is not a good documentation 2.- The organization of the code is messy. You must include in the code a .cpp file. This can be a problem in a separate compilation where several files use your code, and include the .cpp file 3.- In the command line to compile your code don’t use any optimization parameter. It is strange, talk about the speed, and don’t use the optimization 4.- I run your code with the other algorithms of the Boost Sort library 100 000 000 uint64_t random numbers Fastest-Integer-Sort 3.79 secs 1565M used pdq_sort 3.89 secs 785M used spreadsort 4.79 secs 785M used spin_sort 9.60 secs 1175M used flat_stable_sort 10.68 secs 788M used According this your code have a small difference with pdq_sort, but use the double of memory 5.- Many times the data are near sorted. Typically, adding data to the begin or the end of the data sorted, or same element inside is changed. It’s important detect and use this to reduce the time needed. The results obtained was ************************************************************ ** 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 ] spin_sort [ 5 ] flat_stable_sort [ 6 ] timsort [ 7 ] spreadsort [ 8 ] Fastest-Integer-S | | | | | | | | | | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]| [ 7 ]| [ 8 ]| --------------------+------+------+------+------+------+------+------+------+ random | 8.17 | 3.89 |10.17 | 9.60 |10.68 |12.46 | 4.79 | 3.79 | | | | | | | | | | sorted | 1.94 | 0.14 | 2.95 | 0.07 | 0.07 | 0.07 | 0.07 | 0.54 | sorted + 0.1% end | 6.21 | 2.85 | 2.94 | 0.53 | 0.37 | 0.20 | 3.78 | 3.78 | sorted + 1% end |10.65 | 3.33 | 3.07 | 0.69 | 0.50 | 0.32 | 4.02 | 3.76 | sorted + 10% end | 7.64 | 4.12 | 3.91 | 1.47 | 1.40 | 1.35 | 4.79 | 4.12 | | | | | | | | | | sorted + 0.1% mid | 4.70 | 3.20 | 3.14 | 1.97 | 2.54 | 2.25 | 3.78 | 3.79 | sorted + 1% mid | 4.37 | 3.56 | 3.29 | 2.27 | 3.18 | 2.84 | 4.28 | 3.86 | sorted + 10% mid | 6.36 | 4.70 | 5.17 | 4.13 | 5.65 | 6.27 | 5.79 | 4.69 | | | | | | | | | | reverse sorted | 1.46 | 0.28 | 3.30 | 0.14 | 0.14 | 0.14 | 1.47 | 0.54 | rv sorted + 0.1% end| 7.30 | 2.90 | 3.33 | 0.65 | 0.43 | 0.27 | 3.47 | 3.82 | rv sorted + 1% end | 5.09 | 3.32 | 3.38 | 0.79 | 0.56 | 0.39 | 3.78 | 3.82 | rv sorted + 10% end | 4.68 | 4.15 | 4.30 | 1.58 | 1.46 | 1.44 | 4.82 | 4.19 | | | | | | | | | | rv sorted + 0.1% mid| 4.77 | 3.26 | 3.16 | 1.97 | 2.56 | 2.28 | 3.82 | 3.83 | rv sorted + 1% mid | 4.38 | 3.55 | 3.27 | 2.29 | 3.19 | 2.85 | 4.29 | 3.86 | rv sorted + 10% mid | 6.37 | 4.62 | 5.08 | 4.11 | 5.53 | 6.19 | 5.64 | 4.57 | --------------------+------+------+------+------+------+------+------+------+ jue ene 31 15:06:13 CET 2019 . If you admit my guidance. You have the most important qualities, energy and initiative. But must learn some important questions. Be rigorous and strict, check deeply your code. Is someone find a fail in your code, that you didn’t detect, must be unacceptable for you. If you are looking for something to work, consider that if many people is working about it, except if you have a brilliant new idea, you will discover, after a lot of work, that your results are similar. Study, read, learn, and when the adequate idea pass in front your eyes, catch it, and work hard. Yours Francisco Tapia El vie., 25 ene. 2019 a las 1:40, Steven Ross via Boost (< boost@lists.boost.org>) escribió:
On Tue, Jan 22, 2019 at 4:09 AM Fenil Mehta via Boost <boost@lists.boost.org> wrote:
I communicate with this E-mail account only: fenilgmehta@gmail.com I have no other E-mail account.
Please forgive me for my mistyped time complexity, I have corrected it to O(nk). I am not quite good at calculating the time complexity. Hence
may be an error in my time complexity but the sorting idea is good.
I have been working on my project for the past 6 months and it was for
there the
first time I heard about ska_sort. When I read its implementation, it had already implemented what I was planning to do in the near future. I could not find ska_sort in the Boost library which I had recently installed. If someone could throw some light on this, then it would be greatly appreciated. I completely agree that ska_sort is highly optimized. For all arrays of primary data types(like int, float, char) or small objects(like pair<int,int>) ska_sort performance is the best. However, for arrays of large objects, ir_sort is better.
The test cases are generated completely randomly. I do not know the test cases at all when I make the comparison. The source code for test case generation is there on the GitHub[1], you can scrutinize it and a snippet is as follows: // here I pass a vector for arr template<typename T> void fillRandArray(T &arr, const int64_t &low, const int64_t &high, const int64_t &randStart, const int64_t &randEnd) { std::random_device rd; std::mt19937_64 gen(rd()); std::uniform_int_distribution<ArrayIndexType> dis(randStart, randEnd);
for (int64_t i = low; i <= high; i++) arr[i] = dis(gen); }
As of my claims, let me give the clear details of the input. ir_sort is faster when I tested it for an array of objects of size = 1000*64 bits, and array length = 2000 only. I have to test it for other conditions.
I test using this random number generation approach (in addition to the worst-case analysis): https://github.com/boostorg/sort/blob/master/example/randomgen.cpp
So that I can vary the range in both the top and bottom 2 bytes of a 4-byte integer. The same data can be cast to 8-byte if you wish. I use this script to run through the various combinations of distributions and different data types: https://github.com/boostorg/sort/blob/master/tune.pl tune.pl is also capable of tuning constants to the processor with the -tune option.
The optimal sorting approach varies based on input array size, data distribution, processor, and data type. 2000 randomly-distributed elements should fit in L1 cache and be split evenly by a single radix pass; the optimal approach for more complicated distributions and millions of elements, sorted data, or for 256 elements may be quite different. spreadsort is optimized to provide good performance across all these cases (for 256 elements it just uses pdqsort).
Steven, at present I have only implemented the swapping optimization for integers only. ir_sort is in the beginning phase. Once it finalized for integers, I will plan a solution for other data types. I have not looked much at the worst case distribution. At present, I am testing it for random distributions. I will have a look at the worst scenario and mostly sorted data. For memory overhead, it will require two integer arrays of size "n", and probably it can be reduced to a single array of size "n".
Spreadsort uses just the input array and kilobytes of RAM overhead for the bins. For large amounts of data the RAM overhead can be important. Your swapping approach would probably need to change if you sorted in-place.
I agree that these algorithms have been designed keeping generality as the focus. However, generally, objects are indexed based on integers, keeping this in mind I decided to write ir_sort.
The reason it is way faster for large object arrays is that I only make "n" swaps to sort the array. I use indexes to reduce the overhead of swapping. I believe the swapping optimization I have written is not limited to ir_sort, it can be used along with other sorting algorithms to improve their running speed for large objects.
Francisco, thank you for your quick response. I wait for your feedback.
[1]
[2] https://github.com/fenilgmehta/Fastest-Integer-Sort/
Regards, Fenil Mehta
On Mon, Jan 21, 2019 at 8:18 PM Steven Ross via Boost < boost@lists.boost.org> wrote:
Fenil,
Based on the description, this looks like spreadsort without the worst case analysis, and with a new swapping optimization (I know there is room for improvement in the swapping). I expect this algorithm will perform significantly worse than std::sort (or pdqsort) in the worst-case situations, without applying similar worst-case analysis. spreadsort is comparable to std::sort in the worst case distribution for spreadsort because of careful analysis and threshold optimization. If you tweaked the spreadsort constants <
https://github.com/boostorg/sort/blob/master/include/boost/sort/spreadsort/d...
I think you should be able to get comparable performance to your algorithm, minus the impact of your swapping optimization. How does your swapping optimization perform on mostly-sorted data? spreadsort does well in this common case relative to std::sort, which is somewhat tricky with in-place radix sorting. You should try seeing how your algorithm performs on the distributions in https://github.com/boostorg/sort/blob/master/example/alrbreaker.cpp and
https://github.com/boostorg/sort/blob/master/example/binaryalrbreaker.cpp,
tweaking those to hit your worst case. What's the memory overhead? What's the threshold size at which it starts becoming faster than std::sort and pdqsort? comparison-based sorting is surprisingly fast on small
https://github.com/fenilgmehta/Fastest-Integer-Sort/blob/b11ae9ddb3c9cc7e9d1... lists
of integers that fit on L1 cache. How well does it handle common prefixes in string sorting? string_sort is optimized to handle that case extremely quickly. It's a serious performance issue if you don't optimize for it.
I wish more people realized the generality of these algorithms; if you really want a fast sort, you can use spreadsort (or an equivalent algorithm), you just need to define a way to index into the key. This was published a while ago in Engineering Radix Sort, but most people use comparison sorts because they're easier to use (and for most applications, sorting compute time is minor).
On Mon, Jan 21, 2019, 3:29 AM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I am Francisco Tapia, one of the maintainers of the Sort Library.
I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code.
Yours
Francisco Tapia
El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost < boost@lists.boost.org
wrote:
I have written a sorting algorithm which is way faster than std::sort for all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan
https://en.wikipedia.org/wiki/Sagan_standard
The link is as follows: https://github.com/fenilgmehta/Fastest-Integer-Sort
Some guidance would be appreciated on how to improve the project structure and the steps to get it included in boost.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Thu, 31 Jan 2019 at 19:16, Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
I examined and ran your code.
Would it be possible to add ska_sort [1] to your speed-test and publish the results? Then we would have a pretty good shoot-down! degski [1] : https://github.com/skarupke/ska_sort -- *“If something cannot go on forever, it will stop" - Herbert Stein*
Thank you for your detailed analysis. I will review your feedback and take corrective actions as required. If you don't mind, can you share the script or the C++ program you have used to test the performance of all the algorithms for various input array conditions so that I can do the same in future before any review requests. Please tell how did you measure the memory usage and running time for each algorithm. Regards, Fenil Mehta On Thu, Jan 31, 2019 at 10:46 PM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I examined and ran your code. About it we have two perspectives
- Internal, about the algorithm. The Steven’s opinion is the most qualified about the algorithm. He signed several lacks that must be resolved, before any serious consideration. - External. Test the algorithm and measure the speed, the memory used, The documentation and the code. I had seen a couple of questions
1.- The documentation is really poor. You need to explain questions about the worst case, the memory used. The goal of any documentation is help to the user to understand and run the code. If you write a documentation where explain something, and the final user don’t understand. It is not a good documentation
2.- The organization of the code is messy. You must include in the code a .cpp file. This can be a problem in a separate compilation where several files use your code, and include the .cpp file
3.- In the command line to compile your code don’t use any optimization parameter. It is strange, talk about the speed, and don’t use the optimization
4.- I run your code with the other algorithms of the Boost Sort library
100 000 000 uint64_t random numbers
Fastest-Integer-Sort 3.79 secs 1565M used
pdq_sort 3.89 secs 785M used
spreadsort 4.79 secs 785M used
spin_sort 9.60 secs 1175M used
flat_stable_sort 10.68 secs 788M used
According this your code have a small difference with pdq_sort, but use the double of memory
5.- Many times the data are near sorted. Typically, adding data to the begin or the end of the data sorted, or same element inside is changed. It’s important detect and use this to reduce the time needed.
The results obtained was
************************************************************
** 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 ] spin_sort [ 5 ] flat_stable_sort [ 6 ] timsort
[ 7 ] spreadsort [ 8 ] Fastest-Integer-S
| | | | | | | | |
| [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]| [ 7 ]| [ 8 ]|
--------------------+------+------+------+------+------+------+------+------+
random | 8.17 | 3.89 |10.17 | 9.60 |10.68 |12.46 | 4.79 | 3.79 |
| | | | | | | | |
sorted | 1.94 | 0.14 | 2.95 | 0.07 | 0.07 | 0.07 | 0.07 | 0.54 |
sorted + 0.1% end | 6.21 | 2.85 | 2.94 | 0.53 | 0.37 | 0.20 | 3.78 | 3.78 |
sorted + 1% end |10.65 | 3.33 | 3.07 | 0.69 | 0.50 | 0.32 | 4.02 | 3.76 |
sorted + 10% end | 7.64 | 4.12 | 3.91 | 1.47 | 1.40 | 1.35 | 4.79 | 4.12 |
| | | | | | | | |
sorted + 0.1% mid | 4.70 | 3.20 | 3.14 | 1.97 | 2.54 | 2.25 | 3.78 | 3.79 |
sorted + 1% mid | 4.37 | 3.56 | 3.29 | 2.27 | 3.18 | 2.84 | 4.28 | 3.86 |
sorted + 10% mid | 6.36 | 4.70 | 5.17 | 4.13 | 5.65 | 6.27 | 5.79 | 4.69 |
| | | | | | | | |
reverse sorted | 1.46 | 0.28 | 3.30 | 0.14 | 0.14 | 0.14 | 1.47 | 0.54 |
rv sorted + 0.1% end| 7.30 | 2.90 | 3.33 | 0.65 | 0.43 | 0.27 | 3.47 | 3.82 |
rv sorted + 1% end | 5.09 | 3.32 | 3.38 | 0.79 | 0.56 | 0.39 | 3.78 | 3.82 |
rv sorted + 10% end | 4.68 | 4.15 | 4.30 | 1.58 | 1.46 | 1.44 | 4.82 | 4.19 |
| | | | | | | | |
rv sorted + 0.1% mid| 4.77 | 3.26 | 3.16 | 1.97 | 2.56 | 2.28 | 3.82 | 3.83 |
rv sorted + 1% mid | 4.38 | 3.55 | 3.27 | 2.29 | 3.19 | 2.85 | 4.29 | 3.86 |
rv sorted + 10% mid | 6.37 | 4.62 | 5.08 | 4.11 | 5.53 | 6.19 | 5.64 | 4.57 |
--------------------+------+------+------+------+------+------+------+------+
jue ene 31 15:06:13 CET 2019
.
If you admit my guidance. You have the most important qualities, energy and initiative. But must learn some important questions. Be rigorous and strict, check deeply your code. Is someone find a fail in your code, that you didn’t detect, must be unacceptable for you.
If you are looking for something to work, consider that if many people is working about it, except if you have a brilliant new idea, you will discover, after a lot of work, that your results are similar. Study, read, learn, and when the adequate idea pass in front your eyes, catch it, and work hard.
Yours
Francisco Tapia
El vie., 25 ene. 2019 a las 1:40, Steven Ross via Boost (< boost@lists.boost.org>) escribió:
On Tue, Jan 22, 2019 at 4:09 AM Fenil Mehta via Boost <boost@lists.boost.org> wrote:
I communicate with this E-mail account only: fenilgmehta@gmail.com I have no other E-mail account.
Please forgive me for my mistyped time complexity, I have corrected it
O(nk). I am not quite good at calculating the time complexity. Hence
may be an error in my time complexity but the sorting idea is good.
I have been working on my project for the past 6 months and it was for
to there the
first time I heard about ska_sort. When I read its implementation, it had already implemented what I was planning to do in the near future. I could not find ska_sort in the Boost library which I had recently installed. If someone could throw some light on this, then it would be greatly appreciated. I completely agree that ska_sort is highly optimized. For all arrays of primary data types(like int, float, char) or small objects(like pair<int,int>) ska_sort performance is the best. However, for arrays of large objects, ir_sort is better.
The test cases are generated completely randomly. I do not know the test cases at all when I make the comparison. The source code for test case generation is there on the GitHub[1], you can scrutinize it and a snippet is as follows: // here I pass a vector for arr template<typename T> void fillRandArray(T &arr, const int64_t &low, const int64_t &high, const int64_t &randStart, const int64_t &randEnd) { std::random_device rd; std::mt19937_64 gen(rd()); std::uniform_int_distribution<ArrayIndexType> dis(randStart, randEnd);
for (int64_t i = low; i <= high; i++) arr[i] = dis(gen); }
As of my claims, let me give the clear details of the input. ir_sort is faster when I tested it for an array of objects of size = 1000*64 bits, and array length = 2000 only. I have to test it for other conditions.
I test using this random number generation approach (in addition to the worst-case analysis): https://github.com/boostorg/sort/blob/master/example/randomgen.cpp
So that I can vary the range in both the top and bottom 2 bytes of a 4-byte integer. The same data can be cast to 8-byte if you wish. I use this script to run through the various combinations of distributions and different data types: https://github.com/boostorg/sort/blob/master/tune.pl tune.pl is also capable of tuning constants to the processor with the -tune option.
The optimal sorting approach varies based on input array size, data distribution, processor, and data type. 2000 randomly-distributed elements should fit in L1 cache and be split evenly by a single radix pass; the optimal approach for more complicated distributions and millions of elements, sorted data, or for 256 elements may be quite different. spreadsort is optimized to provide good performance across all these cases (for 256 elements it just uses pdqsort).
Steven, at present I have only implemented the swapping optimization
for
integers only. ir_sort is in the beginning phase. Once it finalized for integers, I will plan a solution for other data types. I have not looked much at the worst case distribution. At present, I am testing it for random distributions. I will have a look at the worst scenario and mostly sorted data. For memory overhead, it will require two integer arrays of size "n", and probably it can be reduced to a single array of size "n".
Spreadsort uses just the input array and kilobytes of RAM overhead for the bins. For large amounts of data the RAM overhead can be important. Your swapping approach would probably need to change if you sorted in-place.
I agree that these algorithms have been designed keeping generality as the focus. However, generally, objects are indexed based on integers, keeping this in mind I decided to write ir_sort.
The reason it is way faster for large object arrays is that I only make "n" swaps to sort the array. I use indexes to reduce the overhead of swapping. I believe the swapping optimization I have written is not limited to ir_sort, it can be used along with other sorting algorithms to improve their running speed for large objects.
Francisco, thank you for your quick response. I wait for your feedback.
[1]
https://github.com/fenilgmehta/Fastest-Integer-Sort/blob/b11ae9ddb3c9cc7e9d1...
[2] https://github.com/fenilgmehta/Fastest-Integer-Sort/
Regards, Fenil Mehta
On Mon, Jan 21, 2019 at 8:18 PM Steven Ross via Boost < boost@lists.boost.org> wrote:
Fenil,
Based on the description, this looks like spreadsort without the worst case analysis, and with a new swapping optimization (I know there is room for improvement in the swapping). I expect this algorithm will perform significantly worse than std::sort (or pdqsort) in the worst-case situations, without applying similar worst-case analysis. spreadsort is comparable to std::sort in the worst case distribution for spreadsort because of careful analysis and threshold optimization. If you tweaked the spreadsort constants <
https://github.com/boostorg/sort/blob/master/include/boost/sort/spreadsort/d...
I think you should be able to get comparable performance to your algorithm, minus the impact of your swapping optimization. How does your swapping optimization perform on mostly-sorted data? spreadsort does well in this common case relative to std::sort, which is somewhat tricky with in-place radix sorting. You should try seeing how your algorithm performs on the distributions in https://github.com/boostorg/sort/blob/master/example/alrbreaker.cpp and
tweaking those to hit your worst case. What's the memory overhead? What's the threshold size at which it starts becoming faster than std::sort and pdqsort? comparison-based sorting is surprisingly fast on small lists of integers that fit on L1 cache. How well does it handle common prefixes in string sorting? string_sort is optimized to handle that case extremely quickly. It's a serious performance issue if you don't optimize for it.
I wish more people realized the generality of these algorithms; if you really want a fast sort, you can use spreadsort (or an equivalent algorithm), you just need to define a way to index into the key. This was published a while ago in Engineering Radix Sort, but most people use comparison sorts because they're easier to use (and for most applications, sorting compute time is minor).
On Mon, Jan 21, 2019, 3:29 AM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I am Francisco Tapia, one of the maintainers of the Sort Library.
I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code.
Yours
Francisco Tapia
El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost < boost@lists.boost.org > wrote:
> I have written a sorting algorithm which is way faster than std::sort for > all array size.
"Extraordinary claims require extraordinary evidence" - Carl Sagan
https://en.wikipedia.org/wiki/Sagan_standard
> The link is as follows: > https://github.com/fenilgmehta/Fastest-Integer-Sort > > Some guidance would be appreciated on how to improve the
https://github.com/boostorg/sort/blob/master/example/binaryalrbreaker.cpp, project
structure > and the steps to get it included in boost. > > Regards, > Fenil Mehta > > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost >
-- Richard Hodges hodges.r@gmail.com office: +442032898513 home: +376841522 mobile: +376380212 (this will be *expensive* outside Andorra!) skype: madmongo facebook: hodges.r
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The results con ska_sort are in the attached file numbers_02.txt I say you the same things as Fenil. This is an external test of the algorithm. The internal test is other question very different, and who have more knowledge about these algorithms is, undoubtedly, Steven The memory used by ska_sort to sort 100000000 uint64_t numbers is 784 MB. To measure the memory used by a program in Linux /usr/bin/time -f "%M KB used"./benchmark_ska_sort_numbers I didn't find any similar in Windows. I see the task manager, and take the highest value in the memory used field. ( if someone knows how to do, it will be appreciate) To test the code, change the program benchmark_numbers of the library with the provided in the message. Modify the script runGCC_benchmark_numbers.sh and add the path to the folder of your code. The code is very easy to read and understand, modify it as you prefer. The results of this program, on my machine are in the file numbers_02.txt attached to this file. My machine is - Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz - 6 cores, 12 threads - Caché L1d: 32K - Caché L1i: 32K - Caché L2: 256K - Caché L3: 15360K Different machines implies different results El dom., 3 feb. 2019 a las 14:24, Fenil Mehta via Boost (< boost@lists.boost.org>) escribió:
Thank you for your detailed analysis. I will review your feedback and take corrective actions as required.
If you don't mind, can you share the script or the C++ program you have used to test the performance of all the algorithms for various input array conditions so that I can do the same in future before any review requests. Please tell how did you measure the memory usage and running time for each algorithm.
Regards, Fenil Mehta
On Thu, Jan 31, 2019 at 10:46 PM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I examined and ran your code. About it we have two perspectives
- Internal, about the algorithm. The Steven’s opinion is the most qualified about the algorithm. He signed several lacks that must be resolved, before any serious consideration. - External. Test the algorithm and measure the speed, the memory used, The documentation and the code. I had seen a couple of questions
1.- The documentation is really poor. You need to explain questions about the worst case, the memory used. The goal of any documentation is help to the user to understand and run the code. If you write a documentation where explain something, and the final user don’t understand. It is not a good documentation
2.- The organization of the code is messy. You must include in the code a .cpp file. This can be a problem in a separate compilation where several files use your code, and include the .cpp file
3.- In the command line to compile your code don’t use any optimization parameter. It is strange, talk about the speed, and don’t use the optimization
4.- I run your code with the other algorithms of the Boost Sort library
100 000 000 uint64_t random numbers
Fastest-Integer-Sort 3.79 secs 1565M used
pdq_sort 3.89 secs 785M used
spreadsort 4.79 secs 785M used
spin_sort 9.60 secs 1175M used
flat_stable_sort 10.68 secs 788M used
According this your code have a small difference with pdq_sort, but use the double of memory
5.- Many times the data are near sorted. Typically, adding data to the begin or the end of the data sorted, or same element inside is changed. It’s important detect and use this to reduce the time needed.
The results obtained was
************************************************************
** 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 ] spin_sort [ 5 ] flat_stable_sort [ 6 ] timsort
[ 7 ] spreadsort [ 8 ] Fastest-Integer-S
| | | | | | | | |
| [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]| [ 7 ]| [ 8 ]|
--------------------+------+------+------+------+------+------+------+------+
random | 8.17 | 3.89 |10.17 | 9.60 |10.68 |12.46 | 4.79 |
3.79
|
| | | | | | | | |
sorted | 1.94 | 0.14 | 2.95 | 0.07 | 0.07 | 0.07 | 0.07 | 0.54 |
sorted + 0.1% end | 6.21 | 2.85 | 2.94 | 0.53 | 0.37 | 0.20 | 3.78 | 3.78 |
sorted + 1% end |10.65 | 3.33 | 3.07 | 0.69 | 0.50 | 0.32 | 4.02 | 3.76 |
sorted + 10% end | 7.64 | 4.12 | 3.91 | 1.47 | 1.40 | 1.35 | 4.79 | 4.12 |
| | | | | | | | |
sorted + 0.1% mid | 4.70 | 3.20 | 3.14 | 1.97 | 2.54 | 2.25 | 3.78 | 3.79 |
sorted + 1% mid | 4.37 | 3.56 | 3.29 | 2.27 | 3.18 | 2.84 | 4.28 | 3.86 |
sorted + 10% mid | 6.36 | 4.70 | 5.17 | 4.13 | 5.65 | 6.27 | 5.79 | 4.69 |
| | | | | | | | |
reverse sorted | 1.46 | 0.28 | 3.30 | 0.14 | 0.14 | 0.14 | 1.47 | 0.54 |
rv sorted + 0.1% end| 7.30 | 2.90 | 3.33 | 0.65 | 0.43 | 0.27 | 3.47 | 3.82 |
rv sorted + 1% end | 5.09 | 3.32 | 3.38 | 0.79 | 0.56 | 0.39 | 3.78 | 3.82 |
rv sorted + 10% end | 4.68 | 4.15 | 4.30 | 1.58 | 1.46 | 1.44 | 4.82 | 4.19 |
| | | | | | | | |
rv sorted + 0.1% mid| 4.77 | 3.26 | 3.16 | 1.97 | 2.56 | 2.28 | 3.82 | 3.83 |
rv sorted + 1% mid | 4.38 | 3.55 | 3.27 | 2.29 | 3.19 | 2.85 | 4.29 | 3.86 |
rv sorted + 10% mid | 6.37 | 4.62 | 5.08 | 4.11 | 5.53 | 6.19 | 5.64 | 4.57 |
--------------------+------+------+------+------+------+------+------+------+
jue ene 31 15:06:13 CET 2019
.
If you admit my guidance. You have the most important qualities, energy
and
initiative. But must learn some important questions. Be rigorous and strict, check deeply your code. Is someone find a fail in your code, that you didn’t detect, must be unacceptable for you.
If you are looking for something to work, consider that if many people is working about it, except if you have a brilliant new idea, you will discover, after a lot of work, that your results are similar. Study, read, learn, and when the adequate idea pass in front your eyes, catch it, and work hard.
Yours
Francisco Tapia
El vie., 25 ene. 2019 a las 1:40, Steven Ross via Boost (< boost@lists.boost.org>) escribió:
On Tue, Jan 22, 2019 at 4:09 AM Fenil Mehta via Boost <boost@lists.boost.org> wrote:
I communicate with this E-mail account only: fenilgmehta@gmail.com I have no other E-mail account.
Please forgive me for my mistyped time complexity, I have corrected
O(nk). I am not quite good at calculating the time complexity. Hence
may be an error in my time complexity but the sorting idea is good.
I have been working on my project for the past 6 months and it was for
it to there the
first time I heard about ska_sort. When I read its implementation, it had already implemented what I was planning to do in the near future. I could not find ska_sort in the Boost library which I had recently installed. If someone could throw some light on this, then it would be greatly appreciated. I completely agree that ska_sort is highly optimized. For all arrays of primary data types(like int, float, char) or small objects(like pair<int,int>) ska_sort performance is the best. However, for arrays of large objects, ir_sort is better.
The test cases are generated completely randomly. I do not know the test cases at all when I make the comparison. The source code for test case generation is there on the GitHub[1], you can scrutinize it and a snippet is as follows: // here I pass a vector for arr template<typename T> void fillRandArray(T &arr, const int64_t &low, const int64_t &high, const int64_t &randStart, const int64_t &randEnd) { std::random_device rd; std::mt19937_64 gen(rd()); std::uniform_int_distribution<ArrayIndexType> dis(randStart, randEnd);
for (int64_t i = low; i <= high; i++) arr[i] = dis(gen); }
As of my claims, let me give the clear details of the input. ir_sort is faster when I tested it for an array of objects of size = 1000*64 bits, and array length = 2000 only. I have to test it for other conditions.
I test using this random number generation approach (in addition to the worst-case analysis): https://github.com/boostorg/sort/blob/master/example/randomgen.cpp
So that I can vary the range in both the top and bottom 2 bytes of a 4-byte integer. The same data can be cast to 8-byte if you wish. I use this script to run through the various combinations of distributions and different data types: https://github.com/boostorg/sort/blob/master/tune.pl tune.pl is also capable of tuning constants to the processor with the -tune option.
The optimal sorting approach varies based on input array size, data distribution, processor, and data type. 2000 randomly-distributed elements should fit in L1 cache and be split evenly by a single radix pass; the optimal approach for more complicated distributions and millions of elements, sorted data, or for 256 elements may be quite different. spreadsort is optimized to provide good performance across all these cases (for 256 elements it just uses pdqsort).
Steven, at present I have only implemented the swapping optimization
for
integers only. ir_sort is in the beginning phase. Once it finalized for integers, I will plan a solution for other data types. I have not looked much at the worst case distribution. At present, I am testing it for random distributions. I will have a look at the worst scenario and mostly sorted data. For memory overhead, it will require two integer arrays of size "n", and probably it can be reduced to a single array of size "n".
Spreadsort uses just the input array and kilobytes of RAM overhead for the bins. For large amounts of data the RAM overhead can be important. Your swapping approach would probably need to change if you sorted in-place.
I agree that these algorithms have been designed keeping generality as the focus. However, generally, objects are indexed based on integers, keeping this in mind I decided to write ir_sort.
The reason it is way faster for large object arrays is that I only make "n" swaps to sort the array. I use indexes to reduce the overhead of swapping. I believe the swapping optimization I have written is not limited to ir_sort, it can be used along with other sorting algorithms to improve their running speed for large objects.
Francisco, thank you for your quick response. I wait for your feedback.
[1]
https://github.com/fenilgmehta/Fastest-Integer-Sort/blob/b11ae9ddb3c9cc7e9d1...
[2] https://github.com/fenilgmehta/Fastest-Integer-Sort/
Regards, Fenil Mehta
On Mon, Jan 21, 2019 at 8:18 PM Steven Ross via Boost < boost@lists.boost.org> wrote:
Fenil,
Based on the description, this looks like spreadsort without the worst case analysis, and with a new swapping optimization (I know there is room for improvement in the swapping). I expect this algorithm will perform significantly worse than std::sort (or pdqsort) in the worst-case situations, without applying similar worst-case analysis. spreadsort is comparable to std::sort in the worst case distribution for spreadsort because of careful analysis and threshold optimization. If you tweaked the spreadsort constants <
https://github.com/boostorg/sort/blob/master/include/boost/sort/spreadsort/d...
I think you should be able to get comparable performance to your algorithm, minus the impact of your swapping optimization. How does your swapping optimization perform on mostly-sorted data? spreadsort does well in this common case relative to std::sort, which is somewhat tricky with in-place radix sorting. You should try seeing how your algorithm performs on the distributions in
https://github.com/boostorg/sort/blob/master/example/alrbreaker.cpp and
https://github.com/boostorg/sort/blob/master/example/binaryalrbreaker.cpp,
tweaking those to hit your worst case. What's the memory overhead? What's the threshold size at which it starts becoming faster than std::sort and pdqsort? comparison-based sorting is surprisingly fast on small lists of integers that fit on L1 cache. How well does it handle common prefixes in string sorting? string_sort is optimized to handle that case extremely quickly. It's a serious performance issue if you don't optimize for it.
I wish more people realized the generality of these algorithms; if you really want a fast sort, you can use spreadsort (or an equivalent algorithm), you just need to define a way to index into the key. This was published a while ago in Engineering Radix Sort, but most people use comparison sorts because they're easier to use (and for most applications, sorting compute time is minor).
On Mon, Jan 21, 2019, 3:29 AM Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
Hi Fenil,
I am Francisco Tapia, one of the maintainers of the Sort Library.
I had been watching your code, and find it interesting. But give me a week to say you something. These days I am very busy, and I expect to have time the next weekend, and examine and test your code.
Yours
Francisco Tapia
El lun., 21 ene. 2019 a las 8:41, Richard Hodges via Boost (< boost@lists.boost.org>) escribió:
> On Sat, 29 Dec 2018 at 03:36, Fenil Mehta via Boost < boost@lists.boost.org > > > wrote: > > > I have written a sorting algorithm which is way faster than std::sort for > > all array size. > > > "Extraordinary claims require extraordinary evidence" - Carl Sagan > > https://en.wikipedia.org/wiki/Sagan_standard > > > > > > The link is as follows: > > https://github.com/fenilgmehta/Fastest-Integer-Sort > > > > Some guidance would be appreciated on how to improve the project > structure > > and the steps to get it included in boost. > > > > Regards, > > Fenil Mehta > > > > _______________________________________________ > > Unsubscribe & other changes: > > http://lists.boost.org/mailman/listinfo.cgi/boost > > > > > -- > Richard Hodges > hodges.r@gmail.com > office: +442032898513 > home: +376841522 > mobile: +376380212 (this will be *expensive* outside Andorra!) > skype: madmongo > facebook: hodges.r > > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost >
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sat, 9 Feb 2019 at 14:39, Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
The results con ska_sort are in the attached file numbers_02.txt
Thanks for adding this [and it was worthwhile I would say], this is a great table and shows ska_sort is weak on sorted data [maybe that's fixable], but otherwise better than [Boost] Spreadsort and Fastest-Integer-Sort [sic] and overall fastest on random data. I say you the same things as Fenil. This is an external test of the
algorithm. The internal test is other question very different ...
I don't understand why the "internal test" [unless you mean testing for bugs] has any relevance. degski PS: Please don't top-post, it's just so messy. -- *“If something cannot go on forever, it will stop" - Herbert Stein*
On Sat, Feb 9, 2019 at 11:45 PM degski via Boost <boost@lists.boost.org> wrote:
On Sat, 9 Feb 2019 at 14:39, Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
The results con ska_sort are in the attached file numbers_02.txt
Thanks for adding this [and it was worthwhile I would say], this is a great table and shows ska_sort is weak on sorted data [maybe that's fixable], but otherwise better than [Boost] Spreadsort and Fastest-Integer-Sort [sic] and overall fastest on random data.
I say you the same things as Fenil. This is an external test of the
algorithm. The internal test is other question very different ...
I don't understand why the "internal test" [unless you mean testing for bugs] has any relevance.
It looks like ska_sort is a radix sort designed mostly for the best-case, and that if you feed it the alrbreaker or binaryalrbreaker distributions it will perform poorly (though not as poorly as radix implementations with no fallback or that fallback to insertionsort). There might be some counting and swapping optimizations here to copy into spreadsort (I see block operations), though those might not work if the items being sorted are references or pointers. Mostly-sorted data is a common case to take seriously, and it took only modest tweaking of spreadsort to do well there. Based on Francisco's numbers, I should retune spreadsort to take advantage of the higher speed of pdqsort vs std::sort, at least if I want to optimize for 64-bit integer sorting on modern processors. https://www.boost.org/doc/libs/1_67_0/boost/sort/spreadsort/detail/constants... A higher log_min_split_count (especially) and log_finishing_count is probably appropriate.
degski PS: Please don't top-post, it's just so messy. -- *“If something cannot go on forever, it will stop" - Herbert Stein*
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
While working on the corrections suggested on my sorting project, I tried to test the swapping optimization on timsort and compared it with other sorting algorithms. I used "benchmark_objects.cpp" file in the boost library for the testing purpose. I have attached the results in this email. Summary - When arrays comparison is done by calculating the sum of all the numbers of the array, following was the result: 1) timsort with swapping optimization gives the best result, total time = 17.3, average time = 1.15 2) flat_stable_sort gave the second best result, total time = 33 seconds, average time = 2.2 seconds When arrays comparison is done between the first element of the array, as a key, following was the result: 1) timsort with swapping optimization gives the best result, total time = 3.52 seconds, average time = 0.23 seconds 2) pdqsort gave the second best result, total time = 4.6 seconds, average time = 0.31 seconds I have not yet pushed the swapping function on my GitHub. Please let me know if any queries. Regards, Fenil Mehta On Tue, Feb 12, 2019 at 9:21 AM Steven Ross via Boost <boost@lists.boost.org> wrote:
On Sat, Feb 9, 2019 at 11:45 PM degski via Boost <boost@lists.boost.org> wrote:
On Sat, 9 Feb 2019 at 14:39, Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
The results con ska_sort are in the attached file numbers_02.txt
Thanks for adding this [and it was worthwhile I would say], this is a
great
table and shows ska_sort is weak on sorted data [maybe that's fixable], but otherwise better than [Boost] Spreadsort and Fastest-Integer-Sort [sic] and overall fastest on random data.
I say you the same things as Fenil. This is an external test of the
algorithm. The internal test is other question very different ...
I don't understand why the "internal test" [unless you mean testing for bugs] has any relevance.
It looks like ska_sort is a radix sort designed mostly for the best-case, and that if you feed it the alrbreaker or binaryalrbreaker distributions it will perform poorly (though not as poorly as radix implementations with no fallback or that fallback to insertionsort). There might be some counting and swapping optimizations here to copy into spreadsort (I see block operations), though those might not work if the items being sorted are references or pointers.
Mostly-sorted data is a common case to take seriously, and it took only modest tweaking of spreadsort to do well there.
Based on Francisco's numbers, I should retune spreadsort to take advantage of the higher speed of pdqsort vs std::sort, at least if I want to optimize for 64-bit integer sorting on modern processors.
https://www.boost.org/doc/libs/1_67_0/boost/sort/spreadsort/detail/constants... A higher log_min_split_count (especially) and log_finishing_count is probably appropriate.
degski PS: Please don't top-post, it's just so messy. -- *“If something cannot go on forever, it will stop" - Herbert Stein*
_______________________________________________ Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (11)
-
Andrey Semashev -
degski -
Fenil Mehta -
Francisco José Tapia -
Frédéric -
Jack Adrian Zappa -
Marc Glisse -
Marcin Copik -
Richard Hodges -
Robert Ramey -
Steven Ross