SeaHash: A fast, portable hash function in Rust

https://docs.rs/seahash/2.0.0/seahash/

by pcwalton • 10 years ago

186 114 10 years ago

docs.rs

jedisct1• 10 years ago

Great. But keep in mind that this is not a keyed hash function.

dsp1234• 10 years ago

This is mentioned in the documentation:

"Warning!

This is not a cryptographic function, and it certainly should not be used as one. If you want a good cryptograhic hash function, you should use SHA-3 (Keccak) or BLAKE2."

Dylan168072• 10 years ago

That's not the same thing. You don't usually key for crypto reasons, and a good cryptographic hash does not imply keying.

pcwalton12• 10 years ago

You can use it as a keyed hash function by adjusting the IV. See: https://docs.rs/seahash/2.0.0/src/seahash/.cargo/registry/sr...

tveita• 10 years ago

It seems to already be implemented in https://docs.rs/seahash/2.1.1/src/seahash/.cargo/registry/sr...

But it only seeds one of the lanes, so you can still make collisions trivially in one of the other lanes. I guess it could still be useful for namespacing.

eridius• 10 years ago

Very cool!

BTW, the hyperlink for "reference" in the "Specification" section is broken.

sp332• 10 years ago

I was trying to figure out how this is so much faster than FNV https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo... Is it only because of the parallelism? Or are the operations really that much cheaper somehow?

mastax• 10 years ago

Presumably because SeaHash operates on 8-byte blocks while FNV acts on single bytes.

LeifCarrotson• 10 years ago

Both.

The pseudocode for FNV looks like this:

   hash = FNV_offset_value
   for each byte_of_data to be hashed
   {
        hash = hash XOR byte_of_data
        hash = hash × FNV_prime
   }
   return hash

The pseudocode for seahash looks like this (with '×' as the wrapping multplier operator, and some simplification for padding if the data length in bytes is not a multiple of 8 bytes per word × 4 words in the hash state):

    hash = {offset_1, offset_2, offset_3, offset_4}

    for (int data_index = 0; 
             data_index < data.length_in_64_bit_words; 
             data_index = data_index + 4_words_in_hash)
    {        
        for (int hash_index = 0; hash_index < 4; hash_index++)
        {
            // Mix in data
            hash[hash_index] = hash[hash_index] XOR data[data_index + hash_index]
            // Diffuse
            hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32)
            hash[hash_index] = hash[hash_index] × seahash_prime
            hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32)
            hash[hash_index] = hash[hash_index] × seahash_prime
            hash[hash_index] = hash[hash_index] XOR (hash[hash_index] RSHIFT 32)
        }
    }

    result = hash[0] XOR hash[1] XOR hash[2] XOR hash[3] XOR data.length_in_bytes

    result = result XOR (result RSHIFT 32)
    result = result × seahash_prime
    result = result XOR (result RSHIFT 32)
    result = result × seahash_prime
    result = result XOR (result RSHIFT 32)

    return result

FNV is operating on bytes of data, while seahash is operating on 64-bit words. A modern processor will be able to handle 64 bits at once. True, it can probably handle 8 bits independently in one instruction without having to create a temporary value, but it still needs to do more operations.

FNV is completely sequential. Until the first byte is hashed, no work can be done on the second byte. In seahash, as you observed, parallelism can be exploited. The second, third, and fourth bytes are all completely independent of the first byte, as bytes 6, 7, and 8 are independent of byte 5, and so on. You can have four independent threads each do a quarter of the work, and then put the result back together at the end.

irq-1• 10 years ago

Hardware threads, just to clarify.

SeaHash achieves the performance by heavily exploiting Instruction-Level Parallelism.
This means that almost always the CPU will be able to run the instructions in parallel.

0x6c6f6c2• 10 years ago

So what you're saying is, is that this could be heavily optimized using OpenCL?

I might have to bookmark this as a project to take on. A heavily parallel hashing algorithm that takes advantage of OpenCL would immensely increase the efficiency wouldn't it?

(I'm dipping my toes in parallel processing as of late and am genuinely curious in this topic and question)

0x6c6f6c2• 10 years ago

Is FNV algorithm limited in the same way as a ripple carry adder is then, where every operation relies on the previous result, and can't be (or maybe just isn't but could be) done in parallel due to this implementation?

nullnilvoid2• 10 years ago

Great to see another piece of code written in Rust. That said, how do you make claims of something being blazingly fast without any comparisons to implementations in other languages such as C or C++?

tupshin• 10 years ago

The claim is that it is a blazingly fast hash function compared with other hash functions, and it is also written in Rust. Rust is an enabling technology, but not able to be dramatically faster than a comparable C/C++ implementation, as a general rule.

nullnilvoid2• 10 years ago

The title is confusing. If it tries to compete with other hash functions, why does the title have to bear "in Rust"?

pcwalton12• 10 years ago

Because it's benchmarking a hash function, not a language?

aleyan• 10 years ago

This is is not a knock against SeaHash, but I was looking at buffer.rs [0] and noticed pretty much all the code is wrapped in unsafe {} blocks. How much advantage is there to rust implementation vs c++ if unsafe is used so liberally? I ask this in ernest.

[0] https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs

fnord1232• 10 years ago

None. But once you're out of the buffer code, it's safe.

michaelmior• 10 years ago

It's safe as long as the unsafe code didn't mess with pointers in unexpected ways. Your unsafe code still needs to behave in a sane way for any safety guarantees to hold.

foota• 10 years ago

It seems like a small kernel of unsafe code, while the rest of the library is likely written safe. Perhaps more of this could be written safe?

idsout• 10 years ago

Better integration within the Rust library ecosystem. Instead of having to install a C/C++ library through my package manager, I can just add the seahash dependency to my Cargo.toml file and cargo will handle the rest.

pcwalton12• 10 years ago

Because the unsafe code is isolated into an easily-auditable portion that basically just exists to perform word-aligned reads of a byte buffer.

It might be nice to factor this out into a separate library, but it's fairly harmless.

pcwalton12• 10 years ago

Addendum: There is a separate library for this, of course: byteorder. Can't believe I forgot about it :)

reklawnos• 10 years ago

As others have mentioned, Rust allows you to write a safe wrapper around unsafe code. In this case, all of the functions implemented in buffer.rs are safe, even if their contents are not, so they can be used without having to worry about unsafety.

Another advantage over C++ is that it's much more clear what code is safe and what isn't, as unsafe code is wrapped in `unsafe` blocks, as you mentioned.

killercup• 10 years ago

How much advantage is there to rust implementation vs c++ if unsafe is used so liberally?

I'm no expert on the topic. IIRC, Rust does not have the same kind/amount of unspecified behavior as C/C++ do.

FYI: This is a "highly optimized version of SeaHash" (see comment in first line) with "optimized" meaning fiddling with raw pointers. You can find a version without any unsafe code is in `reference.rs`. I have no idea how fast the reference implementation is.

wyldfire• 10 years ago

How much advantage is there to rust implementation vs c++ if unsafe is used so liberally?

I think this code could potentially be refactored with smaller unsafe blocks, if that were a goal.

The benefit in general is present for many reasons, among which is that you still have to opt-in to unsafe{} and SeaHash consumers wouldn't need to in order to leverage these features.

The benefit for SeaHash specifically is that Rust isn't merely a safer language, it's also one with arguably newer/better language features than C++. And it's one that has support for several targets today.

dbaupp3• 10 years ago

That code looks like it could (and should, IMO) be refactored to put the unsafe code in more contained locations, e.g. the &[u8] could be manipulated into a (&[u64], &[u8]) pair (with the main sequence of values, and the trailing ones). Rust unfortunately can't stop people writing code that makes life hard for themselves.

Animats7• 10 years ago

This code is C code written as unsafe Rust:

    let mut ptr = buf.as_ptr();        
    let end_ptr = buf.as_ptr().offset(buf.len() as isize & !0x1F) as usize;
    while end_ptr > ptr as usize {
        a = a ^ read_u64(ptr);
        ptr = ptr.offset(8);
        b = b ^ read_u64(ptr);
        ptr = ptr.offset(8);
        c = c ^ read_u64(ptr);
        ptr = ptr.offset(8);
        d = d ^ read_u64(ptr);
        ptr = ptr.offset(8);

        ....
        match excessive {
            0 => {},
            1...7 => {                
                a = a ^ read_int(slice::from_raw_parts(ptr as *const u8, excessive));
                a = diffuse(a);
            },
            8 => {
                a = a ^ read_u64(ptr);
                a = diffuse(a);
            },
            9...15 => {               
                a = a ^ read_u64(ptr);
                ptr = ptr.offset(8);
                excessive = excessive - 8;
        ....

This bothers me about Rust. There's too much "unsafe" code in libraries. The language is unable to express some essential concepts. Known areas of trouble include partial initialization of an array, needed to implement growable collections, and single ownership doubly linked lists. Neither of those is expressible within Rust, which leads to unsafe code to implement them. Here, though, it's purely a performance issue. That's disturbing. If you can't do fast big-banging in safe Rust, there's a problem somewhere.

If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting, the code above could be much more straightforward. That's what I mean about expressive power. The hack to do that used here:

    let end_ptr = buf.as_ptr().offset(buf.len() as isize & !0x1F) as usize;

is iffy. Why is there an "isize" (a signed quantity) in there? They want to align with a 32-bit cache line, yes, but why the signed quantity? The documentation for Rust's "std::ops::BitAnd" doesn't say what the semantics are for signed numbers. What would happen on a 32-bit machine if someone allocated a buffer bigger than 2GB? Exploitable?

pcwalton12• 10 years ago

Why would hard-coding the ability to access a slice of bytes as ints into the compiler be safer than a well-encapsulated unsafe code abstraction?

We used to implement things like vectors directly in the compiler, but it was a big headache for no gain. Writing actual code is way easier than writing code to generate LLVM IR.

Anyway, there is a commonly-used crate for this: byteorder. Had I written the library, I would have just used that crate. But it's not a big deal either way.

Why is there an "isize" (a signed quantity) in there?

Because pointer arithmetic is signed.

The documentation for Rust's "std::ops::BitAnd" doesn't say what the semantics are for signed numbers

Bitwise operations on signed integers are applied to their twos complement representations.

What would happen on a 32-bit machine if someone allocated a buffer bigger than 2GB?

It would work.

Exploitable?

No.

Manishearth16• 10 years ago

There's too much "unsafe" code in libraries.

Which libraries? I see very few that do this, and all of them are safe abstractions containing some unsafe code.

You keep repeating this claim but I haven't seen any evidence to back it up.

If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting, the code above could be much more straightforward. That's what I mean about expressive power. The hack to do that used here:

The byteorder crate lets you do this. Of course, it uses unsafe code, but that's safely encapsulated away (and easy to verify). This crate doesn't use it, but it could. Not every operation needs to be baked into the language semantics.

valarauca1• 10 years ago

   This bothers me about Rust.
   There's too much "unsafe" code in libraries.

I like how with Rust you use one or two unsafe blocks and everyone loses their mind. But in C/C++ you spatter your code with undefined behavior and nobody bats an eye. I get Rust is _safe_ so violating this contract is in a way self defeating. But even with a handful of unsafe blocks you are miles ahead of other guarantees C/C++ give you. Lastly unlike C/C++ Rust makes you call out I'm doing dangerous stuff here!

    The language is unable to express some essential concepts.

Not really. The same code the parent poster highlighted [1] is undefined behavior in C/C++ (with standard types). So really no language has the ability to express those concepts. Your doing pointer casts and possibly unaligned dereferences at the same time. This has zero consistency between CPU vendors.

[1] https://docs.rs/crate/seahash/2.0.0/source/src/buffer.rs

    Known areas of trouble include partial initialization of an array, needed to implement growable collections

You mean Vector? C Doesn't have grow-able array's. They have re-alloc but Rust's Vector does that.

https://doc.rust-lang.org/std/vec/struct.Vec.html

    and single ownership doubly linked lists.

They already did, and it is in the standard library.

https://doc.rust-lang.org/std/collections/struct.LinkedList....

    If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting,
    the code above could be much more straightforward.

I mean C/C++ do, but without stdint.h you do this at your own peril. Even then you'll likely use Unions which are undefined behavior.

    What would happen on a 32-bit machine if someone allocated a buffer bigger than 2GB? Exploitable?

You can state this about C/C++ also.

Dylan168072• 10 years ago

I was unsure how to read the diffusion function's description, so I went to the source.

The first line, "x ← x ≫ 32", might have a typo? It's actually assigning (x XOR (x >> 32)).

With "x ← px", p is a fixed prime number being multiplied by x.

aappleby5• 10 years ago

Looks like a pretty straightforward 64-bit block hash unrolled 4 times. I'd prefer a bit more assymetry in the diffuse() method, but since it passes SMHasher it's probably OK.

I wonder how the Rust version compares with plain-jane C.

-Austin (murmurhash guy).

aappleby5• 10 years ago

Actually, just noticed a minor issue - since there's no intermixing between the four lanes and the diffuse() function is the same for all of them, if any of the IVs match then I can swap all the blocks in those lanes and get the same hash out.

For example, if IV1 and IV2 match and the block pattern is ABCDABCDABCD, then BACDBACDBACD will produce the same hash value.

A minor finalizer change would fix it for any IV (pseudocode as I don't actually know Rust) -

vec[0] ^= diffuse(vec[1]); vec[1] ^= diffuse(vec[0]); vec[2] ^= diffuse(vec[3]); vec[3] ^= diffuse(vec[2]);

u64 result = diffuse(vec[1] ^ diffuse(vec[3]));

that's probably overkill but should work.

alekratz• 10 years ago

I'm not a "hash guy" by any means - what impact would that have on its performance?

pbsd• 10 years ago

That won't help much; you can zero the entire final state easily, e.g., with the message IV0 IV1 IV2 IV3 (or by xoring the latest diffuse() output back into the state), in which case you get diffuse(0) = 0 and with your finalization function you still get easy collisions.

The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.

thomasahle• 10 years ago

Since you clearly pit a lot of thought into these kinds of hash functions, I wonder what you thoughts are about the kind of hash functions used in theory? That is theoretically proven "k-independent" functions, such as polynomial hashing, multiply shift or tabulation hashing?

aappleby5• 10 years ago

Making a fast, good hash function isn't too hard now, so some sort of "provable key-independent collision resistance" is definitely the next thing that needs to be worked on.

That said, I haven't really looked into the theory much.

warmwaffles• 10 years ago

I love working with murmurhash, but where the hell do I even start learning about hashing and the current theories around it?

aappleby5• 10 years ago

Take a look at the tests in SMHasher, they indirectly spell out a lot of what makes a hash "good" (though not all the tests are particularly readable).

tibbe• 10 years ago

How does it perform on short strings (e.g. <= 16 bytes)? We've seen several new hash functions lately with great throughput numbers, but unfortunately they often end up being slower than FNV when used e.g. on keys in hash maps, which are often short strings.

crtc• 10 years ago

What's the matter with this stupid word "blazingly" in the Rust community?

SeaHash: A fast, portable hash function in Rust

Related Stories