1477628 - Convert FnvHash{Set,Map} instances to FxHash{Set,Map}

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, enhancement, P3)

Description

[Nicholas Nethercote [inactive]]

Bug 1477622 shows that FxHash{Set,Map} are much faster than FnvHash{Set,Map}. We should convert all the existing instances in Firefox of the latter to the former. 

The same conversion was a significant win within rustc back in 2016: https://github.com/rust-lang/rust/pull/37229.

Comment 1

[Cameron McCormack (:heycam)]

The hottest uses of FnvHash{Map,Set} are probably those used in invalidation and those used to store entries in the RuleCache.  If none of our existing perf-reftests exercise the performance of these, it would be good to write some microbenchmarks for them and see how the switch to FxHash{Map,Set} affects them.

Comment 2

[Bobby Holley (:bholley)]

(In reply to Cameron McCormack (:heycam) from comment #1)
> The hottest uses of FnvHash{Map,Set} are probably those used in invalidation
> and those used to store entries in the RuleCache.  If none of our existing
> perf-reftests exercise the performance of these, it would be good to write
> some microbenchmarks for them and see how the switch to FxHash{Map,Set}
> affects them.

It's also possible that StyleBench might exercise them.

Note also that our discussion with Joel settled on making perf-reftests more up/down (and scalable), at the expense of not sheriffing single-digit percentage shifts (see bug 1477014). So it should work now if we want to use it as a workload to compare hashtable performance, but we shouldn't depend on them long-term to catch performance changes of the sort that hashtable changes would introduce.

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477628 - Convert FnvHash{Set,Map} instances to FxHash{Set,Map}.

Because the latter are faster.

Review commit: https://reviewboard.mozilla.org/r/258970/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/258970/

Comment 4

[Nicholas Nethercote [inactive]]

I tried StyleBench (following the instructions in bug 1425058 comment 0) and any difference was in the noise.

Webrender made the FnvHash-to-FxHash switch a while back for significant wins: https://github.com/servo/webrender/commit/52b48101ade4cb976f875bdb4576a1402b9e78ca

Comment 5

[Cameron McCormack (:heycam)]

I'll write some microbenchmarks tomorrow to test this against.

Comment 6

[Cameron McCormack (:heycam)]

Attachment: microbenchmark

I tested three things, two with a microbenchmark test file (attached) and one using an existing cargo benchmark.

The test file tests two existing hash tables that currently use fnv as the hasher.  The first is the rule cache, and the test does 
100,000 lookups and insertions into its table of cached ComputedStyle objects.  The second is the style sheet invalidation table (the element_invalidations one), which gets 100,000 entries inserted into it from the test's style sheet.

I loaded the test file a number of times and used the profiler to find the relevant functions that poke at the hash tables.  Since these are otherwise inlined, I stuck #[inline(never)] on the two RuleCache functions, and broke out the `self.invalid_elements.insert(s)` call in StylesheetInvalidationSet::collect_invalidations into a separate #[inline(never)] function.

(The test file as a whole takes a long time to run, almost 30s on my machine, most of it is to set up the conditions where we will end up using the rule cache.)

The third test was running the create_insert_1000_remove_100_lookup_100 bench in the selectors crate's bloom.rs.


Results, five iterations for each test:

* time in RuleCache:: functions

without patch:

50.6 ms
48.3 ms
54.4 ms
49.9 ms
51.0 ms

with patch:

72.3 ms
73.6 ms
70.9 ms
76.0 ms
74.7 ms

* time in insert_element_invalidation

without patch:

10.9 ms
10.9 ms
10.3 ms
10.9 ms
11.4 ms

with patch:

10.6 ms
9.4 ms
10.1 ms
10.9 ms
10.0 ms

* bloom filter benchmark

without patch:

test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         999 ns/iter (+/- 38)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         998 ns/iter (+/- 39)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         994 ns/iter (+/- 45)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         975 ns/iter (+/- 32)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         976 ns/iter (+/- 31)

with patch:

test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         984 ns/iter (+/- 44)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:       1,001 ns/iter (+/- 54)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         998 ns/iter (+/- 52)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         993 ns/iter (+/- 28)
test bloom::bench::create_insert_1000_remove_100_lookup_100 ... bench:         977 ns/iter (+/- 21)


So overall, a little worse on the rule cache hash table, and no change on the other two tests.

Comment 7

[Nicholas Nethercote [inactive]]

Thanks for the measurements. It's surprising that FxHash does so badly here, when it was a clear win in three other contexts (rustc, Webrender, and xpcom microbenchmarks).

Comment 8

[Cameron McCormack (:heycam)]

The numbers are very small anyway given the number of elements the test is operating on.  We should land this anyway to reduce the number of hashers we use.

Comment 9

[Cameron McCormack (:heycam)]

Comment on attachment 8994416 [details]
Bug 1477628 - Convert FnvHash{Set,Map} instances to FxHash{Set,Map}.

https://reviewboard.mozilla.org/r/258970/#review266580

::: servo/components/hashglobe/src/hash_map.rs:237
(Diff revision 1)
>  /// strings, though those algorithms will typically *not* protect against
>  /// attacks such as HashDoS.
>  ///
>  /// The hashing algorithm can be replaced on a per-`HashMap` basis using the
>  /// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods. Many
> -/// alternative algorithms are available on crates.io, such as the [`fnv`] crate.
> +/// alternative algorithms are available on crates.io, such as the [`fxhash`] crate.

Since this big comment here is just a copy of the one on std's HashMap, let's leave the fnv reference as is.

::: servo/components/style/hash.rs:28
(Diff revision 1)
>  /// Hash map that uses the FNV hasher
> -pub type FnvHashMap<K, V> = HashMap<K, V, fnv::FnvBuildHasher>;
> +pub type FxHashMap<K, V> = HashMap<K, V, fxhash::FxBuildHasher>;
>  /// Hash set that uses the FNV hasher

Please update these comments.

Comment 10

[Nicholas Nethercote [inactive]]

I did a try push that failed miserably, even though it builds fine locally:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=1064f9d2a3414b3375833ca5d1711160028de2ed

The error is here:

> [task 2018-07-26T08:08:18.479Z] 08:08:18     INFO -  force-cargo-library-build
> [task 2018-07-26T08:08:18.480Z] 08:08:18     INFO -  env   RUSTC_BOOTSTRAP=1 RUSTFLAGS='-C opt-level=2 -C debuginfo=2  ' RUSTC_WRAPPER='/builds/worker/workspace/build/src/sccache2/sccache' CARGO_TARGET_DIR=/builds/worker/workspace/build/src/obj-firefox/toolkit/library RUSTC=/builds/worker/workspace/build/src/rustc/bin/rustc RUSTDOC=/builds/worker/workspace/build/src/rustc/bin/rustdoc RUSTFMT=/builds/worker/workspace/build/src/rustc/bin/rustfmt MOZ_SRC=/builds/worker/workspace/build/src MOZ_DIST=/builds/worker/workspace/build/src/obj-firefox/dist LIBCLANG_PATH="/builds/worker/workspace/build/src/clang/lib" CLANG_PATH="/builds/worker/workspace/build/src/clang/bin/clang" PKG_CONFIG_ALLOW_CROSS=1 RUST_BACKTRACE=full MOZ_TOPOBJDIR=/builds/worker/workspace/build/src/obj-firefox CARGO_INCREMENTAL=0 MOZ_CARGO_WRAP_LDFLAGS="-lpthread -Wl,-z,noexecstack -Wl,-z,text -Wl,-z,relro -Wl,--build-id -Wl,-rpath-link,/builds/worker/workspace/build/src/obj-firefox/dist/bin -Wl,-rpath-link,/usr/local/lib" MOZ_CARGO_WRAP_LD=" /builds/worker/workspace/build/src/sccache2/sccache /builds/worker/workspace/build/src/gcc/bin/gcc -std=gnu99" CARGO_TARGET_X86_64_UNKNOWN_LINUX_GNU_LINKER=/builds/worker/workspace/build/src/build/cargo-linker /builds/worker/workspace/build/src/rustc/bin/cargo rustc  --release --frozen --manifest-path /builds/worker/workspace/build/src/toolkit/library/gtest/rust/Cargo.toml -vv --lib --target=x86_64-unknown-linux-gnu --features "servo bindgen quantum_render cubeb_pulse_rust simd-accel cubeb-remoting moz_memory" --  -C lto
> [task 2018-07-26T08:08:18.481Z] 08:08:18     INFO -  error: failed to parse lock file at: /builds/worker/workspace/build/src/Cargo.lock
> [task 2018-07-26T08:08:18.481Z] 08:08:18     INFO -  Caused by:
> [task 2018-07-26T08:08:18.481Z] 08:08:18     INFO -    package `fnv 1.0.5 (registry+https://github.com/rust-lang/crates.io-index)` is specified as a dependency, but is missing from the package list
> [task 2018-07-26T08:08:18.481Z] 08:08:18     INFO -  /builds/worker/workspace/build/src/config/rules.mk:971: recipe for target 'force-cargo-library-build' failed
> [task 2018-07-26T08:08:18.481Z] 08:08:18     INFO -  make[4]: *** [force-cargo-library-build] Error 101

The patch removes all direct dependencies on the `fnv` crate, and I ran `./mach vendor rust` to get the `Cargo.lock` changes. So I don't know how/why fnv 1.0.5 is specified as a dependency.

froydnj, any ideas?

Comment 11

[Nathan Froyd [:froydnj]]

https://hg.mozilla.org/try/file/8d9aaad2ca76/Cargo.lock#l147 says bench-collections-gtest still depends on fnv, which https://hg.mozilla.org/try/file/8d9aaad2ca767552e4dc1a69c190e8c69bb35b55/xpcom/rust/gtest/bench-collections/Cargo.toml#l8 appears to confirm.

Do you have --disable-tests locally, or something like that?

Comment 12

[Nicholas Nethercote [inactive]]

Oh... I hadn't updated that repo since bench-collections-gtest was added. So it worked locally but didn't work when I added the patch to mozilla-central and pushed to try (as I normally do with try pushes).

Which means that we can't remove the `fnv` crate, oh well.

Thanks for the tip!

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/72b855b514f9
Convert FnvHash{Set,Map} instances to FxHash{Set,Map}. r=heycam

Comment 14

[Bogdan Tara[:bogdan_tara | bogdant]]

Backed out changeset 72b855b514f9 (Bug 1477628) for rusttests build bustages.

Push with failures: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=72b855b514f912ddd458272348b3849361ed4deb

Backout link: https://hg.mozilla.org/integration/mozilla-inbound/rev/75ec3f923e76aa6c9b39bdc838995e6d1cccb025 

Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=190440538&repo=mozilla-inbound&lineNumber=42966

Comment 15

[Nicholas Nethercote [inactive]]

heycam, we have this failure:

> thread 'bloom::create_and_insert_some_stuff' panicked at '199 is not < 160', servo/components/selectors/bloom.rs:338:5

Looks like fxhash causes more collisions (and thus false positives) in the bloom filter, and thus we exceed this hard-coded false positive threshold.

Do you have a preference whether we:

- revert to fnv for bloom_filter, or

- increase the threshold?

Comment 16

[Bobby Holley (:bholley)]

Collisions in the bloom filter are generally not great, as they cause us to do a lot of expensive work if we can't fast-reject. Does bloom filter insertion/removal doesn't get measurably faster by switching to fxhash? If not, I think we should revert.

Comment 17

[Cameron McCormack (:heycam)]

Yes, I concur.  Since it doesn't look like the bloom filter insertion/removal did get any faster (the create_insert_1000_remove_100_lookup_100 bench stayed the same), let's revert that part of the patch.

Comment 18

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f13608115d2d
Convert FnvHash{Set,Map} instances to FxHash{Set,Map} (attempt 2). r=heycam

Comment 19

[Emilio Cobos Álvarez [:emilio]]

Just for the record, I don't think we use fnv for the bloom filter. We use insert_hash / remove_hash with the hash atoms have precomputed already.

Comment 20

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez (:emilio) from comment #19)
> Just for the record, I don't think we use fnv for the bloom filter. We use
> insert_hash / remove_hash with the hash atoms have precomputed already.

Ah right, that's a good point. And looking at the source, that particular unit test just hashes the numbers 0 through 1000, which doesn't seem like all that realistic of a workload (and has more to do with how the hash machinery handles an int than it does with any differences in how how the machinery would handle strings).

So I think it would be reasonable to switch this to FxHash if that was important. It might be nice to switch the unit test to doing something more realistic with strings if we did that.

Comment 21

[Daniel Varga [:dvarga]]

https://hg.mozilla.org/mozilla-central/rev/f13608115d2d

Comment 22

[Cameron McCormack (:heycam)]

(In reply to Bobby Holley (:bholley) from comment #20)
> Ah right, that's a good point. And looking at the source, that particular
> unit test just hashes the numbers 0 through 1000, which doesn't seem like
> all that realistic of a workload (and has more to do with how the hash
> machinery handles an int than it does with any differences in how how the
> machinery would handle strings).

I think I misread that test -- I thought it was hashing the pointers to those numbers!  Hashing the numbers themselves isn't such a useful benchmark for us.