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

101–110 of 328 posts

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

#101

Post by graycat »

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"

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.

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

#103

Post by cypherpunks01 »

thomasahle wrote: post #49
fwlr wrote: post #34

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

I'm surprised they only report results up to sort5. It seems at that level, you could just iterate through all possible programs. AI generated code seems more interested once you get to 10+ values, where classical methods break down.

I believe that's because above 5 elements, fixed sorting networks are no longer used. Introsort takes over and dispatches to insertion sort, quicksort, or heap sort as appropriate.

Divide and conquer strategies are used for larger sorts, and the smaller arrays could include the fixed lengths 3, 4, 5.

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

#104

Post by zerodensity »

GravityLabs wrote: post #32
jackmott42 wrote: post #29

Earlier quoted context omitted.

Part of it is because hardware properties are always changing. The instructions available, the relative speed of CPU to memory and the various caches, how big and numerous and fast the various caches are, etc etc.

I am curious why things can't just get better on a base that doesn't change, until the base changes because the improvements with the new base are just that much better... Or is that why hardware properties change so much?

For a time that is what happened. Every year you would get a new CPU and that would be faster at pretty much everything than the version the year before. But then we hit the clockspeed wall and the only way of making faster CPUs was to add complexity to the internals of the CPUs. So branch prediction, micro code pipelining, larger caches, simd instructions more CPU cores ect was the result.

So nowadays a new CPU might not be better at everything then the previous version but it will most likely have more cache and some internal improvements to pipelining/concurrency.

Given this, for newer versions it can be useful to add instructions to take advantage of extra pipelining or using a different instruction that happen to be faster now.

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

#105

Post by bitshiftfaced »

thomasahle wrote: post #49
fwlr wrote: post #34

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

I'm surprised they only report results up to sort5. It seems at that level, you could just iterate through all possible programs. AI generated code seems more interested once you get to 10+ values, where classical methods break down.

The paper notes that they brute forced all solutions for sort3 to verify that it was optimal. It said that this wasn't possible for 4+.

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

#106

Post by nurettin »

bgirard wrote: post #22

The title implies it found an entirely new algorithmic approach to sorting (like quick sort) which would have been a fantastic discovery. But it feels a lot like micro-optimizing the control flow and codegen.

My first intuition, knowing the limitations of generating first-order logic sequences, was that they must have somehow restricted the sorting sequence to a number of elements.

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

#107

Post by eklitzke »

thomasahle wrote: post #48
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…

I'm disappointed a the hashing is just based on training on microbenchmarks and SMHasher, rather than designing a fast _provably_ universal hash. Suites like SMHasher are never complete. They are just trying to catch the most common weaknesses. If you train on the test cases you'll only get an algorithm that passes the tests, but people can always find a set of values on which you will do badly.

I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function, but outside of cryptographic applications that is rarely the requirement. And (huge caveat, this isn't my domain expertise) I'm not sure what security properties are really "proven" about existing cryptographic hash functions, AFAIK existing cryptographic hash functions are considered secure because we don't know how to break them, not because of some fundamental mathematical property about them.

For the other 99.999% of hashing applications there is a balance between collision resistance and hashing latency. For example, in a hash table (probably the most common use for a non-cryptographic hash function) there is a cost incurred by hash collisions because lookups on keys with collisions may have to do extra probing. On the other hand, every hash table lookup requires doing at least one hash operation, regardless of whether or not it collides. So it may make sense to have a slightly worse hash function (in the sense that it is more likely to have collisions with pathological inputs) if it has slightly lower latency. The only way to really know what is faster for a real world application is to have some kind of benchmark to train against as a loss function.

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

#108

Post by whatever1 »

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.

Optimal routing of delivery vehicles for UPS/Fedex etc is also non-compressible to the drivers, so the planners often intentionally generate suboptimal solutions.

A suboptimal implemented solution is a better than an optimal not implemented one.

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

#109

Post by CyberDildonics »

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.

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

#110

Post by thomasahle »

eklitzke wrote: post #107
thomasahle wrote: post #48

Earlier quoted context omitted.

I'm disappointed a the hashing is just based on training on microbenchmarks and SMHasher, rather than designing a fast _provably_ universal hash. Suites like SMHasher are never complete. They are just trying to catch the most common weaknesses. If you train on the test cases you'll only get an algorithm that passes the tests, but people can always find a set of values on which you will do badly.

I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function, but outside of cryptographic applications that is rarely the requirement. And (huge caveat, this isn't my domain expertise) I'm not sure what security properties are really "proven" about existing cryptog…

> I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function.

I wish this misconception would die. There is a great theory of algorithmic probabilistic hash functions, completely distinct from cryptographic hash functions. If you are designing a hash table, or a different algorithm using a hash function, you nearly always want the former kind.

The idea is that `Pr[h(x) = h(y)]` is small _no matter the inputs x and y_. Here the probability is over the random seed of h. Lots of good hash functions, like UMASH (https://engineering.backtrace.io/2020-08-24-umash-fast-enoug...) has this guarantee. Other fast hash functions, like MURMUR don't.

When a function doesn't have this guarantee, it means I can find sets of values x1, x2, ... that will likely collide under _any_ or most seeds! Sure, if your inputs are basically random, this probably won't happen, but people can still use this to DDoS your hash table, or whatever you are coding.

Notice again, this has nothing to do with cryptography. It is all about probabilistic guarantees. You can't just test the hash function on a fixed number of inputs and say it's good, since you may just have moved the "bad set" to somewhere else.

In this day and age there are super fast algorithmic hash functions with guaranteed low expected collisions. It's just silly to use one that you can break so easily.

Post reply on HN