Switch from SHA-1 to MD4 or something else cheap

[pcwalton]

SHA-1 is high in the profiles (4.8%). We don't need the strong cryptographic properties AFAICT.

[brson]

This is fine, but we're also using a very inefficient sha-1 implementation. I'm sure it's profile would drop considerably if we used git's.

[eholk]

I like that our SHA-1 implementation is written in Rust. Is the fact that it's slow because we wrote it in Rust, or because we wrote it in Rust using an inefficient algorithm?

[brson]

It's probably both. The Rust version is based on the reference implementation, which is not fast. Trying to optimize it could be a good experiment, but git's version uses a lot of tricks. I don't really like the idea of using a C implementation of SHA-1 either and I don't have any opposition to using MD4.

[marijnh]

I tried this today, and the performance gain was minimal. The MD4 hasher is in std::md4 now. It's moderately optimized, but I was forced to do some crummy things like manually assembling u32s from u8s and allocating a fixed-length vector on the heap.

[graydon]

If you're willing to drop strong cryptographic properties (which may well be fine in the context we're using this) then just switch to a modern non-CHF like spooky, murmur or city. Actually, might as well just put all 3 of those in our library: they're useful and one or another ought to be our default hash.

http://code.google.com/p/smhasher/
http://code.google.com/p/cityhash/
http://www.burtleburtle.net/bob/hash/spooky.html

All of them are much faster than md4.

[brson]

There's a Rust implementation of murmur here

[brson]

I haven't heard of sha1 being high in our profiles lately though, so it may not be as big of a concern as it once was.

[brson]

sha1 is still around 1% of profiles

[catamorphism]

We have to switch the remaining sha1 code to use sip in order for this bug to be resolved.

[graydon]

Closed by 1854a73