HashMap starts the search even if the map is empty

[pmarcelll]

It was mentioned in the latest Ferris Makes Emulators episode that contains showed up in the profiling results, although a lot of the times the map itself was empty.
I think the extra checking is worth it before starting the search and that way the hashing is also skipped.

[Manishearth]

contains() calls contains_key() which calls search() and finally search_hashed()

That function checks for zero capacity the first thing it does. The only work that is done between the contains() call and search_hashed() is computing the hash.

Now, if the map was empty (but had nonzero capacity) we'd have a problem. search_hashed can't bail early in that case because it still needs to produce the entry, but contains doesn't care about that.

In Ferris' example, were hashmaps with nonzero capacity but zero length used? You can make that happen with HashMap::with_capacity(foo), but by default hashmaps are zero capacity (no allocation till you insert things into them). If not, this probably isn't the problem.

Bailing out on size == 0 in contains is an interesting idea. Small negative impact on users of regular hashmaps, large positive impact on users of preallocated hashmaps.

[leonardo-m]

Small negative impact on users of regular hashmaps, large positive impact on users of preallocated hashmaps.

How much "small" is the negative impact in the regular case needs to be benchmarked.

[Manishearth]

Yes. It's probably negligible.

[Stebalien]

@Manishearth That really depends on the use case. If you have a large vector of mostly empty HashMap/HashSets, repeatedly re-hashing the key could take a while. However, this probably isn't a common use-case so the programmer could just check the length in cases like this.

Anyways, wasn't there some talk about falling back on linear search/storage for small maps/sets? That would probably be more useful in practice.

[arthurprs]

I wanted to move the capacity check from search_hashed up in the call stack, notably to the get* and contain methods (and there it can become a len = 0 check, solving this), as entry and insert reserve at least 1 space upfront anyway (so it's never really capacity 0). This saves 1 branch offsetting the extra ones required by #38368 . Probably not worth the trouble though :)

[technicalguy]

So I've had a look into this issue.

The only work that is done between the contains() call and search_hashed() is computing the hash.

Computing the hash can be quite costly, even for integer keys on an empty HashMap it seems contains() is an order of magnitude faster with an empty check before hash computation than with one after.

Bailing out on size == 0 in contains is an interesting idea. Small negative impact on users of regular hashmaps, large positive impact on users of preallocated hashmaps.

I think it should be possible to make an early size == 0 check without requiring a second check afterwards (i.e. no negative impact on regular HashMap users with non-empty maps). Some kind of search_hashed_no_empty_check method could be called by a search_no_empty_check method, given that contains_key has already checked that it is empty.

Anyways, wasn't there some talk about falling back on linear search/storage for small maps/sets? That would probably be more useful in practice.

This works well for small collections (e.g. integer keys up to about 16 items), however the problem is that different types require different amounts of time to compute the hash, and and also different amounts of time to compute equality. This is not necessarily consistent between values (e.g. strings or lists).

I think I can implement this for types with simple equality checks, but it cannot be used in general. (The empty check can be used in general, so I propose we implement both.)