Live data from Hacker News

SeaHash: A fast, portable hash function in Rust

docs.rs

51–60 of 116 posts

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

#51
post #31

Earlier quoted context omitted.

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.

Execution units, to be precise. Separate threads of execution are not involved, hardware or software.

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

#52
post #45

Earlier quoted context omitted.

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?

The compiler can look at more data to decide if something is valid, or can be optimized.

C++ is trying to add move semantics via templates, but can't get all the way to Rust's borrow checker that way.

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

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

> 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 /* int */) {`.

Ideally, the usage of `unsafe` should be discouraged by the compiler via friction. The compiler should, at the least, spit out some metrics after a compile cycle about the percentage of `unsafe` lines/instructions. Even more ideal, when the compiler detects an `unsafe` it would pause and ask, "Is Crate Z trusted [y/N]?". Cargo can then make this easy in Cargo.toml.

All of a sudden Crate writers need to think twice about their usage of `unsafe`, will users be willing to trust my code? is using `unsafe` here really worth the risk of adopting fewer users? is there already a library that solves this which is generally trusted?

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

#54

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?

Negligible, a few tens of cycles of extra overhead.

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

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

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 MIPS or SPARC just like the C code would. And that crash could potentially be triggered by malicious input. "unsafe" doesn't make behavior well-defined in Rust anymore than an explicit cast makes it well-defined in C.

Moreover, type-punning is generally a warning of bad code in C. Both C and Rust will generally[1] diagnose a type-pun. And you can silence the diagnostic in both languages by using special syntax--unsafe in Rust, a cast in C. But in both cases the way that you silence the warning is over-broad; you often need to silence it for good reason, X, while accidentally silencing the diagnostic for usage Y.

The correct way to read in a little-endian integer in C is the same way you'd do it anywhere else:

  unsigned char *p;
  size_t plen;
  uint64_t n;
  // initialize p and plen
  _Static_assert(CHAR_BIT == 8, "CHAR_BIT != 8"); // [2]
  n = 0;
  for (size_t i = 0; i 
It's correct regardless of endianness and regardless of whether the address is aligned. And the above loop can be unrolled, too, so that it pipelines well. If performance is so important that you can't be bothered to care about alignment constraints, you may as well drop down into assembly and use SIMD instructions directly. Type-punning with a C-style cast or Rust-style unsafe block is just a bad idea, IMO.

I've never seen a situation in C where type-punning of this sort was a good idea. The performance aspect is negligible. My parsers generally runs rings around code that uses type-punning. The gains are nothing compared to what you can get by better restructuring of higher-level code. For example, with hashing functions you're generally hashing small strings; thus the alignment checks you would need to add would typically cost more than the benefit because they couldn't be amortized well.

If you really had to, then C11 provides _Alignof that can be used to type-pun in a safe manner just like you could in Rust. (If a builtin type has padding issues, so would the same Rust code. It just so happens that Rust affirmatively has selected at the outset to never support such architectures. Thus, running the same code on the same architecture would work correctly in both languages.) It's not even type-punning if in addition to correct alignment you can prove that all bits are value bits. That would be the case for both the fixed-sized integer types, as well as for unsigned types where you can prove there are no padding bits (which can be accomplished using well-defined code as well).

So for general usage, if you really want to you could implement two versions of the code--one that type-punned correctly for long strings, and a simpler, more concise, more obviously correct one for typical strings. So it can be done correctly while still reaping the same performance; it's just more hassle than writing incorrect code. But even the incorrect code is more obtuse than the trivially correct version, which is why I've never had a good reason to type-pun.

[1] The exception in C is implicit conversions through a void pointer. But in C++, which lacks implicit void pointer conversions, engineers will often instinctively add an explicit cast where you would normally use a void pointer in C, substantially blunting the benefit of removing the implicit conversion from the language. And that habit to cast can easily lead to more bugs, just like in this case, where unsafe was used to permit the use of a broken idiom that is poor code even in C.

Good C rarely uses casts. Avoiding casts is a good habit to get into in C. And I've personally never seen good reason to type-pun anything, period, in C.

[2] The code could be trivially made correct on platforms where CHAR_BIT > 8 if the convention was that input strings only filled the bottom 8 bits of char. It would just be a distraction here, though.

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

#56
post #52

Earlier quoted context omitted.

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

The compiler can look at more data to decide if something is valid, or can be optimized. C++ is trying to add move semantics via templates, but can't get all the way to Rust's borrow checker that way.

Right, but in this case it doesn't need to. I have yet to see an example of an operation that:

- should be safe in Rust but isn't

- needs /compiler/ support to work well (can't be done cleanly as a library)

- isn't already on the track for implementation (non-lexical lifetimes, SEME regions)

You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe. Instead, you make it safe by encoding the invariants specific to your use case in your code and creating a safe wrapper -- these invariants differ by use case, so it can't be made a generic operation.

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

#57

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?

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.

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

#58

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…

Nobody is putting effort into propaganda about unsafe because the community is already very strongly averse to this, and is careful about writing unsafe code. It's not a problem. If it becomes a problem (I doubt it) we can put effort into it. People learn about the language through discussion or documentation, and both of these venues actively discourage unsafe. The one resource out there that teaches unsafe code in depth (the Rustonomicon) is very heavy on warning the reader about unsafe code pitfalls and in general discouraging the reader from writing unsafe code.

A tool for tracking unsafe dependencies has been talked about before, though. Sounds like a good idea to me. Like I said I don't think there's a particular need for it, but it would be nice to have.

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

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

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

#60
post #52

Earlier quoted context omitted.

The compiler can look at more data to decide if something is valid, or can be optimized. C++ is trying to add move semantics via templates, but can't get all the way to Rust's borrow checker that way.

Right, but in this case it doesn't need to. I have yet to see an example of an operation that: - should be safe in Rust but isn't - needs /compiler/ support to work well (can't be done cleanly as a library) - isn't already on the track for implementation (non-lexical lifetimes, SEME regions) You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe.…

You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe.

Sure it can. You just need primitives which can be used in asserts such as

    is_initialized(tab,i,j)
indicating that an array is initialized within those limits. Then you can write asserts such as

    assert(is_initialized(tab,i,j-1));
    ... initialize tab[j]
    assert(is_initialized(tab,i,j));
Standard program verification technology. Verification of unsafe sections is a useful goal, and deserves language support. Hand-waving about "encoding the invariants specific to your use case in your code" is insufficient. You need to write them down and prove them. Then you can eliminate them from the run-time code.
Post reply on HN