Franciso, Thanks for your detailed explanation. I'll repeat what I've said before about your object benchmark: I suggest changing the struct you use for benchmarking to this: template <uint32_t NN> struct reburcio { uint64_t M[NN]; reburcio () { init(); } void init() { for (int i = 0; i < NN; ++i) { M[i] = my_rand(); // or something with less variability to test identical substring performance } } bool operator < ( const reburcio &R) const{ for (int i = 0; i < NN; ++i) { if (M[i] != R.M[i]) { return M[i] < R.M[i]; } } return false; } }; That way it's using the default copy and assignment operators, which copy over the entire datastructure, and it initializes and compares all elements of the array. It appears that the benchmark you sent me only copies over and compares the first element in the array, which might have caused some of the large-element differences in performance you were seeing. Another alternative is just using a vector for the array of elements. On Tue, Mar 24, 2015 at 4:56 PM Francisco José Tapia <fjtapia@gmail.com> wrote:
-
GCC sort → M -
boost sort → M
I don't think we'll ship this; this looks more like a proof-of-concept, unless the indirect sorting benefits are demonstrable after fixing the object you use in testing as described above. -
GCC parallel_sort → M -
boost parallel_sort → M
I see no advantage to this sort relative to tbb, and its performance on already-sorted data needs to improve to be competitive with tbb.
-
TBB parallel_sort → M
-
GCC stable_sort → 2 M -
boost stable_sort → 1.5 M
The combination of improved speed and lower memory usage looks impressive. I'll try to verify this, but this looks promising.
-
TimSort -> 2M -
GCC parallel_stable_sort → 2.5 M -
TBB parallel_sort → 2 M -
boost sample_sort → 2 M -
boost parallel_stable_sort → 1.5 M
Both of these algorithms look good. I'm inclined towards parallel_stable_sort because memory is becoming more of a bottleneck on modern systems, but I'll have to do some testing. Timsort seems fairly impressive, but specialized and already available for free, hence not necessary to include in the library.
If you found any problem , error or doubt, please , contact me for to resolve
Please fix your object benchmarks as described at the beginning of my email; otherwise I don't trust them. I also would like to see string sorting speeds. Once that is all together, I'd like to test and review them carefully and look to see if there are any weaknesses missed by your current tests. If they look good, and we can agree on which algorithms you want to add to the library, we should move on to cleaning this up for review. Steve