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

Re: [PATCH 21/22] teach the merge algorithm about cache iterators

From
CLChuck Lever <cel@citi.umich.edu>
Date
Sep 14, 2005, 19:49 UTC
Message-ID
<43287ECB.8090308@citi.umich.edu>
In-Reply-To
<Pine.LNX.4.63.0509141214490.23242@iabervon.org>
Daniel Barkalow wrote:
> The really exciting thing to do would be to have different programs use 
> different implementations, by way of linker magic.

yes, i've been considering that, but i'm not sure it is really worth the effort. see below -- the right data structure should be good for just about any git workload.

Show 7 quoted lines
> My guess for the ideal is to have a linked list with a hashtable for 
> finding entries by looking up names, because we don't look things up by 
> index. This combination gives O(1) in-order iteration, O(1) lookup by 
> name, O(1) append, O(n) insert, and O(1) remove. This means that 
> git-update-cache --add would be slow, but everything else would be fast. 
> (Except, of course, for the overhead of actually reading and writing the 
> index file, rather than mmaping it.)
[ i'm not sure why you think insert would be O(n). ]

keeping the linked list for O(1) next/prev and delete, and augmenting it with a hash table to allow O(m/n) insert and find would be ideal. with a fairly large hash table, we do better than a tree for any reasonably sized repository i can imagine.

and, i believe simply adding a hash table to my list implementation will be easy, and simpler overall than a tree implementation. famous last words.

mmapping the index file is still OK. i haven't changed the cache_entry structure at all.

begin:vcard fn:Chuck Lever n:Lever;Charles org:Network Appliance, Incorporated;Linux NFS Client Development adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA email;internet:cel@citi.umich.edu title:Member of Technical Staff tel;work:+1 734 763 4415 tel;fax:+1 734 763 4434 tel;home:+1 734 668 1089 x-mozilla-html:FALSE url:http://www.monkey.org/~cel/ version:2.1 end:vcard

Previous: Junio C HamanoNext: Daniel Barkalow
Message 28 of 49 in “cache cursors: an introduction”
  1. 00/22 cache cursors: an introductionChuck Lever, Sep 12, 2005
  2. 01/22 introduce facility to walk through the active cacheChuck Lever, Sep 12, 2005
  3. 02/22 use cache iterator in checkout-index.cChuck Lever, Sep 12, 2005
  4. 03/22 teach diff.c about cache iteratorsChuck Lever, Sep 12, 2005
  5. 04/22 teach diff-index.c about cache iteratorsChuck Lever, Sep 12, 2005
  6. 05/22 teach diff-files.c about cache iteratorsChuck Lever, Sep 12, 2005
  7. 06/22 teach diff-stages.c about cache iteratorsChuck Lever, Sep 12, 2005
  8. 07/22 teach fsck-objects.c to use cache iteratorsChuck Lever, Sep 12, 2005
  9. 08/22 teach ls-files.c to use cache iteratorsChuck Lever, Sep 12, 2005
  10. 09/22 teach read-tree.c to use cache iteratorsChuck Lever, Sep 12, 2005
  11. 10/22 teach update-index.c about cache cursorsChuck Lever, Sep 12, 2005
  12. 11/22 teach write-tree.c to use cache iteratorsChuck Lever, Sep 12, 2005
  13. 12/22 simplify write_cache() calling sequenceChuck Lever, Sep 12, 2005
  14. 13/22 move purge_cache() to read-cache.cChuck Lever, Sep 12, 2005
  15. 14/22 move read_cache_unmerged into read-cache.cChuck Lever, Sep 12, 2005
  16. 15/22 replace cache_name_posChuck Lever, Sep 12, 2005
  17. 16/22 teach apply.c to use cache_find_name()Chuck Lever, Sep 12, 2005
  18. 17/22 teach checkout-index.c to use cache_find_name()Chuck Lever, Sep 12, 2005
  19. 18/22 teach diff.c to use cache_find_name()Chuck Lever, Sep 12, 2005
  20. 19/22 teach ls-files.c to use cache_find_name()Chuck Lever, Sep 12, 2005
  21. 20/22 teach merge-index.c to use cache_find_name()Chuck Lever, Sep 12, 2005
  22. 21/22 teach the merge algorithm about cache iteratorsChuck Lever, Sep 12, 2005
  23. Daniel BarkalowSep 12, 2005
  24. Chuck LeverSep 13, 2005
  25. Chuck LeverSep 14, 2005
  26. Daniel BarkalowSep 14, 2005
  27. Junio C HamanoSep 14, 2005
  28. Chuck LeverSep 14, 2005
  29. Daniel BarkalowSep 14, 2005
  30. Chuck LeverSep 14, 2005
  31. Linus TorvaldsSep 14, 2005
  32. Daniel BarkalowSep 14, 2005
  33. Chuck LeverSep 15, 2005
  34. 22/22 teach read-cache.c to use cache_find_name()Chuck Lever, Sep 12, 2005
  35. A Large Angry SCMSep 12, 2005
  36. Chuck LeverSep 12, 2005
  37. Daniel BarkalowSep 12, 2005
  38. Junio C HamanoSep 12, 2005
  39. Tim OttingerSep 13, 2005
  40. Junio C HamanoSep 13, 2005
  41. Tim OttingerSep 13, 2005
  42. Catalin MarinasSep 14, 2005
  43. Chuck LeverSep 14, 2005
  44. Junio C HamanoSep 12, 2005
  45. Daniel BarkalowSep 12, 2005
  46. Junio C HamanoSep 12, 2005
  47. Chuck LeverSep 12, 2005
  48. Junio C HamanoSep 13, 2005
  49. Linus TorvaldsSep 13, 2005

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.