4 ms·

In the source code, it is not apparent where the size restriction comes from. It seems to me that it can be easily modified to work with any data types. Maybe I

by acmj 5y ago

In the source code, it is not apparent where the size restriction comes from. It seems to me that it can be easily modified to work with any data types. Maybe I am wrong. I am more concerned with this sentence: > Blitsort's performance is similar to that of quadsort as long as the auxiliary memory is greater or equal to the square root of the array being sorted, which comes out at 262,144 elements with the default stack of 512 elements. Performance on larger arrays degrades marginally. I wonder what "marginally" means here. What if we sort 10 million integers?

nuclearnice3 5y ago
Is the included bench.c the right way to answer that question? 1m random dist size 128 avg qsort 0.206549 blitsort 0.281630 10m random dist size 32 avg qsort 2.963479 blitsort 4.394143 100m random dist size 128 avg qsort 34.996847 blitsort 54.102616
- scandum 5y ago
  It is, those numbers are less favorable than they are on my own machine. The speed of your RAM memory is likely to have an influence on performance. My system is running at 2133MHz.
  - deleted 5y ago
    [deleted]
  - nuclearnice3 5y ago
    Interesting. 16 GB 2133 MHz LPDDR3 Built with Apple clang version 12.0.5 (clang-1205.0.22.11) gcc -O3 bench.c
scandum 5y ago
Blitsort can sort strings, but something like a 12 byte data structure would require an array with pointer references to sort. As for the degradation against std:stable_sort: 5% slower at 1 million, 10% slower at 10 million, 20% slower at 100 million. With sqrt n auxiliary you're looking at 2%, 4%, 6% slower. Against qsort() it remains faster at 10 million, 3% slower at 100 million.
- acmj 5y ago
  I am thinking more about sorting, say, 20-byte or 24-byte custom structs. Directly sorting arrays is probably faster than sorting pointers to arrays. At least in my applications, I rarely just sort numbers; I more often sort numbers along with other data associated with the numbers.
  - scandum 5y ago
    Hard to say which would be faster, I've made a mental note to benchmark sorting 16 byte long doubles through pointers as well as directly. I never tried, but it should be possible (and relatively easy) to add custom sizes in the .h file.

by acmj 5y ago

nuclearnice3 5y ago

Is the included bench.c the right way to answer that question? 1m random dist size 128 avg qsort 0.206549 blitsort 0.281630 10m random dist size 32 avg qsort 2.963479 blitsort 4.394143 100m random dist size 128 avg qsort 34.996847 blitsort 54.102616

scandum 5y ago
It is, those numbers are less favorable than they are on my own machine. The speed of your RAM memory is likely to have an influence on performance. My system is running at 2133MHz.
- deleted 5y ago
  [deleted]
- nuclearnice3 5y ago
  Interesting. 16 GB 2133 MHz LPDDR3 Built with Apple clang version 12.0.5 (clang-1205.0.22.11) gcc -O3 bench.c

scandum 5y ago

Blitsort can sort strings, but something like a 12 byte data structure would require an array with pointer references to sort. As for the degradation against std:stable_sort: 5% slower at 1 million, 10% slower at 10 million, 20% slower at 100 million. With sqrt n auxiliary you're looking at 2%, 4%, 6% slower. Against qsort() it remains faster at 10 million, 3% slower at 100 million.

acmj 5y ago
I am thinking more about sorting, say, 20-byte or 24-byte custom structs. Directly sorting arrays is probably faster than sorting pointers to arrays. At least in my applications, I rarely just sort numbers; I more often sort numbers along with other data associated with the numbers.
- scandum 5y ago
  Hard to say which would be faster, I've made a mental note to benchmark sorting 16 byte long doubles through pointers as well as directly. I never tried, but it should be possible (and relatively easy) to add custom sizes in the .h file.