Skip to content

Improving performance of lookups by removing is-empty check #636

@gaujay

Description

@gaujay

This optional test was added in commit dec8e8c:

fn get_inner<Q>(&self, k: &Q) -> Option<&(K, V)>
where
    Q: Hash + Equivalent<K> + ?Sized,
{
    if self.table.is_empty() {
        None
    } else {
        let hash = make_hash::<Q, S>(&self.hash_builder, k);
        self.table.get(hash, equivalent_key(k))
    }
}

The rational was:

Don't hash the key when searching in an empty table.
In rustc, approximately one third of all non-modifying lookups are on an empty table!

But this additional branch seems to cost up to 12.5% performance on every normal lookup
(e.g. for a HashMap<usize, usize>, even with a hot branch predictor in micro-benchmarks).
See comment in linked commit for detailed bench results (sorry for the double post, not sure a comment had enough visibility).

Are we sure we want to degrade the nominal use case of non-empty lookups here?
Shouldn't it be rustc responsibility to do the emptiness check on its side (in particular when hashing is expensive).
Or is there a better way maybe?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions