Re: [PATCH 4/6] rerere: use strmap to store rerere directories

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 28, 2021, 19:52 UTC
Message-ID: <xmqq8s8cx2iz.fsf@gitster.c.googlers.com>
In-Reply-To: <YBJa98B1a6mP/Bsx@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 21 quoted lines

> Subject: [PATCH] rerere: use strmap to store rerere directories
>
> We store a struct for each directory we access under .git/rr-cache. The
> structs are kept in an array sorted by the binary hash associated with
> their name (and we do lookups with a binary search).
>
> This works OK, but there are a few small downsides:
>
>  - the amount of code isn't huge, but it's more than we'd need using one
>    of our other stock data structures
>
>  - the insertion into a sorted array is quadratic (though in practice
>    it's unlikely anybody has enough conflicts for this to matter)
>
>  - it's intimately tied to the representation of an object hash. This
>    isn't a big deal, as the conflict ids we generate use the same hash,
>    but it produces a few awkward bits (e.g., we are the only user of
>    hash_pos() that is not using object_id).
>
> Let's instead just treat the directory names as strings, and store them
> in a strmap. This is less code, and removes the use of hash_pos().

Nice. I didn't realize that this part is so well isolated that another table implementation can easily be dropped in (it was a long time since I stared at this part of the system, back when I was extending it to handle <preimage,postimage> pairs that share the same conflict IDs, which was quite tricky to get right).

> This one might be controversial, or at least considered unnecessary
> churn. Because the benefits I listed above are pretty negligible, and
> really my ulterior motive is getting rid of the call to hash_pos().

No objection from me.  Thanks.