Re: [PATCH] object: measure time needed for resolving hash collisions

From: Jeff King <peff@peff.net>
Date: Sep 15, 2016, 18:47 UTC
Message-ID: <20160915184737.2vcarwyhdp7xl3mg@sigill.intra.peff.net>
In-Reply-To: <xmqq60pxoy4h.fsf@gitster.mtv.corp.google.com>

On Thu, Sep 15, 2016 at 10:45:34AM -0700, Junio C Hamano wrote:

Show 14 quoted lines

> Jeff King <peff@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.

-Peff