par_extend for hashbrown's HashMap is less efficient than rayon's implementation for stdlib HashMap with par_iter over a Vec

[gaynor-anthropic]

In hashbrown, we collect all the elements of the parallel iterator into a LinkedList of Vec and then we extend the map with each of those vecs. See:

• https://docs.rs/hashbrown/latest/src/hashbrown/external_trait_impls/rayon/map.rs.html#444-463
• https://docs.rs/hashbrown/latest/src/hashbrown/external_trait_impls/rayon/helpers.rs.html#8-27

Whereas in rayon, there is a fast path for if the parallel iterator's opt_len method returns a Some (this happens with iterators over Vec and slice and such). See:

• https://docs.rs/rayon/latest/src/rayon/iter/extend.rs.html#15
• https://docs.rs/rayon/latest/src/rayon/iter/extend.rs.html#67

in that case, rayon will collect the values directly into that vec, without allocating N Vecs and a LinkedList: https://docs.rs/rayon/latest/src/rayon/iter/collect/mod.rs.html#23

Ideally hashbrown would either be able to implement this optimization itself, or somehow delegate to a public API in rayon to perform this optimization.

[cuviper]

There's a helper that uses the fast path, since rayon 1.9.0:
https://docs.rs/rayon/latest/rayon/iter/trait.ParallelIterator.html#method.collect_vec_list

[gaynor-anthropic]

@cuviper And you just pay teh overhead of a single item linkedlist I guess? Seems like a good improvement. I'll probably send a PR tonight unless someone beats me to it.