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 8, 2012, 13:54 UTC
Message-ID
<CACsJy8DfJJpwidfUQFDeqM=5uPpGF6rZ6C1pS0H6mSNHUqOkbg@mail.gmail.com>
In-Reply-To
<7v7gtaups3.fsf@alter.siamese.dyndns.org>
On Wed, Aug 8, 2012 at 8:38 AM, Junio C Hamano <gitster@pobox.com> wrote:
Show 13 quoted lines
> If the workload we _care_ about is served better by using an API
> that works over an in-core tree-shaped index data structure, I do
> not think it is unreasonable to read the v2 on-disk format and
> represent it as a tree-shaped index while we read it.  Of course,
> there are things that are not as effective when reading from the
> flat v2 on-disk format (e.g. path limited reading will have to at
> least _scan_ the whole thing, even though it may process only the
> entries that match the pathspec) compared to reading from a
> tree-shaped on-disk format, but I doubt that the difference between
> the cost of reading into a flat array and the cost of reading and
> forming whatever non-flat data structure you seem to think is better
> is so big that it would negate the benefit of using a better in-core
> structure.

OK how about this. The general idea is preserve/extend current flat index API and add a new (tree-based) one. Index users can use either. They can even mix them up (which they do because we can't just flip the API in one day for about 200 source files).

The day that unpack_trees() is converted to tree API, I will declare v5 victory ;)

= Cleanup =

struct cache_entry becomes partly opaque. ce_ctime..ce_gid are hidden in -v2.c and -v5.c. We only expose ce_size, ce_flags, ce_namelen, name and sha1 to index users. Extra v5 fields like ce_stat_crc, next and dir_next are also hidden. These fields can be put in a real struct in read-cache.h, which is supposedly included by -v2.c and -v5.c

= Updating =

All index update API (add_index_entry, add_to_index, remove_index_entry_at, remove_marked_cached_entries) are hooked by v5 when the loaded index is v5. v5 can update internal data when these are called (e.g. conflict resolution), or just mark them "dirty" to be worked on later in flush_index().

Anybody who updates a cache_entry is supposed to call cache_entry_updated() function, which is no-op for v2 but v5 may want to watch this activity.

Refreshing index is a special operation. Of course it's hooked by v5. v5 may need its own implementation because it could walk working tree and index tree at the same time. Of course v5 impl must also update flat API data structure along the way.

A new function flush_index() is introduced, where v5 can update all internal data and keep it in sync with index_state. When flat/tree APIs are mixed, flush_index() must be called when switching from flat API to tree API.

To help v5 deal with index rewrite in unpack_trees(), index_bulk_update() may be introduced, which tells v5 "we are going to do a lot of adding/removing/shuffling, keep your actions to minimum, you most likely have to rebuild the trees at flush_index() anyway"

New API may be introduced for some big operations if it proves v5-beneficial. I'm thinking of adding/removing a bunch of files by pathspec, where v5 can walk working directory at the same time it walks index directory tables.

= Tree traversal =

I don't see big problems here. We support opendir/readdir-like API for tree traversing (with pathspec filtering). We also support lookup_cache_entry to get cache_entry* of a certain path.

When tree traversal gets to a conflict entry, it lets the caller know there's a conflict entry, it does not traverse through stage 1-3 during traversal. Caller is expected to use conflict lookup API for that.

We also support reading partial index, filtered by pathspec. On v2, it reads full index.

= Tree update =

At some point we may want to work on trees exclusively. Any operations here must keep flat API data structure in sync.

We may want to postpone the sync if it's a lot of work, by doing all the work in flush_index() before caller switches from tree API to flat API again.

= Flat API deprecation =

At some point, tree update API will not update flat API any more unless explicitly asked by caller. I don't expect "cache" in struct index_state to be removed, unless we do really good merges using tree API.

-- 
Duy
Previous: Junio C HamanoNext: Junio C Hamano
Message 52 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.