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

71–80 of 328 posts

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

#71

Post by hajile »

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?

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

#72

Post by utopcell »

xdavidliu wrote: post #63
iopq wrote: post #53

Earlier quoted context omitted.

That's not true because Thorup's algorithm is O(n log log n)

any sort that only uses comparisons is provably not better than n log n. Hence whatever Thorup is, it doesn't work for arbitrary input, and must assume something further, something like "all elements under 1000 or something"

I think the parent's argument is that, since they only evaluated their algorithms on sorting arrays of 32-bit or 64-bit integers, it is fair game to compare against integer sorting algorithms for which we have better complexities than O(nlgn).

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

#73

Post by CalChris »

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…

This sounds like a more intelligent version of superoptimization. The original Masselin SO, albeit for its time, also created surprising results which is similar to AlphaDev's incomprehensible for humans. You see the same thing in computer chess which Agadmator calls disgusting engine lines.

https://courses.cs.washington.edu/courses/cse501/15sp/papers...

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

#74

Post by thesz »

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…

So it works as a superoptimizer of sorts.

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

#75

Post by GreedClarifies »

benlivengood wrote: post #54
GreedClarifies wrote: post #46

Deepmind shouldn’t be part of a for profit entity. There I said it. They are clearly focused on moving technology forward and helping humanity. That’s great. However, pulling down 1M+ salaries (for L6+ developers) and using hundreds of millions or billions in borg resources while adding nothing to the bottom line is not in the interest of Google. Not to mention the negative effects on productivity as other Googlers a…

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.

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

#76

Post by m3kw9 »

cabalamat wrote: post #70
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…

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

It’s not that is written like obfuscated, the routine/ algo is just hard to understand even if they commented every line. Likely some recursive trick is involved, those are always hard to follow

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

#77

Post by xwdv »

VikingCoder wrote: post #67

Dumb question - Where are the machine learning de-compilers? Given an executable program, give me human-readable code that generates the executable exactly. With machine learning guessed function, type, variable names...? I get that it's a very hard problem. But... Does it just not work? Or have people not done it yet? Or have I missed it?

This is the killer app for me with AI. A way to get a non-copyrighted code for any program you already have binary code for.

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

#78

Post by skeaker »

VikingCoder wrote: post #67

Dumb question - Where are the machine learning de-compilers? Given an executable program, give me human-readable code that generates the executable exactly. With machine learning guessed function, type, variable names...? I get that it's a very hard problem. But... Does it just not work? Or have people not done it yet? Or have I missed it?

Personally I think this would be very exciting. Currently there are a ton of projects to decompile older games (see the Mario 64 and Ocarina of Time de-compilations and subsequent native PC ports as an example), but those projects are huge and take whole teams years to finish. If you could simply point an AI at a project like that and have usable source code in a reasonable amount of time, it would be huge for those scenes. You would have a sort of defacto-open source moment for just about all software. It feels like the stuff of far off sci-fi.

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

#80

Post by dekhn »

xdavidliu wrote: post #65
boomanaiden154 wrote: post #25

Earlier quoted context omitted.

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.

for example, matrix multiplication has all sorts of algorithms with exponent significantly less than 3, but they are nearly all curiosities. In practice, the straightforward N^3 algo is used nearly everywhere

I had a long discussion with Rob Pike once that ended with me saying "you know, I don't think people actually use Strassen on supercomputers" (we were discussing how somebody had managed to show an N*2.37 algorithm or something like that and "it was a new world's record").
Post reply on HN