12 ms·
> 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 abo
by orlp 3y ago
> 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 https://bugs.llvm.org/show_bug.cgi?id=20837) finally being fixed late 2021 https://reviews.llvm.org/D113413 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.
- usmansk 3y agoThe claim "faster sorting algorithm" is wrong. They have to show the time-complexity. They have to prove that their algorithm is faster than linear sorting algorithms. Otherwise, they have to accept that their claim is wrong.
- usmansk 3y agoCan anyone refute the claim of orlp that it is unrolled insertion sort
- TaupeRanger 3y agoThis is DeepMind's modus operandi. Every press release is just utterly hyperbolic nonsense that doesn't withstand the slightest scrutiny. AlphaGo, AlphaFold, AlphaDev... they've done literally nothing to improve the human condition, and may have actually made things worse. Go players have DECREASED their Elo after playing AlphaGo (or just quit the game altogether). I would be embarrassed to be associated with DeepMind.
- blazespin 3y agoIt's a bit surprising how poorly DeepMind has lived up to their hype. But they're an OK lab, maybe a bit overly vain.
- hugopenmir 3y agoI can’t believe this
- TaupeRanger 3y agoIt's probably very fun to be at DeepMind, I just don't think I'd want to be a part of the cringey hype machine.
- blazespin 3y agoI bet it really sucks, tbh. They did all this over promising and now the only way they can deliver is by grifting like this. That sounds really stressful to me.
- blazespin 3y agoYeah, this type of grifting is very proforma for Researchers. I used to stress about it, but realize it just sort of goes with the territory. It's also worth noting that the paper is blindingly obvious and everyone started doing this a long time ago but didn't want to tip their cards. And that's the real contribution here - Google is tipping their cards. We now have a rough baseline to compare our results against.
- aldousd666 3y agoWell. I feel grifted too because being a developer, yet not into the state of the art in algorithms (at that level,) i was inclined to buy their BS
- ryao 3y agoIt is likely meant to help secure further research funds.
- scotty79 3y agoShouldn't libc++ be kinda good? Since it's the standard and all? Why isn't/wasn't it?
- petschge 3y agoThe LLVM implementation of libc++ is very young compared to other implementations (it was started 5 years ago or so), so there is still a lot of things missing and a lot of things that can be improved.
- bigcheesegs 3y agolibc++ was open sourced May 11th 2010. 13 years ago. https://blog.llvm.org/2010/05/new-libc-c-standard-library.html https://blog.llvm.org/2010/05/new-libc-c-standard-library.ht...
- throwaway106382 3y ago[flagged]
- danlark 3y agoI agree on the sorting front. Removing one cmov is not likely to improve much.
- orlp 3y agoIt's not even a cmov. Look at Figure 3 in the paper: https://www.nature.com/articles/s41586-023-06004-9 https://www.nature.com/articles/s41586-023-06004-9 They eliminated a register-register mov.
- choppaface 3y agoA decade ago Google had people with breadth and context who could have adjusted the framing of the result of this work (and maybe even re-targeted it yo something useful). Today however Google is a mix of hyper-narrow expert ICs and leaders who lack domain expertise. Paper in Nature? Sure let’s take it!
- dundarious 3y agoYes, I believe what they're doing already exists in the literature as "supercompilation", though good to see its application under any name.
- as4296 3y agoLol I was about to say that would be incredibly crazy if they found a new sorting algorithm. My time complexity in USACO bout to go crazy.
- dataflow 3y agoI get your sentiment but note that discovering a new algorithm doesn't have to imply a better time complexity. Bubble Sort and Insertion Sort have the same time complexity but are different algorithms.
- saiojd 3y agoI feel like your take is overly cynical. The fact that humans can do the same thing by hand is not really the point. The contribution lies in the fact that their method derived this improvement *automatically*, which is where the impact lies. No one cares all that much if a human can make a sorting routine 2% faster, but if a program can do it, it suddenly becomes interesting (since it suggests that a similar approach can be applied to many other routines).
- smeagull 3y agoA thing that is also not novel. People have done search for optimisations for at least the past decade.
- saiojd 3y agoSure, but the whole point is to reduce this kind of search to RL, which is a very general framework. Their paper shows that such a generic approach can solve a very specific problem, and solve it well. But, their paper is about improving RL, not about improving sorting.
- Zacharias030 3y agosometimes one has to wonder how RL can be both so generic and still be qualification to publich in nature again and again and again ;)
- orlp 3y agoI am not cynical about the research itself, I am critical of claims such as "new sorting algorithm uncovered", "up to 70% faster", or "first change in a decade". The research is good. The achieved results are massively inflated. What they achieved: automatically generated good code. What they claim: automatically generated code that is revolutionary and an improvement on the state of the art. And as another commenter noted, superoptimizers are also already a thing: https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization There's also automatic searching being done on faster sorting networks that actually recently produced better than state of the art sorting networks: https://github.com/bertdobbelaere/SorterHunter https://github.com/bertdobbelaere/SorterHunter
- neximo64 3y agoWhat you're saying is a certain perspective which seeks to look at it from first principles. To the brutalist, the algorithm change is faster, and thats all that matters. A human didn't previously come up with the optimisation. You might as well say a computer sorting an algorithm is bullshit vs a person because the difference is just a bloated chip does it instead, and thats it.
- tlringer 3y agoEvery DeepMind press release is like this.
- hugopenmir 3y agoYou know people at Google, tell Demis about this.
- wsdookadr 3y agoWhat's surprising is that anyone would've expected an AI to come up with a brand-new algorithm with better complexity than pre-exsiting human-made solutions. How could it possibly come up with something better when it doesn't even understand how the original authors of qsort/mergesort/etc came up with their own.. Sure, it's great PR for the company, but.. the results just aren't there.
- congoe 3y agoHow could AlphaZero possibly play better chess than humans when it doesn’t even understand the history of chess theory? RL doesn’t stop at human levels
- Maken 3y agoBecause the entire history of chess theory is really a set of heuristics to optimize a tree search.
- wsdookadr 3y agoEven if AlphaZero does play better chess, there's absolutely zero it can do in terms of explaining why it played that way. AlphaZero is zero in terms of explainability. Humans have to explain to themselves and to others what they do, this is key in understanding what's happening, in communicating what's happening, in human decision-making, in deciding between what works and what doesn't and how well or how bad it works. Returning back to the original DeepMind press release, it's misinforming the public about the alleged progress, in fact no fundamental progress was made, DeepMind did not come up with an entirely new sorting algorithm, the improvement was marginal at best. I maintain my opinion that Alphadev does not understand any of the existing sorting algorithms at all. Even if AI comes up with a marginal improvement to something, it's incapable of explaining what it has done. Humans (unless they're a politician or a dictator) always have to explain their decisions, how they got there, they have to argue their decisions and their thought-process.