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

[Duy Nguyen <pclouds@gmail.com>]

On Wed, Aug 7, 2013 at 3:23 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
>> 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..
>
> You're right, I don't need it for the reading code.  I do need to keep a
> list of cache-entries for writing though, where a linked list is best
> suited for the task.  I'll use a next_ce pointer for that.

Hmm.. yeah you need to maintain temporary structures before writing
out direntries, then fileentries table. We can't just write as we
traverse through the cache in one go. Maybe a new field in cache_entry
for the linked list, or maintain the linked list off cache_entry..
whichever is easier for you.

> I've tried implementing both versions with the internal tree structure,
> see below for timings.
>
> simpleapi is the code that was posted to the list, HEAD uses a
> tree-structure for the directories internally, and replaces strcmp with
> cache_name_compare and leaves out the prefix.  This tree uses dummy
> entries for the sub-directories.
>
> Dummy entries are single NUL-bytes mixed with the cache-entries, which
> should give optimal performance.  I haven't thought much about
> corruption of the index, but I don't think we would need any additional
> crc checksums or similar.
>
> The performance advantage seems very slim to none when using the dummy
> entries to avoid the comparison though, so I don't think it makes sense
> to make the index more complicated for a very small speed-up.

Agreed.

> Test                                        simpleapi         HEAD                     this tree
> -------------------------------------------------------------------------------------------------------------
> 0003.2: v[23]: update-index                 3.22(2.61+0.58)   3.20(2.56+0.61) -0.6%    3.22(2.67+0.53) +0.0%
> 0003.3: v[23]: grep nonexistent -- subdir   1.65(1.36+0.27)   1.65(1.34+0.30) +0.0%    1.67(1.34+0.31) +1.2%
> 0003.4: v[23]: ls-files -- subdir           1.50(1.20+0.29)   1.54(1.18+0.34) +2.7%    1.53(1.22+0.30) +2.0%
> 0003.6: v4: update-index                    2.69(2.28+0.39)   2.70(2.21+0.47) +0.4%    2.70(2.27+0.41) +0.4%
> 0003.7: v4: grep nonexistent -- subdir      1.33(0.98+0.34)   1.36(1.01+0.33) +2.3%    1.34(1.03+0.30) +0.8%
> 0003.8: v4: ls-files -- subdir              1.21(0.86+0.33)   1.23(0.91+0.30) +1.7%    1.22(0.90+0.30) +0.8%
> 0003.10: v5: update-index                   2.12(1.58+0.52)   2.20(1.67+0.52) +3.8%    2.19(1.66+0.51) +3.3%
> 0003.11: v5: ls-files                       1.57(1.21+0.34)   1.55(1.20+0.33) -1.3%    1.52(1.21+0.29) -3.2%
> 0003.12: v5: grep nonexistent -- subdir     0.08(0.06+0.01)   0.07(0.04+0.02) -12.5%   0.07(0.04+0.02) -12.5%
> 0003.13: v5: ls-files -- subdir             0.07(0.04+0.01)   0.06(0.05+0.00) -14.3%   0.07(0.05+0.01) +0.0%
-- 
Duy