Skip Menu |
Report information
Id: 131774
Status: open
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.



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