On 10/12/08 23:29, H. Sasse wrote:
> 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 might get problems if there isn't enough free space on the stack to
allocate all lines to be joined. (On 32-bit machines, Vim is supposed to
be able to handle files or even lines of 2GB each.)
Maybe compute first the total size of the joined lines, then allocate
one block that size, and copy the joined lines one after another into
it? Wouldn't that be O(N)?
Best regards,
Tony.
--
The first duty of a revolutionary is to get away with it.
-- Abbie Hoffman
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_dev" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
