Hacker News Reader

This sounds like a more intelligent version of superoptimization. The original Masselin SO, albeit for its time, also created surprising results which is similar to AlphaDev's incomprehensible for humans. You see the same thing in computer chess which Agadmator calls disgusting engine lines.

https://courses.cs.washington.edu/courses/cse501/15sp/papers...

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

SPSA, if memory serves.

https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_st...

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.

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.

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?

Sounds like the JVMs recompilation of hor paths to me.

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.

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

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.

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

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

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

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

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

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

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

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

> The idea is that `Pr[h(x) = h(y)]` is small _no matter the inputs x and y_.

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.

> > It is all about probabilistic guarantees

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

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

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.

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

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.

By definition, if they're secure then they should meet the requirements, right?

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

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

Yes, but the point is that hash functions used for hash tables are much, much faster than these cryptographic ones.

>If you really need a collision resistant hash you need to use a cryptographic hash function, but outside of cryptographic applications that is rarely the requirement.

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

> I'm not sure what security properties are really "proven" about existing cryptographic hash functions

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

IIRC, if P=NP then trapdoor functions do not exist, so proving that one existed would be a huge deal even outside of cryptography.

Only if your definitions of "easy" and "hard" are based entirely on complexity classes.

If you show me a setup where "easy" is n^3 and "hard" is n^15 I will happily call that a trapdoor function.

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?

In this particular case they were universal but in paper it's said the optimizations were done on x86. One of the ideas was to use LLVM IR but intuition for optimizer over optimizer was unlikely to work properly.

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

Wut?

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

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

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.

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

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.

Strawman; nul-terminated strings are horribly slow for nearly every application. Hence I assume (especially given that they are using c++) that they are using length-accompanied strings rather than nul-terminated ones.

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

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

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

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

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.

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.

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)

> It can do well with optimization and readability if you ask it specifically for those things

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.

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

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

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

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.

Packages might have delivery time windows attached to them, so the optimal solution calls for multiple visits in the same neighborhood by the same van. This is bs from a driver’s perspective.

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

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

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.

So it works as a superoptimizer of sorts.

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?

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?

> optimal programs are very inhuman

sounds revolutionary