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?
> 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.
>
>
> Best regards,
> Tony.
Hugh
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_dev" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
