From: Junio C Hamano <gitster@pobox.com>
Date: Mon, 08 Jul 2013 17:37:09 GMT
Subject: Re: expanding pack idx fanout table
Message-ID: <7vsizpymuy.fsf@alter.siamese.dyndns.org>
In-Reply-To: <CAJo=hJsto1ik=GTC8c3+2_jBuUqcAPL0UWp-1uoYYMpgbLB+qg@mail.gmail.com>

Shawn Pearce <spearce@spearce.org> writes:

> Has anyone studied the impact of converting the pack idx fanout table
> from 256 entries to 65536 entries?
>
> Back of the envelope estimates for 3.1M objects in linux.git suggests
> a 2^16 fanout table would decrease the number of binary search
> iterations from ~14 to ~6. The increased table costs an extra 255 KiB
> of disk. On a 70M idx file this is noise.
>
> I'm starting to wonder if increasing the fanout table once the object
> count is above a certain threshold is a reasonable optimization for
> larger repositories.

Yeah, and I do not think we have to be worried too much about
backward compatibility for .idx files, as they are local and can be
regenerated if an older version cannot read it.

I also wonder if we can generate a finer-grained fan-out table on
the fly, perhaps lazily, without changing the on-disk format ;-)