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

Re: [PATCH v2 12/19] read-cache: read index-v5

From
Duy Nguyen <pclouds@gmail.com>
Date
Jul 15, 2013, 10:12 UTC
Message-ID
<CACsJy8DDRN5aTOzxuiGSa6UjbBiVUYwHjPcnN+8mw4xKmvkx-A@mail.gmail.com>
In-Reply-To
<1373650024-3001-13-git-send-email-t.gummerer@gmail.com>
A little bit more..
On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
Show 13 quoted lines
> +static void ce_queue_push(struct cache_entry **head,
> +                            struct cache_entry **tail,
> +                            struct cache_entry *ce)
> +{
> +       if (!*head) {
> +               *head = *tail = ce;
> +               (*tail)->next = NULL;
> +               return;
> +       }
> +
> +       (*tail)->next = ce;
> +       ce->next = NULL;
> +       *tail = (*tail)->next;

No no no. "next" is for name-hash.c don't "reuse" it here. And I don't think you really need to maintain a linked list of cache_entries by the way. More on read_entries comments below..

Show 10 quoted lines
> +}
> +
> +static struct cache_entry *ce_queue_pop(struct cache_entry **head)
> +{
> +       struct cache_entry *ce;
> +
> +       ce = *head;
> +       *head = (*head)->next;
> +       return ce;
> +}
Same as ce_queue_push.
Show 44 quoted lines
> +static int read_entries(struct index_state *istate, struct directory_entry **de,
> +                       unsigned int *entry_offset, void **mmap,
> +                       unsigned long mmap_size, unsigned int *nr,
> +                       unsigned int *foffsetblock)
> +{
> +       struct cache_entry *head = NULL, *tail = NULL;
> +       struct conflict_entry *conflict_queue;
> +       struct cache_entry *ce;
> +       int i;
> +
> +       conflict_queue = NULL;
> +       if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
> +               return -1;
> +       for (i = 0; i < (*de)->de_nfiles; i++) {
> +               if (read_entry(&ce,
> +                              *de,
> +                              entry_offset,
> +                              mmap,
> +                              mmap_size,
> +                              foffsetblock) < 0)
> +                       return -1;
> +               ce_queue_push(&head, &tail, ce);
> +               *foffsetblock += 4;
> +
> +               /*
> +                * Add the conflicted entries at the end of the index file
> +                * to the in memory format
> +                */
> +               if (conflict_queue &&
> +                   (conflict_queue->entries->flags & CONFLICT_CONFLICTED) != 0 &&
> +                   !cache_name_compare(conflict_queue->name, conflict_queue->namelen,
> +                                       ce->name, ce_namelen(ce))) {
> +                       struct conflict_part *cp;
> +                       cp = conflict_queue->entries;
> +                       cp = cp->next;
> +                       while (cp) {
> +                               ce = convert_conflict_part(cp,
> +                                               conflict_queue->name,
> +                                               conflict_queue->namelen);
> +                               ce_queue_push(&head, &tail, ce);
> +                               conflict_part_head_remove(&cp);
> +                       }
> +                       conflict_entry_head_remove(&conflict_queue);
> +               }

I start to wonder if separating staged entries is a good idea. It seems to make the code more complicated. The good point about conflict section at the end of the file is you can just truncate() it out. Another way is putting staged entries in fileentries, sorted alphabetically then by stage number, and a flag indicating if the entry is valid. When you remove resolve an entry, just set the flag to invalid (partial write), so that read code will skip it.

I think this approach is reasonably cheap (unless there are a lot of conflicts) and it simplifies this piece of code. truncate() may be overrated anyway. In my experience, I "git add <path>" as soon as I resolve <path> (so that "git diff" shrinks). One entry at a time, one index write at a time. I don't think I ever resolve everything then "git add -u .", which is where truncate() shines because staged entries are removed all at once. We should optimize for one file resolution at a time, imo.

Show 20 quoted lines
> +       }
> +
> +       *de = (*de)->next;
> +
> +       while (head) {
> +               if (*de != NULL
> +                   && strcmp(head->name, (*de)->pathname) > 0) {
> +                       read_entries(istate,
> +                                    de,
> +                                    entry_offset,
> +                                    mmap,
> +                                    mmap_size,
> +                                    nr,
> +                                    foffsetblock);
> +               } else {
> +                       ce = ce_queue_pop(&head);
> +                       set_index_entry(istate, *nr, ce);
> +                       (*nr)++;
> +                       ce->next = NULL;
> +               }

In this loop, you do some sort of merge sort combining a list of sorted files and a list of sorted directories (which will be expanded to bunches of files by the recursive read_entries). strcmp() does two things. Assume we're in directory 'a', it makes sure that subdirectory 'a/b' is only inserted after file 'a/a' is inserted to maintain index sort order. It also makes sure that 'de' of an outside directory 'b' will not be expanded here. strcmp will be called for every file, checking _full_ path. Sounds expensive.

If you maintain two pointers first_subdir and next_sibling in "de" as in my previous mail, you know "de" 'b' is out without string comparison (de->next_sibling would be NULL). With that, the purpose of strcmp is simply making sure that 'a/b' is inserted after 'a/a'. Because we know all possible "de" is a subdirectory of 'a', we don't need to compare the prefix 'a/'. We still need to strcmp on every file, but we only need to compare the file name, not the leading directory anymore. Cheaper.

Going further, I wonder if we could eliminate strcmp completely. We could store dummy entries in fileentries to mark the positions of the subdirectories. When we encounter a dummy entry, we call read_entries() instead of set_index_entry.

If you merge the "read_entry" for loop in this while loop, you don't need to maintain a linked list of ce to pop out one by one here.

> +       }
> +       return 0;
> +}
> +
-- 
Duy
Previous: Thomas GummererNext: Thomas Gummerer
Message 29 of 51 in “Index-v5”
  1. 00/19 Index-v5Thomas Gummerer, Jul 12, 2013
  2. 01/19 t2104: Don't fail for index versions other than [23]Thomas Gummerer, Jul 12, 2013
  3. 02/19 read-cache: split index file version specific functionalityThomas Gummerer, Jul 12, 2013
  4. 03/19 read-cache: move index v2 specific functions to their own fileThomas Gummerer, Jul 12, 2013
  5. Duy NguyenJul 14, 2013
  6. Thomas GummererJul 19, 2013
  7. 04/19 read-cache: Re-read index if index file changedThomas Gummerer, Jul 12, 2013
  8. 05/19 Add documentation for the index apiThomas Gummerer, Jul 12, 2013
  9. 06/19 read-cache: add index reading apiThomas Gummerer, Jul 12, 2013
  10. Duy NguyenJul 14, 2013
  11. 07/19 make sure partially read index is not changedThomas Gummerer, Jul 12, 2013
  12. Duy NguyenJul 14, 2013
  13. Thomas GummererJul 17, 2013
  14. 08/19 grep.c: Use index apiThomas Gummerer, Jul 12, 2013
  15. Duy NguyenJul 14, 2013
  16. Thomas GummererJul 15, 2013
  17. 09/19 ls-files.c: use index apiThomas Gummerer, Jul 12, 2013
  18. Duy NguyenJul 14, 2013
  19. Thomas GummererJul 17, 2013
  20. 10/19 documentation: add documentation of the index-v5 file formatThomas Gummerer, Jul 12, 2013
  21. Duy NguyenJul 14, 2013
  22. Thomas GummererJul 17, 2013
  23. Duy NguyenAug 4, 2013
  24. Thomas GummererAug 4, 2013
  25. 11/19 read-cache: make in-memory format aware of stat_crcThomas Gummerer, Jul 12, 2013
  26. 12/19 read-cache: read index-v5Thomas Gummerer, Jul 12, 2013
  27. Duy NguyenJul 14, 2013
  28. Thomas GummererAug 7, 2013
  29. Duy NguyenJul 15, 2013
  30. Thomas GummererJul 17, 2013
  31. Duy NguyenAug 8, 2013
  32. Thomas GummererAug 8, 2013
  33. Thomas GummererAug 9, 2013
  34. Thomas GummererAug 7, 2013
  35. Duy NguyenAug 8, 2013
  36. 13/19 read-cache: read resolve-undo dataThomas Gummerer, Jul 12, 2013
  37. 14/19 read-cache: read cache-tree in index-v5Thomas Gummerer, Jul 12, 2013
  38. 15/19 read-cache: write index-v5Thomas Gummerer, Jul 12, 2013
  39. 16/19 read-cache: write index-v5 cache-tree dataThomas Gummerer, Jul 12, 2013
  40. 17/19 read-cache: write resolve-undo data for index-v5Thomas Gummerer, Jul 12, 2013
  41. 18/19 update-index.c: rewrite index when index-version is givenThomas Gummerer, Jul 12, 2013
  42. 19/19 p0003-index.sh: add perf test for the index formatsThomas Gummerer, Jul 12, 2013
  43. Duy NguyenJul 14, 2013
  44. Thomas GummererJul 15, 2013
  45. Duy NguyenJul 15, 2013
  46. Thomas GummererJul 17, 2013
  47. Junio C HamanoJul 17, 2013
  48. Thomas GummererJul 19, 2013
  49. Junio C HamanoJul 19, 2013
  50. Ramsay JonesJul 16, 2013
  51. Thomas GummererJul 17, 2013

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.