New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Simple, if artificial, string concatenation example hogs memory and time #6401
Comments
From @ronaldxsFrom 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 Gets a MoarVM memory panic from the eval bot for 75_000 constructing a |
From @LLFournI did an experiment a while ago and found that string concatenation in a (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>
|
The RT System itself - Status changed from 'new' to 'open' |
From @ronaldxsOn Thu, 20 Jul 2017 20:32:12 -0700, lloyd.fourn@gmail.com wrote:
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. |
From @ronaldxs |
From @MasterDuke17On Sun, 30 Jul 2017 09:49:39 -0700, ronaldxs wrote:
The numbers seem a little better now (though still non-linear): $ perl6 --version |
From @lizmatSame, 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) wallclock util% max-rss Legend: 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
|
From @MasterDuke17This was essentially fixed in MoarVM/MoarVM#750, brought into Rakudo in rakudo/rakudo@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 }' wallclock util% max-rss Legend: $ perl6 --version |
1 similar comment
From @MasterDuke17This was essentially fixed in MoarVM/MoarVM#750, brought into Rakudo in rakudo/rakudo@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 }' wallclock util% max-rss Legend: $ perl6 --version |
@MasterDuke17 - Status changed from 'open' to 'resolved' |
Migrated from rt.perl.org#131774 (status was 'resolved')
Searchable as RT131774$
The text was updated successfully, but these errors were encountered: