In 2023 we saw the first glimpse of machines becoming better at programming than humans when an AI created a new sorting algorithm that was faster than anything humans had yet created.
Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
21–30 of 328 posts
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#22The title implies it found an entirely new algorithmic approach to sorting (like quick sort) which would have been a fantastic discovery. But it feels a lot like micro-optimizing the control flow and codegen.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#23> The confidence intervals are represented as latency ± (lower, upper), in which latency corresponds to the fifth percentile of latency measurements across 100 different machines. Lower and upper refer to the bounds of the 95% confidence interval for this percentile. Does anybody know why they chose fifth percentile? I though we should always choose the fastest time when measuring performance.
Because they want to make sure that the sorting algorithm works well for all possible workloads, not just the most preferable ones.
If we measured sorting algorithms by the fastest measurement, we might conclude that BubbleSort is the fastest possible sort algorithm on some inputs. (Bubblesorting an already-sorted list makes at most one comparison per list element)
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#24Does anyone have high level guidance on when (deep) RL is worth pursuing for optimization (e.g. optimizing algorithm design) rather than other approaches (e.g genetic)?
Less of a scale problem than a type problem usually in my experience.
My rule of thumb is when it’s easy to specify a reward function but infinite ways to traverse the action space - versus having a constrained state and action space (small n solution traversal pathways) and only a few possible paths to traverse.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#25Earlier quoted context omitted.
> up to 70% faster So O(0.3(N log N))? That's still O(N log N)
In the real world, we care about runtime as much as, if not more than, computational complexity.
Definitely more. There are lots of things that might be more optimal in terms of raw complexity but end up having abysmal performance due to things like cache locality. Anything with pointer chasing usually kills performance.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#26The most interesting part of this paper to me is that they let the agent guess how efficient it’s own solutions were and only had the model experimentally verify it’s guesses in 0.002% of cases. This allowed the model to search much faster than another program that didn’t guess and had to run every program.
That sounds like intuition.
Intuition is the only thing we've figured out how to automate. Reason turns out to be higher hanging fruit.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#27It is astounding how something as well as studied as sorting still has opportunities for further improvements!
It is not the sorting per-se which was improved here, but sorting (particularly short sequences) on modern CPUs with really the complexity being on the difficulty of predicting what will work quickly on these modern CPUs.
Doing an empirical algorithm search to find which algorithms fit well on modern CPUs/memory systems is pretty common, see e.g. FFTW, ATLAS, https://halide-lang.org/
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#28[deleted]
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#29It is astounding how something as well as studied as sorting still has opportunities for further improvements!
Part of it is because hardware properties are always changing. The instructions available, the relative speed of CPU to memory and the various caches, how big and numerous and fast the various caches are, etc etc.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#30LLVM merge: https://reviews.llvm.org/D118029 Benchmark: https://bit.ly/3AtesYf Benchmark seems to be in the range of a 1-5% improvement for 80% of sizes.
And for the hashing patch this is the commit to Abseil:
https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d...