64-bit object_qsort

[nh2]

The README says:

For performance reasons, we support object_qsort only when the array size is less than or equal to UINT32_MAX.

This to me seems the biggest limitation in the whole library. There are many cases where you have more than 4B things to sort.

It would be great to have 64-bit object_qsort, even if the speedup isn't as large as on 32-bit-many objects.

[r-devulap]

@nh2 I have not benchmarked performance for array sizes beyond UINT32_MAX, so it may actually perform worse than std::sort in those cases.

That said, its easy to support both uint32_t and uint64_t by templating the arrsize parameter as T arrsize. If we do this, we should include a warning in the README.

[nh2]

I have not benchmarked performance for array sizes beyond UINT32_MAX, so it may actually perform worse than std::sort in those cases.

@r-devulap Ah, interesting. Curious why -- all the other functions like qsort(), qselect(), partial_qsort() etc. seem to be size_t.

That said, its easy to support both uint32_t and uint64_t by templating the arrsize parameter as T arrsize. If we do this, we should include a warning in the README.

Sounds like a good plan!

Would love a short benchmark though -- even if it's slower, good to know what the current state is!

[r-devulap]

Ah, interesting. Curious why -- all the other functions like qsort(), qselect(), partial_qsort() etc. seem to be size_t.

Supporting size_t is the ideal goal and most of sorting/partial sorting routines perform well for large arrays. The way we sort objects is different and involves an in place permutation of the object array which performs very poorly once the array doesn't fit in the caches.

[r-devulap]

See #207

[nh2]

Thank you!