On Thu, Sep 15, 2016 at 10:45:34AM -0700, Junio C Hamano wrote:
> Jeff King <p...@peff.net> writes:
> > Measuring _just_ the collisions is more like the patch below. In my
> > measurements it's more like 30ms, compared to 10s for all of the
> > hashcmps.
> > So we really aren't dealing with collisions, but rather just verifying
> > that our hash landed at the right spot. And _any_ data structure is
> > going to have to do that.
> The reverse side of the coin may be if we can shrink the hashtable
> smaller and load it more heavily without sacrificing performance by
> making the necessary "have we landed at the right spot" check cheap
> enough, I guess.
I think that's where things like cuckoo hashing come into play. They
didn't have any effect for us because we already keep the table very
unloaded. But you could _probably_ increase the load factor without
sacrificing performance using a more clever scheme.
It's not clear to me that the current table size is a big problem,
though. It might be hurting us with cache effects, but I think the only
way we'd know is to measure.