Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

SeaHash: A fast, portable hash function in Rust

docs.rs

Post reply on HN
Print view View original

41–50 of 116 posts

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

#41

Post by Manishearth »

Animats wrote: post #34
fnord123 wrote: post #29

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.

> there's the possibility of safe code misusing the unsafe code to create unsafe behavior.

This is a misconception.

You can write un-abusable unsafe code pretty easily. There are a couple of invariants that the language requires you to uphold. As long as you uphold them you are fine. If your unsafe code can be broken by external safe code that is a bug in your unsafe code, on par with doing `let p = ptr::null(); print(*p);` in your unsafe code.

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

#42

Post by Animats »

pcwalton wrote: post #37
Animats wrote: post #34

Earlier quoted context omitted.

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.

Unsafe code must uphold the invariants of safe Rust.

Ideally, yes. In practice, maybe. We're probably going to see "unsafe" code that assumes good behavior on the part of the caller. That's a classic problem with APIs.

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

#43

Post by pcwalton »

Animats wrote: post #42
pcwalton wrote: post #37

Earlier quoted context omitted.

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.

Unsafe code must uphold the invariants of safe Rust. Ideally, yes. In practice, maybe. We're probably going to see "unsafe" code that assumes good behavior on the part of the caller. That's a classic problem with APIs.

There's no way to solve that problem without just forbidding unsafe code entirely. Unsafe code can have bugs; that's why you should keep it to the minimum and keep it well-known and audited.

In this case, the byteorder crate would have been more appropriate than handrolling unsafe code.

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

#44

Post by valarauca1 »

Animats wrote: post #33
aleyan wrote: 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…

   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.

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

#45

Post by Animats »

pcwalton wrote: post #43
Animats wrote: post #42

Earlier quoted context omitted.

Unsafe code must uphold the invariants of safe Rust. Ideally, yes. In practice, maybe. We're probably going to see "unsafe" code that assumes good behavior on the part of the caller. That's a classic problem with APIs.

There's no way to solve that problem without just forbidding unsafe code entirely. Unsafe code can have bugs; that's why you should keep it to the minimum and keep it well-known and audited. In this case, the byteorder crate would have been more appropriate than handrolling unsafe code.

There's no way to solve that problem without just forbidding unsafe code entirely.

That's not at all clear. It's worth looking at unsafe code and asking "why was this necessary"? What couldn't you do within the language? As patterns reoccur, it may become clear what new safe primitives are needed.

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

#46

Post by Manishearth »

Animats wrote: post #42
pcwalton wrote: post #37

Earlier quoted context omitted.

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.

Unsafe code must uphold the invariants of safe Rust. Ideally, yes. In practice, maybe. We're probably going to see "unsafe" code that assumes good behavior on the part of the caller. That's a classic problem with APIs.

> We're probably going to see "unsafe" code that assumes good behavior on the part of the caller.

I have yet to see any of this.

I have noticed that it's harder to write correct unsafe code when it comes to parallelism and FFI, but parallelism has always been a hard problem and the FFI problems generally come from the fact that you need to know the invariants being upheld on the other end, which is trickier.

But for this kind of unsafe code -- designing (non-parallel) abstractions -- upholding invariants is pretty straightforward.

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

#47

Post by pcwalton »

Animats wrote: post #45
pcwalton wrote: post #43

Earlier quoted context omitted.

There's no way to solve that problem without just forbidding unsafe code entirely. Unsafe code can have bugs; that's why you should keep it to the minimum and keep it well-known and audited. In this case, the byteorder crate would have been more appropriate than handrolling unsafe code.

There's no way to solve that problem without just forbidding unsafe code entirely. That's not at all clear. It's worth looking at unsafe code and asking "why was this necessary"? What couldn't you do within the language? As patterns reoccur, it may become clear what new safe primitives are needed.

Why is it better to add safe primitives directly to the compiler rather than implementing them in libraries?

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

#48

Post by Manishearth »

Animats wrote: post #45
pcwalton wrote: post #43

Earlier quoted context omitted.

There's no way to solve that problem without just forbidding unsafe code entirely. Unsafe code can have bugs; that's why you should keep it to the minimum and keep it well-known and audited. In this case, the byteorder crate would have been more appropriate than handrolling unsafe code.

There's no way to solve that problem without just forbidding unsafe code entirely. That's not at all clear. It's worth looking at unsafe code and asking "why was this necessary"? What couldn't you do within the language? As patterns reoccur, it may become clear what new safe primitives are needed.

> As patterns reoccur, it may become clear what new safe primitives are needed.

In these cases you have a choice between inventing a safe language primitive or inventing a safe library primitive. This exists in most cases for seemingly-safe operations, like the byteorder crate in this case.

If it were a language primitive it would be just as trustworthy as the corresponding verified library primitive.

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

#49

Post by tveita »

pcwalton wrote: post #10
jedisct1 wrote: post #2

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

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

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.

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

#50

Post by thomasahle »

aappleby wrote: post #28

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

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?
Post reply on HN