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.
https://courses.cs.washington.edu/courses/cse501/15sp/papers...
https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_st...
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.
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.
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.
Wut?
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.
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.
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.
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.
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.
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.
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
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
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.
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.
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.
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.
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
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.
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 might, and in fact I think it probably will. But it hasn't yet.
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.
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.
They eliminated a register-register mov.
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.
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.
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
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.
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.
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.
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.
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)
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.
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).
https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...
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.
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.
I never use ^ for "to the power of" due to its use in C for bitwise OR.
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/
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...
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.
Does anybody know why they chose fifth percentile? I though we should always choose the fastest time when measuring performance.
> 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.
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)
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.