git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 0/9] Prefix-compress on-disk index entries

From
David Barr <davidbarr@google.com>
Date
May 2, 2012, 04:26 UTC
Message-ID
<CAFfmPPOPWkUcuWRFYGk9LHCAJAbvNYK=Xk+pvSa8fbffpRDppQ@mail.gmail.com>
In-Reply-To
<CACsJy8DZ4t0f_mdDJTUZvz_pBPrPTsEBxHEkYREowWm6D1ikkw@mail.gmail.com>
On Wed, May 2, 2012 at 11:58 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
Show 23 quoted lines
> On Fri, Apr 6, 2012 at 3:41 PM, David Barr <davidbarr@google.com> wrote:
>> On Thu, Apr 5, 2012 at 4:44 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>> Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:
>>>
>>>> On Wed, Apr 4, 2012 at 5:53 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>> ...
>>>> I wonder what causes user time drop from .29s to .13s here. I think
>>>> the main patch should increase computation, even only slightly, not
>>>> less.
>>>
>>> The main patch reduced the amount of the data needs to be sent to the
>>> machinery to checksum and write to disk by about 45%, saving both I/O
>>> and computation.
>>
>> I hacked together a quick patch to try predictive coding the other
>> fields of the index. I got a further 34% improvement in size over
>> this series. Patches to come. I just used the previous cache entry as
>> the predictor and reused varint.h together with zigzag encoding[1].
>>
>> That's a total improvement in size over v2 of 62%.
>
> Have you posted (and I missed) the patches? I'm interested in seeing
> what changes you made.
I haven't posted anything - my proof of concept was write-only and slow.

I added a prelude with a bitmask that describes which fields differ with the previous entry.

For each differing field, I encoded something like: diff := this - prev; zigzag := (diff << 1) ^ (diff >> 31) raw := zigzag - 1 /* zero impossible because of mask */ write_varint(raw)

I also experimented with using unique sha1 prefixes but it was slow and probably introduces race conditions.

>> [1] https://developers.google.com/protocol-buffers/docs/encoding#types

-- David Barr

Previous: Nguyen Thai Ngoc DuyNext: Junio C Hamano
Message 19 of 27 in “Prefix-compress on-disk index entries”
  1. 0/9 Prefix-compress on-disk index entriesJunio C Hamano, Apr 3, 2012
  2. 1/9 varint: make it available outside the context of packJunio C Hamano, Apr 3, 2012
  3. 2/9 cache.h: hide on-disk index detailsJunio C Hamano, Apr 3, 2012
  4. 3/9 read-cache.c: allow unaligned mapping of the index fileJunio C Hamano, Apr 3, 2012
  5. 4/9 read-cache.c: make create_from_disk() report number of bytes it consumedJunio C Hamano, Apr 3, 2012
  6. 5/9 read-cache.c: report the header version we do not understandJunio C Hamano, Apr 3, 2012
  7. 6/9 read-cache.c: move code to copy ondisk to incore cache to a helper functionJunio C Hamano, Apr 3, 2012
  8. 7/9 read-cache.c: move code to copy incore to ondisk cache to a helper functionJunio C Hamano, Apr 3, 2012
  9. 8/9 read-cache.c: read prefix-compressed names in index on-disk version v4Junio C Hamano, Apr 3, 2012
  10. 9/9 read-cache.c: write index v4 formatJunio C Hamano, Apr 3, 2012
  11. David BarrApr 4, 2012
  12. Junio C HamanoApr 4, 2012
  13. Junio C HamanoApr 4, 2012
  14. 2/2 update-index: upgrade/downgrade on-disk index versionJunio C Hamano, Apr 4, 2012
  15. Nguyen Thai Ngoc DuyApr 4, 2012
  16. Junio C HamanoApr 4, 2012
  17. David BarrApr 6, 2012
  18. Nguyen Thai Ngoc DuyMay 2, 2012
  19. David BarrMay 2, 2012
  20. 1/2 unpack-trees: preserve the index file version of originalJunio C Hamano, Apr 27, 2012
  21. 2/2 index-v4: document the entry formatJunio C Hamano, Apr 27, 2012
  22. Thomas RastApr 30, 2012
  23. Junio C HamanoMay 1, 2012
  24. Thomas RastMay 1, 2012
  25. Shawn PearceMay 2, 2012
  26. Junio C HamanoMay 2, 2012
  27. Shawn PearceMay 2, 2012

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.