AlphaDev discovers faster sorting algorithms

3 years ago by ericjmorey to c/programming

In our paper published today in Nature, we introduce AlphaDev, an artificial intelligence (AI) system that uses reinforcement learning to discover enhanced computer science algorithms – surpassing those honed by scientists and engineers over decades.

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.

simple 20 points 3 years ago

This is the stuff that makes me really excited for AI. Sure, having a personal assistant is nice. Generating images and music is also very cool. Optimizing software and hardware though, this is where things get amazing.

Modern software is pretty abysmal when you think about it. In the last 20 years we've focused more on making things faster rather than making more optimized things. We ended up with ultra bloated operating systems, regularly 100mb+ apps, RAM sucking programs like web browsers and background apps that make even 8 gigabytes of RAM not enough, and so on.

I'm waiting for a point where AI can start optimizing legacy code and say "Wait, this is really dumb and wastes so much energy". Imagine Windows running on only 100mb of ram. Imagine apps and websites being 10x more efficient than they are now. It's not that crazy of a concept, only a matter of time.

save

path: 0 19419, hotness: undefined, score: 20, children: 6

knighthawk0811 5 points 3 years ago

to be fair sometimes the bloat is for security. but yeah, I'm with you here

save

path: 0 19419 19476, hotness: undefined, score: 5, children: 4

Hexorg 1 point 3 years ago

Eh security bloat is in the order of kilobytes per megabyte of code.

save

path: 0 19419 19476 32509, hotness: undefined, score: 1, children: 3

knighthawk0811 3 points 3 years ago

so somewhere between 1K and 999K per 1M? got it

save

path: 0 19419 19476 32509 32679, hotness: undefined, score: 3, children: 2

Hexorg 1 point 3 years ago

Still less than the rest of the data for UI

save

path: 0 19419 19476 32509 32679 32876, hotness: undefined, score: 1, children: 1

ericjmorey 5 points 3 years ago

I agree. There's a lot that automation can do that we generally know can be done, but don't because the limited development resources are allocated towards easier payouts.

save

path: 0 19419 20038, hotness: undefined, score: 5, children: 0

Sibbo 3 points 3 years ago

That is 70% faster on sequences of five elements. Using this for handling the end of the recursion in LLVMs current std::sort implementation results in a 1.7% speedup on sequences exceeding 250k elements.

save

path: 0 20655, hotness: undefined, score: 3, children: 3

greysemanticist 2 points 3 years ago

I wonder if their paper has a plot of the speedups against number of elements. Did they just stop measuring at 250k? What was the shape of the curve?

save

path: 0 20655 47451, hotness: undefined, score: 2, children: 2

Sibbo 1 point 3 years ago

I didn't bother reading, not so interested in AI stuff. But since they highlight these results, it likely does not get better for higher numbers.

save

path: 0 20655 47451 47482, hotness: undefined, score: 1, children: 1

greysemanticist 1 point 3 years ago

I'll bet it just ends up being the limitations of memory bandwidth to stuff things into registers for the optimized algorithm. Or, something like Mojo's autotuning finds the best way to partition the work for the hardware.

save

path: 0 20655 47451 47482 47596, hotness: undefined, score: 1, children: 0

Hexorg 3 points 3 years ago

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

save

path: 0 32534, hotness: undefined, score: 3, children: 2

ericjmorey 3 points 3 years 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.

save

path: 0 32534 34256, hotness: undefined, score: 3, children: 1

Hexorg 3 points 3 years ago

Oh I see! I didn’t realize llvm had specific-count implementation thanks!!

save

path: 0 32534 34256 34335, hotness: undefined, score: 3, children: 0