Suggestion for stack size when calling par_sort_unstable

[vigna]

Is there any standard suggestion for the stack size when calling par_sort_unstable? We're sorting dozens of billions of elements and we would like to provide the user with some sound default.

[cuviper]

I don't there can be a standard suggestion, because it depends on both the number of elements and the number of threads in the pool, at least. In theory it will have logarithmic depth, but work-stealing will lengthen that further.

I wonder if we need to be smarter about MAX_SEQUENTIAL here:

rayon/src/slice/quicksort.rs

Lines 754 to 756 in 990841b

	// If both partitions are up to this length, we continue sequentially. This number is as small
	// as possible but so that the overhead of Rayon's task scheduling is still negligible.
	const MAX_SEQUENTIAL: usize = 2000;

i.e. rather than just a fixed constant, maybe that should also consider num_elem / num_threads and some additional factor to account for imbalance. Then it should use a higher limit when you're starting with billions, and you won't get so much stack use due to work stealing.

---

Similarly, the stable sort has two constants, CHUNK_SIZE while splitting and MAX_SEQUENTIAL while merging:

rayon/src/slice/mergesort.rs

Lines 621 to 623 in 990841b

	// The length of initial chunks. This number is as small as possible but so that the overhead
	// of Rayon's task scheduling is still negligible.
	const CHUNK_LENGTH: usize = 2000;

rayon/src/slice/mergesort.rs

Lines 440 to 444 in 990841b

	// Slices whose lengths sum up to this value are merged sequentially. This number is slightly
	// larger than `CHUNK_LENGTH`, and the reason is that merging is faster than merge sorting, so
	// merging needs a bit coarser granularity in order to hide the overhead of Rayon's task
	// scheduling.
	const MAX_SEQUENTIAL: usize = 5000;

[vigna]

Well, what if I know the number of elements, their size, and the number of threads in the pool? Just ballpark.

[cuviper]

I don't know. You'll get a better answer if you run a few experiments yourself.

[norabelrose]

I'm running into the same issue and have found that around 5-10B elements the default of 2MB seems to break, so I'm testing out a heuristic of using max[1, log2(N / 5e9)] * 2 MB right now.
(this is sorting a memory mapped slice of u64 on a machine with 48 physical cores)

[norabelrose]

Update: I actually ran into a bus error (core dumped) when using the logarithmic scaling. Linear scaling would sort of defeat the purpose of memory mapping the data, so I might try square root scaling.