Matias Larre Borges wrote: > On Wed, Dec 10, 2008 at 11:29 PM, H. Sasse <[EMAIL PROTECTED]> wrote: >> Lua faces a similar problem exacerbated by garbage collection and >> immutable strings. The solution >> >> http://www.lua.org/pil/11.6.html >> > > If I understood well, this approach is efficient in Lua because it > avoids taking the worst of their garbage collecting algorithm.
But that is because it avoids repeated copying. (The repeated copying implies the creation of new immutable strings. If Vim creates space then copies then that aspect is very similar. The garbage collection is not.) That repeated copying applies here, which is why I brought it up in the first place. I think it's rather elegant. Tony's argument does make me wonder why Lua needs it but I think that must be due do dynamic data that can't be pre-allocated. Otherwise I don't know why they don't use his algorithm. > But (and correct me if I'm wrong) it doesn't avoid the problem that > for each concatenation the contents of the strings are copied into a > new one. Yes, it does. By keeping them on a stack, only the top elements get copied until they are bigger than the one below, to which they get joined. So if your lines are 1000, 500, 100, chars long, and the next is 200 chars long, that will be joined to the 100 -> 300, which is still smaller than 500, so that line doesn't get copied yet. Add another 250 char line, 250 + 300 = 550, which is bigger than 500, so that gets added on the front 500 + 550, giving a stack of: 1000 char line, then a 1050 char line. So 1050 > 1000 so those get joined to give the 2050 char line. Currently you'd have 1000 + 500 giving one copy, then 1500 + 100 giving another large copy, then 1600 + 200 giving another large copy, then 1800 + 250, giving the 2050. Doing the small ones first is more efficient. > > As mentioned above, the use of realloc could speed up a little the > process. But it would still be the same in the worst case scenarios. I > will take a look as how memory is handled for each line. This problem > is very interesting :) > --~--~---------~--~----~------------~-------~--~----~ You received this message from the "vim_dev" maillist. For more information, visit http://www.vim.org/maillist.php -~----------~----~----~----~------~----~------~--~---
