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

On data structures and parallelism

From
HOHeikki Orsila <shdl@zakalwe.fi>
Date
May 17, 2009, 15:23 UTC
Message-ID
<20090517152335.GC11543@zakalwe.fi>
There was an interesting discussion at
http://realworldtech.com/forums/index.cfm?action=detail&id=98909&threadid=98430&roomid=2

that involves DAGs and decompression in Git. The problem is achieving parallelism. The following comment was made:

"And is it possible to store the block pointers from one object to another in uncompressed form?"

Is there a case in Git where an "object" could store SHA1 in uncompressed format, allowing prefetching the next object in chain before uncompressing the current object? Prefetching could increase parallelism (and speedup) in some cases.

A quick glance at Git's source code showed that commit objects are compressed. Having even a single parent SHA1 in uncompressed format would allow some prefetching. All but perhaps a few objects contain at least one parent SHA1 :-)

-- 
Heikki Orsila
heikki.orsila@iki.fi
http://www.iki.fi/shd
Next: Linus Torvalds
Message 1 of 5 in “On data structures and parallelism”
  1. Heikki OrsilaMay 17, 2009
  2. Linus TorvaldsMay 17, 2009
  3. Linus TorvaldsMay 17, 2009
  4. david@lang.hmMay 17, 2009
  5. Linus TorvaldsMay 17, 2009

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.