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
Linus Torvalds <torvalds@osdl.org>
Date
Sep 14, 2005, 22:50 UTC
Message-ID
<Pine.LNX.4.58.0509141549270.26803@g5.osdl.org>
In-Reply-To
<4328A3F9.1010506@citi.umich.edu>
On Wed, 14 Sep 2005, Chuck Lever wrote:
> 
> oh, i see.  the hash table won't help cache_find_name find an insertion 
> point quickly if the name isn't already in the cache.
Note that almost all insertion tends to happen linearly.
In particular, read-tree always inserts things in order.

So probably _most_ of the file finding could actually use even a stupid linear search, if they just had a place to start from. And 99% of the time, it would be very close to where they wanted to be.

Hmm?
		Linus
Previous: Chuck LeverNext: Daniel Barkalow
Message 31 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.