`wasmparser`: Allow to drop hash-based dependencies entirely

[Robbepop]

• Adds hash-collections crate feature.
• Adds prefer-btree-collections crate feature.
• Removes no-hash-maps crate feature.

Advantages

• This allows to get rid of ahash, hashbrown and indexmap dependencies entirely when the hash-collections crate feature is disabled to further reduce compilation times and binary sizes. wasmparser's own built-in btree-based collections are used instead.
• This still allows to use btree-collections instead of hash-collections when prefer-btree-collections is enabled even if hash-collections is enabled as well (higher precedence), similar to no-hash-maps.
• The 2 new crate features are additive and are positively named (no negations).

Compile Times

Including hash-based collections:

cargo build --release -p wasmparser --no-default-features --features hash-collections
4.14s user 0.34s system 190% cpu 2.347 total

Excluding hash-based collections:

cargo build --release -p wasmparser --no-default-features
2.81s user 0.15s system 174% cpu 1.692 total

4.14 seconds to 2.81 seconds 🎉

[alexcrichton]

Thanks for this! In the abstract we ideally wouldn't have to deal with any of this and would instead have only one type used, so this has got me thinking again. AFAIK the main motivations for each are:

• btree - only suitable collection when there is no default source of randomness (e.g. no_std)
• hash maps - theoretically faster with O(1) access instead of O(log(n))

Originally wasmparser used hash maps everywhere and no_std is where the btree versions grew out of to handle environments without randomness. I know I advocated at the time for keeping hash maps but this PR is raising the question again for me of "why not just always use btrees"?

Have you measured the binary size with/without hash maps? I'd be surprised if it were significantly different since both hash maps and btree maps have a nontrivial code size. The crate rlibs themselves probably aren't really linking in a whole lot since everything is monomorphized here anyway, but I also want to double-check this point. (I realize that naively "fewer crates probably means smaller binary" which is why I want to double-check here too)

Is there really a compelling use case for hash maps still to warrant all this collections infrastructure? In the abstract I'm a little sad to lose O(1) bits here just because of no_std but concretely being able to simplify everything here feels pretty compelling.

@fitzgen do you perhaps have any thoughts on this? I'm personally leaning towards removing wasmparser's usage of hash maps outright since it feels difficult to motivate over "just use btrees", but I'm curious if you think there's a compelling use case for preserving guaranteed O(1) access.

(also sorry @Robbepop I don't mean to commandeer the PR too much here, if we end up deciding to remove hash maps it's probably best to merge this PR and then do that work as a follow-up)

[Robbepop]

@alexcrichton Thank you for the elaborate answer. I just measured the binary sizes and they are equal. So the only thing that really is affected with this PR are compile times.

Wasmi also has the no-hash-maps crate feature inherited by wasmparser and I conducted many benchmarks in the past. The summary is that for small (~ <40kB) Wasm blobs btree usually is significantly faster, for medium (~ <500kB) sized blobs there is no significant difference between btree and hash and for very large (~ >500kB) there sometimes are small wins for hash based collections. However, btree always wins in memory consumption. Especially since many maps are mapping simple integers which a btree-tree embeds whereas a hash-map is required to also store their hashes everywhere which are of equal size etc.

I had similar thoughts in Wasmi, e.g. to get rid of the features altogether and just always use btree collections. What kept me from doing this is that without wasmparser doing the same, not too much is gained.

I am not concerned about performnce of BTree{Map,Set} in general but mostly concerned when it comes to the built-in data structures that are built on top of them, e.g. the built-in IndexMap or in Wasmi's case its built-in StringInterner. Due to missing low-level APIs in BTreeMap these tend to be slower and it is harder to optimize them.

In conclusion, I am fine with both options forward. However, I also think that in the long-term future we might want to drop HashMap usage, especially once we figured out how we can make our built-in BTreeMap-based data structures fast enough for all use cases - if that is not already the case even.

[fitzgen]

Dropping HashMaps completely sounds fine to me, assuming that we reproduce similar results in wasmparser- specific benchmarking that were found for wasmi.

[Robbepop]

In case you want to reproduce the Wasmi benchmark results for yourself, this is the small set of Wasm blobs that are used: https://github.com/wasmi-labs/wasmi/tree/main/crates/wasmi/benches/wasm And also these Rust sourced benchmarks, too: https://github.com/wasmi-labs/rust-benchmarks/tree/cf035b986969a93a61004b7a28f6f5cde69b84d7/cases

[alexcrichton]

Ok I'm going to go ahead and flag this for merge (thanks again @Robbepop)

This doesn't regress anything except users of default-features = false and that's less of a "regression" and more of a "doing the same thing as before requires a different incantation". Given that and the benefits of compile times here I think this is good.

I'm additionally going to file a follow-up issue for more discussion on hash maps vs not.