Tony Mechelynck wrote:
> On 11/12/08 00:14, H. Sasse wrote:
>> Tony Mechelynck wrote:
>>> On 10/12/08 23:29, H. Sasse wrote:
>>>> 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
>> It's not *the* C stack, it's a stack, which may not alter your point...
>>
>>> 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.)
>> So they must be held somewhere. Lua just makes that data structure some
>> kind of stack
>>
>> "aaa" + "bb" + "CCC" (well, it's .. for concatenation in Lua, but...)
>> Writing the stack as in Forth, top on the right:
>> "aaa"
>> "aaa" becomes "aaa" "bb"
>> "aaa" "bb" becomes "aaa" "bb" "CCC" -- top heavy, becomes "aaa"
>> "bbCCC" -- still top heavy becomes "aaabbCCC"
>>
>>> 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
>> Your point about storing that>2GB block still stands?
>
> The idea is that you know the block size before you allocate it. The
Yes, agreed.
> calling stack is an open-end structure but its size is finite and I'm
The calling stack is irrelevant :-). The lua algorithm uses a data
structure which is a stack. It doesn't use the calling stack for the
data. Neither would this were it implemented in Vim. And any stack it
used (were it to be in vim) could point at the lines to be joined. But
I concede that it is probably overkill for this purpose.
> not sure of what would happen if (when) a stack overflow happens -- and
> when joining lots of lines, sooner of later it will happen.
>
>>> it? Wouldn't that be O(N)?
>> If the line joining code will always be using data that doesn't change,
>> which I think Lua can't depend on, then that would be simpler. I can't
>> see why J would have to deal with unexpected line lengths.
>
> I believe that Vim can depend on the fact that the data of the lines to
> be joined won't change between the begin and the end of the join
> operation. Of course, it will change after the join is finished. I don't
Yes, I was thinking out loud as to why Lua needs this algorithm rather
than yours. The only case I can think of is the collection of strings
to join being dynamic, so it can't just pre-allocate as you suggest.
> know how Vim handles insertion of data into a line (so that its length
> increases) but I'm sure Bram has foreseen something to avoid memory
> overruns.
Absolutely. Vim's been very stable for me.
>
>>> Best regards,
>>> Tony.
>> Hugh
>
> Best regards,
> Tony.
Thank you,
Hugh
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_dev" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
