Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

nature.com

Post reply on HN
Print view View original

91–100 of 328 posts

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#91

Post by orlp »

> 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.

As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements.

They found a sequence of assembly that saves... one MOV. That's it. And it's not even novel, it's simply an unrolled insertion sort on three elements. That their patch for libc++ is 70% faster for small inputs is only due to the library not having an efficient implementation with a *branchless* sorting network beforehand. Those are not novel either, they already exist, made by humans.

> By open sourcing our new sorting algorithms in the main C++ library, millions of developers and companies around the world now use it on AI applications across industries from cloud computing and online shopping to supply chain management. This is the first change to this part of the sorting library in over a decade and the first time an algorithm designed through reinforcement learning has been added to this library. We see this as an important stepping stone for using AI to optimise the world’s code, one algorithm at a time.

I'm happy for the researchers that the reinforcement learning approach worked, and that it gave good code. But the paper and surrounding press release is self-aggrandizing in both its results and impact. That this is the first change to 'this part' of the sorting routine in a decade is also just completely cherry-picked. For example, I would say that my 2014 report and (ignored patch of) the fact that the libc++ sorting routine was QUADRATIC (https://bugs.llvm.org/show_bug.cgi?id=20837) finally being fixed late 2021 https://reviews.llvm.org/D113413 is quite the notable change. If anything it shows that there wasn't a particularly active development schedule on the libc++ sorting routine the past decade.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#93

Post by dsign »

finitestateuni wrote: post #5

The 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.

I've been wondering about a similar approach for biomolecular simulations, where exact computations are still a hard bottleneck. I wonder if something like this could give us a few orders of magnitude more speed.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#94

Post by graycat »

"Faster sorting"?

Heap sort achieves the Gleason bound and, thus, is the fastest possible sort by comparing pairs of keys.

For keys not too long, radix sort can be faster.

These facts have been very well known for decades.

There might be more to do in sorting with some different records, keys, computer architecture, concerns about caches and locality of reference, but otherwise, thankfully, sorting is a well solved problem.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#95

Post by danlark »

hajile wrote: post #71
danlark wrote: post #37

You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sort... , https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It…

To what extent is this simply working around the weirdness of x86? Do these improvements apply to something like MIPS, ARM64, or RISC-V that have inherently simpler ISAs?

In this particular case they were universal but in paper it's said the optimizations were done on x86. One of the ideas was to use LLVM IR but intuition for optimizer over optimizer was unlikely to work properly.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#96

Post by casey2 »

GreedClarifies wrote: post #75
benlivengood wrote: post #54

Earlier quoted context omitted.

I think Google's biggest net positives in the world at this point are Waymo and DeepMind. Way better than spending money on new chat apps. Google's history has been having a very lucrative bottom line that allows for very beneficial research with absolutely no hardships on anyone. Supremely better than lining shareholder pockets; shareholders can't think enough quarters ahead for long-term human benefit. Salaries are…

The billions who use their search everyday would likely disagree. The billions who use YouTube per day would likely disagree. The billions who use android would likely disagree. The hundreds of millions who use gmail, or gsuite would disagree. Products.

Products are at best optimization of a yesterday's technology, in tech you realistically can't peek into the future without spending billions on r&d. Having smart people work on any of the things you listed is a (further) waste of their time.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#97

Post by sytelus »

danlark wrote: post #37

You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sort... , https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It…

If more compute is spent than before but in parallel to reduce latency then wouldn't this increase power? Shouldn't latency and power both be objective?

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#98

Post by munchler »

the_other wrote: post #39
Filligree wrote: post #26

Earlier quoted context omitted.

Intuition is the only thing we've figured out how to automate. Reason turns out to be higher hanging fruit.

Like humans’ “slow” and “fast” thinking, then?

The Google Bard folks have a blog post today making exactly that connection: https://blog.google/technology/ai/bard-improved-reasoning-go...

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#99

Post by ska »

make3 wrote: post #90
cabalamat wrote: post #70

Earlier quoted context omitted.

> proves the point that optimal programs are very inhuman Maybe there should be an AI that produces optimally-readable/understandable programs? That's what I would want if I was adding the output to a codebase.

that's what LLMs can with rl from human (or ai) readability feedback & instruction tuning + prompting. we will 100% see this if gpt-4 doesn't already do this.

I wouldn't classify any of the output I've seen so far as "optimally readable/understandable".

Some if it looks pretty ok, especially where it overlaps with well established approaches.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#100

Post by ska »

gumby wrote: post #89
danlark wrote: post #37

You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sort... , https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It…

Your description makes the approach sound like applying ca 1980s simulated annealing, also a form of gradient descent. Am I missing something?

This doesn't really sound like SA, which is a principled approach to avoid the local min problem in descent algorithms and end up with a true global optimization. The general result is clean and impractical, the approximations hard to analyze.
Post reply on HN