Dominique Pellé wrote:
> 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.
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 <[email protected]>
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
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
