Dominique Pelle wrote:
> Bram Moolenaar wrote:
>>
>> Lee Naish wrote:
>>
>>> The "J" command seems to have a complexity bug when given a large numeric
>>> argument, eg 100000J
>>>
[...]
>> This is a known problem. It works like doing J 100000 times. So near
>> the end you are appending a short line to a very long line, copying
>> everything into newly allocated memory.
>>
>> Allocating all the memory at once is a bit complicated. Perhaps an easy
>> solution would be to join two lines at a time.
>
>
> I see at least 2 things that explain the O(n^2) complexity when
> joining many lines:
>
> 1/ STRLEN() is called every time on the current line. As the current
> line grows, STRLEN(..) becomes slow and has O(n^2) complexity
> when joining n lines.
>
> 2/ For each join, a new line gets allocated, and the current line + next
> line get copied into the new one. As the current line size increases,
> copying has complexity O(n^2).
>
> I have a patch which fixes at least 1/ (but not 2/). The speeds up
> is quite noticeable, but complexity is still O(n^2) since I only
> addressed 1 of the 2 issues.
I don't do enough in C these days so this first point could be rubbish,
but would it make sense to just realloc rather than allocate and copy
every time? I've not looked at the source recently to check.
The point I really wanted to make was:
Lua faces a similar problem exacerbated by garbage collection and
immutable strings. The solution
http://www.lua.org/pil/11.6.html
is to build up the string on a stack so that the top of the stack gets
joined to the element below it, when it is just bigger than it, so the
stack looks like disks in a tower of Hanoi. They claim a large speedup
for this technique.
HTH
Hugh
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_dev" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
