Slow deserialization compared to stock `HashMap`

[hniksic]

I tried using FxHashMap to improve performance of internal hash maps, but I noticed that it takes several times longer to deserialize a large hash map that we need to persist. I couldn't find anything about it on google, so I created a minimal example and am reporting it here.

The behavior can be reproduced using a simple set of random elements. For example, on my machine this code takes 0.08s to serialize and 1.2s to deserialize a HashSet, as reported by cargo run --release:

use std::collections::HashSet;
use std::time::Instant;
use rand::Rng;

fn main() {
    let mut rnd = rand::thread_rng();
    let h: HashSet<u64> = (0..10_000_000).map(|_| rnd.gen::<u64>()).collect();

    let t0 = Instant::now();
    let mut out = vec![];
    bincode::serialize_into(&mut out, &h).unwrap();
    let t1 = Instant::now();
    println!("serialize: {}", (t1 - t0).as_secs_f64());

    let h2: HashSet<u64> = bincode::deserialize_from(&*out).unwrap();
    let t2 = Instant::now();
    println!("deserialize: {}", (t2 - t1).as_secs_f64());

    println!("{}", h2.len());
}

Trivially changing HashSet to rustc_hash::FxHashSet increases deserialization time to 5.5s (almost 5x slower), while serialization is unchanged. In our actual use case the original deserialization takes on the order of 2 minutes, so the slowdown visibly affects our total processing times. Code:

use rustc_hash::FxHashSet;
use std::time::Instant;
use rand::Rng;

fn main() {
    let mut rnd = rand::thread_rng();
    let h: FxHashSet<u64> = (0..10_000_000).map(|_| rnd.gen::<u64>()).collect();

    let t0 = Instant::now();
    let mut out = vec![];
    bincode::serialize_into(&mut out, &h).unwrap();
    let t1 = Instant::now();
    println!("serialize: {}", (t1 - t0).as_secs_f64());

    let h2: FxHashSet<u64> = bincode::deserialize_from(&*out).unwrap();
    let t2 = Instant::now();
    println!("deserialize: {}", (t2 - t1).as_secs_f64());

    println!("{}", h2.len());
}

I thought that perhaps the issue is in pathological behavior when rebuilding a hashmap from elements extracted in the same order, so I modified the code to serialize a Vec and deserialize by building an FxHashSet out of the Vec. That results in slightly slower serialization of 0.12s, but deserializes in just 0.15s, which includes both the time to deserialize the vector and the time to collect it into a new FxHashSet. (Applying this to ordinary HashSet didn't speed it up, it takes 0.11s to serialize and 1.3s to deserialize.) Code:

use rustc_hash::FxHashSet;
use std::time::Instant;
use rand::Rng;

fn main() {
    let mut rnd = rand::thread_rng();
    let h: FxHashSet<u64> = (0..10_000_000).map(|_| rnd.gen::<u64>()).collect();

    let t0 = Instant::now();
    let mut out = vec![];
    let hack = h.iter().copied().collect::<Vec<u64>>();
    bincode::serialize_into(&mut out, &hack).unwrap();
    let t1 = Instant::now();
    println!("serialize: {}", (t1 - t0).as_secs_f64());

    let hack2: Vec<u64> = bincode::deserialize_from(&*out).unwrap();
    let h2: FxHashSet<u64> = hack2.into_iter().collect();
    let t2 = Instant::now();
    println!("deserialize: {}", (t2 - t1).as_secs_f64());

    println!("{}", h2.len());
}

Is this expected behavior for an FxHashMap? Is there a way to fix it without going through a custom (and space-inefficieent) serialization/deserialization?

Note: I have reported the essentially same issue is reported to the fxhash crate, which also provides an FxHashMap with the same deserialization behavior.

[hniksic]

It turns out that the issue can be reproduced without serde and boils down to the performance of growing the hashmap from scratch. This code builds the 10m-element std HashSet in 1.1s:

use std::collections::HashSet;
use std::time::Instant;
use rand::Rng;

fn main() {
    let mut rnd = rand::thread_rng();
    let h: HashSet<u64> = (0..10_000_000).map(|_| rnd.gen::<u64>()).collect();

    let t0 = Instant::now();
    let mut h2 = HashSet::<u64>::default();
    for &n in h.iter() {
        h2.insert(n);
    }
    let t1 = Instant::now();
    println!("rebuild: {}", (t1 - t0).as_secs_f64());

    println!("{}", h2.len());
}

But building a FxHashSet requires 5.4s:

use rustc_hash::FxHashSet;
use std::time::Instant;
use rand::Rng;

fn main() {
    let mut rnd = rand::thread_rng();
    let h: FxHashSet<u64> = (0..10_000_000).map(|_| rnd.gen::<u64>()).collect();

    let t0 = Instant::now();
    let mut h2 = FxHashSet::<u64>::default();
    for &n in h.iter() {
        h2.insert(n);
    }
    let t1 = Instant::now();
    println!("rebuild: {}", (t1 - t0).as_secs_f64());

    println!("{}", h2.len());
}

The slowdown only happens if the hashmap is fed the keys in the order provided by the hashmap built using the same hash function, reminiscent of this bug. If the original map is std HashMap and the newly built one FxHashMap, the rebuild time is 0.9s, faster than the original.

The issue got exposed by serde because serde is capping the size hint to a very conservative 4096 elements.

It's not obvious that the underlying issue is fixable in this crate, but maybe the documentation should warn of the performance degradation when rebuilding from an existing hash table, particularly when deserializing with serde.

[nagisa]

Right. FxHash does not seed itself with random-ish data like SipHash does, but I don't see any reason it couldn't.

[hniksic]

Seeding with pseudo-random data could also be implemented outside the library, with a manual implementation of BuildHasher. The only problem is that rustc_hash::FxHasher, as far as I can tell, doesn't provide a way to set the initial hash value, it's always 0. I'll open a separate issue for that.

[FeldrinH]

In case someone came here looking for a workaround I will point out that @hniksic proposes a fairly good workaround in #15 (comment).

With it and a default implementation like this:

impl Default for BuildHasherRandom {
    fn default() -> Self {
        Self(rand::thread_rng().gen())
    }
}

I got the benchmark posted by @hniksic down from 4.55 s with fixed initial state to 0.48 s with pseudorandom initial state.

[FeldrinH]

It seems that there has been a regression with this in 2.0.0. Even if you use two FxHashMaps/FxHashSets with different initial seeds you still get extremely bad performance when values are inserted in the iteration order of another FxHashMap/FxHashSet.

For example, try this:

fn main() {
    let mut rnd = rand::thread_rng();

    let t0 = Instant::now();
    let mut h1 = HashSet::with_hasher(FxSeededState::with_seed(9943));
    for _ in 0..10_000_000 {
        h1.insert(rnd.gen::<u64>());
    }
    let t1 = Instant::now();
    println!("build: {}", (t1 - t0).as_secs_f64());

    let t0 = Instant::now();
    let mut h2 = HashSet::with_hasher(FxSeededState::with_seed(1829319203));
    for &n in h1.iter() {
        h2.insert(n);
    }
    let t1 = Instant::now();
    println!("rebuild: {}", (t1 - t0).as_secs_f64());

    println!("{}", h2.len());
}

On my computer this takes 0.3 seconds for the inital build, but 2.6 seconds for the rebuild.

Note that FxHashSetRand and FxHashMapRand have the same problem, since no matter what seeds they generate you get more or less the same 8-9x slowdown.

[orlp]

@FeldrinH I don't think this is a regression in 2.0. 1.2.0 was yanked, but If I put

rustc-hash = { git = "https://github.com/rust-lang/rustc-hash/", commit = "4f07f813c384e4ad5391264816e131e405a7989e"}

in my Cargo.toml and try to run your example, it also had this issue on 1.2.0.

[FeldrinH]

That is not the correct syntax for specifying a commit (see https://doc.rust-lang.org/cargo/reference/specifying-dependencies.html#choice-of-commit). You are actually running the latest master branch commit when you use that.

[FeldrinH]

Using rustc-hash = { git = "https://github.com/rust-lang/rustc-hash/", tag = "v1.2.0"} and the snippet I posted before I get an initial build of 0.3 seconds and rebuild of 0.3 seconds, which seems to strongly indicate that this is a regression.

[orlp]

Ah, silly of me, yeah this is a regression then. Can you make a dedicated issue?

[FeldrinH]

Done