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

Re: [PATCH 00/32] Split index mode for very large indexes

From
Duy Nguyen <pclouds@gmail.com>
Date
Apr 29, 2014, 01:52 UTC
Message-ID
<CACsJy8B7P0Un0__9mS2j81PimPZbz9oTKZHKx8yo_smOMck1qA@mail.gmail.com>
In-Reply-To
<CAJo=hJtgijOOMPbFjvTUaENw=hr0YixYmy1UkdqEd=CpLZ5L2A@mail.gmail.com>
On Tue, Apr 29, 2014 at 4:18 AM, Shawn Pearce <spearce@spearce.org> wrote:
Show 20 quoted lines
> On Mon, Apr 28, 2014 at 3:55 AM, Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
>> I hinted about it earlier [1]. It now passes the test suite and with a
>> design that I'm happy with (thanks to Junio for a suggestion about the
>> rename problem).
>>
>> From the user point of view, this reduces the writable size of index
>> down to the number of updated files. For example my webkit index v4 is
>> 14MB. With a fresh split, I only have to update an index of 200KB.
>> Every file I touch will add about 80 bytes to that. As long as I don't
>> touch every single tracked file in my worktree, I should not pay
>> penalty for writing 14MB index file on every operation.
>
> This is a very welcome type of improvement.
>
> I am however concerned about the complexity of the format employed.
> Why do we need two EWAH bitmaps in the new index? Why isn't this just
> a pair of sorted files that are merge-joined at read, with records in
> $GIT_DIR/index taking priority over same-named records in
> $GIT_DIR/sharedindex.$SHA1?  Deletes could be marked with a bit or an
> "all zero" metadata record.

With the bitmaps, I know the exact position to replace or delete an entry. Merge sort works, but I would need to walk through all entries in both indexes to compare entry name and stage, a bit costly in my opinion. And if you look at the format description in patch 0017, I store the replaced entries without their names to save a bit more space. "EWAH" is just an implementation detail. A straightforward bitmap should work fine (25kb for 200k entries seem reasonable).

-- 
Duy
Previous: Shawn PearceNext: Duy Nguyen
Message 42 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.