Skip to content
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

Closed
p6rt opened this issue Jul 20, 2017 · 11 comments
Closed

Simple, if artificial, string concatenation example hogs memory and time #6401

p6rt opened this issue Jul 20, 2017 · 11 comments
Labels

Comments

@p6rt
Copy link

p6rt commented Jul 20, 2017

Migrated from rt.perl.org#131774 (status was 'resolved')

Searchable as RT131774$

@p6rt
Copy link
Author

p6rt commented Jul 20, 2017

From @ronaldxs

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.

@p6rt
Copy link
Author

p6rt commented Jul 21, 2017

From @LLFourn

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

(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​:

# 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-archive.perl.org/perl6/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.

@p6rt
Copy link
Author

p6rt commented Jul 21, 2017

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented Jul 30, 2017

From @ronaldxs

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.

@p6rt
Copy link
Author

p6rt commented Jul 30, 2017

From @ronaldxs

strcat.java

@p6rt
Copy link
Author

p6rt commented Jul 30, 2017

From @ronaldxs

strcat.js

@p6rt
Copy link
Author

p6rt commented Nov 10, 2017

From @MasterDuke17

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

@p6rt
Copy link
Author

p6rt commented Nov 10, 2017

From @lizmat

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-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

@p6rt
Copy link
Author

p6rt commented Nov 14, 2017

From @MasterDuke17

This 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 }'
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

1 similar comment
@p6rt
Copy link
Author

p6rt commented Nov 14, 2017

From @MasterDuke17

This 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 }'
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

@p6rt
Copy link
Author

p6rt commented Nov 14, 2017

@MasterDuke17 - Status changed from 'open' to 'resolved'

@p6rt p6rt closed this as completed Nov 14, 2017
@p6rt p6rt added the perf label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant