Mailing List Archive

On Tue, Jul 20, 2021 at 04:28:40PM +0000, Ovid via perl5-porters wrote:
> In case it was missed here, Aristotle posted to BPO about quadratic time
> constant folding:
> http://blogs.perl.org/users/aristotle/2021/06/stringbuilder.html.
[snip]
> ? ? (((( $str .= "foo" ).= $::bar ).= "baz" ).= $::quux ).= "qux";
[snip]
> ? ? $str .= "foo${::bar}baz${::quux}qux";

The first ('conc') form was a way of doing multiple concatenations as
efficiently as possible, allowing for the way which perl internals worked.
It would sometimes make things faster.

With the introduction of the multiconcat op in 5.28.0, the second ('intp')
form should now usually be the fastest, since the whole collection of
concatenations can be replaced with a single multiconcat op. The first
form isn't as fully optimisable.

Here are the results I got (using plain Benchmark and 1E7 iterations)
for 5.26.0:

Rate intp conc
intp 4214075/s -- -41%
conc 7178751/s 70% --


and 5.28.0:

Rate intp conc
intp 6662225/s -- -28%
conc 9216590/s 38% --

and 5.34.0:

Rate intp conc
intp 6321113/s -- -32%
conc 9319664/s 47% --

(I'm actually surprised that intp doesn't beat conc in 5.28.0 onwards.
I'll have to look into that).


But I don't get what any of this has to do with quadratic time constant
folding??


--
No man treats a motor car as foolishly as he treats another human being.
When the car will not go, he does not attribute its annoying behaviour to
sin, he does not say, You are a wicked motorcar, and I shall not give you
any more petrol until you go. He attempts to find out what is wrong and
set it right.
-- Bertrand Russell,
Has Religion Made Useful Contributions to Civilization?

On Tue, Jul 20, 2021 at 7:15 PM Dave Mitchell <davem@iabyn.com> wrote:

> On Tue, Jul 20, 2021 at 04:28:40PM +0000, Ovid via perl5-porters wrote:
> > In case it was missed here, Aristotle posted to BPO about quadratic time
> > constant folding:
> > http://blogs.perl.org/users/aristotle/2021/06/stringbuilder.html.
>



> But I don't get what any of this has to do with quadratic time constant
> folding??
>

The referenced blog entry (https://accidentallyquadratic.tumblr.com/)
speaks of quadratic space, not quadratic time – is there a mixup here?


Eirik

On Tue, Jul 20, 2021 at 7:15 PM Dave Mitchell <davem@iabyn.com> wrote:


On Tue, Jul 20, 2021 at 04:28:40PM +0000, Ovid via perl5-porters wrote:
> In case it was missed here, Aristotle posted to BPO about quadratic time
> constant folding:
> http://blogs.perl.org/users/aristotle/2021/06/stringbuilder.html.


 
But I don't get what any of this has to do with quadratic time constant
folding??


  The referenced blog entry (https://accidentallyquadratic.tumblr.com/) speaks of quadratic space, not quadratic time – is there a mixup here?


Yeah, I posted this quickly as I headed out the door. My bad.

-- IT consulting, training, specializing in Perl, databases, and agile developmenthttp://www.allaroundtheworld.fr/. 
Buy my book! - http://bit.ly/beginning_perl

On Wed, Jul 21, 2021 at 07:19:44AM +0000, Ovid via perl5-porters wrote:
> On Tue, Jul 20, 2021 at 7:15 PM Dave Mitchell <davem@iabyn.com> wrote:
> But I don't get what any of this has to do with quadratic time constant
> folding??

After some playing around with this code:

my $code = q{my $s = "abc"} . (q{."abc"} x 100000);
eval qq{sub foo { $code }; 1} or die;

(wrapping the evalled code in a sub means its compiled but not executed)
and varying the loop count, I get max mem usage which is proportional to
the number of substrings, but whose CPU usage is cubic on # substrings.

So there is something going on there. I don't think its so much of an
issue in a language like perl, which, due to things like heredocs and
<DATA>, doesn't generally force programmers to concatenate lots of const
strings.


So when I get time, I'll look further into
1) why the compile-time is cubic;
2) why at runtime, Aristotle's nested concat example is still faster than
the interpolated version.


--
I don't want to achieve immortality through my work...
I want to achieve it through not dying.
-- Woody Allen

On Wed, Jul 21, 2021 at 09:32:45AM +0100, Dave Mitchell wrote:
> On Wed, Jul 21, 2021 at 07:19:44AM +0000, Ovid via perl5-porters wrote:
> > On Tue, Jul 20, 2021 at 7:15 PM Dave Mitchell <davem@iabyn.com> wrote:
> > But I don't get what any of this has to do with quadratic time constant
> > folding??
>
> After some playing around with this code:
>
> my $code = q{my $s = "abc"} . (q{."abc"} x 100000);
> eval qq{sub foo { $code }; 1} or die;
>
> (wrapping the evalled code in a sub means its compiled but not executed)
> and varying the loop count, I get max mem usage which is proportional to
> the number of substrings, but whose CPU usage is cubic on # substrings.
>
> So there is something going on there. I don't think its so much of an
> issue in a language like perl, which, due to things like heredocs and
> <DATA>, doesn't generally force programmers to concatenate lots of const
> strings.
>
>
> So when I get time, I'll look further into
> 1) why the compile-time is cubic;
> 2) why at runtime, Aristotle's nested concat example is still faster than
> the interpolated version.

[just following up this thread from 6 months ago]

1) The compile time is cubic because the constant folding of a series
of concatenated constant strings does a series of the equivalent of:

p = malloc(left_len);
memcpy(p, left, left_len);
realloc(p, left_len + right_len);
memcopy(p + left_len, right, right_len);
free(left);
free(right);

so a whole bunch of copying, mallocing, growing and freeing.

This would be quite hard to fix, as constant folding is done in sync with
parsing, so in

"a" . "b" . "c" . "d"

the parser calls the constant folder after it has parsed "a" . "b" and
so before it has any idea whether further string constants follow. I
suspect it would be quite hard to change/fix this.

But as I said earlier, given perl's heredocs etc, it's relatively unlikely
for perl source code to include a large number of concatenated constant
strings compared with other languages.

2) the reason why the interpolated string (which gets optimised into a
multiconcat op) was still slower than than the

((($x .= 2a") .= "b") .= "c")

form (which mostly doesn't get optimised) turned out to be not really
to do with concatenation but how the package variables were written for
the benchmark.

The use of a package var like $foo in the source code is compiled as:

gv[*foo]
rv2sv

which is optimised to

gvsv[*foo]

while ${::foo}

is compiled as

const[PV "::foo"]
rv2sv

and is not subsequently optimised into an rvgv.
The benchmark used an interpolated string of the form "x${::foo}y".

Given that the ${::foo} form of usage is probably fairly unusual, I'm not
too worried about it.

Note that ${foo::bar} *is* optimised.


--
Dave's first rule of Opera:
If something needs saying, say it: don't warble it.