Re: [PATCH 3/5] make object_directory.loose_objects_subdir_seen a bitmap

From: "René Scharfe" <l.s.r@web.de>
To: Eric Wong <e@80x24.org>, git@vger.kernel.org
Cc: Jeff King <peff@peff.net>
Subject: Re: [PATCH 3/5] make object_directory.loose_objects_subdir_seen a bitmap
Date: Sun, 27 Jun 2021 12:23:18 +0200	[thread overview]
Message-ID: <496545dc-e372-401c-13f4-daa7ee765d39@web.de> (raw)
In-Reply-To: <20210627024718.25383-4-e@80x24.org>

Am 27.06.21 um 04:47 schrieb Eric Wong:
> There's no point in using 8 bits per-directory when 1 bit
> will do.  This saves us 224 bytes per object directory, which
> ends up being 22MB when dealing with 100K alternates.

The point was simplicity under the assumption that the number of
repositories is low -- for most users it's only one.  That obviously
doesn't hold for your use case anymore. :)

A compact representation should also reduce dcache misses, so this
should be a win for the single-repo case as well.

> Signed-off-by: Eric Wong <e@80x24.org>
> ---
>  object-file.c  | 10 +++++++---
>  object-store.h |  2 +-
>  2 files changed, 8 insertions(+), 4 deletions(-)
>
> diff --git a/object-file.c b/object-file.c
> index 6be43c2b60..2c8b9c05f9 100644
> --- a/object-file.c
> +++ b/object-file.c
> @@ -2463,12 +2463,16 @@ struct oid_array *odb_loose_cache(struct object_directory *odb,
>  {
>  	int subdir_nr = oid->hash[0];
>  	struct strbuf buf = STRBUF_INIT;
> +	size_t BM_SIZE = sizeof(odb->loose_objects_subdir_seen[0]) * CHAR_BIT;

With that name I'd expect the variable to contain the number of bytes or
bits in the whole bitmap.  And to not be a variable at all, but rather a
macro.  Perhaps word_bits?

bitsizeof() does the same and is slightly shorter.

> +	uint32_t *bitmap;

Ah, you call the array items bitmap, which they are.  Hmm.  I rather
think of the whole thing as a bitmap and its uint32_t elements as words.
Does it matter?  Not sure.

> +	uint32_t bit = 1 << (subdir_nr % BM_SIZE);

I'd call that mask, but bit is fine as well..

Anyway, it would look something like this:

	size_t word_bits = bitsizeof(odb->loose_objects_subdir_seen[0]);
	size_t word_index = subdir_nr / word_bits;
	size_t mask = 1 << (subdir_nr % word_bits);

>
>  	if (subdir_nr < 0 ||
> -	    subdir_nr >= ARRAY_SIZE(odb->loose_objects_subdir_seen))
> +	    subdir_nr >= ARRAY_SIZE(odb->loose_objects_subdir_seen) * BM_SIZE)

bitsizeof(odb->loose_objects_subdir_seen) would be easier to read and
understand, I think.

>  		BUG("subdir_nr out of range");
>
> -	if (odb->loose_objects_subdir_seen[subdir_nr])
> +	bitmap = &odb->loose_objects_subdir_seen[subdir_nr / BM_SIZE];
> +	if (*bitmap & bit)
>  		return &odb->loose_objects_cache[subdir_nr];
>
>  	strbuf_addstr(&buf, odb->path);
> @@ -2476,7 +2480,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb,
>  				    append_loose_object,
>  				    NULL, NULL,
>  				    &odb->loose_objects_cache[subdir_nr]);
> -	odb->loose_objects_subdir_seen[subdir_nr] = 1;
> +	*bitmap |= bit;
>  	strbuf_release(&buf);
>  	return &odb->loose_objects_cache[subdir_nr];
>  }
> diff --git a/object-store.h b/object-store.h
> index 20c1cedb75..8fcddf3e65 100644
> --- a/object-store.h
> +++ b/object-store.h
> @@ -22,7 +22,7 @@ struct object_directory {
>  	 *
>  	 * Be sure to call odb_load_loose_cache() before using.
>  	 */
> -	char loose_objects_subdir_seen[256];
> +	uint32_t loose_objects_subdir_seen[8]; /* 256 bits */

Perhaps	DIV_ROUND_UP(256, bitsizeof(uint32_t))?  The comment explains
it nicely already, though.

>  	struct oid_array loose_objects_cache[256];
>
>  	/*
>

Summary: Good idea, the implementation looks correct, I stumbled
over some of the names, bitsizeof() could be used.

René