4 ms·

Pretty neat! So it looks like you have a few things happening in parallel. What is instruction level paralellism and how does it speed the sort up?

• deleted 4y ago
  [deleted]
• orlp 4y ago
  Modern processors execute out-of-order (reordering instructions) and are superscalar (they execute more than one instruction per cycle). By providing multiple independent data paths in the tight merging/partitioning loops we can keep the CPU busier than a traditional merge/partition loop and have higher throughput. Note that this all happens on a single thread, this is in addition to thread-level parallel sorting (which glidesort does not (yet) have). Also note that this is different than SIMD, which processes more data in a single instruction. This can give you incredible speed-ups, but the code is very dependent on the data (e.g. code for sorting integers looks very different than sorting strings with SIMD). Glidesort is written using scalar code with fully generic comparison functions, no SIMD-specific speedups.
  • repsilat 4y ago
    Would a simple example of this be something like, > In a traditional "merge" algorithm, the second comparison depends on the output of the first, so it can't be done at the same time. So it might make sense to merge "from the left" and merge "from the right" at the same time because those things can be done in parallel when both arrays have length > 1. ?
    • orlp 4y ago
      That is exactly right.