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

111–116 of 116 posts

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

#111

Post by glangdale »

wahern wrote: post #96
burntsushi wrote: post #89

Earlier quoted context omitted.

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

Notice how tight this loop is. In particular, we're dealing with a single simple load to read our u64. Notice that you're reading the data into a statically allocated buffer, and doing it in such a way that it's trivial for the compiler to prove alignment. This is a classic case where the benchmark is irrelevant for a general purpose implementation. Try running the code so that the buffer is dynamically allocated, an…

Hi, author of Hyperscan (https://github.com/01org/hyperscan) here.

I strongly suspect we don't support enough of this:

> many of which used zero-width assertions that required non-trivial transformations and pre- and post-processing of input

... to really support your use case. But we're interested in the workload, especially as we're looking at extensions to handle more of the zero-width assertion cases. We'll never be able to handle some of them in streaming mode (they break our semantics and the assumption that stream state is a fixed size for a given set of regular expressions).

Can you share anything about what you're doing with zero-width assertions?

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

#112

Post by rurban »

Gankro wrote: post #69
throwbsidbdk wrote: post #66

Earlier quoted context omitted.

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.

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

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.

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

#113

Post by rurban »

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…

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

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

#114

Post by 0x6c6f6c »

LeifCarrotson wrote: post #26
sp332 wrote: post #5

I was trying to figure out how this is so much faster than FNV https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo... Is it only because of the parallelism? Or are the operations really that much cheaper somehow?

Both. The pseudocode for FNV looks like this: hash = FNV_offset_value for each byte_of_data to be hashed { hash = hash XOR byte_of_data hash = hash × FNV_prime } return hash The pseudocode for seahash looks like this (with '×' as the wrapping multplier operator, and some simplification for padding if the data length in bytes is not a multiple of 8 bytes per word × 4 words in the hash state): hash = {offset_1, offset_…

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)

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

#115

Post by 0x6c6f6c »

LeifCarrotson wrote: post #26
sp332 wrote: post #5

I was trying to figure out how this is so much faster than FNV https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo... Is it only because of the parallelism? Or are the operations really that much cheaper somehow?

Both. The pseudocode for FNV looks like this: hash = FNV_offset_value for each byte_of_data to be hashed { hash = hash XOR byte_of_data hash = hash × FNV_prime } return hash The pseudocode for seahash looks like this (with '×' as the wrapping multplier operator, and some simplification for padding if the data length in bytes is not a multiple of 8 bytes per word × 4 words in the hash state): hash = {offset_1, offset_…

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?

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

#116

Post by Ajedi32 »

pbsd wrote: post #97
aappleby wrote: post #30

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…

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

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.

Post reply on HN