[patch] speed up ga_grow()

[Dominique Pellé]

Hi

Attached patch speeds up function ga_grow() by
using realloc() instead of freeing and allocating
a new block when growing an array. It should also
reduce memory usage.

Vim is 25% faster after patch with this test case:

$ wget http://dominique.pelle.free.fr/speed-join.vim.gz
$ gzip -d speed-join.vim.gz

$ time vim -u NONE -S speed-join.vim

3 measurements with vim-7.3.444 _before_ patch:

22.252 sec
23.094 sec
22.748 sec

3 measurements with vim-7.3.444 _after_ patch:

16.509 sec
16.342 sec
16.077 sec

That's ~25% faster.

ga_grow() is used for many things in Vim
so there might be other things that are also faster.

Regards
-- Dominique

[Dominique Pellé]

Dominique Pellé wrote:

I thought a bit more about this and found why my change
speeds up by 25%. The reason why ga_grow() was slow, is
because it grows an array using an arithmetic growth
rather a geometric growth in getsourceline() when calling
ga_concat() at ex_cmds2.c:3452, and ex_cmds2.c:3463:

ex_cmds2.c:

3395 char_u *
3396 getsourceline(c, cookie, indent)
...
3438 if (line != NULL && (vim_strchr(p_cpo, CPO_CONCAT) == NULL))
3439 {
3440 /* compensate for the one line read-ahead */
3441 --sourcing_lnum;
3442
3443 /* Get the next line and concatenate it when it starts with a
3444 * backslash. We always need to read the next line, keep it in
3445 * sp->nextline. */
3446 sp->nextline = get_one_sourceline(sp);
3447 if (sp->nextline != NULL && *(p = skipwhite(sp->nextline)) == '\\')
3448 {
3449 garray_T ga;
3450
3451 ga_init2(&ga, (int)sizeof(char_u), 200);
3452 ga_concat(&ga, line);
3453 ga_concat(&ga, p + 1);
3454 for (;;)
3455 {
3456 vim_free(sp->nextline);
3457 sp->nextline = get_one_sourceline(sp);
3458 if (sp->nextline == NULL)
3459 break;
3460 p = skipwhite(sp->nextline);
3461 if (*p != '\\')
3462 break;
3463 ga_concat(&ga, p + 1); /// <--- arithmetic growth!
3464 }
3465 ga_append(&ga, NUL);
3466 vim_free(line);
3467 line = ga.ga_data;
3468 }
3469 }

Arithmetic growth can lead to O(n^2) behavior because
of memory being copied. This code was introduced recently
in Vim-7.3.433:

===
changeset: 3332:8a731d7f0664
tag: v7-3-433
user: Bram Moolenaar <br...@vim.org>
date: Sun Feb 05 23:10:30 2012 +0100
files: src/ex_cmds2.c src/version.c
description:
updated for version 7.3.433
Problem: Using continued lines in a Vim script can be slow.
Solution: Instead of reallocating for every line use a growarray. (Yasuhiro
Matsumoto)
===

Using a geometric growth would be faster. But I also still think
that using realloc() in ga_grow() as proposed is complementary
and should also be done since realloc() can only be faster than
alloc(), memmove(), free().

Regards
-- Dominique

[Ernie Rael]

On 2/13/2012 2:36 PM, Dominique Pellé wrote:
> since realloc() can only be faster than ...
Perhaps "can not be slower than" is more accurate

-ernie

[John Little]

On Feb 14, 11:45 am, Ernie Rael <e...@raelity.com> wrote:
> On 2/13/2012 2:36 PM, Dominique Pellé wrote:> since realloc() can only be faster than ...
>
> Perhaps "can not be slower than" is more accurate

Disregarding function call overheads, I agree. I can imagine
scenarios with the heap being heavily fragmented, maybe in a very long
running vim instance, where realloc is forced to move and copy. I
agree, Dominique, that replacing arithmetic growth with geometric is
complementary and a good idea.

Regards, John

[Bram Moolenaar]

Dominique Pelle wrote:

Thanks. I'll check out the details soon.

--
"I simultaneously try to keep my head in the clouds and my feet on the
ground. Sometimes it's a stretch, though." -- Larry Wall

/// Bram Moolenaar -- Br...@Moolenaar.net -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///