Skip Menu |
Report information
Id: 131774
Status: resolved
Priority: 0/
Queue: perl6

Owner: Nobody
Requestors: ronaldxs <ronaldxs [at] software-path.com>
Cc:
AdminCc:

Severity: (no value)
Tag: (no value)
Platform: (no value)
Patch Status: (no value)
VM: (no value)



Date: Thu, 20 Jul 2017 22:21:59 +0200
From: Ronald Schmidt <ronaldxs [...] software-path.com>
Subject: [PERF] Simple, if artificial, string concatenation example hogs memory and time
To: rakudobug [...] perl.org
Download (untitled) / with headers
text/plain 693b

From IRC:

https://irclog.perlgeek.de/perl6-dev/2017-07-19#i_14893012

https://irclog.perlgeek.de/perl6/2017-07-20#i_14899215

Code example:

for (50_000, 75_000) -> $limit {my $x; my $y = "x" x 100; $x ~= $y for (1..$limit); say "$limit: ", now - ENTER now}

Gets a MoarVM memory panic from the eval bot for 75_000 constructing a 7.5 Meg string.  According to valgrind 50_000 was allocating 10GB of memory.  At a concat count of 150_000 Perl 5 finishes in hundredths of a second where p6 takes around a minute and the growth in time with p6 is clearly worse than linear.  "blead" updates as of July 20 include some improvements and timotimo on IRC mentioned that he is working on others.

Subject: Re: [perl #131774] [PERF] Simple, if artificial, string concatenation example hogs memory and time
To: perl6-compiler [...] perl.org, bugs-bitbucket [...] rt.perl.org
Date: Fri, 21 Jul 2017 03:31:55 +0000
From: Lloyd Fournier <lloyd.fourn [...] gmail.com>
Download (untitled) / with headers
text/plain 1.3k
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):

(some encoding issue causes  Ο(n²) to have a bunch of Ãs in it)

On Fri, Jul 21, 2017 at 6:39 AM Ron Schmidt <perl6-bugs-followup@perl.org> wrote:
Show quoted text
# New Ticket Created by  Ron Schmidt
# Please include the string:  [perl #131774]
# in the subject line of all future correspondence about this issue.
# <URL: https://rt.perl.org/Ticket/Display.html?id=131774 >


From IRC:

https://irclog.perlgeek.de/perl6-dev/2017-07-19#i_14893012

https://irclog.perlgeek.de/perl6/2017-07-20#i_14899215

Code example:

for (50_000, 75_000) -> $limit {my $x; my $y = "x" x 100; $x ~= $y for
(1..$limit); say "$limit: ", now - ENTER now}

Gets a MoarVM memory panic from the eval bot for 75_000 constructing a
7.5 Meg string.  According to valgrind 50_000 was allocating 10GB of
memory.  At a concat count of 150_000 Perl 5 finishes in hundredths of a
second where p6 takes around a minute and the growth in time with p6 is
clearly worse than linear.  "blead" updates as of July 20 include some
improvements and timotimo on IRC mentioned that he is working on others.
Download (untitled) / with headers
text/plain 1.6k
On Thu, 20 Jul 2017 20:32:12 -0700, lloyd.fourn@gmail.com wrote: Show quoted text
> 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.
Subject: strcat.java
Download strcat.java
application/octet-stream 953b

Message body not shown because it is not plain text.

Subject: strcat.js
Download strcat.js
application/x-javascript 371b

Message body not shown because it is not plain text.

RT-Send-CC: lloyd.fourn [...] gmail.com
Download (untitled) / with headers
text/plain 2.3k
On Sun, 30 Jul 2017 09:49:39 -0700, ronaldxs wrote: Show quoted text
> On Thu, 20 Jul 2017 20:32:12 -0700, lloyd.fourn@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
Date: Fri, 10 Nov 2017 17:34:00 +0100
Subject: Re: [perl #131774] [PERF] Simple, if artificial, string concatenation example hogs memory and time
To: perl6-bugs-followup [...] perl.org
From: Elizabeth Mattijsen <liz [...] dijkmat.nl>
Download (untitled) / with headers
text/plain 3.4k
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 Show quoted text
> On 10 Nov 2017, at 16:02, Daniel Green via RT <perl6-bugs-followup@perl.org> wrote: > > On Sun, 30 Jul 2017 09:49:39 -0700, ronaldxs wrote:
>> On Thu, 20 Jul 2017 20:32:12 -0700, lloyd.fourn@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
RT-Send-CC: lloyd.fourn [...] gmail.com, liz [...] dijkmat.nl
Download (untitled) / with headers
text/plain 974b
This was essentially fixed in https://github.com/MoarVM/MoarVM/pull/750, brought into Rakudo in https://github.com/rakudo/rakudo/commit/b2fbf893db. $ 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 #30107 (2017-11-14T02:56:50Z) Number of Snapshots: 7 Initial/Final Size: 93152 / 95532 Kbytes Total Time: 0.13 seconds Total CPU Usage: 0.13 seconds No supervisor thread has been running wallclock util% max-rss 1217 12.53 154 12.50 411 12.50 3246 29.50 4 17745 13.92 2376 102497 12.50 --------- ------ -------- 125270 13.14 2380 Legend: wallclock Number of microseconds elapsed util% Percentage of CPU utilization (0..100%) max-rss Maximum resident set size (in Kbytes) $ perl6 --version This is Rakudo version 2017.10-185-g88d675166 built on MoarVM version 2017.10-70-gb37905067


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org