Live data from Hacker News

SeaHash: A fast, portable hash function in Rust

docs.rs

31–40 of 116 posts

Re: SeaHash: A fast, portable hash function in Rust

#31
post #5

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?

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_…

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.

Re: SeaHash: A fast, portable hash function in Rust

#32

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

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 (p…

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

Re: SeaHash: A fast, portable hash function in Rust

#33
post #12

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

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?

Re: SeaHash: A fast, portable hash function in Rust

#34

Earlier quoted context omitted.

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.

Sure. And if there's a problem, the search for the bug should be limited to the unsafe blocks. Which is the promised benefit over C++.

No. As soon as there's unsafe code, there's the possibility of safe code misusing the unsafe code to create unsafe behavior. One would like to have un-abusable unsafe code, but the language does nothing to guarantee that.

Re: SeaHash: A fast, portable hash function in Rust

#35
post #33
post #12

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

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::fr…

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.

Re: SeaHash: A fast, portable hash function in Rust

#36
post #12

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

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.

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

Re: SeaHash: A fast, portable hash function in Rust

#37
post #34

Earlier quoted context omitted.

Sure. And if there's a problem, the search for the bug should be limited to the unsafe blocks. Which is the promised benefit over C++.

No. As soon as there's unsafe code, there's the possibility of safe code misusing the unsafe code to create unsafe behavior. One would like to have un-abusable unsafe code, but the language does nothing to guarantee that.

The parent post is correct. Unsafe code must uphold the invariants of safe Rust. If unsafe code is safe only if the caller upholds some invariants not enforced by the compiler, then by definition it's the unsafe code that is wrong.

Re: SeaHash: A fast, portable hash function in Rust

#38
post #33
post #12

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

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::fr…

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

Re: SeaHash: A fast, portable hash function in Rust

#39

Earlier quoted context omitted.

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 (p…

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

None for large strings and you'd have to benchmark small strings.

Re: SeaHash: A fast, portable hash function in Rust

#40
post #34

Earlier quoted context omitted.

Sure. And if there's a problem, the search for the bug should be limited to the unsafe blocks. Which is the promised benefit over C++.

No. As soon as there's unsafe code, there's the possibility of safe code misusing the unsafe code to create unsafe behavior. One would like to have un-abusable unsafe code, but the language does nothing to guarantee that.

The unsafety still originates in the unsafe code, thus you can audit the use of the unsafe code or the unsafe code itself just the same.
Post reply on HN