Re: [PATCH] cherry: cache patch-ids to avoid repeating work

["Geoffrey Irving" <irving@naml.us>]

On Fri, Jul 11, 2008 at 8:36 AM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> Hi,
>
> On Fri, 11 Jul 2008, Geoffrey Irving wrote:
>
>> On Thu, Jul 10, 2008 at 11:54 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> > "Geoffrey Irving" <irving@naml.us> writes:
>> >
>> >>>> Oops: avoiding the infinite loop only requires reading expected O(1)
>> >>>> entries on load, so I can fix that if you like.  It would only be all of
>> >>>> them if it actually did detect the infinite loop.
>> >>>
>> >>> I have to admit that you lost me there.  AFAIR the patch-id cache is a
>> >>> simple commit->patch_id store, right?  Then there should be no way to get
>> >>> an infinite loop.
>> >>
>> >> If every entry is nonnull, find_helper loops forever.
>> >
>> > Isn't it sufficient to make this part check the condition as well?
>> >
>> > +       if (cache->count >= cache->size)
>> > +       {
>> > +               warning("%s is corrupt: count %"PRIu32" >= size %"PRIu32,
>> > +                       filename, cache->count, cache->size);
>> > +               goto empty;
>> > +       }
>> >
>> > At runtime you keep the invariants that hashtable always has at most 3/4
>> > full and whoever wrote the file you are reading must have honored that as
>> > well, or there is something fishy going on.
>>
>> Good point.  There's no reason not to check the 3/4 condition.  It isn't
>> sufficient to avoid the infinite loop, though, since we don't verify
>> that count is accurate.
>
> Why so complicated?  I mean, you can count in that "infinite" loop
> yourself, no?

Yeah, I was just trying to avoid the extra termination condition,
because I don't think it adds any real safety.

Geoffrey