Parallel sort

Found this on Mastodon:

There are also some interesting comments in this thread:

Would be nice to have a parallel sorting algorithm in Crystal as well, seems to be well worth it :smirk:

1 Like

Maybe. The blog post presents a pathological example that rarely occurs in reality in any programming language β€” sorting an array of size 128M in memory with gobs of CPU cores available to a single process that are otherwise doing nothing.

Generally speaking, I follow 2 rules of thumb regarding parallelization of a single unit of work:

  1. It’s usually worth it to parallelize spiky workloads because you have a lot of available CPU time that you can actually put to use, but high-baseline workloads don’t make sense to parallelize β€” you’re already using those CPU cores
  2. It’s almost always worth it to parallelize large workloads, but almost never worth it to parallelize smaller workloads β€” the cost of parallelization needs to be amortized by the reduced latency of the workload

I had never heard of Chapel. So doing a little research I came across the below items where someone questioned the comparison of Chapel with Rust for the sort algorithm.

One of my enduring hopes is that Crystal will also (soon) develop a true parallel processing implementation (not based on fibers) to truly compete in the field of highly parallel arithmetic and numerical algorithms.