> I need to split up my problem into spaces that don't require synchronization/serialisation. When I first got a dual CPU (before "cores" were a thing) compute

> I need to split up my problem into spaces that don't require synchronization/serialisation. When I first got a dual CPU (before "cores" were a thing) computer, I decided I'd try dipping my feet in some "proper" parallel coding. I started with something simple, parallelizing a quicksort routine. This seemed quite trivial: instead of recursing, add the spans to be sorted to a list. I then spawned a thread per CPU, which fetched a span from the list, did a single quicksort pass on it and added up to two new spans to the list. Rinse repeat until list was empty. Since each span was non-overlapping, the threads only had to synchronize while accessing the list of tasks. When benchmarking it became clear that while there was a good performance win for large arrays, for short arrays the multithreaded code was much slower than the non-multithreaded version. At my hardware the threshold was around 50k items for integer elements and 20k or so for string elements, IIRC. I added a threshold detection, where the thread would do a regular recursive quicksort on the span if the length was below the threshold, and this yielded significantly better results. And with that the harsh reality of multithreading hit me: no free lunch. It was clear the threshold varies not just with element type (slow/complex comparators would reduce the threshold, and vice versa) but with the details of the hardware. So a hardcoded threshold was out of the picture, and it would have to be dynamically determined at runtime. Was a great learning experience though.