On Thu, Sep 15, 2016 at 10:45:34AM -0700, Junio C Hamano wrote: > Jeff King <peff@xxxxxxxx> 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. -Peff