SeaHash: A fast, portable hash function in Rust(docs.rs)

186 pointsby pcwalton10 tahun yang lalu114 comments

SeaHash: A fast, portable hash function in Rust

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

102 comments

aappleby10 tahun yang lalu

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

aappleby10 tahun yang lalu

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.

pbsd10 tahun yang lalu

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.

Ajedi3210 tahun yang lalu

Not sure what you mean by "secure". The linked page flat-out says:

> Warning! This is not a cryptographic function, and it certainly should not be used as one.

So the focus here is speed, not resistance to malicious actors attempting to generate collisions.

alekratz10 tahun yang lalu

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

loeg10 tahun yang lalu

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

aappleby10 tahun yang lalu

Negligible, a few tens of cycles of extra overhead.

warmwaffles10 tahun yang lalu

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

aappleby10 tahun yang lalu

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

thomasahle10 tahun yang lalu

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?

aappleby10 tahun yang lalu

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.

throwbsidbdk10 tahun yang lalu

Have you looked at Siphash? I remember reading recently that murmur has been found to have some predictable hashes independent of salts but a lot of big names still use it since it's fast and has good properties.

Gankro10 tahun yang lalu

When SipHash was presented at CCC, it was alongside the proof of concept attacks against MurmurHash and CityHash. See the "Attacks" section of [0].

Murmur was notable at the time for its use in Java and Ruby. Ruby has since moved to SipHash-2-4, while Java (OpenJDK) has thrown up its hands in disgust at the problem and created a binary tree fallback mode for its HashMaps[1]. Which at this point I'm pretty confident is the only rigorously correct solution.

[0]: https://131002.net/siphash/

[1]: http://openjdk.java.net/jeps/180

kccqzy10 tahun yang lalu

It's a bit disingenuous to say java has given up and created a binary tree fallback mode. It doesn't actually switch the whole hash table into a binary tree, but rather it switches the linked list inside each bucket into a binary tree, and only when a certain threshold is passed.

Gankro10 tahun yang lalu

If you trigger this fallback (e.g. someone is colliding all your hashes), your entire collection is probably stuffed into one bucket.

Degrading only individual buckets is of course a nice middle ground that avoids harsh discontinuities in performance for slightly bad inputs.

rurban10 tahun yang lalu

See also http://perl11.org/blog/seed.html "The dangerous SipHash myth"

It's technically impossible to declare a hash function used in hash table secure, a countermeasure against DoS attacks. djb made a bad mistake here. You always get seed exposure somehow. It is independent on the hash function. You can always brute-force it.

So java is right. The only countermeasure against collision attacks are fixes in the collision resolution. Adding stronger hash functions only makes the table slower, but not secure. And lot's of prominent hash tables are insecure, since they drank djb's cool aid.

aleyan10 tahun yang lalu

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

pcwalton10 tahun yang lalu

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.

pcwalton10 tahun yang lalu

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

wyldfire10 tahun yang lalu

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

killercup10 tahun yang lalu

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

reklawnos10 tahun yang lalu

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.

dbaupp10 tahun yang lalu

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.

foota10 tahun yang lalu

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?

Animats10 tahun yang lalu

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?

pcwalton10 tahun yang lalu

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.

Gankro10 tahun yang lalu

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.

pcwalton10 tahun yang lalu

My understanding is that overflow is pretty much fine and dandy in LLVM unless your frontend opts into the nsw flag.

Gankro10 tahun yang lalu

Yeah, it just wasn't clear to me (or anyone else I asked) that GEP wasn't "allowed" to strictly interpret signedness and inboundness. LLVM docs, amirite?

valarauca110 tahun yang lalu

   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.

wahern10 tahun yang lalu

  > 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 < MIN(plen, sizeof n); i++) {
    n |= p[i] << (8 * 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.

wahern10 tahun yang lalu

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.

rurban10 tahun yang lalu

> Rust code that type-puns an unaligned pointer into an integer would crash on MIPS or SPARC just like the C code would.

Actually you can enforce that on Intel too. I do that for some hash functions in debugging mode, to avoid valgrind slowdown.

e.g. https://github.com/perl11/cperl/blob/master/cpan/Digest-MD5/...

    #if defined(U32_ALIGNMENT_REQUIRED) && defined(__GNUC__) && (defined(__x86_64__) || defined(__i386))
        /* Generate SIGBUS on unaligned access even on x86:
           Set AC in EFLAGS. See http://orchistro.tistory.com/206
           Also see https://sourceforge.net/p/predef/wiki/Architectures/
           for possible other compilers. Here only GNU C: gcc, clang, icc.
           MSVC would be nice also. */
    #ifdef __x86_64__
        __asm__("pushf\n"
                "orl $0x40000, (%rsp)\n"
                "popf");
    #else
        __asm__("pushf\n"
                "orl $0x40000, (%esp)\n"
                "popf");
    #endif
    #endif

This way you won't get the SPARC/MIPS surprises debian maintainers are struggling with. If it doesn't align, copy it temp. It's still faster.

Gankro10 tahun yang lalu

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.

wahern10 tahun yang lalu

Type-punning is the not the same thing as deriving an object pointer through casting. Or relying on the rule concerning the equivalence of structures containing the same initial sequence of sub-members.

Specifically, the following common macro in C is _not_ type-punning, at least not the kind I had in mind.

  #define container_of(ptr, type, member) \
     (type *)((char *)(ptr) - offsetof(type, member))

Neither is the idiomatic BSD <sys/queue.h> library. It's all valid, well-defined code, as long as they're not being abused to hide undefined shenanigans.

In C, as long as the last access to an object had the same type as the type you're accessing that object from (and provided it's the same object), that's perfectly well-defined. People think that this is an aliasing violation in C, but it's not. Aliasing issues only come into play when there are side-effects (including order of evaluation) that you implicitly depend on but that the compiler cannot see. That issue is too complex to bother discussing in fine detail here, but suffice it to say that Rust either has similar undefinedness issues, or it assumes any pointer however derived can alias even inside an unsafe block and therefore cannot perform the same optimizations that a C compiler can. I doubt the latter is the case given that rustc relies on the LLVM backend.

Note that the general rule in C is that all pointers of the same type can alias, so if you derive two object pointers to the same type through explicit conversion (casting) or implicit conversion, and as long as they're actually referring to the same object, then as long as the last access is through the same type as the last store all is well-defined.[1] This is not type-punning. If this wasn't allowed by the language there wouldn't even be any use for casting at all. The cast is a way to stop the optimizer in its tracks and ensure that it doesn't fubar otherwise correct code.

The aliasing issue typically comes into play when you access at least one object through a structure or union, and there's no union definition in scope that hints that the layout is such that the sub-members of the union or structure might alias. Though the dereferenced expressions might have the same type, the dereference isn't occurring through pointers with the proper compatible type. This is one of the few cases where the compiler isn't required to assume that accesses might alias. And this is why the C standard requires those types of evaluations to occur through pointers to a union.

Type-punning, at least the kind I had in mind, is violating the core rule that access can only happen through an object with the same type as the last store. This is type-punning:

  unsigned long l = 1;
  unsigned *i;
  i = (unsigned *)&l;
  printf("i:%d\n", *i);

The access through i has a different type than the store to l.

An example that isn't type-punning per se, but raises the aliasing issue,

  struct foo {
    int i;
  }

  int add(struct foo *fp, int *ip) {
    int i;
    fp->i = 0;
    i = *ip;
    return fp->i + i;
  }

  int main(void) {
    struct foo f;
    return add(&f, &f.i);
  }

In add(), the C compiler isn't required to assume that &fp->i might alias ip and so might reorder the statements. If the hidden dependency on ordering didn't exist, the code could otherwise be okay (that's why I don't call it type-punning).

(Note: I'm having trouble using the asterisk without bolding everything. Please keep that in mind.)

The above can be made correct simply by casting:

  int add(struct foo *fp, int *ip) {
    int i;
    *(int *)&fp->i = 0;
    i = *ip;
    return *(int *)&fp->i + i;
  }

because now the initial store occurs through type pointer-to-integer, same as the type of ip. IOW, the compiler must assume that the store and loads might alias and cannot reorder things.

As you can see, this is a much more contrived scenario. It's not as common as you'd think. It's most common when type-punning--storing through one type and accessing through another. Don't type-pun and you won't run into this issue very often, if ever. It's not even that common when using the typical C OOP-like inheritance tricks. It can happen in a silent and deadly way, but that requires some serious hackery. Don't pretend that C is Java and you're unlikely to write such code. One of the common places this occurs in practice is type-punning struct sockaddr, struct sockaddr_storage, etc. That's a very unique situation for many reasons. But as optimizations in compilers improve it is admittedly an increasing problem; it's a loaded gun, for sure.

FWIW, C11 defines type-punning in a footnote 95 of section 6.5.2.3p3.

  If the member used to read the contents of a union object is
  not the same as the member last used to store a value in the
  object, the appropriate part of the object representation of
  the value is reinterpreted as an object representation in
  the new type as described in 6.2.6 (a process sometimes
  called ‘‘type punning’’). This might be a trap
  representation.

This definition is even narrower than mine, but it still comports with the core rule about loads occurring through the same type as stores.

[1] Storing a value through char is also okay as long as you ensure the representation is valid. Which is trivial when dealing with the standard fixed-width unsigned types. And access is always valid through char. That's why sometimes you'll see a seemingly superfluous cast through (char *). It's not necessarily type-punning; it might be used because a pointer-to-char can alias _anything_, and that can be useful as a barrier to prevent an optimizer from deciding two expressions might not alias.

Manishearth10 tahun yang lalu

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

yazaddaruvala10 tahun yang lalu

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?

Manishearth10 tahun yang lalu

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.

duaneb10 tahun yang lalu

Have you ever been bitten by unsafe code?

IMHO any metrics would be gamed and prioritized above actually quality. As actual quality isn't suffering, why add the unsafe metric in at all? Seems like paranoia not born out of experience.

Manishearth10 tahun yang lalu

> Have you ever been bitten by unsafe code?

Yeah. Most often in FFI code (when the invariants are much harder to uphold). Rarely when writing unsafe abstractions. The few times I remember this happening with abstractions is due to really old code that broke in a compiler upgrade (pre-1.0).

> IMHO any metrics would be gamed and prioritized above actually quality.

Yeah, there have been discussions in the past about a "safe code" badge for crates and stuff like this, and the conclusion is that it might discourage people from using unsafe code where they actually should be.

yazaddaruvala10 tahun yang lalu

I have been bitten by the lack of a type checker.

I have been bitten by inexplicit casts.

I have been bitten by segfaults.

I have been bitten by poor/no tests.

I have been bitten by mutable containers.

In every case, more constraints and more explicitness have liberated portions of my cognitive load. I've ended up with fewer bugs, more flexibility to play, reduced ramp-up time for new devs, increased speed of iteration. Why would this trend, to add constraints and explicitness, not continue to be beneficial?

P.S. You haven't been bitten by unsafe code, yet, because the people that write Rust, are still builders of the language. It is still in the early adopter stage. Think about Java, which is now predominantly written by users of the language, imagine that for Rust. The teams currently working with Rust, chose to do so as an experiment. They don't have to get a feature out tomorrow, but that will come. Similarly, there isn't "legacy Rust", yet (except in the compiler - which is fine because it is literally maintained by the experts). Is it really worth waiting for crappy code to get written, then re-written, then forgotten and finally broken, and to relive our mistakes, before we fix a predictable problem?

steveklabnik10 tahun yang lalu

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

yazaddaruvala10 tahun yang lalu

Explain to me why, ticki, who is a relatively experienced Rust dev choose to retype `unsafe` over re-using a crate (byteorder) which is supposedly equivalent?

1. Crate discoverability could be improved.

2. He wanted full control of the abstraction.

3. This particular library is just an experiment.

4. ...

Regardless of the reason, the reality is the same, `unsafe` could have been ignored but wasn't. Instead, the path of least resistance was to re-write `unsafe` blocks. IMO, it is not truly "friction"/discouraged if it is also the path of least resistance.

Manishearth10 tahun yang lalu

> is a relatively experienced Rust dev choose to retype

Probably because they were an experienced dev and are experienced enough with unsafe code to write good unsafe code without worrying about it. It was a minor unsafe operation of which the validity is easily proven. Doesn't really prove that there isn't an aversion to unsafe code in the community.

I would generally put the folks who work on Redox in the bucket of "experienced people who know how to write unsafe code" and am pretty sure that they're more comfortable with writing unsafe code than most. Byteorder is a crate that handles this neatly and well (including endianness and stuff), but for ticki's purposes, really, a simple type pun on integers is not that bad. It's like the left-pad of unsafe code.

yazaddaruvala10 tahun yang lalu

To paraphrase - "If you're experienced, the Rust community doesn't discourage it. They likely know what they're doing." :)

This sounds very similar to C or C++ developers who criticize Rust. "Experienced C / C++ developers know what they are doing. Why do we need the borrow checker. In my code, these issues Rust claims to solve haven't been an issue for a decade."

The argument seems a little hypocritical. Anyways, its not a big deal, it just seems like an easy problem to solve today, but a tedious problem to live with tomorrow. I'll stop playing devil's advocate now.

Manishearth10 tahun yang lalu

> "If you're experienced, the Rust community doesn't discourage it. They likely know what they're doing."

That's not what I'm saying. I'm saying that I can understand why ticki just reimplemented it here; because they are experienced enough to know what they're doing, AND because this isn't a dangerous unsafe operation. The AND is important here. There are a couple of unsafe operations which are basically no big deal, and this is one of them (another is the use of unchecked indexing in some cases).

An inexperienced Rust programmer would generally still avoid unsafe like the plague and ask around before doing this. We get this often enough -- folks asking how to do lower level operations well (and often getting pointed to crates like byteorder).

An experienced Rust programmer knows that this specific operation is trivial enough to not worry that much. I know about byteorder, so I would use it in this case, but if I hadn't I'm pretty sure I wouldn't be too averse to just doing the type pun.

I'm not talking about general unsafe code here. I've seen very experienced Rust programmers ask for help in getting rid of or double-checking unsafe code. I'm talking about this specific instance, and saying that it's not in the category of unsafe code that needs to be worried about.

dbaupp10 tahun yang lalu

I disagree: this sort of operation that seems safe is some of the most deceptive code to write... there's always the risk of reading a little bit more than intended or incrementing a pointer a little too far and hitting undefined behaviour. (There is in fact a bug (or two) in the type punning `read_u64` code, fortunately just a correctness one, but the small amount of code in that function is enough to obscure it, let alone the long sequence of copy-pasted `unsafe` code that makes up the main algorithm.)

It is definitely a red flag for a function that just reads some bytes to be entirely wrapped in an unsafe block, and I don't think it makes sense to defend it while also saying that the Rust community discourages gratuitous use of `unsafe`. The whole point of Rust is the "experts know what they're doing" argument doesn't work in practice, and people shouldn't get a free pass for large amounts of seemingly undocumented and unjustified `unsafe` just because they have some prominent projects.

Manishearth10 tahun yang lalu

Fair; I guess I'm wrong here. Perhaps we should be doing something to prevent gratuitous use of unsafe code. I'm quite wary that we may overly stigmatize unsafe code this way, though (leading to people avoiding even the use of libraries like byteorder that contain unsafe code). It's a careful balance to maintain.

steveklabnik10 tahun yang lalu

I can't read ticki's mind, so I can't really say why they made this decision. But I don't think you're right to suggest that this is inherently about using the path of least resistance; #2 on your list is not about that, for example.

yazaddaruvala10 tahun yang lalu

Disagree.

Unless improving the flexibility of the existing abstraction has been explored and deemed infeasible, re-building an abstraction instead of working with the existing abstraction's owner, to improve its flexibility, is taking the path of least resistance.

Animats10 tahun yang lalu

Tooling could encourage this by requiring that if a module or crate contains unsafe code, its name has to contain "unsafe".

marvy10 tahun yang lalu

That sounds horrifying (to me).

I'm not a Rust user. I've never written a line of Rust code in my life. So my opinion is not worth much. And I'm exaggerating a bit. But still.

I don't think I can explain my real reason for objecting to such a thing; it's more emotional than rational, but at least let me give one rational-sounding example of where I think even you would agree such a policy would backfire.

Some library comes out, becomes fairly popular. Eventually a version 2 is released, but the new version has a few lines of unsafe code, whereas the old one did not. Maybe it's to enable a new feature, or maybe it's for performance. Maybe the author was properly paranoid and did a full-fledged correctness proof that his code had no bugs compared to the documentation, and then verified the proof with several different interactive proof assistants. (This is getting a bit unrealistic, but bear with me for a few more sentences.)

But he now has to rename his crate, instantly making the upgrade process for existing users way more annoying. And to add insult to injury, the new name is wrong! There's nothing unsafe about his code, as far as users are concerned. The only trouble is that the Rust compiler could not prove it safe. As you pointed out yourself, this is not surprising: it can't even cope with a linked list! Sophomores in college implement these things, but the borrow checker can't cope with them. So of course unsafe is needed.

And if version 3 finds a workaround, so that unsafe is no longer needed, do you rename it yet again? People think Java's checked exceptions are annoying, but surely this is far worse?

jononor10 tahun yang lalu

How does one verify unsafe blocks in a library? Wondering what are the best practices.

idsout10 tahun yang lalu

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.

fnord12310 tahun yang lalu

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

michaelmior10 tahun yang lalu

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.

fnord12310 tahun yang lalu

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

Animats10 tahun yang lalu

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.

pcwalton10 tahun yang lalu

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.

Animats10 tahun yang lalu

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.

pcwalton10 tahun yang lalu

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.

wahern10 tahun yang lalu

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 amount of time pondering whether to even bother using a pre-existing library might have been better spent second-guessing the urge to type-pun at all.

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.

To even make it worthwhile, any byteorder library should provide some kind of iterator interface so that it can maintain alignment state while permitting the loop to be unrolled by the compiler. (And it might require a closure or someway of expanding a block of code inline.) That's probably the only way it could outperform the simple, hand-rolled, endianness- and alignment-neutral solution. But it doesn't provide that kind of interface AFAICT.

It's all sort of ironic, which I suppose was the point upthread--this is an example of the irrational urge for premature optimization and of bad programming idioms being hauled into Rust land completely unhindered by Rust's type safety features. And the better, correct, and likely more performant way of accomplishing this task could have been done just as safely from C as it could from Rust.

burntsushi10 tahun yang lalu

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

wahern10 tahun yang lalu

  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.

burntsushi10 tahun yang lalu

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

I had edited my comment after-the-fact to include the "on x86" qualification.

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

Your advice is overspecified. If you want to make something faster, then build a benchmark that measures the time you care about and iterate on it. If "micro optimizations" make it faster, then there's nothing wrong with that. I once doubled the throughput of a regex implementation by eliminating a single pointer indirection in the inner loop. It doesn't get any more micro then that, but consumers are no doubt happier with the increased throughput. In general, I find most of your hand waving about performance curious. You seem keen on making a strong assertion about performance, but the standard currency for this sort of thing is benchmarks.

I did all of this with byteorder when I built it years ago. I'll do it again for you.

    $ curl -sOL https://gist.github.com/anonymous/042d05e1e480b89434a673b30534efd8/raw/d2c9a4516a57c26da23c8beaffd5ad583da0a889/Cargo.toml
    $ curl -sOL https://gist.github.com/anonymous/042d05e1e480b89434a673b30534efd8/raw/d2c9a4516a57c26da23c8beaffd5ad583da0a889/lib.rs
    $ RUSTFLAGS="--emit asm" cargo bench
    test bit_shifting ... bench:   1,999,496 ns/iter (+/- 53,427)
    test type_punning ... bench:     476,105 ns/iter (+/- 11,920)

(The `RUSTFLAGS="--emit asm"` dumps the generated asm to target/release/deps.)

The benchmark reads 1,000,000 64 bit integers from a buffer in memory and sums them.

Analyzing the hotspots of each benchmark using `perf` is instructive. For type_punning:

    $ perf record target/release/deps/benchbytes-a1cc37a72d289957 --bench type_punning
    $ perf report

The corresponding asm is:

    cmpq	$7, %rsi
    jbe	.LBB4_10
    movq	(%rbx), %rcx
    addq	(%rcx,%rax), %rdi
    addq	$8, %rax
    addq	$-8, %rsi
    cmpq	%rax, %rdx
    ja	.LBB4_6

Notice how tight this loop is. In particular, we're dealing with a single simple load to read our u64. Now let's repeat the process for bit shifting:

    $ perf record target/release/deps/benchbytes-a1cc37a72d289957 --bench bit_shifting
    $ perf report

The hotspot's corresponding asm is:

    .LBB5_6:
    	cmpq	$7, %rsi
    	jbe	.LBB5_10
    	movzbl	(%rdx,%rbx), %ecx
    	movzbl	1(%rdx,%rbx), %eax
    	shlq	$8, %rax
    	orq	%rcx, %rax
    	movzbl	2(%rdx,%rbx), %ecx
    	shlq	$16, %rcx
    	orq	%rax, %rcx
    	movzbl	3(%rdx,%rbx), %eax
    	shlq	$24, %rax
    	orq	%rcx, %rax
    	movzbl	4(%rdx,%rbx), %ecx
    	shlq	$32, %rcx
    	orq	%rax, %rcx
    	movzbl	5(%rdx,%rbx), %eax
    	shlq	$40, %rax
    	orq	%rcx, %rax
    	movzbl	6(%rdx,%rbx), %ecx
    	shlq	$48, %rcx
    	movzbl	7(%rdx,%rbx), %edi
    	shlq	$54, %rdi
    	orq	%rcx, %rdi
    	orq	%rax, %rdi
    	addq	%rdi, %r12
    	addq	$8, %rbx
    	addq	$-8, %rsi
    	cmpq	%rbx, %r11
    	ja	.LBB5_6

It's no surprise that the type punning approach is faster here. (N.B. Compiling with `RUSTFLAGS="-C target-cpu=native"` seems to permit some auto-vectorization to happen, but I don't observe any noticeable improvement to the benchmark times for bit_shifting. In fact, it seems to get a touch slower.)

I could be reasonably accused of micro-optimizing here, but I do feel like reading 1,000,000 integers from a buffer is a pretty generalizable use case, and the performance difference here in particular is especially dramatic. Finding a real world problem that this helps is left as an exercise to the reader. (I've exceeded my time budget for a single HN comment.)

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

Do you feel anyone has contested this point? I note your use of the word "primarily." If type punning gives a 10% boost to something that is already fast, do you care? If not, do you think other people might care? If they do, then what exactly is your point again?

Note that I am responding to your criticism of byteorder in particular. I don't really know whether the OP's optimization of reading little-endian integers is actually worth while or not. I would hazard a guess, but would suspend certainty until I saw a benchmark. (And even then, it is so incredibly easy to misunderstand a benchmark.)

dbaupp10 tahun yang lalu

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.

Animats10 tahun yang lalu

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.

Manishearth10 tahun yang lalu

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

pcwalton10 tahun yang lalu

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

Animats10 tahun yang lalu

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.

pcwalton10 tahun yang lalu

OK, but we're not talking about the borrow checker, we're talking about byteorder. There's nothing about the byteorder crate that would benefit from being added to the compiler.

In fact it would make it less safe, since we'd be debugging code that emits LLVM IR instead of writing in an actual language.

Manishearth10 tahun yang lalu

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.

Manishearth10 tahun yang lalu

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

Gankro10 tahun yang lalu

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

Manishearth10 tahun yang lalu

> mem::forget-pocalypse was this.

I would say that this is from a time when the invariants were not understood. In particular, the fact that leaking is safe to do in safe code was not known.

(The invariants are still not completely understood, but there's work to specify that, and IMO they're understood enough to be able to avoid unsafe bugs)

> BTreeMap::range still has an UB bug from trusting the caller!

Fair :) I'd completely forgotten about that one.

Gankro10 tahun yang lalu

> I would say that this is from a time when the invariants were not understood.

Yeah, but it's not like "oh this is an obvious thing to consider trusting the caller about". It's an exceptionally niche problem that you'd only know about if someone told you about it. Especially since a Rust programmer shouldn't be expected to write unsafe code often, if ever!

Similarly: not trusting traits to be implemented correctly. Not trusting closures to not-unwind.

Manishearth10 tahun yang lalu

Fair. I'm not saying that your average Rust programmer will be able to deal with unsafe code immediately. But I do think that at this stage the list of things you can and cannot rely on (and the invariants you must uphold) is clear enough that in theory you could make a checklist to deal with this. The nomicon provides much of the background for folks wanting to figure this out and write unsafe code.

These days I've been writing a lot of unsafe code (for FFI) and I do want to get around to penning a concise guide (or just expanding the nomicon). But I'm mostly waiting for the unsafe code subteam to figure out a couple things before doing this (specifically, the exact boundaries of rust's noalias UB becomes important in FFI and this is not specified yet).

But yeah, it's not necessarily obvious. I'd like to make it easier to get this understanding of unsafe code though.

Manishearth10 tahun yang lalu

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

staticassertion10 tahun yang lalu

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.

sp33210 tahun yang lalu

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?

LeifCarrotson10 tahun yang lalu

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.

0x6c6f6c10 tahun yang lalu

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)

0x6c6f6c10 tahun yang lalu

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?

irq-110 tahun yang lalu

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.

Sharlin10 tahun yang lalu

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

mastax10 tahun yang lalu

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

tibbe10 tahun yang lalu

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.

Dylan1680710 tahun yang lalu

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.

nullnilvoid10 tahun yang lalu

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++?

tupshin10 tahun yang lalu

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.

nullnilvoid10 tahun yang lalu

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

pcwalton10 tahun yang lalu

Because it's probably the most notable/unusual part of this hash function. Virtually all other hash functions for at least a decade have had their reference implementations written in C or C++.

echelon10 tahun yang lalu

The Rust ecosystem is growing rapidly, and I personally think it's awesome that we're telling the world about it. Rust is production-ready and presents several advantages over C and C++. The more people that jump on board, the faster we get more libraries, and the more companies will take a look at using Rust in their own production environments.

I predict Rust will also begin to find use as a backend server language, and begin to eat into Java, Go, Python, and Ruby mindshare. Though there's a learning curve with Rust, it doesn't take too long to become productive. I'm also excited to see how Rust makes inroads in game development.

I think we're all going to start seeing more Rust in our headlines. It's a great language, and the people I know that use it are in love with it (myself included).

pcwalton10 tahun yang lalu

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

[deleted]10 tahun yang lalu

eridius10 tahun yang lalu

Very cool!

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

jedisct110 tahun yang lalu

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

pcwalton10 tahun yang lalu

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

tveita10 tahun yang lalu

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.

dsp123410 tahun yang lalu

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

Dylan1680710 tahun yang lalu

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

crtc10 tahun yang lalu

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