Improving performance of lookups by removing is-empty check

[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?

[cuviper]

It performs well if I lift that condition from get_inner to get instead (which we would have to repeat for all callers). I guess having the match afterward fails to optimize that fast-path? Compared inlined, it's something like:

    let get_inner = if self.table.is_empty() {
        None
    } else {
        let hash = make_hash::<Q, S>(&self.hash_builder, k);
        self.table.get(hash, equivalent_key(k))
    };
    match get_inner {
        Some((_, v)) => Some(v),
        None => None,
    }

vs.

    if self.table.is_empty() {
        None
    } else {
        let get_inner = {
            let hash = make_hash::<Q, S>(&self.hash_builder, k);
            self.table.get(hash, equivalent_key(k))
        };
        match get_inner {
            Some((_, v)) => Some(v),
            None => None,
        }
    }

[gaujay]

Great, now the branch predictor can do its work it seems.
I'm still worried about cold calls that will be heavily penalized by a branch misprediction though.
Maybe we could add an unlikely at least, to the is-empty path?