I want this for sql compilation, plan choosing. So much effort is wasted on suboptimal database performance and trying to improve that. I think even sorting pales in comparison.
Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
61–70 of 328 posts
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#62Some very cool improvements found in already highly optimized algorithms. They found that in a sorting network handling 3 inputs, the AI found a way to save an instruction by reducing a "min(A, B, C)" operation to just "min(A, B)" by taking advantage of the fact that previous operations guaranteed that B = min(A, C) in this case) that can be taken advantage of to remove an instruction as well. The compiler may not be…
Interesting that it took AI to pull this off. I think mutagen testing would have discovered the first (by virtue of checking which code isn’t necessary globally ) though likely not the second (which needs a new branch, unless that branch was already there?).
As I understand it it kind of _did that_, just in an extremely guided kind of way, which is why it produced results in some reasonable amount of time (probably)
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#63Earlier quoted context omitted.
They're not going to find a general sorting algorithm faster than O(n log n), but that doesn't mean all O(n log n) sorts are created equal.
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"
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#64Earlier quoted context omitted.
They're not going to find a general sorting algorithm faster than O(n log n), but that doesn't mean all O(n log n) sorts are created equal.
If the thing you have to sort is within a known domain you can definitely beat o(n log(n)). Just expect crazy memory usage. And that's only not the case in theory. But nobody owns a real Turing machine with infinite tape and truly infinite numbers. It doesn't exist in reality. You can always divide time by multiplying space with the same factor.
by "general sort" your parent comment means "comparison sort", and the claim (which has been proved, see CLRS intro to algorithms) is that you cannot do it in better than O(n log n) comparisons.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#65Earlier quoted context omitted.
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.
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
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#66The sorting seems cool but I am more interested in the varint decoder. Does anyone know where the source code of that landed, if it did?
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#67Dumb 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?
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#68Dumb 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?
You can already do that to some extent with ChatGPT. Paste in the assembly and it gives pretty good results
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#69Dumb 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?
That is a good question!
Training datasets should be pretty trivial for this, all open source software that is buildable on the internet could provide training sets (source code & compiled code).
But I guess it would have to be trained specifically for every architechture.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#70You 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.