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

From: Stefan Beller <sbeller@google.com>
Date: Sep 15, 2016, 16:26 UTC
Message-ID: <CAGZ79kZ-rLVijKj31uYgYrLkSCCOaLKWrr8u=6LXnd=gmma+xQ@mail.gmail.com>
In-Reply-To: <20160915064701.c4ishixuynbzpgwx@sigill.intra.peff.net>

On Wed, Sep 14, 2016 at 11:47 PM, Jeff King <peff@peff.net> wrote:

Show 24 quoted lines

> On Wed, Sep 14, 2016 at 07:01:41PM -0700, Stefan Beller wrote:
>
>>  According to Jeff, sending patches that don't get accepted is the new hype!
>
> It is what all the cool kids are doing. Unfortunately, it does not save
> you from nitpicky reviews...;)
>
>>       first = i = hash_obj(sha1, obj_hash_size);
>> +     clock_gettime(CLOCK_MONOTONIC, &time1);
>>       while ((obj = obj_hash[i]) != NULL) {
>>               if (!hashcmp(sha1, obj->oid.hash))
>>                       break;
>> @@ -98,6 +131,9 @@ struct object *lookup_object(const unsigned char *sha1)
>>               if (i == obj_hash_size)
>>                       i = 0;
>>       }
>> +     clock_gettime(CLOCK_MONOTONIC, &time2);
>> +     diff(&time1, &time2, &t_diff);
>> +     add_time_to(&caching, &t_diff);
>>       if (obj && i != first) {
>
> I don't think this is actually measuring the time spent on collisions.
> It's measuring the time we spend in hashcmp(), but that includes the
> non-collision case where we find it in the first hashcmp.

Right. I measured all lookup times, i.e. this function accounts for 1/3 of the run time.

>
> 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 off by a few orders of magnitude, i.e. we don't have to worry about the time spent in resolving collisions.

Show 20 quoted lines

>
> 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. If you want to make it faster, I'd try
> optimizing hashcmp (and you can see why the critbit tree was slower; if
> we spend so much time just on hashcmp() to make sure we're at the right
> key, then making that slower with a bunch of branching is not going to
> help).
>
> I notice we still open-code hashcmp. I get a slight speedup by switching
> it to memcmp(). About 2.5%, which is similar to what I showed in
>
>   http://public-inbox.org/git/20130318073229.GA5551@sigill.intra.peff.net/
>
> a few years ago (though it's more pronounced as a portion of the whole
> now, because we've optimized some of the other bits).
>
> The main driver there was memcmp() improvements that went into glibc
> 2.13 several years ago. It might be time to start assuming that memcmp()
> beats our open-coded loop.

http://stackoverflow.com/questions/21106801/why-is-memcmp-so-much-faster-than-a-for-loop-check

seems to agree with you; so I'd think I'll agree with switching over.

Show 5 quoted lines

>
> It may also be possible to really micro-optimize it on some platforms,
> because we know the size in advance (I'd kind of expect the compiler to
> do that, but if we're ending up in glibc memcmp then it sounds like it
> is not the case).

That stackoverflow link suggests that glibc already has microoptimisations for a variety of platforms.

>
> -Peff