On Sun, 30 Jul 2017 09:49:39 -0700, ronaldxs wrote:
> On Thu, 20 Jul 2017 20:32:12 -0700, lloyd.fo...@gmail.com wrote:
> > I did an experiment a while ago and found that string concatenation
> > in a
> > loop was Ο(n²) in rakudo. I asked about it on irc and jnthn explained
> > to me
> > that this was expected because strings are immutable (and therefore
> > wasn't
> > worth RTing):
> > https://irclog.perlgeek.de/perl6/2015-12-15#i_11720228
> >
>
> If the string is represented by an array and is immutable then each
> append allocates a new array, copies in the existing prefix string and
> copies the new appended string at the end, which is the sum of an
> arithmetic sequence and so O(n ** 2). Other languages have immutable
> strings including Java, JavaScript and Python, and each has found ways
> around the problem. Perl 6 Str objects perform somewhat faster than
> Java String objects (on my system – Java 8?) but Java has mutable
> StringBuffer and StringBuilder classes. Python v2.7 cheats by making
> strings mutable for the case where a string has a reference count of 1
> (http://blog.mclemon.io/python-efficient-string-concatenation-in-
> python-2016-edition and see the comment in source stringobject.c for
> _PyString_Resize). For JavaScript FireFox/SpiderMonkey ropes seem to
> solve the problem (https://stackoverflow.com/questions/7299010/why-is-
> string-concatenation-faster-than-array-join) which is also solved in
> other ways by V8 (Node JS) etc. As noted on IRC the Perl 6 native
> “str” also has an optimization for this case
> (https://irclog.perlgeek.de/perl6-dev/2017-07-27#i_14930258 – sorry
> about any confusion on ropes and V8).
>
> The memory situation has improved since the ticket was open but at
> 150_000 iterations or 15 million characters there is still a MoarVM
> memory panic with ulimit of 4Gb.
The numbers seem a little better now (though still non-linear):
$ /usr/bin/time perl6 -e 'for (1, 10, 100, 1_000, 10_000, 100_000) -> $limit
{my $x; my $y = "x" x 100; $x ~= $y for (1..$limit); say "$limit: ", now -
ENTER now}'
1: 0.0045150
10: 0.0004916
100: 0.00096704
1000: 0.0077635
10000: 0.4149077
100000: 40.1284791
37.36user 3.66system 0:41.02elapsed 100%CPU (0avgtext+0avgdata
3776812maxresident)k
$ perl6 --version
This is Rakudo version 2017.10-146-gf8e1a5faa built on MoarVM version
2017.10-64-g2ca7e8587
