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

Re: generation numbers (was: [PATCH 0/4] Speed up git tag --contains)

From
Jeff King <peff@peff.net>
Date
Jul 6, 2011, 18:12 UTC
Message-ID
<20110706181200.GD17978@sigill.intra.peff.net>
In-Reply-To
<20110706150103.GA2693@thunk.org>
On Wed, Jul 06, 2011 at 11:01:03AM -0400, Ted Ts'o wrote:
> Is it worth it to try to replicate this information across repositories?

Probably not. I suggested notes-cache just because the amount of code is very trivial.

One problem with notes storage is that it's not well optimized for tiny pieces of data like this (e.g., the generation number should fit in a 32-bit unsigned int, as its max is the size of the longest single path in the history graph). But notes are much more general; we will actually map each commit to a blob object containing the generation number, which is pretty wasteful.

> Why not just simply have a cache file in the git directory which is
> managed somewhat like gitk.cache; call it generation.cache?

Yeah, that would be fine. With a sorted list of binary sha1s and 32-bit generation numbers, you're talking about 24 bytes per commit. Or a 6 megabyte cache for linux-2.6.

You'd probably want to be a little clever with updates. If I have calculated the generation number of every commit, and then do "git commit; git tag --contains HEAD", you probably don't want to rewrite the entire cache. You could probably journal a fixed number of entries in an unsorted file (or even in a parallel directory structure to loose objects), and then periodically write out the whole sorted list when the journal gets too big. Or choose a more clever data structure that can do in-place updates.

-Peff
Previous: Ted Ts'oNext: Jakub Narebski
Message 13 of 28 in “Speed up git tag --contains”
  1. 0/4 Speed up git tag --containsÆvar Arnfjörð Bjarmason, Jun 11, 2011
  2. 1/4 tag: speed up --contains calculationÆvar Arnfjörð Bjarmason, Jun 11, 2011
  3. 2/4 limit "contains" traversals based on commit timestampÆvar Arnfjörð Bjarmason, Jun 11, 2011
  4. 3/4 default core.clockskew variable to one dayÆvar Arnfjörð Bjarmason, Jun 11, 2011
  5. 4/4 Why is "git tag --contains" so slow?Ævar Arnfjörð Bjarmason, Jun 11, 2011
  6. Jeff KingJul 6, 2011
  7. Jeff KingJul 6, 2011
  8. Clemens BuchacherJul 6, 2011
  9. Jonathan NiederJul 6, 2011
  10. Jeff KingJul 6, 2011
  11. Jakub NarebskiJul 6, 2011
  12. Ted Ts'oJul 6, 2011
  13. Jeff KingJul 6, 2011
  14. Jakub NarebskiJul 6, 2011
  15. Jeff KingJul 7, 2011
  16. Junio C HamanoJul 7, 2011
  17. Jakub NarebskiJul 7, 2011
  18. A Large Angry SCMJul 7, 2011
  19. Junio C HamanoJul 8, 2011
  20. Jeff KingJul 8, 2011
  21. Junio C HamanoJul 6, 2011
  22. Jeff KingJul 7, 2011
  23. Jakub NarebskiJul 7, 2011
  24. csilversJan 12, 2018
  25. Jeff KingMar 3, 2018
  26. csilversMar 8, 2018
  27. Derrick StoleeMar 12, 2018
  28. Jeff KingMar 12, 2018

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.