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

71–80 of 116 posts

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

#71

Post by Gankro »

pcwalton wrote: post #35
Animats wrote: post #33

Earlier quoted context omitted.

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…

I actually talked to Lattner about the isize thing a few months back -- according to him it's fine to overflow while doing GEP because llvm shouldn't care if you pass in negative offsets to represent really big positive ones.

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

#72

Post by wahern »

wahern wrote: post #55
valarauca1 wrote: post #44

Earlier quoted context omitted.

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…

> 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. It's undefined behavior in Rust, too. Rust code that type-puns an unaligned pointer into an integer would crash on…

Apropos of the mention of SHA-3 elsewhere in this thread:

I recently implemented my own version of SHA-3 in C. The original reference code from the authors (Google "Keccak-readable-and-compact.c") used type-punning in the inner loops (inside the the round function) on little-endian. On non-little-endian systems a macro was used to read and convert the 64-bit value.

This is typical premature optimization that is habitual among some developers, and another example of needless use of type-punning.

My code uses the simple code above to read bytes into the uint64_t buffer in the outer loop (outside the round function). Not only is my code simpler and easier to understand, it's no slower than the type-punning code even on x86-64.

Seriously, people, just don't type-pun. It's bad practice--in C, in Rust, in any language when using a remotely modern compiler. The only time it _might_ make sense is in very peculiar circumstances with peculiar access patterns, you've exhausted other easy gains, _and_ you've benchmarked and confirmed that type-punning is an improvement worth the cost in code complexity.

And even then, at least implement it correctly and safely. If you've already met the prerequisites above, the additional effort is negligible in the grander scheme of things. And committing to always writing correct and safe code keeps you honest when assessing whether performance hacks are truly necessary.

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

#73

Post by burntsushi »

wahern wrote: post #67
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.

I think the issue, if there is one, is that arguably the more appropriate thing to do would have been to implement the code without unsafe, using an intrinsically correct algorithm. The type-punning is premature optimization. _That_ was the misstep. That the byteorder crate exists is irrelevant in as much as this was an example of the urge for premature optimization leading the developer down the wrong path. The same…

> Also, looking at the byteorder crate, I wouldn't be surprised if it's even slower than the simpler and correct loop I posted elsethread. read_num_bytes in that create uses copy_nonoverlapping, which I assume is analogous to memcpy in C. That's a very round-a-bout and inefficient way to accomplish the task, and likely patterned after similarly bad C code.

It wasn't patterned after any C code. ptr::copy_nonoverlapping doesn't necessarily compile down to memcpy. Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores on x86, which is probably going to do better than the bit-shifting approach. Namely, loading a little-endian encoded integer on a little-endian architecture should be as simple as a single word-sized load (because the byte swap is unnecessary). It would be interesting to consider whether the safer and more readable bit-shifting approach could be compiled down to the same code, but when I wrote the byteorder crate, this wasn't the case.

This isn't the only place that ptr::copy_nonoverlapping is useful. I used it in my snappy[1] implementation as well, specifically to avoid the overhead of memcpy. To be clear, this wasn't my idea. This is what the C++ Snappy reference implementation does as well. Avoiding memcpys in favor of unaligned loads/stores is a dramatic win. I know this because I tried to write my Snappy implementation without specific unaligned loads/stores, and it performed quite a bit worse. The performance of the Rust implementation is now on par with the C++ implementation. Of course, this is always dealing with raw bytes---there's no type punning here.

ptr::copy_nonoverlapping is a bit generic for this use case. That's why we recently accepted an RFC to add read_unaligned/write_unaligned to the standard library[2]. (Which are implemented via straight-forward calls to ptr::copy_nonoverlapping.)

[1] - https://github.com/BurntSushi/rust-snappy/blob/master/src/de...

[2] - https://github.com/rust-lang/rfcs/blob/master/text/1725-unal...

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

#74

Post by Gankro »

wahern wrote: post #55
valarauca1 wrote: post #44

Earlier quoted context omitted.

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…

> 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. It's undefined behavior in Rust, too. Rust code that type-puns an unaligned pointer into an integer would crash on…

Type punning is a mess in C because you have to jump through hoops to make it legal. The language subsequently failed to provide ergonomic solutions to the very real problems type punning solves in a systems language.

Type punning is perfectly allowed in Rust, I'm not aware of any lints against it. Although you need to use an annotation to specify the struct layout algorithm to do it "correctly" for custom types.

We use it in BTreeMap to implement a kind of inheritance between nodes. Internal nodes have the same layout as Leaf nodes, except internal nodes have an extra field for their array of edges (which you don't want to allocate for leaf nodes). So everything stores pointers to leaf nodes, and mostly manipulates all nodes as leaf nodes, but sometimes you "down cast" them to internal nodes to manipulate the edges.

In this particular case we use the standard C++ pattern of making a LeafNode the first field of an InternalNode.

https://doc.rust-lang.org/nightly/src/collections/up/src/lib...

The other common usage of punning in Rust is to gain access to some raw representation of a type. For instance, last time I worked on Rust, this was how fat pointers (&[T], &Trait) were constructed and decomposed at the lowest level.

I can't speak to whether the usage of punning in this code is particularly good though.

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

#75

Post by dbaupp »

wahern wrote: post #67
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.

I think the issue, if there is one, is that arguably the more appropriate thing to do would have been to implement the code without unsafe, using an intrinsically correct algorithm. The type-punning is premature optimization. _That_ was the misstep. That the byteorder crate exists is irrelevant in as much as this was an example of the urge for premature optimization leading the developer down the wrong path. The same…

Compilers understand memcpy, especially in the context of type punning (historically being the recommended standards-compliant way to do it) where one has small constant sizes. The copy_nonoverlapping "function" is actually a compiler intrinsic, but even if it wasn't, compilers like LLVM recognises calls to "memcpy" and even loops that reimplement memcpy and canonicalise them all to the same internal representation.

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

#76

Post by nickpsecurity »

Manishearth wrote: post #68
nickpsecurity wrote: post #65

Earlier quoted context omitted.

Don't forget there's a middle ground between not having them and manual, formal verification. It started with Eiffel with basic contracts that checked properties during testing and/or runtime. That did well in commercial deployments. SPARK took it formal with a basic, boolean encoding for programmer understanding. It uses a subset of Ada to prove absence of all kinds of error conditions without runtime checks or manu…

Yeah, this exists, and would be interesting. I again think that it's a bit too extreme a solution to be baked into Rust itself, but I'd love a SPARKish Rust variant.

I'd like both. SPARK's stuff was ported to Ada 2012. It can be done for Rust as well. The trick is to make it optional so people don't have to pay attention to it. Maybe even have editors filter it out for people not paying attention to it. At the least, it being used in standard library and OS API's would let it enforce correct usage of those in debug/testing mode. 80/20 rule says that should have some impact given how much damage we've seen C and Java developers do misusing the foundational stuff.

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

#77

Post by steveklabnik »

yazaddaruvala wrote: post #53
Manishearth wrote: post #38

Earlier quoted context omitted.

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

While I mostly agree with you, I'd like to play devil's advocate: The Rust core team is relatively relaxed about the community's usage of `unsafe`. I say this because they do not seem to be interested in actively discouraging it's usage. i.e. `unsafe` is discouraged in documentation, not via tools. "Hey please don't use `unsafe` unless you know what you're doing". Is like writing a comment in Javascript, `function(x…

> Ideally, the usage of `unsafe` should be discouraged by the compiler via friction.

This is enforced via tools: you have to say 'unsafe' to use something unsafe. That's the speed bump.

In addition, there's a lint that you can on to fail the build if you use `unsafe`. This won't apply to your dependencies, but you can make it apply to your code.

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

#78

Post by wahern »

burntsushi wrote: post #73
wahern wrote: post #67

Earlier quoted context omitted.

I think the issue, if there is one, is that arguably the more appropriate thing to do would have been to implement the code without unsafe, using an intrinsically correct algorithm. The type-punning is premature optimization. _That_ was the misstep. That the byteorder crate exists is irrelevant in as much as this was an example of the urge for premature optimization leading the developer down the wrong path. The same…

> Also, looking at the byteorder crate, I wouldn't be surprised if it's even slower than the simpler and correct loop I posted elsethread. read_num_bytes in that create uses copy_nonoverlapping, which I assume is analogous to memcpy in C. That's a very round-a-bout and inefficient way to accomplish the task, and likely patterned after similarly bad C code. It wasn't patterned after any C code. ptr::copy_nonoverlappin…

  Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores, which is going to do better than the bit-shifting approach
It can't optimize it down to simple loads and stores unless it can prove that it's aligned. If it can't optimize it to a simple load, it has to check for alignment. If it has to check for alignment, it's unlikely to be faster than the byte-loading function. The bit-shifting approach can be parallelized by superscalar CPUs if you unroll the loop. Whereas the alignment check cannot be parallelized on CPUs where alignment matters, whether or not it's been unrolled to load in chunks.

FWIW, memcpy can be similarly optimized in C. memcpy -> scalar assignment is an optimization that GCC (and probably clang) performs. But if it can't prove alignment it can't optimize it to a scalar load/store, and alignment typically can't be proven except for small functions where the optimizer can see the definition of the array _and_ can prove any pointer derived from the array is properly aligned. That's generally not the case when juggling user-provided strings because there are too many conditionals between where memcpy is invoked and the origin of the pointer.

Also, as a general rule unaligned loads are slower even on x86, so it often times makes sense to check for alignment regardless, especially to optimize the case of loading a long series of integers. And when performance matters, that's precisely what you want to do if you can. You want to batch load the series of integers because doing operations in batches is the key to performance on any modern processor. Indeed, it's the key to SeaHash as well. And that's what I meant by saying effort and code complexity is better spent refactoring the algorithm at a higher level than trying to micro-optimize such a small operation. And in addition to often reaping much better gains, you often marginalize if not erase any benefit the micro-optimization might had provided. It's beyond dispute that the gains from SeaHash primarily come from how it refactored its inner loop to operate on a 64-bit word instead of 8 8-bit words.

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

#79

Post by Gankro »

Manishearth wrote: post #46
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.

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

> I have yet to see any of this.

mem::forget-pocalypse was this. (Rc/Arc, Vec::drain, thread::scoped)

Any UB bug that results from an overflow is kind've implicitly this.

BTreeMap::range still has an UB bug from trusting the caller! I literally asked you to fix it! https://github.com/rust-lang/rust/issues/33197

Bugs happen man.

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

#80

Post by warmwaffles »

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

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