AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements.

  • Hexorg@beehaw.orgM
    link
    fedilink
    English
    arrow-up
    1
    ·
    1 year ago

    This write up talks about sequences of 3 and 4 items… does their full paper generalize to variable sized lists?

    • ericjmorey@lemmy.worldOP
      link
      fedilink
      English
      arrow-up
      1
      ·
      edit-2
      1 year ago

      From the main section of the paper published in Nature (which is available for free):

      Using AlphaDev, we have discovered fixed and variable sort algorithms from scratch that are both new and more efficient than the state-of-the-art human benchmarks. The fixed sort solutions for sort 3, sort 4 and sort 5 discovered by AlphaDev have been integrated into the standard sort function in the LLVM standard C++ library

      It seems they did find improvements for sorting variable sized list but only the sort 3, sort 4 and sort 5 algorithms got implemented in LLVM.