Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
nature.com
nature.com
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 was not revolutionary in a sense it hasn't found completely new approaches but converged to something incomprehensible for humans but relatively good for performance which proves the point that optimal programs are very inhuman.
Note that for instructions in sorting, removing them does not always lead to better performance, for example, instructions can run in parallel and the effect can be less profound. Benchmarks can lie and compiler could do something differently when recompiling the sort3 function which was changed.
For hashing it was even funnier, very small strings up to 64 bit already used 3 instructions like add some constant -> multiply 64x64 -> xor upper/lower. For bigger ones the question becomes more complicated, that's why 9-16 was a better spot and it simplified from 2 multiplications to just one and a rotation. Distribution on real workloads was good, it almost passed smhasher and we decided it was good enough to try out in prod. We did not rollback as you can see from abseil :)
But even given all that, it was fascinating to watch how this system was searching and was able to find particular programs can be further simplified. Kudos to everyone involved, it's a great incremental change that can bring more results in the future.
It's an instance of overfitting.
Deepmind did the exact same thing with AlphaTensor. While they do some geniunely incredible things, there's always a massive caveat that the media ignores. Still, I think it's great that they figured out a way to search a massive space where most of the solutions are wrong, and with only 16 TPUs running for 2 days max. Hopefully this can be repurposed into a more useful program, like one that finds proofs for theorems.
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.
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.
That sounds like such a function is strongly collision resistant, which means it's also second preimage resistant. And that gets you most of the way to a cryptographic hash function.
Is the only difference that it doesn't have to be first preimage resistant? Compared to cryptographic hashes, does that expand the set of viable functions a lot, to allow first preimages while still not allowing second preimages?
> It is all about probabilistic guarantees
So are cryptographic hash functions.
When I search for `algorithmic probabilistic hash functions` I just get results about bloom filters.
> So are cryptographic hash functions.
Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not.
It's muddied a bit by the fact that cryptographers also use universal hashing (or probabilistic hashing, or what I called algorithmic hashing) for stuff like UMACs, https://en.m.wikipedia.org/wiki/UMAC#NH_and_the_RFC_UMAC , but they often have a lot of extra considerations on top of just collision resistance.
Some algorithms also need stronger probabilistic guarantees than just collision resistance (see e.g. https://en.m.wikipedia.org/wiki/K-independent_hashing#Indepe... ). These properties are usually too hard to test for with an experimental testing suite like SMhasher, but if your hash function don't have them, people will be able to find inputs that break your algorthm.
Eh, that's how I usually see collision resistance described. The probability is based on generating fresh inputs with any method you want/the most effective attack method available.
But I wouldn't say the hash you linked is nondeterministic just because it has a seed. You can seed MD5, SHA-2, and BLAKE2 by tossing bytes in as a prefix. It'll prevent the same attacks and you can give it the same analysis.
So I'm still not sure in what sense a hash like this is facing different requirements than a cryptographic hash.
I'm curious if you can link to such an analysis. These functions are notoriously much harder to analyze than simple functions like "h(x) = ax+b mod p" which is all you need for the probabilistic guarantee.
But even if you could analyze this, you would just end up with a universal hash function that's way slower than you need, because you didn't pick the right tool for the job.
> But even if you could analyze this, you would just end up with a universal hash function that's way slower than you need, because you didn't pick the right tool for the job.
I understand that, I'm just trying to figure out how a universal hash is easier to construct. But as you've gone through the descriptions here I think I understand how the collision resistance necessary is much much simpler, and there seems to be an assumption that the output of the hash will not be available to the attacker.
Yes, but the point is that hash functions used for hash tables are much, much faster than these cryptographic ones.
There are reasons to use (strongly) collision resistant hashes outside of cryptographic settings. E.g., the default Rust hash function, used in hash maps and sets, has strong collision resistance, because otherwise you could open up applications to DoS attacks (the attacker uses lots of inserts with collisions to kill performance of accesses and further inserts at those buckets).[0]
>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.
There are provably secure hash functions[1] (typically using the same sort of primitives as public key crypto), but they're generally only used when certain properties need to be composed, and are often less secure than the non-provable ones in practice anyway. This is pretty similar to the state of symmetric vs. asymmetric cryptography in general: primitives like RSA, DH, etc. have much stronger proofs than AES, but algorithms built using AES for security are generally viewed as a lot less likely to be broken any time soon than algorithms built using typical asymmetric primitives for security, even ignoring things like quantum advantage.
[0] https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
[1] https://en.wikipedia.org/wiki/Security_of_cryptographic_hash...
AFAIK, we don’t even know whether trapdoor functions exist.
https://en.wikipedia.org/wiki/Trapdoor_function:
“As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions”
Also note that the ‘examples’ section starts with:
“In the following two examples, we always assume it is difficult to factorize a large composite number (see Integer factorization).”
If you show me a setup where "easy" is n^3 and "hard" is n^15 I will happily call that a trapdoor function.
This might be buggy whip talk, but I wonder if you could take the same system and apply it to smaller problems (e.g. computing an 8-bit hash) so the novel techniques could be identified and used by humans.
"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 <= C."
Which isn't incomprehensible at all.
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.
Some if it looks pretty ok, especially where it overlaps with well established approaches.
This is why these systems are helpful in programming: they allow developers to think more about the design paradigms, and algorithmic solutions, rather than the fine grained code syntax and typing.
My hope (not prediction unfortunately, but *hope*) is that these systems will make people "better* programmers. This could happen by alleviating the requirement of typing out the code in a particular way, and allowing more time to really try out or think carefully about the correct solution for how to make their programs (i.e. multiprocessed, producer-consumers, distribute data with ipfs, faster algorithms, etc)
My experience so far (including -4) this isn't really true, even when focusing on those aspects. I'm cautiously optimistic this will get better.
A suboptimal implemented solution is a better than an optimal not implemented one.
Really? That's the first time I've heard that (and I've worked on vehicle routing).
Normally, the driver would get the next address they have to visit and would use satnav to work out how to get there. They don't need to "comprehend" the overall route.
Wut?
https://courses.cs.washington.edu/courses/cse501/15sp/papers...
https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_st...
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.
I would expect the equality test to compare at least a full word at a time, just as the hash hashes at least a full word at a time.
sounds revolutionary
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 <= C. They also found that in a sorting network handling 4 inputs, when it is part of a "sort 8" network, there are similar guarantees (D >= min(A, C) in this case) that can be taken advantage of to remove an instruction as well. The compiler may not be able to compete with hand-written assembly, but it seems an AI can hand-write assembly code that's even better in some cases.
Another improvement is also very cool. They discuss VarSort4, which takes a list that may be 2, 3, or 4 elements long, and sorts it. The existing algorithm is
if (len = 4) {
sort4
}
elif (len = 3) {
sort3
}
elif (len = 2) {
sort2
}
if (len = 2) {
sort2
}
else {
sort3
if (len = 4) {
sortspecial
}
}
Very cool. Improving on core LLVM sorting algorithms that have already been heavily hand-optimized by the best in the world is definitely a "it's 1997 and Deep Blue defeats the World Champion in chess" kind of feeling.
Divide and conquer strategies are used for larger sorts, and the smaller arrays could include the fixed lengths 3, 4, 5.
This made me think “imagine if AI was the compiler”, that is to say you went from C or whatever to assembly via AI directly so it was “hand writing” the equivalent assembly for your instructions instead of using generic compilation.
We might find everything runs much faster.
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) finally being fixed late 2021 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.
Can you explain this for someone unfamiliar with the game?
https://www.youtube.com/watch?v=H4DvCj4ySKM
EDIT:
Also, if you want to get into it, Micheal Redmond's Go TV on youtube has an amazing beginner playlist, watch some of that then maybe blacktoplay.com and if you likey play :)
https://forums.online-go.com/t/how-does-the-rating-system-wo...
We (hacker news) discussed Lee Sedol's retirement here: [1]
To active go players at the time, Alpha Go and Alpha Zero really were as shocking as the debut of Chat GTP was recently.
I think their assertion is that the release of AlphaGo has actually made human Go players worse at the game, contrasted with chess where most agree that the introduction of Superhuman chess engines has elevated the (human) state of play.
But I don't think there is actually much evidence for that. I'm sure the introduction of AlphaGo did take the wind out of some players sails, who thought of themselves as superior to our best computers, but for everyone else it seems to have elevated the overall level of play just the same as the chess engines have done.
[0]: "The sudden overall increase in agreement in 2016 also reinforces the belief that the introduction of powerful AI opponents has boosted the skills of professional players." https://ai.facebook.com/blog/open-sourcing-new-elf-opengo-bo...
Geez. We are talking about pebbles on a wooden plank. They are not even colourful!
Go is super cool game, but it is that. Just a game. We are not talking about curing cancer, or solving world hunger, or reversing climate change here. So by the very formulation a Go playing AI can be cool, or interesting, or promising. But could it really be useful/important with all-caps? It sounds like you have too high expectations here.
It’s not hard to see why, with the emergence (ha) of OpenAI, Midjourney and all of this generative modelling, what has DeepMind done? I imagine the execs at Google are asking them some very probing questions on their mediocre performance over the last 5 years.
Deep minds work on Density functional theory was complete rubbish, and everyone in computational chemistry knows it. They simply modelled static geometry and overfit their data, we wanted this methodology to work, computing DFT is expensive, and we did multiple months of rigorous work and the reality of the situation is that a bunch of machine learning engineers with a glancing amount of chemistry knowledge, made approximations that were way too naive, and announced it as a huge success in their typical fashion.
What they then count on is people not having enough knowledge of DFT / Quantum property prediction to query their work and make claims like “it certainly does move academia way further ahead” - which is total rubbish. In what way? Why aren’t these models being used in ab initio simulators now? The answer to that is simple: they are not revolutionary, in fact they are not even useful.
There must be a "demonstrate (1) DeepMind #Win per <interval>" requirement somewhere that gets the once-over from the marketing dept. to meet some MBOs.
Go players are using AI to get better at Go.
Read this for example. The author is Korean pro.
"The upside is that we sometimes see a player who was somewhat past his prime suddenly climb back to the top, having trained with AI more intensely. There are a growing number of young and new pros who demonstrate surprising strength. This change gives hope to all pros who dream to become number one, and also makes competitions more interesting to fans as well." [0]
There are serious downsides too.
Also [1]
[0] https://hajinlee.medium.com/impact-of-go-ai-on-the-professio...
[1] https://www.newscientist.com/article/2364137-humans-have-imp...
Hear me out - what if we learned something about creating AI by creating a new AI?
A rising tide floats all ships – if the best in the world becomes better, others can look at the best and learn from it. What difference does it make if the best player is an AI or a human? The better moves and strategies are still better moves and strategies.
1) you could see increased activity in go clubs and online go servers
2) the analysis of the games published by Deepmind has resulted in interesting "discoveries" (or rediscoveries) and changes to what is considered joseki.
3) many people started analyzing their kifus using AI, to find fluctuations in estimated win rate across moves.
So I disagree entirely
Don't get me wrong, Sutskyver (et al) has done incredibly good work previously, but when it comes to the products, they're much more engineering and marketing polish than scientific endeavours.
Botvinick's work on metaRL for example is an interesting direction that Deepmind has shown that few other companies that are only interested in engineering would venture towards.
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.
I disagree. Of course there is a lot of engineering involved and it's also very important but it's much easier to rebuild things based on published research than develop novel ideas.
It might, and in fact I think it probably will. But it hasn't yet.
AlphaFold catapulted protein structure prediction forward, and it's hard to overstate how important understanding protein structure is in modern drug development
As an example of how this will be used to help actual people, here's a paper that uses AlphaFold to identify the parts of cancer-associated proteins that interact with each other.
https://onlinelibrary.wiley.com/doi/full/10.1002/pro.4479
The obvious next step is to develop drugs that disrupt these interactions and thereby disrupt cancer. But, it's going to take years, maybe decades before any drug resulting from this research is in actual patients.
There are dozens of other papers like this.
1) The drug couldn't have been discovered without AlphaFold 2) It has been proven to reduce all cause mortality (the thing real patients actually care about) in a randomized controlled clinical trial BETTER than the prior standard of care (or significantly more cheaply, or with significantly reduced side effects)
It's like pointing to special relativity in 1905 and saying it'll never be useful for anything.
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.
They eliminated a register-register mov.
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
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
Edit: compiling the hunter code Right Away and hopefully in some weeks I'll have better networks. Selection networks are even harder to find optimizers for, hopefully one can hack this new thing to get some.
But, at its core, this is really a RL paper. The objective is to see how far a generic approach can work while understanding as little as possible about the actual domain. After AlphaGo exceeded expectations, the question becomes: "What else can RL do, and can it do anything actually useful?", and this paper seems to suggest that it can optimize code pretty well! I'm really not sure they are self-aggrandizing in terms of impact. The impact of an approach like this could potentially be very large (although I'm not saying that it actually is, I don't know enough).
But ya, discovering a new compiler optimization automatically is kinda cool.
Is it really? I've heard of a few "better sorting algorithms" and it's never meant that in my experience.
There are already superoptimizers who use genetic algorithms to find the most optimal code sequence for small easily verifiable tasks. That is also a form of reinforcement learning in a way
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.
Sure, it's great PR for the company, but.. the results just aren't there.
RL doesn’t stop at human levels
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.
But it's reasonable to imagine a later model trained to explain things. The issue is that some positions might not be explainable, as they require branching too much and a lot of edge cases, so the explanation is not understandable by the human.
Can you explain how you had the intuition for a certain idea ? No you can explain why it works but not how the intuition came.
In the end, no matter what divide-and-conquer sorting algorithm you pick, you will be doing lots of "small sorts". And it is those small sorts that DeepMind has optimized here.
I think the sci-fi-but-possibly-real hope is that for sorting (among other things), we may have the perspective that there isn't any new algorithmic approach available, but an AI finds one for us.
Benchmark seems to be in the range of a 1-5% improvement for 80% of sizes.
For GPT you can kind of prompt it to do chain-of-thought reasoning, but it doesn't work very well; not if you compare it to what humans do.
Once again it seems like what we thought was hard, is easy; what we thought was easy and computer-like turns out to be hard.
Fast search often beats accurate search. Sometimes adding clever heuristics or more complex scoring "works" but slows down the search enough that it's an overall loss. Another kind of a bitter lesson, perhaps
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?
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.
In copyright, "transformative" refers to modifying or adapting a copyrighted work in a way that creates a new and original expression; resulting in a new work with a different purpose or meaning.
In terms of code, you'd "just be transforming" the assembly code to a systems language of your choice.
What's more interesting to me would be a model that can automatically port a program between languages, such as converting a C program to a fairly idiomatic Rust program.
I didn't hear of them in CS undergrad algorithms, perhaps because they can be thought of as a special case or optimization, rather than fundamental and generic variable-length sort algos.
It's a simple concept, and forms the basis of all the sort optimizations described here.
So O(0.3(N log N))? That's still O(N log N)
I never use ^ for "to the power of" due to its use in C for bitwise OR.
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.
You said: > you have to sort is within a known domain you can definitely beat
Not sure why you framed your response this way?
Every sorting on a computer existing in reality is within a limited domain.
The general sorting problem is an artificial problem for theoretical computers with infinite memory.
It's a philosophical problem not an engineer one
Thank you.
Note that the proposed ML (micro-)algorithms rely heavily on the fact that they are sorting 32-bit or 64-bit integers because they are using conditional moves. A conditional move avoids a branch by converting the instruction to a no-op when the condition doesn't hold. This is fine when moving 4 or 8 bytes because it can be done in a single clock cycle, but you can't apply the same technique when sorting larger objects.
https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...
No, absolutely no, it's not in any meaningful or useful sense "faster" as in which algorithm is "faster". You utterly fail to get this point.
You keep trying to equate naive algorithmic complexity and speed, but you haven't even linked anything that shows heapsort is better than other sorts like quicksort at that. You haven't actually linked anything to back up any of what you're saying, even the irrelevant offtopic claims.
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.
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.
I think you're the only one saying that. Where did you get this idea? I just showed you a quicksort being 10 times faster than a heapsort. You can try this for yourself.
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.
This is never going to be true. Quicksort and other sorts exploit locality much better. Partitioning an array gradually makes the sorting more local. That's going to work better relatively to a heap sort as data gets bigger, not worse.
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.
No, on any modern computer other sorts are going to beat a heapsort. It isn't exotic, it is how it works. Even if you have to scan every element first to get a distribution of your elements to choose your pivot, that is still going to be O(n log n) and it will still beat a heap sort.
Heap sorts are not the fastest way to sort. They can be consistent and they can split the time between inserting and extracting elements.
"in general" is not very specific.
The main issue is the big-O expression. Again, if win in the big-O expression, then, in the assumptions of the context, for sorting n keys for all sufficiently large n will win.
Sure, maybe the heap sort O( n log(n) ) is wrong. In that case, maybe could beat heap sort.
How could O( n log(n) ) be wrong? Well for large enough n, could encounter virtual memory paging that would make the cost of a comparison grow with n and an algorithm that had better locality of reference and less paging might win. So, for such a context, would have to redo the big-O derivation.
Merge sort is based on comparing keys two at a time, and that was the assumption in Gleason's argument. So, Gleason's argument should also apply to merge sort. Some people prefer heap sort or quick sort because they are in place and merge sort is not.
I wrote and you quoted:
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.
> I think you're the only one saying that.
Also Gleason, Knuth, and much of the academic computer science community.
> Where did you get this idea? I just showed you a quicksort being 10 times faster than a heap sort.
Your "10 times" is not for all values of number of keys n. The crucial issue is the big-O expression, and your "10 times" says next to nothing about the big-O expression.
Again, the big-O expression is crucial because winning in the big-O expression means winning for all sufficiently large n, and that is, sadly, the only really meaningful means we have of comparing "in general" two pieces of code.
Instead, sure, if in a particular application have an upper bound on n, say, always less than 10,000,000, then use the code that is fastest from 1 to 10,000,000 or in expectation on the probability distribution of n from 1 to 10,000,000 in the particular application. Or, maybe in some application don't care about the average execution time but definitely always want execution time faster than some given T milliseconds for all n from 1 to 10,000,000. Okay, pick the code that best achieves this.
Gleason's work didn't cure cancer, exceed the speed of light, say what is in the center of a black hole, say what happened before the big bang or will happen after the heat death of the universe, .... Instead, Gleason stated and proved a theorem in applied math. The theorem shows what is the best possible given the assumptions. Similarly for what Knuth said about heap sort and Gleason's theorem. A lot of progress in pure/applied math and science is like that -- not everything but just a specific result given some specific assumptions.
Or, assume that Joe has a new computer, 1000 cores, 10 GHz clock, 500 GB first level cache, and writes some really careful code in assembler that makes full use of the 1000 processors, to sort 10 billion 32 bit numbers via bubble sort. Then it runs in O(n^2), that is, for some constant k_Joe runs in
k_Joe n^2 = k_Joe (10^10)^2
milliseconds.
Along comes Bill with a PC based on a 64 bit single core processor with a 2 GHz clock. Bill's code uses heap sort. Then Bill's code runs in O( n log(n) ) or for some constant k_Bill runs in
k_Bill (n log(n) ) =
k_Bill (10^10 log(10^10) )
milliseconds.
And Bill is a bit sloppy and uses an interpretive language so the constant k_Bill is large.
Then the ratio of running times is
(k_Joe / k_Bill) (n / log(n) )
Well, assume for simplicity and without loss of generality that the log has base 10. Then
log(n) = log(10^10) = 10
so that
n / (log(n)) = 10^10 / 10
= 1,000,000,000
Well, let's account for Joe's 1000 cores to get a ratio of 1,000,000 and Joe's 5 times faster clock speed to get 200,000. Say the interpretative language Bill used is 10 times slower than compiled C for a ratio of
20,000
and say that Joe's hand coding in assembler is 2 times faster than C code for a ratio of
10,000.
So, still Bill's code runs
10,000
times faster than Joe's.
That's an example of, the algorithm that wins in big-O wins for all sufficiently large n, even considering coding in assembler with 1000 cores and a 10 GHz clock.
Sure, for n = 100, maybe Joe's code wins -- I'll let you find the ratio.
That's what the computer science community noticed some decades ago and, thus, settled on big-O as the way to compare algorithms and code. Again, heap sort meets the Gleason bound in worst case. Since in the context the Gleason bound says that O( n log(n) ) is the best can do, the best quick sort can do is tie. And if the quick sort code does not make the partitions carefully, quick sort won't be O( n log(n) ) in worst case and for sufficiently large n will lose by whatever ratio want, 1,000,000:1 if you want.
Look, guys, all this is just from, say, the first week of a ugrad course in computer science.
Arguing with the Gleason bound -- about like arguing with the Pythagorean theorem.
Don't argue with me. Instead, send a question to a comp/sci prof at your local university giving him the URL of this post.
Prove it, show me who is saying 'nothing can beat a heapsort'.
says next to nothing about the big-O expression.
Why do you think heap sort is the only n log n sort? Link something that proves what you say.
settled on big-O as the way to compare algorithms and code
Time determines speed, that's what this thread is about. I already linked you a benchmark of 32 million floats. Link me something that actually backs up what you are saying.
Arguing with the Gleason bound -- about like arguing with the Pythagorean theorem.
Link me where you got these ideas from. I'll link you something, a google search on 'gleason bound' - https://www.google.com/search?q=%22Gleason+bound%22
The only thing that comes up is your comment. I've shown you actual results, you keep saying 'maybe possibly in some scenario I can't show, this other one wins, so it is the fastest'. You are hallucinating a reality that you can't demonstrate.
Here you are embarrassing yourself.
All you did was repeat your claim over and over. No benchmarks, no link to 'gleason bound' and nothing but hallucinating hypothetical scenarios and declaring that somehow they would back up your claims that go against literally all benchmarks and computer science knowledge. If I'm wrong, show me some links.
More precisely, if the key length is w, then radix sort is O(w n) operations. In particular, if the n elements are distinct integers for example, w is greater than log(n).
Early in my career, I had a really good career going. I paid a lot of attention to writing fast code.
Some of that career was in a Navy lab, and some of the people there wrote fast code by going down to the assembly language and checking each instruction, load, store, etc.
At times that career bumped into some math -- 0-1 integer linear programming, even ordinary linear programming, optimization, e.g., BFGS as elsewhere in this thread, the fast Fourier transform, power spectral estimation, optimal control, stochastic optimal control, classic linear statistics, non-parametric statistics, ill-conditioned matrices, on and on. So, to get a better background in the math, I put my career on hold and went for a Ph.D. in pure/applied math.
In my first semester the faculty wanted me to take their first ugrad computing course. Heck, I'd already taught such a course at/for Georgetown U. But I took the course anyway.
Then in the course, the issue of fast code came up. Soon, by some of the computer science faculty interested in computational complexity, I got slapped around like a butterfly in a hurricane.
Yup, one way, commonly the way first seen, to write fast code is to check each machine instruction, pay attention to caches, locality of reference, etc.
But another way to write fast code is to back off, basically forget about the individual instructions, etc. and take as the criterion number of comparisons of pairs of keys. Right, just f'get about all those other details of the hardware, just what the compiler did with do-while and if-then-else, etc. That's what was catching on, strongly, in computer science at the time.
Sooo, broadly that's two quite different ways to look at how to write fast code.
The Gleason bound? That's in one of the D. Knuth volumes The Art of Computer Programming. That was A. Gleason, a math prof at Harvard with a spectacular career -- before his Ph.D., solved one of D. Hilbert's famous problems intended to keep mathematicians occupied for the 20th century, was made a Harvard Fellow, joined the math faculty, and never bothered with a Ph.D.
Gleason started with, for any given positive integer n, we will be sorting n keys. Sooooo, how big of a problem is that? Well (from my memory and not looking up my copy of Knuth on a shelf just behind me), assume the keys are distinct, that is, no ties. Then the problem is sorting all n! permutations of the n distinct keys. Then, ... Gleason argued from just counting the permutations and assuming that the sorting was by comparing pairs of keys, that on average could not sort in fewer than O(n log n) such comparisons. So, Gleason just counts comparisons and ignores number of parallel processors, number of levels of cache memories, the details of the instruction set of the processor(s), .... Then, as I recall, Knuth continues on and argues that heap sort achieves the Gleason bound both on average and worst case. Sooooo, in that context, heap sort is the fastest possible.
Right: The class could have had a contest, who can write code for the fastest sort on a certain list of, say, 10,000 names. Some people use quick sort, heap sort, radix sort, shell sort, bubble sort, ....
No telling who will win. Even if several students use heap sort, no telling.
So what CAN we tell? As n grows, even some really inefficient coding, maybe even in an interpretive language, will totally blow away like that butterfly in a hurricane ANY coding of bubble sort. And as I recall, it's possible for quick sort to lose on some permutations unless the partitions are selected carefully -- that is, the worst case performance of some versions of quick sort can fail to achieve the Gleason bound and run slower than even a very inefficient coding of heap sort.
That is, if want to take Gleason's approach, just count comparisons of pairs of keys and look at the big-O results, can't beat heap sort.
A short answer is, if win in the big-O comparison, then, no matter how sloppy the coding, for all sufficiently large n, still will win no matter how measure speed. In short, that's the reason people took big-O very seriously.
Yes, there is more to computational complexity than I've outlined here, and as I've already mentioned, in some contexts there can be more to sorting.
Still, again, in short, in simple terms, in a very important sense, Gleason was right, can't beat the Gleason bound, and can't beat heap sort.
I just wanted to improve my career. I never wanted to be a college professor, teacher, researcher, etc., yet for various reasons I've done all those things.
Now "to improve my career", I want to be a successful entrepreneur. My startup? It might flop, and I can't be sure it won't. But it might be worth $100 billion, and I can't say it won't. Here I've made a little contribution to the teaching of computing, coding, and computer science of sorting. But I'm no college professor. Back to my startup. A Chaired Professor of Applied Math? I don't want to occupy one. If my startup is really successful, maybe I'll fund one.
Second, your "alternative speed" measures are a hallucination.
Sooo, broadly that's two quite different ways to look at how to write fast code.
No there isn't. The one that takes 1/10th the time of the other one is faster. You going off on tangents and making up terms to try to say that a heap sort is the fastest sort (of all the strange things to argue) is nonsense.
For the answer and posted in this thread, I wrote:
The Gleason bound? That's in one of the D. Knuth volumes The Art of Computer Programming.
> Second, your "alternative speed" measures are a hallucination.
No. Instead, I wrote in this thread:
A short answer is, if win in the big-O comparison, then, no matter how sloppy the coding, for all sufficiently large n, still will win no matter how measure speed. In short, that's the reason people took big-O very seriously.
If you want to argue against heap sort, then you need to argue that in counting comparisons the big-O expression for heap sort is wrong and loses out to some other sorting algorithm.
The Gleason bound assumes that each comparison costs the same. So you may want to argue that for n keys, as n grows the issues of caches, locality of reference, parallel processors, etc. mean that the cost of each comparison grows so that in the big-O competition heap sort can be beat.
I'll let someone else calculate the big-O expressions again considering locality of reference, etc.
Instead of repeating yourself, can you link to some actual information?
still will win no matter how measure speed
Speed is measured with time. You can keep saying algorithmic complexity is speed, but that will never make it reality.
If you want to argue against heap sort, then you need to argue
That's not how it works. Other sorts take a fraction of the time. I showed you this already.
I'll let someone else calculate the big-O expressions again considering locality of reference, etc.
This was never about algorithmic complexity, that's something that you hallucinated. Not only that, but you do realize that other sorts have the same complexity as heap sort right? There a lot of ways to sort with n log n.
You are trying to argue something that isn't real to make a point that no one cares about and has nothing to do with this thread.
In a word, you are wrong.
I've been very, very, very clear again, over again, once again, yet again, and you just fail to get it, a simple lesson often just in the first week of an easy, first college course in computer science.
> Other sorts take a fraction of the time. I showed you this already.
Nope. You showed no such thing. Your evidence is meaningless. Heck, even bubble sort could beat heap sort or quick sort under some circumstances.
So, again, sit down, pay attention, listen up: What matters for any measurement of performance in comparing code is the big-O expression. Read this again, again, again, write it on the blackboard 1000 times after school, repeat it to yourself before each meal, going to sleep, waking up. You just pass this off as computational complexity irrelevant to execution time. Here you are just wrong, totally, badly wrong. You seem not to understand this. For any measurement, time, Watts, Joules, comparisons, cycles, any measurement, in the reasonable context, what matters is the big-O expression.
> There a lot of ways to sort with n log n.
Well, merge sort can. Maybe some versions of quick sort can. Okay, there are some ties. I never said there are no ties. But, in the context, can't beat O( n log(n) ) -- the Gleason bound shows this. I've said this over and over and over and over. So, in the context, can't beat heap sort. What you saw in some two pieces of code on 1000 keys is just irrelevant to a meaningful comparison of performance.
> The Gleason bound?
> Instead of repeating yourself, can you link to some actual information?
I gave the information: First in the context heap sort, merge sort, maybe quick sort run in O( n log(n) ) in comparisons and also, in this context, inescapably, in time, cycles, Watts, Joules, whatever. The "faster" is not for n = 1000 but for all sufficiently large n. For n = 1000, anything can happen. Second the Gleason bound says that, in the context, can't sort faster than this. So that's why it's call a "bound", a lower bound on how fast can sort. Third, I gave the reference, D. Knuth's famous book.
The Gleason bound is one of the nicer, most powerful, most useful, most important pieces of work in all of computer science, computer programming, sorting, and computing for any and all purposes, in particular for practical performance, and you just fail to get it.
You have some problems, some blocks in understanding. You just do not want to learn something new to you. You deeply resent this. Your problem is not about computers or applied math but emotional. For your emotional problems, nothing in computing, computer science, or my writing can help you.
Prove it, show me something.
Your evidence is meaningless.
I showed you benchmarks with source code. You showed me nothing.
Heck, even bubble sort could beat heap sort or quick sort under some circumstances.
It isn't going to beat them on 32 million floats, which was what that benchmark showed. And are you now mixing up actual execution time with your other bizarre claims where 'speed' and 'faster' for some reason don't mean less time?
Okay, there are some ties. I never said there are no ties.
You did actually, now you're back peddling hard. Also these don't tie, they are faster because of locality.
Third, I gave the reference, D. Knuth's famous book.
Link something then, link any trace of what you are saying.
The Gleason bound is one of the nicer, most powerful, most useful, most important pieces of work in all of computer science,
Then why is there no evidence that it exists? Link me literally anything you can.
You have some problems, some blocks in understanding.
No, I have evidence and links that back up what I'm saying. You keep repeating the same things with no evidence. Link me literally anything you can find that reinforces your claims.
For your emotional problems, nothing in computing, computer science, or my writing can help you.
This is pure projection.
> I gave the reference, D. Knuth's famous book.
I just Ctrl+F'd "Gleason" in The Art of Computer Programming Vol 1, Vol 2, Vol 3, Vol 4A, and Vol 4B, with no hits in any of the 5 books.
I even looked in the glossaries. There's lots of last names -- Glaisher, Glassey, Gnedenko -- and no "Gleason".
I'm tempted to side with this iteration of CyberD's brutal takedowns on this one. :D
---- EDIT ----
WAIT: I found it in the glossary of Vol 3!
"Gleason, Andrew Mattei, 193, 648."
For this one, case sensitivity got me when I searched "gleason"!
The most relevant bit here seems to be page 193, discussing ways to minimize the average number of comparisons:
```
The minimum possible average number of comparisons, obtained by dividing by N, is never less than lg N and never more than lg N + 0.0861. [This result was first obtained by A. Gleason in an internal IBM memorandum (1956).]
```
"Gleason" is only mentioned in Vol 3.
"Gleason bound" is not used in Vol 3, which must be why it doesn't pop up on Google.
CyberD: now on the backfoot
graycat's startup: in talks for VC funding
Every accusation, as they say, is a confession.
My rule of thumb is when it’s easy to specify a reward function but infinite ways to traverse the action space - versus having a constrained state and action space (small n solution traversal pathways) and only a few possible paths to traverse.
News Release:
https://www.deepmind.com/blog/alphadev-discovers-faster-sort...
Not exactly what the title would lead you to believe.
Doing an empirical algorithm search to find which algorithms fit well on modern CPUs/memory systems is pretty common, see e.g. FFTW, ATLAS, https://halide-lang.org/
Or is that why hardware properties change so much?
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.
For practical sorting, for a particular CPU architecture, there is still plenty of low hanging fruit:
> Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort, and outperforms state of the art architecture-specific algorithms, while being portable across all modern CPU architectures
https://opensource.googleblog.com/2022/06/Vectorized%20and%2...
Does anybody know why they chose fifth percentile? I though we should always choose the fastest time when measuring performance.
If we measured sorting algorithms by the fastest measurement, we might conclude that BubbleSort is the fastest possible sort algorithm on some inputs. (Bubblesorting an already-sorted list makes at most one comparison per list element)
> 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 measuring performance.
Depends. For games you usually do sth similar to what they did - exclude small percentage of worst results to reduce influence of noise and then optimize the worst scenario to make the game run consistent and smooth.
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.
As always, speed depends on the use case. What's optimal for a sorting algorithm depends on the size of the data, its distribution, and also how it fits into the rest of the program and how that program fits into what else the machine is doing.
For example, you can make things faster by using more hardware resources, but that would penalize the rest of your program that doesn't have access to them anymore. I've frequently seen cases where a function was made faster in a microbenchmark by using all of the registers available, but then real programs ended up slower because the rest of the code had to spill to call it.
The instruction that was removed was: `P=min(A,C)`, which means that `P=A` at that point.
The next instructions:
cmp S Q
cmovg Q P
if S>Q: P=Q
if min(A,C)>B: P=B
So, the end result for sorting A,B,C=3,2,1 would be 3,2,3 for Alphadev's code.
I can't believe, I'm the first one to notice, so I'm probably wrong, but I cannot see where.
Apparently it just shows some algorithm that was modified and resulted in a different one, neither being a sorting algorithm, but the original still being better.
The text praises Alphadev by saying it makes "moves" that look like a mistake, but are actually brilliant. After that passage the code is shown that does not corroborate that statement, and just illustrates that Alphadev can make changes to code.
I would be interested to know if ML can be used to reverse hashes, such as to more quickly solve the numbers that satisfy the Bitcoin Hash challenge. Maybe it can even get P and NP closer together!
Are there theoretical results on SHA-256 or something that preclude finding an ML algorithm that, with a billion parameters, can speed up the search for a Bitcoin Hash input?
If that can be done say OS wide I could see that having an actual impact on global energy usage
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 problem.
BERT was 5 years ago. Of course it's worse than anything introduced more recently (both inside and outside Google).
What did it do if it didn't have a useful partial score function? How did it avoid brute force?
> To better estimate latency, we implemented a dual value function setup, whereby AlphaDev has two value function heads: one predicting algorithm correctness and the second predicting algorithm latency. The latency head is used to directly predict the latency of a given program by using the program’s actual computed latency as a Monte Carlo target for AlphaDev during training. This dual-head approach achieved substantially better results than the vanilla, single head value function setup when optimizing for real latency.
Briefly, they use a neural network to predict whether a given sequence of instructions is correct, and how fast it is. Then they used this neural network to guide the program generation via Monte Carlo tree search [1]. It is this procedure that keeps track of the partial score functions at each node.
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 attempt to replicate the “publish everything to support my brand” strategy of Deepmind.
I know Google is not a normal company in that Larry and Sergey have complete control of the company, but sooner or later they have to realize that Deepmind needs to be spun off, and further that Demis is entirely the wrong person to run Google’s AI. He doesn’t care a whit about Google, it is only a vessel to fund his research.
Products. A company is about products and customers not research papers. Academia or non-profits are about papers.
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 just the way to attract and retain quality folks.
Products.