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 calling stack is an open-end structure but its size is finite and I'm 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 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. >> >> Best regards, >> Tony. > > Hugh Best regards, Tony. -- FIRST GUARD: Ah! Now ... we're not allowed to ... SIR LAUNCELOT runs him through, grabs his spear and stabs the other guard who collapses in a heap. Hiccoughs quietly. "Monty Python and the Holy Grail" PYTHON (MONTY) PICTURES LTD --~--~---------~--~----~------------~-------~--~----~ You received this message from the "vim_dev" maillist. For more information, visit http://www.vim.org/maillist.php -~----------~----~----~----~------~----~------~--~---