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

Re: [PATCH 17/32] read-cache: split-index mode

From
Duy Nguyen <pclouds@gmail.com>
Date
Apr 29, 2014, 22:45 UTC
Message-ID
<CACsJy8Da=n+kh8_bUkJ11-dK09A6zOMnhBQJCsPCWcCJ2mY0pw@mail.gmail.com>
In-Reply-To
<xmqqiopskq1o.fsf@gitster.dls.corp.google.com>
On Wed, Apr 30, 2014 at 12:23 AM, Junio C Hamano <gitster@pobox.com> wrote:
Show 20 quoted lines
> Duy Nguyen <pclouds@gmail.com> writes:
>
>>> I do think it is sensible to keep two arrays of "struct cache_entry"
>>> around (one for base and one for incremental changes) inside
>>> index_state, and the patch seems to do so via "struct split_index"
>>> that does have a copy of saved_cache.  If the write-out codepath
>>> walks these two sorted arrays in parallel, shouldn't it be able to
>>> figure out which entry is added, deleted and modified without
>>> fattening this structure?
>>
>> So far without that "index" field I would have to resort to hasing
>> entries in both arrays to find the shared paths. But ideas are
>> welcome.
>
> Hmm, why do you need to hash, when both arrays are sorted?  Wouldn't
> it be just the matter of walking these two arrays in parallel,
> with one scanning index for each array initialized to the beginning,
> comparing the elements pointed by these indices, noting the side
> that comes earlier in the sort order and advancing the index on that
> side (or if they compare equal then advance both), ...?

And compare all names and stages (especially in the unpack-trees case, when no entry is reused). I kinda hope to avoid that. Speaking about reusing cache_entry, we won't be able to share cache_entry because when it's freed in replace_index_entry, or remove_index_entry_at in the main index, we need to locate the same entry in the shared index as well and remove that stale pointer. Without sharing, we nearly double memory usage from the beginning.

-- 
Duy
Previous: Junio C HamanoNext: Junio C Hamano
Message 22 of 75 in “Split index mode for very large indexes”
  1. 00/32 Split index mode for very large indexesNguyễn Thái Ngọc Duy, Apr 28, 2014
  2. 01/32 ewah: fix constness of ewah_read_mmapNguyễn Thái Ngọc Duy, Apr 28, 2014
  3. 02/32 ewah: delete unused ewah_read_mmap_native declarationNguyễn Thái Ngọc Duy, Apr 28, 2014
  4. 03/32 sequencer: do not update/refresh index if the lock cannot be heldNguyễn Thái Ngọc Duy, Apr 28, 2014
  5. 04/32 read-cache: new API write_locked_index instead of write_index/write_cacheNguyễn Thái Ngọc Duy, Apr 28, 2014
  6. 05/32 read-cache: relocate and unexport commit_locked_index()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  7. 06/32 read-cache: store in-memory flags in the first 12 bits of ce_flagsNguyễn Thái Ngọc Duy, Apr 28, 2014
  8. 07/32 read-cache: be strict about "changed" in remove_marked_cache_entries()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  9. 08/32 read-cache: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  10. 09/32 update-index: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  11. 10/32 resolve-undo: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  12. 11/32 unpack-trees: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  13. 12/32 cache-tree: mark istate->cache_changed on cache tree invalidationNguyễn Thái Ngọc Duy, Apr 28, 2014
  14. 13/32 cache-tree: mark istate->cache_changed on cache tree updateNguyễn Thái Ngọc Duy, Apr 28, 2014
  15. 14/32 cache-tree: mark istate->cache_changed on prime_cache_tree()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  16. 15/32 entry.c: update cache_changed if refresh_cache is set in checkout_entry()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  17. 16/32 read-cache: save index SHA-1 after readingNguyễn Thái Ngọc Duy, Apr 28, 2014
  18. 17/32 read-cache: split-index modeNguyễn Thái Ngọc Duy, Apr 28, 2014
  19. Junio C HamanoApr 28, 2014
  20. Duy NguyenApr 29, 2014
  21. Junio C HamanoApr 29, 2014
  22. Duy NguyenApr 29, 2014
  23. Junio C HamanoApr 30, 2014
  24. 18/32 read-cache: mark new entries for split indexNguyễn Thái Ngọc Duy, Apr 28, 2014
  25. Eric SunshineApr 30, 2014
  26. 19/32 read-cache: save deleted entries in split indexNguyễn Thái Ngọc Duy, Apr 28, 2014
  27. 20/32 read-cache: mark updated entries for split indexNguyễn Thái Ngọc Duy, Apr 28, 2014
  28. 21/32 split-index: the writing partNguyễn Thái Ngọc Duy, Apr 28, 2014
  29. 22/32 split-index: the reading partNguyễn Thái Ngọc Duy, Apr 28, 2014
  30. 23/32 split-index: do not invalidate cache-tree at read timeNguyễn Thái Ngọc Duy, Apr 28, 2014
  31. 24/32 split-index: strip pathname of on-disk replaced entriesNguyễn Thái Ngọc Duy, Apr 28, 2014
  32. Junio C HamanoApr 29, 2014
  33. 25/32 update-index: new options to enable/disable split index modeNguyễn Thái Ngọc Duy, Apr 28, 2014
  34. 26/32 update-index --split-index: do not split if $GIT_DIR is read onlyNguyễn Thái Ngọc Duy, Apr 28, 2014
  35. 27/32 rev-parse: add --shared-index-path to get shared index pathNguyễn Thái Ngọc Duy, Apr 28, 2014
  36. 28/32 read-tree: force split-index mode off on --index-outputNguyễn Thái Ngọc Duy, Apr 28, 2014
  37. 29/32 read-tree: note about dropping split-index mode or index versionNguyễn Thái Ngọc Duy, Apr 28, 2014
  38. 30/32 read-cache: force split index mode with GIT_TEST_SPLIT_INDEXNguyễn Thái Ngọc Duy, Apr 28, 2014
  39. 31/32 t2104: make sure split index mode is off for the version testNguyễn Thái Ngọc Duy, Apr 28, 2014
  40. 32/32 t1700: new tests for split-index modeNguyễn Thái Ngọc Duy, Apr 28, 2014
  41. Shawn PearceApr 28, 2014
  42. Duy NguyenApr 29, 2014
  43. Duy NguyenMay 9, 2014
  44. Junio C HamanoMay 9, 2014
  45. 0/8 Speed up cache loading timeNguyễn Thái Ngọc Duy, May 13, 2014
  46. 1/8 read-cache: allow to keep mmap'd memory after readingNguyễn Thái Ngọc Duy, May 13, 2014
  47. 2/3 Add read-cache--daemonNguyễn Thái Ngọc Duy, May 13, 2014
  48. Erik Faye-LundMay 13, 2014
  49. Duy NguyenMay 13, 2014
  50. Duy NguyenMay 13, 2014
  51. Erik Faye-LundMay 13, 2014
  52. Duy NguyenMay 13, 2014
  53. Erik Faye-LundMay 13, 2014
  54. Duy NguyenMay 13, 2014
  55. Erik Faye-LundMay 13, 2014
  56. 2/8 unix-socket: stub impl. for platforms with no unix socket supportNguyễn Thái Ngọc Duy, May 13, 2014
  57. Erik Faye-LundMay 13, 2014
  58. Erik Faye-LundMay 13, 2014
  59. 3/8 daemonize: set a flag before exiting the main processNguyễn Thái Ngọc Duy, May 13, 2014
  60. 3/3 read-cache: try index data from shared memoryNguyễn Thái Ngọc Duy, May 13, 2014
  61. 4/8 Add read-cache--daemon for caching index and related stuffNguyễn Thái Ngọc Duy, May 13, 2014
  62. Erik Faye-LundMay 13, 2014
  63. 5/8 read-cache: try index data from shared memoryNguyễn Thái Ngọc Duy, May 13, 2014
  64. Erik Faye-LundMay 13, 2014
  65. 6/8 read-cache--daemon: do not read index from shared memoryNguyễn Thái Ngọc Duy, May 13, 2014
  66. 7/8 read-cache: skip verifying trailing SHA-1 on cached indexNguyễn Thái Ngọc Duy, May 13, 2014
  67. 8/8 read-cache: inform the daemon that the index has been updatedNguyễn Thái Ngọc Duy, May 13, 2014
  68. Erik Faye-LundMay 13, 2014
  69. David TurnerMay 22, 2014
  70. Stefan BellerMay 13, 2014
  71. Duy NguyenMay 13, 2014
  72. 9/8 even faster loading time with index version 254Nguyễn Thái Ngọc Duy, May 13, 2014
  73. Junio C HamanoApr 28, 2014
  74. Richard HansenApr 30, 2014
  75. Duy NguyenMay 1, 2014

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.