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

[Duy Nguyen <pclouds@gmail.com>]

A little bit more..

On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
> +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..

> +}
> +
> +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.

> +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.

> +       }
> +
> +       *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