Same, but with the new Telemetry module so you can see better what’s going on:
$ perl6 -MTelemetry -e 'for (1, 10, 100, 1_000, 10_000, 100_000) -> $limit { snap; my $x; my $y = "x" x 100; $x ~= $y for 1..$limit }' Telemetry Report of Process #79213 (2017-11-10T16:24:00Z) Number of Snapshots: 7 No supervisor thread has been running Initial Size: 83236 Kbytes Total Time: 37.40 seconds Total CPU Usage: 37.37 seconds wallclock util% max-rss 1084 39.13 164 124 25.20 192 355 23.35 280 6912 21.83 1940 397311 12.48 83628 36996468 12.49 3993120 --------- ------ -------- 37402254 12.49 4079324 Legend: wallclock Number of microseconds elapsed util% Percentage of CPU utilization (0..100%) max-rss Maximum resident set size (in Kbytes) So, going from 1_000 -> 10_000 -> 100_000 seems to have a quadratic effect on memory and CPU usage (as shown in wallclock, with the 1 in 8 CPU’s being fully in use all of the time). Feels like a clear case of O² to me. Liz > On 10 Nov 2017, at 16:02, Daniel Green via RT <perl6-bugs-follo...@perl.org> > wrote: > > 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