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

Re: [PATCH/RFC v2 0/16] Introduce index file format version 5

From
Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Date
Aug 7, 2012, 12:16 UTC
Message-ID
<CACsJy8CepAQr4r-c_hzwgT2-_bpFV-=VmOsFaBcDZqBpG52reQ@mail.gmail.com>
In-Reply-To
<7vehnjzzfd.fsf@alter.siamese.dyndns.org>
On Tue, Aug 7, 2012 at 12:46 AM, Junio C Hamano <gitster@pobox.com> wrote:
Show 28 quoted lines
> The index_ops abstraction is a right way to go, and I like it, but I
> think the split illustrated in this patch might turn out to be at
> wrong levels (and it is OK, as I understand this is a illustration
> of concept patch).
>
> For example, add_to_index() interface may be a good candidate to
> have in index_ops.  Because your in-core index may not be holding
> everything in a flat array, "find the location in the flat array the
> entry would sit, replace the existing one if there is any, otherwise
> insert" cannot be a generic way to add a new entry.  If you make the
> whole thing an abstract API entry point, a sparse implementation of
> the in-core index could still implement it without bringing the
> untouched and irrelevant parts of the index to core.
>
>         Side note: with a tree-like implementation of the in-core
>         index, "find the location the entry would sit", "get the
>         entry at the location", "insert the entry at the location",
>         could still be a set of good abstract API, though.  The
>         definition of _location_ may be quite different from "the
>         offset of the entry counting from the beginning of a flat
>         array", which is what index_name_pos() returns.
>
> The story is the same on the removal front.  The current
> remove_index_entry_at() interface is tied to the flat array
> implementation, so "remove the nth entry from the beginning" is an
> inappropriate interface for anything but such an implementation
> (unless we come up with an abstract notion of the "location" that is
> usable efficiently in a tree-like implementation, that is).

add_to_index and remove_index_entry_at seem good places for the cut. But do we need to redefine the location? I think we need to sketch out a long term plan first. In my mind it's like this:

 - for 3-5 years since v5 is released, we support v2 and v5 in
parallel. Other code can take advantage of v5, but it must neither
sacrifice v2 performance, compatibility nor maintainability
 - after that, we deprecate v2. v2 is automatically converted to v5 in
memory. v2 perf may suffer but at that point we don't care any more as
the majority of users should have been migrated to v5 (*)

If the long term plan is actually that, we will need to stick to flat array implementation for forseeable future as moving from it most likely impacts v2 performance. When v5 is used, it must maintain two views, tree and list, at the same time. We can then postpone thinking about the redefinition until v2 is deprecated and in-core moved to tree view only.

This might not be the best way forward as v2 incompatible features (like keeping empty directories in index, what else?) may never come until v2 is deprecated.

(*) this is questionable though. Depending on the benchmarks, we may want to support both v2 and v5 for indefinite time with v2 recommended for small projects and v5 the rest. If it's so, yeah we need to think of better API now.

Show 6 quoted lines
> I wish that the development of this topic was done more in a
> top-down direction, instead of bottom-up, so that it identified the
> necessary access patterns to the in-core index early and come up
> with a good set of abstract API first, and then only after that is
> done, came up with in-core and on-disk format to support the
> necessary operations.

Yeah, which is why I asked to try out partial reading/writing early as I'm a learn by example kind of guy. Speaking of which, now that we have something substantial, what should be done before this may be considered for 'next'?

I don't think we should wait until it reaches full potential (i.e. significant perf gain from all major index-related commands). Apart from patch preparation, more testing and benchmarking, should we wait until we get new public API or just use current index API?

One API addition that I (if nobody else) will do soon is read_index_partial(<pathspec>) and adapt as many read-only commands as possible to it. (v2 just ignores the pathspec input and loads the whole thing, so all commands must be aware the the loaded may be more than what they asked). But this can wait until v5 gets in.

-- 
Duy
Previous: Junio C HamanoNext: Junio C Hamano
Message 50 of 59 in “Introduce index file format version 5”
  1. 0/16 Introduce index file format version 5Thomas Gummerer, Aug 5, 2012
  2. 01/16 Modify cache_header to prepare for other index formatsThomas Gummerer, Aug 5, 2012
  3. Junio C HamanoAug 6, 2012
  4. Thomas GummererAug 7, 2012
  5. Junio C HamanoAug 7, 2012
  6. 02/16 Modify read functions to prepare for other index formatsThomas Gummerer, Aug 5, 2012
  7. 03/16 Modify match_stat_basic to prepare for other index formatsThomas Gummerer, Aug 5, 2012
  8. 04/16 Modify write functions to prepare for other index formatsThomas Gummerer, Aug 5, 2012
  9. Junio C HamanoAug 6, 2012
  10. Thomas GummererAug 7, 2012
  11. 05/16 t2104: Don't fail for index versions other than [23]Thomas Gummerer, Aug 5, 2012
  12. Junio C HamanoAug 6, 2012
  13. 06/16 t3700: sleep for 1 second, to avoid interfering with the racy codeThomas Gummerer, Aug 5, 2012
  14. Junio C HamanoAug 6, 2012
  15. Thomas GummererAug 7, 2012
  16. Junio C HamanoAug 8, 2012
  17. Junio C HamanoAug 8, 2012
  18. Thomas GummererAug 9, 2012
  19. Junio C HamanoAug 9, 2012
  20. Thomas GummererAug 9, 2012
  21. 07/16 Add documentation of the index-v5 file formatThomas Gummerer, Aug 5, 2012
  22. 08/16 Make in-memory format aware of stat_crcThomas Gummerer, Aug 5, 2012
  23. Junio C HamanoAug 6, 2012
  24. Thomas GummererAug 7, 2012
  25. 09/16 Read index-v5Thomas Gummerer, Aug 5, 2012
  26. Junio C HamanoAug 6, 2012
  27. Thomas GummererAug 8, 2012
  28. Junio C HamanoAug 8, 2012
  29. Thomas GummererAug 8, 2012
  30. Junio C HamanoAug 8, 2012
  31. 10/16 Read resolve-undo dataThomas Gummerer, Aug 5, 2012
  32. Junio C HamanoAug 6, 2012
  33. Thomas GummererAug 7, 2012
  34. 11/16 Read cache-tree in index-v5Thomas Gummerer, Aug 5, 2012
  35. 12/16 Write index-v5Thomas Gummerer, Aug 5, 2012
  36. 13/16 Write index-v5 cache-tree dataThomas Gummerer, Aug 5, 2012
  37. 14/16 Write resolve-undo data for index-v5Thomas Gummerer, Aug 5, 2012
  38. 15/16 update-index.c: add a force-rewrite optionThomas Gummerer, Aug 5, 2012
  39. Junio C HamanoAug 6, 2012
  40. Thomas GummererAug 8, 2012
  41. 16/16 p0002-index.sh: add perf test for the index formatsThomas Gummerer, Aug 5, 2012
  42. Nguyễn Thái Ngọc DuyAug 6, 2012
  43. 1/2 Move index v2 specific code out of read-cacheNguyễn Thái Ngọc Duy, Aug 6, 2012
  44. 2/2 Add index-v5Nguyễn Thái Ngọc Duy, Aug 6, 2012
  45. Robin RosenbergAug 7, 2012
  46. Thomas GummererAug 8, 2012
  47. Junio C HamanoAug 6, 2012
  48. Thomas GummererAug 6, 2012
  49. Junio C HamanoAug 6, 2012
  50. Nguyen Thai Ngoc DuyAug 7, 2012
  51. Junio C HamanoAug 8, 2012
  52. Nguyen Thai Ngoc DuyAug 8, 2012
  53. Junio C HamanoAug 8, 2012
  54. Nguyen Thai Ngoc DuyAug 9, 2012
  55. Thomas RastAug 7, 2012
  56. Junio C HamanoAug 7, 2012
  57. Thomas RastAug 8, 2012
  58. Junio C HamanoAug 8, 2012
  59. Nguyen Thai Ngoc DuyAug 8, 2012

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.