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

221–230 of 328 posts

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

#221

Post by congoe »

wsdookadr wrote: post #215
orlp wrote: post #91

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

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

How 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

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

#222

Post by mtlmtlmtlmtl »

chaxor wrote: post #160
TaupeRanger wrote: post #114

Earlier quoted context omitted.

This 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 DeepMin…

This is unbelievably wrong. Deepmind has probably the best academic group in RL. The difference between Deepmind and OpenAI is that Deepmind favors academic endeavours and novelty much more, while completely ignoring any commercialization or products, while OpenAI is the stark opposite in that they almost entirely focus on products first, and typically their academic endeavours are just slight modifications of other…

That's the thing with Deepmind though. They almost never actually end up advancing things because A) they don't release weights and B) they don't usually develop their ideas into useful tools themselves, forcing others to redo all their work.

So yeah, it's essentially a PoC PR stunt factory. Just look at AlphaZero. They make a huge deal about a suspiciously set up match against Stockfish. Supposedly revolutionising computer chess. But the problem is the computer chess community had to redo all of the work, including all the training to build Leela Chess Zero. Due to lack of Google-sized datacentres the training took years to catch up to the weights in AlphaZero. Same thing with AlphaGo, same thing with transformers.

Now, in AI, usually getting a proof of concept is the easy part. Developing that into an idea that actually works in real world situations is usually the hardest part. I completely reject your idea that somehow the work by OpenAI is less worthy of recognition. I think that's just nonsense.

And surely, Google created Deepmind to actually make them product ideas, not create new competitors, which is what has happened.

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

#223

Post by moonchild »

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…

> 9-16 was a better spot and it simplified from 2 multiplications to just one and a rotation

I'm very confused as to why rotation was at all useful. Xoring with a random-ish constant makes sense, because the constant has high entropy and is likely to decorrelate bits from the input (also can use a different constant per hash table). But rotating by a constant—and a fixed one at that—seems like it just accounts for expected input distribution. Especially (assuming this is intended for text) if shifting by a value >8 makes a significant difference (vs shifting by the same value mod 8), it smells like serious overfit. Could be useful for something like a perfect hash, but seems problematic and prone to issues as a general hash.

Edit: to make my objection clearer: the hash simply replaces lo with rotr(lo, 53). If rotr(lo, 53) performs significantly better than rotr(lo, 53 mod 8), then that implies the following. I can take a set of strings, and I can apply the same permutation to the characters of all of the strings in the set, and this will significantly affect the quality of the hash function. That seems like an undesirable property, even for a non-cryptographic hash.

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

#224

Post by mtlmtlmtlmtl »

CalChris wrote: post #73
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...

Stockfish actually use machine learning to pick the best magic numbers for their code.

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

#225

Post by xdavidliu »

utopcell wrote: post #187
xdavidliu wrote: post #158

Earlier quoted context omitted.

but the number of elements in the array is also a 32 or 64 bit integer, so you still cannot do better than O(n log n) even with fancy radix sort or whatever

not with radix sort, but you can do better when your elements are integers, even if there there are a lot of them, i.e. even when n ~ 2^32.

interesting; got an example or link? What exact asymptotic form do you mean by "better" here?

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

#226

Post by mindwok »

ndesaulniers wrote: post #153
danlark wrote: post #95

Earlier quoted context omitted.

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.

> but intuition for optimizer over optimizer was unlikely to work properly. Wut?

My guess: Using LLVM IR would mean that the LLVM optimiser might have made the results more noisy or hard to understand when it was compiled to actually execute.

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

#227

Post by graycat »

CyberDildonics wrote: post #111
graycat wrote: post #101

Earlier quoted context omitted.

The Gleason bound is n log(n) and says that no sorting algorithm based on comparing pairs of keys can be faster. Heap sort meets the Gleason bound so is the fastest possible in this context. Actually the usual versions of quick sort are slower. If the keys are not too long, radix sort is O(n) and faster. All this has been well known for decades. I explained a little more in another post in this thread.

I think you are getting your information mixed up. Here is a comparison that shows quicksort running in 1/10th the time as heapsort. https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...

Versions of quick sort differ in how the partitions are determined. A guess is that some of the versions are not worst case O(n log n) for sorting n keys. In that case, for sufficiently large n, on a normal computer, any version of heap sort will beat that version of quick sort in number of comparisons, time in seconds, Joules of energy to run the computer, etc.

It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort.

Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers.

Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort.

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

#229

Post by janwas »

ajuc wrote: post #41
hexomancer wrote: post #13

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

Usually you discard extreme values to reduce noise, and in fact they wrote that's why they did it: > We then take the fifth percentile as our final measurement, because we assume that most noise sources are one-sided (for example, cache misses, pre-emptions and so on). During training we process the measurements across ten machines for computational efficiency. > I though we should always choose the fastest time when…

One possibility which seems not so well-known is that clocks with per-core state might not be perfectly synchronized. If your initial measurement is from core0, then we migrate to core1, the end measurement could even be 'before' the initial.

Then there are manufacturing differences between cores that affect e.g. their leakage current and thus the (turbo) frequency at which they can run.

So the measurement noise is indeed not one-sided, that is to say: measurements are not always overestimates. Thus a trimmed mean on both sides is a good idea, and pinning threads to a core when measuring is also helpful.

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

#230

Post by janwas »

CyberDildonics wrote: post #109
graycat wrote: post #94

"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…

Heap sort gets beat by sorting algorithms with better locality. You can't be the fastest while skipping through memory for every operation.

Agreed. And I am not aware of a heapsort that can take advantage of SIMD, so our not very well-tuned heapsort is about 20 times slower in practice than our VQSort (vectorized quicksort).
Post reply on HN