On Mon, 15 Nov 2004 18:46:15 -0500 (EST), Dan Sugalski <[EMAIL PROTECTED]> wrote: > On Mon, 15 Nov 2004, Ben Tilly wrote: > > > On Mon, 15 Nov 2004 15:58:11 -0500, Aaron Sherman > > <[EMAIL PROTECTED]> wrote: > > > On Sat, 13 Nov 2004 11:40:25 -0800, Ben Tilly <[EMAIL PROTECTED]> wrote: > > > > On Fri, 12 Nov 2004 23:04:46 -0500, Aaron Sherman <[EMAIL PROTECTED]> > > > > wrote: > > > > > On Fri, 2004-11-12 at 13:22 -0800, Ben Tilly wrote: > [Massive snippage of two ships passing in the night]
Heh. :-) > > > > In Perl I'd expect it to be possible but fragile. If Parrot could make > > > > it possible and not fragile, that would be great. > > > > > > In parrot it's quite robust. Parrot supports "buffers" as core PMC > > > types. A buffer can refer to any part of memory with any read-only or > > > copy-on-write semantics you like. > > > > That would be nice. > > > > Incidentally will Parrot also support efficiently building strings > > incrementally? I like the fact that in Perl 5 it is O($n) to do > > something like: > > > > $string .= "hello" for 1..$n; > > > > In most other languages that is quadratic, and I'm wondering > > what to expect in Perl 6. > > That's not O(n) in Perl 5, it's just smaller than O(n^2). The same's true > for Parrot -- we've got mutable strings and generally over-allocate, so > it's not going to be quadratic time. Neither, though, is it going to be > linear. Expect somewhere in between. I don't have source-code in front of me, but my memory says that when you have to reassign a string in Perl 5, the amount of extra length that you give is proportional to the length of the string. (If that is not how Perl does it, then Perl darned well should!) In that case it really is O(n). What happens is that the total recopying work can be bounded above by a geometric series that converges to something O(n). Everything else is O(n). So the result is O(n). I gave you more details at http://www.perlmonks.org/?node_id=276051. (Hey, my math background has to be good for something...) Perl uses the same strategy for other data structures, including growing a hash and on various array operations. Of course the main reason that I'm familiar with this trick is that my 2 miniscule core contributions to Perl were performance enhancements from using this trick in places where it had not been previously used. (i.e. unshift and map.) Unlike you, I don't have any other performance knowledge to confuse me... Cheers, Ben _______________________________________________ Boston-pm mailing list [EMAIL PROTECTED] http://mail.pm.org/mailman/listinfo/boston-pm
