Re: reftable [v4]: new ref storage format

From: Shawn Pearce <spearce@spearce.org>
Date: Jul 31, 2017, 23:05 UTC
Message-ID: <CAJo=hJu-j+7CfKy8vCS9t+6=-PVGNC5D6HuYgqpO7GrNi=MDig@mail.gmail.com>
In-Reply-To: <CAGZ79kZ3vbpzSEMHVHMtF0drY1P1rgz1eB7OB-J31-y6K+x5sw@mail.gmail.com>

On Mon, Jul 31, 2017 at 12:01 PM, Stefan Beller <sbeller@google.com> wrote:

Show 15 quoted lines

> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce <spearce@spearce.org> wrote:
>> 4th iteration of the reftable storage format.
>>
>> You can read a rendered version of this here:
>> https://googlers.googlesource.com/sop/jgit/+/reftable/Documentation/technical/reftable.md
>>
>
>>     uint16( restart_count )
>
> When looking for 16/32/64 bit hard coded ints I came across
> this one once again. How much more expensive is reading
> a varint? As the block_len points at the restart_count, we cannot
> replace it with a varint easily, but we could use a byte-reversed
> varint instead. If we do this step, all restart offsets could also be
> (reverse) varints?

Its not the expense of decoding a varint, its making the file structure predictable so its simple to binary search within restart points. If these were varints, it becomes much more difficult to divide the remaining range in half and update the boundary conditions to locate the next mid-point.