13 ms·

You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms https://www.deepmind.com/blog/alphadev-disc

You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms https://www.deepmind.com/blog/alphadev-discovers-faster-sort..., https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It 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.

lukeplato 3y ago
> optimal programs are very inhuman sounds revolutionary
brundolf 3y ago
Thought: optimizing JIT compilers like V8 already observe code behavior and use that to choose how to optimize things as they go. I wonder if one day V8 will incorporate some ML to help study and optimize the running code
ks84 3y ago
I haven’t read the paper, but it sounds like this is a sort of similar approach to genetic algorithms? Create lots of agents with random changes and pick the ones that produce the most promising results? Is my impression wrong?
thomasahle 3y ago
I'm disappointed a the hashing is just based on training on microbenchmarks and SMHasher, rather than designing a fast _provably_ universal hash. Suites like SMHasher are never complete. They are just trying to catch the most common weaknesses. If you train on the test cases you'll only get an algorithm that passes the tests, but people can always find a set of values on which you will do badly.
- jacquesm 3y ago
  Indeed, and this has been the case for quite a while now. You can always improve on some general algorithm by taking advantage of knowledge of the data but that never generalizes and usually leads to either worse performance on other data and/or new pathological cases that result in results that are unusable. It's an instance of overfitting.
  - bee_rider 3y ago
    Ship the optimization framework in with the application, sample from the user data, and optimize for that? It isn’t overfitting if you overfit on the data you care about, right?
    - scns 3y ago
      Sounds like the JVMs recompilation of hor paths to me.
    - jacquesm 3y ago
      Data tends to change over time, and once a hash function is in use you can't really replace it easily without a lot of overhead, possibly quite a bit more overhead than what you saved in the first place. There are some examples of this in the sorting arena too, such as 'Timsort', personally I haven't found any that gave a substantial boost, but probably there are some cases where they do. Unless sorting or hashing (and lookup) are the main bottleneck for an application I would spend my time on other aspects of it.
    - deleted 3y ago
      [deleted]
13of40 3y ago
> something incomprehensible for humans 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.
- tyingq 3y ago
  One of the examples from another comment[1] here was: "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. [1] https://news.ycombinator.com/item?id=36229068 https://news.ycombinator.com/item?id=36229068
cabalamat 3y ago
> proves the point that optimal programs are very inhuman Maybe there should be an AI that produces optimally-readable/understandable programs? That's what I would want if I was adding the output to a codebase.
- m3kw9 3y ago
  It’s not that is written like obfuscated, the routine/ algo is just hard to understand even if they commented every line. Likely some recursive trick is involved, those are always hard to follow
- make3 3y ago
  that's what LLMs can with rl from human (or ai) readability feedback & instruction tuning + prompting. we will 100% see this if gpt-4 doesn't already do this.
  - ska 3y ago
    I wouldn't classify any of the output I've seen so far as "optimally readable/understandable". Some if it looks pretty ok, especially where it overlaps with well established approaches.
    - chaxor 3y ago
      It can do well with optimization and readability *if you ask it specifically for those things*. Especially if you have a particular paradigm and algorithm in mind (you obviously already should anyway). 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)
hajile 3y ago
To what extent is this simply working around the weirdness of x86? Do these improvements apply to something like MIPS, ARM64, or RISC-V that have inherently simpler ISAs?
- danlark 3y ago
  In this particular case they were universal but in paper it's said the optimizations were done on x86. One of the ideas was to use LLVM IR but intuition for optimizer over optimizer was unlikely to work properly.
  - ndesaulniers 3y ago
    > but intuition for optimizer over optimizer was unlikely to work properly. Wut?
    - mindwok 3y ago
      My guess: Using LLVM IR would mean that the LLVM optimiser might have made the results more noisy or hard to understand when it was compiled to actually execute.
CalChris 3y ago
This sounds like a more intelligent version of superoptimization. The original Masselin SO, albeit for its time, also created surprising results which is similar to AlphaDev's incomprehensible for humans. You see the same thing in computer chess which Agadmator calls disgusting engine lines. https://courses.cs.washington.edu/courses/cse501/15sp/papers/massalin.pdf https://courses.cs.washington.edu/courses/cse501/15sp/papers...
- mtlmtlmtlmtl 3y ago
  Stockfish actually use machine learning to pick the best magic numbers for their code.
  - agalunar 3y ago
    SPSA, if memory serves. https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_stochastic_approximation https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_st...
thesz 3y ago
So it works as a superoptimizer of sorts.
gumby 3y ago
Your description makes the approach sound like applying ca 1980s simulated annealing, also a form of gradient descent. Am I missing something?
- ska 3y ago
  This doesn't really sound like SA, which is a principled approach to avoid the local min problem in descent algorithms and end up with a true global optimization. The general result is clean and impractical, the approximations hard to analyze.
sytelus 3y ago
If more compute is spent than before but in parallel to reduce latency then wouldn't this increase power? Shouldn't latency and power both be objective?
moonchild 3y ago
> 9-16 was a better spot and it simplified from 2 multiplications to just one and a rotation I'm very confused as to why rotation was at all useful. Xoring with a random-ish constant makes sense, because the constant has high entropy and is likely to decorrelate bits from the input (also can use a different constant per hash table). But rotating by a constant—and a fixed one at that—seems like it just accounts for expected input distribution. Especially (assuming this is intended for text) if shifting by a value >8 makes a significant difference (vs shifting by the same value mod 8), it smells like serious overfit. Could be useful for something like a perfect hash, but seems problematic and prone to issues as a general hash. Edit: to make my objection clearer: the hash simply replaces lo with rotr(lo, 53). If rotr(lo, 53) performs significantly better than rotr(lo, 53 mod 8), then that implies the following. I can take a set of strings, and I can apply the same permutation to the characters of all of the strings in the set, and this will significantly affect the quality of the hash function. That seems like an undesirable property, even for a non-cryptographic hash.
- manwe150 3y ago
  Does that end up moving high bits into the low bits? That could possibly be very helpful for all sets of strings, since the equality test will start with the first byte, so it could better to have the rotr on the hash so that the hash is less affected by the first byte (and more affected by later bytes). Just hypothetically speaking that is where the implication could break down, since it doesn’t consider the non-uniform cost of the equality.
  - moonchild 3y ago
    > the equality test will start with the first byte 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.
    - manwe150 3y ago
      I didn’t look at their implementation, but in general, strings don’t have to be aligned so you can only peek one byte at a time looking for the end, besides not wanting to annoy valgrind and other similar UB detection tools by reading past the end of the string.

lukeplato 3y ago

> optimal programs are very inhuman sounds revolutionary

brundolf 3y ago

Thought: optimizing JIT compilers like V8 already observe code behavior and use that to choose how to optimize things as they go. I wonder if one day V8 will incorporate some ML to help study and optimize the running code

ks84 3y ago

I haven’t read the paper, but it sounds like this is a sort of similar approach to genetic algorithms? Create lots of agents with random changes and pick the ones that produce the most promising results? Is my impression wrong?

thomasahle 3y ago

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

jacquesm 3y ago
Indeed, and this has been the case for quite a while now. You can always improve on some general algorithm by taking advantage of knowledge of the data but that never generalizes and usually leads to either worse performance on other data and/or new pathological cases that result in results that are unusable. It's an instance of overfitting.
- bee_rider 3y ago
  Ship the optimization framework in with the application, sample from the user data, and optimize for that? It isn’t overfitting if you overfit on the data you care about, right?
  - scns 3y ago
    Sounds like the JVMs recompilation of hor paths to me.
  - jacquesm 3y ago
    Data tends to change over time, and once a hash function is in use you can't really replace it easily without a lot of overhead, possibly quite a bit more overhead than what you saved in the first place. There are some examples of this in the sorting arena too, such as 'Timsort', personally I haven't found any that gave a substantial boost, but probably there are some cases where they do. Unless sorting or hashing (and lookup) are the main bottleneck for an application I would spend my time on other aspects of it.
  - deleted 3y ago
    [deleted]

13of40 3y ago

> something incomprehensible for humans 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.

tyingq 3y ago
One of the examples from another comment[1] here was: "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. [1] https://news.ycombinator.com/item?id=36229068 https://news.ycombinator.com/item?id=36229068

cabalamat 3y ago

> proves the point that optimal programs are very inhuman Maybe there should be an AI that produces optimally-readable/understandable programs? That's what I would want if I was adding the output to a codebase.

m3kw9 3y ago
It’s not that is written like obfuscated, the routine/ algo is just hard to understand even if they commented every line. Likely some recursive trick is involved, those are always hard to follow
make3 3y ago
that's what LLMs can with rl from human (or ai) readability feedback & instruction tuning + prompting. we will 100% see this if gpt-4 doesn't already do this.
- ska 3y ago
  I wouldn't classify any of the output I've seen so far as "optimally readable/understandable". Some if it looks pretty ok, especially where it overlaps with well established approaches.
  - chaxor 3y ago
    It can do well with optimization and readability *if you ask it specifically for those things*. Especially if you have a particular paradigm and algorithm in mind (you obviously already should anyway). 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)

hajile 3y ago

To what extent is this simply working around the weirdness of x86? Do these improvements apply to something like MIPS, ARM64, or RISC-V that have inherently simpler ISAs?

danlark 3y ago
In this particular case they were universal but in paper it's said the optimizations were done on x86. One of the ideas was to use LLVM IR but intuition for optimizer over optimizer was unlikely to work properly.
- ndesaulniers 3y ago
  > but intuition for optimizer over optimizer was unlikely to work properly. Wut?
  - mindwok 3y ago
    My guess: Using LLVM IR would mean that the LLVM optimiser might have made the results more noisy or hard to understand when it was compiled to actually execute.

CalChris 3y ago

This sounds like a more intelligent version of superoptimization. The original Masselin SO, albeit for its time, also created surprising results which is similar to AlphaDev's incomprehensible for humans. You see the same thing in computer chess which Agadmator calls disgusting engine lines. https://courses.cs.washington.edu/courses/cse501/15sp/papers/massalin.pdf https://courses.cs.washington.edu/courses/cse501/15sp/papers...

mtlmtlmtlmtl 3y ago
Stockfish actually use machine learning to pick the best magic numbers for their code.
- agalunar 3y ago
  SPSA, if memory serves. https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_stochastic_approximation https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_st...

thesz 3y ago

So it works as a superoptimizer of sorts.

gumby 3y ago

Your description makes the approach sound like applying ca 1980s simulated annealing, also a form of gradient descent. Am I missing something?

ska 3y ago
This doesn't really sound like SA, which is a principled approach to avoid the local min problem in descent algorithms and end up with a true global optimization. The general result is clean and impractical, the approximations hard to analyze.

sytelus 3y ago

If more compute is spent than before but in parallel to reduce latency then wouldn't this increase power? Shouldn't latency and power both be objective?

moonchild 3y ago

> 9-16 was a better spot and it simplified from 2 multiplications to just one and a rotation I'm very confused as to why rotation was at all useful. Xoring with a random-ish constant makes sense, because the constant has high entropy and is likely to decorrelate bits from the input (also can use a different constant per hash table). But rotating by a constant—and a fixed one at that—seems like it just accounts for expected input distribution. Especially (assuming this is intended for text) if shifting by a value >8 makes a significant difference (vs shifting by the same value mod 8), it smells like serious overfit. Could be useful for something like a perfect hash, but seems problematic and prone to issues as a general hash. Edit: to make my objection clearer: the hash simply replaces lo with rotr(lo, 53). If rotr(lo, 53) performs significantly better than rotr(lo, 53 mod 8), then that implies the following. I can take a set of strings, and I can apply the same permutation to the characters of all of the strings in the set, and this will significantly affect the quality of the hash function. That seems like an undesirable property, even for a non-cryptographic hash.

manwe150 3y ago
Does that end up moving high bits into the low bits? That could possibly be very helpful for all sets of strings, since the equality test will start with the first byte, so it could better to have the rotr on the hash so that the hash is less affected by the first byte (and more affected by later bytes). Just hypothetically speaking that is where the implication could break down, since it doesn’t consider the non-uniform cost of the equality.
- moonchild 3y ago
  > the equality test will start with the first byte 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.
  - manwe150 3y ago
    I didn’t look at their implementation, but in general, strings don’t have to be aligned so you can only peek one byte at a time looking for the end, besides not wanting to annoy valgrind and other similar UB detection tools by reading past the end of the string.