Re: expanding pack idx fanout table

[Junio C Hamano <gitster@pobox.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 ;-)