Low-latency hashing

libs
1

Hey folks.

I've been working on optimizing hash-based data structures recently and I think I've found an important pattern Rust's current Hash/Hasher traits cannot express or support. We've got support for performant and cryptographic hashing for large objects, but very little for low-latency hashing of small objects, which is what, in my experience, hashmaps are often used for.

I've written a post on this covering the problem: Thoughts on Rust hashing | purplesyringa's blog. If this reads like an offensive critique, I'm sorry; I can assure you this wasn't my intention.

TL;DR: I've found that the current design forces the Hasher to be able to consume objects of arbitrary structure without being aware of it beforehand, leading to suboptimal behavior on such "simple" tasks as hashing a struct containing three integers (or, indeed, hashing arrays of small objects).

The bummer here is that the Java-style hashCode-like API would kind of support this use case better, but it has its own share of problems. I didn't manage to find a new architectural design (yet alone something backwards-compatible) to fix this, so I'm interested if anyone knows a better approach.

18 Likes
2

You can create your own Hasher that is generic over the type being hashed:

use std::hash::Hash;

pub trait MyHasher<T: ?Sized> {
    fn write(&mut self, value: &T);
    fn finish(&self) -> u64;
}

impl<T: Hash, H: std::hash::Hasher> MyHasher<T> for H {
    fn write(&mut self, value: &T) {
        T::hash(value, self);
    }

    fn finish(&self) -> u64 {
        std::hash::Hasher::finish(self)
    }
}

Then you can impl MyHasher specifically with your type. Unfortunately I don't believe replacing Hasher with MyHasher will be backwards-compatible for collections, but I can't pinpoint why exactly.

3

I don't have a solution or opinion but thanks for the comprehensive post about hashing internals, @purplesyringa! Learned a lot.

6 Likes
4

On the side note about the default hasher not implementation an optimization: I have a PR to re-land that: Optimize DefaultHasher siphash by Noratrieb · Pull Request #130112 · rust-lang/rust · GitHub, but I haven't gotten around to doing benchmarks. If anyone wants to provide some, that would be valuable.

7 Likes
5

It seems to me that if you had comprehensive compile time reflection you could get all the benefits (except probably compile times). You could then introspect the data layout to determine where the padding is and if it is safe to hash a block of data in one go or not.

9 Likes
6

Safe transmute project also may be helpful here

2 Likes
7

Maybe we could go part of the way by improving the derive(Hash) macro to do this reflection in const with size_of to check if we're just hashing a bunch of primitives where the size adds up to the overall struct. But that too likely is going to drive up compile times.

4 Likes
8

I got to thinking a bit more about this. One point I don't see addressed here or in the blog is enums.

It seems to me that this could quickly get extremely complicated and convoluted to do optimally with enums. Any proposed solution should consider this case, as enums is (IMO) one of the flagship features of Rust[1] and we don't want to discourage using them for performance reasons.

  1. I have a C++ background, and the type safety and modelling power offered by enums is truly astounding compared to what you can do in C++. To me it is the main feature (together with borrow checking/ownership) that makes Rust safe and ergonomic. ↩︎

4 Likes
9

The obvious way to hash sum types is to emit the discriminant and then the variant, padding it with zeroes (or whatever static garbage) s.t. all variants take the same amount of space.

Mixing a small discriminant into the state can also be achieved by simply XORing pseudo-random data into the state instead of running the block hash (just like hashing bool could return either 0 or a random integer). How good of an idea this is depends heavily on the underlying hash, but IMO fast hashes might like this. Ideally this possibility would be supported by the API.

10

Yes, but consider Option<NonZeroU32>, there is no reason it shouldn't hash as quickly as a u32, since due to niches the layout is the same. Hashing both should ideally be the same speed.

2 Likes
11

The obvious way to hash sum types is to emit the discriminant and then the variant

I don't think this works for Option<String>, which 1. doesn't have a discriminant byte (as Vorpal pointed out for Option<NonZeroU32>) and 2. can't be hashed by looking at just its stack-allocated data.

Also, if an enum has one variant much larger than the rest, you shouldn't pay the cost of hashing the smaller variants’ padding bytes when hashing them, at least not unless the cost of branching is greater than the savings from not hashing the padding bytes, which probably depends on the size of the enum and the difference in size between the variants. (But see above, where in the case of something like Result<T, String> you have to branch if T is not also String.)

Maybe the compiler could choose what kind of hashing code to emit based on whether the payload types are Copy or not? I think there is a lot of room in the design space to explore here.

12

Padding bytes can never be hashed. Reading them is UB. They have undefined contents, and LLVM is permitted to change it according to it's whims (e.g. not copy the padding bytes when moving around a struct).

They are also poison. Which means that LLVM can assume you never read them and optimise accordingly.

EDIT: They might be undef rather than poison when I think about it. Unsure. Either way, you can't hash them.

5 Likes