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. F.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.
-- 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
diff -r 0dabc2ce136c src/eval.c
--- a/src/eval.c Tue Jan 10 22:31:32 2012 +0100
+++ b/src/eval.c Fri Jan 20 20:58:42 2012 +0100
@@ -14389,11 +14389,9 @@
s = vim_strnsave(buf + tolist, len);
else
{
- s = alloc((unsigned)(prevlen + len + 1));
+ s = vim_realloc(prev, prevlen + len + 1);
if (s != NULL)
{
- mch_memmove(s, prev, prevlen);
- vim_free(prev);
prev = NULL;
mch_memmove(s + prevlen, buf + tolist, len);
s[prevlen + len] = NUL;
@@ -14449,12 +14447,10 @@
}
else
{
- s = alloc((unsigned)(prevlen + buflen));
+ s = vim_realloc(prev, prevlen + buflen);
if (s != NULL)
{
- mch_memmove(s, prev, prevlen);
mch_memmove(s + prevlen, buf, buflen);
- vim_free(prev);
prev = s;
prevlen += buflen;
}
