Dominique Pelle wrote:
> John Little wrote:
>
> > Hi all
> >
> > I'm revising the function f_readfile in eval.c, to speed it up when
> > processing very long lines. (It presently grows a string every 200
> > bytes by allocating a new one 200 bytes longer, copying the old to the
> > new, and deallocating the new. =A0F.ex., for a 1 MB line, such as may be
> > used by the yank ring plug in, there's 5000 allocations and
> > deallocations and about 5 GB of data copies.)
>
> Hi John
>
> We can speed this up by using vim_realloc() instead of allocating
> a new block and freeing the old one. vim_realloc() can in general
> increase the size of the allocated block without having to copy,
> hence the speed up.
>
> See attached patch.
>
> The speed up is huge on my laptop (5 year old laptop):
>
> # Create a sample file with a 2 Mb single line.
> $ perl -e "print 'x' x 2000000" > file.txt
>
> # Measure how long it takes to read the line _before_ patch (slow)
> $ time vim -u NONE -c ":call readfile('file.txt')|q"
> real 0m13.724s
> user 0m4.748s
> sys 0m8.829s
>
> # Measure again how long it takes _after_ applying attached patch (fast)
> $ time vim -u NONE -c ":call readfile('file.txt')|q"
> real 0m0.068s
> user 0m0.060s
> sys 0m0.000s
>
> Much faster after patch!
>
> The original algorithm had O(n^2) complexity.
> After patch it becomes O(n) I think, though in theory
> the worse case is still O(n^2) since each realloc could
> very well have to copy all the time, but that's unlikely
> in practice and measuring shows that it's faster.
Sounds good. I'll add this in the todo list.
--
BLACK KNIGHT: I'm invincible!
ARTHUR: You're a looney.
"Monty Python and the Holy Grail" PYTHON (MONTY) PICTURES LTD
/// Bram Moolenaar -- [email protected] -- 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 ///
--
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
