# Use "ropes" for string concatenation

- Thread: https://externals.io/message/85428
- Original archive: https://news-web.php.net/php.internals/85428
- Started by Dmitry Stogov on 2015-03-23T22:41:08+00:00
- Messages: 19
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #85428 — Dmitry Stogov — 2015-03-23T22:41:08+00:00

URL: https://externals.io/message/85428#85428

Hi,

Recently, Xinchen and me worked on optimization that eliminates useless
reallocations and copying during string concatenation (ZEND_ADD_STRING and
family + ZEND_CONCAT).

The idea comes from ropes, but adopted especially for our needs.
Rope is popular data structure in languages with immutable strings.
http://en.wikipedia.org/wiki/Rope_%28data_structure%29

We don't try to use ropes everywhere in the engine (at least it's too later
for 7.0), only for concatenation.

The first branch uses ropes only instead of ZEND_ADD_STRING and family.
This must be safe. The only problem is possible memory leaks on exception
(but we already have this problem anyway). The simplest way to understand
the patch - read code for new opcodes in zend_vm_def.h.

https://github.com/php/php-src/pull/1194/files

The second branch in addition uses ropes for series of ZEND_CONCAT. It
disables calls to do_operation(ZEND_CONCAT) handler of custom internal
classes.

https://github.com/php/php-src/pull/1195/files

Both make slight speed improvement (first +0.3%, second +0.6% on wordpress
home page).

We don't currently use ability to override CONCAT behavior in internal
classes, and I'm not sure if it may be useful at all. (For example Lua
doesn't provide concat meta-method). May be remove it?

Thoughts and comments are welcome.

Thanks. Dmitry.

---

## #85430 — Pierre Joye — 2015-03-24T05:31:53+00:00

URL: https://externals.io/message/85428#85430 · In reply to: #85428

hi!


> Hi,
>
> Recently, Xinchen and me worked on optimization that eliminates useless
> reallocations and copying during string concatenation (ZEND_ADD_STRING and
> family + ZEND_CONCAT).
>
> The idea comes from ropes, but adopted especially for our needs.
> Rope is popular data structure in languages with immutable strings.
> http://en.wikipedia.org/wiki/Rope_%28data_structure%29
>
> We don't try to use ropes everywhere in the engine (at least it's too later
> for 7.0), only for concatenation.
>
> The first branch uses ropes only instead of ZEND_ADD_STRING and family.
> This must be safe. The only problem is possible memory leaks on exception
> (but we already have this problem anyway). The simplest way to understand
> the patch - read code for new opcodes in zend_vm_def.h.
>
> https://github.com/php/php-src/pull/1194/files
>
> The second branch in addition uses ropes for series of ZEND_CONCAT. It
> disables calls to do_operation(ZEND_CONCAT) handler of custom internal
> classes.
>
> https://github.com/php/php-src/pull/1195/files
>
> Both make slight speed improvement (first +0.3%, second +0.6% on wordpress
> home page).
>
> We don't currently use ability to override CONCAT behavior in internal
> classes, and I'm not sure if it may be useful at all. (For example Lua
> doesn't provide concat meta-method). May be remove it?
>
> Thoughts and comments are welcome.

Great work! :)

Do you expect similar gain for other ops?

I wonder if it would not be better to target 7.1 for that,  adding it
for other string operations, in one go. Most of the current patch is
self contained, it adds quite some complexity to the engine for these
operations only and it is not a small change at this stage (post
features freeze). It sounds like a possible maintenance pain. Taking
more time to actually experiment and implement this idea sounds safer
to me (read: we have a bit less than a year to valid it then).

Cheers,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #85431 — Xinchen Hui — 2015-03-24T05:35:00+00:00

URL: https://externals.io/message/85428#85431 · In reply to: #85430

Hey:


> hi!
>
> 
> > […]
>
> Great work! :)
>
> Do you expect similar gain for other ops?
>
> I wonder if it would not be better to target 7.1 for that,  adding it
> for other string operations, in one go. Most of the current patch is
> self contained, it adds quite some complexity to the engine for these
> operations only and it is not a small change at this stage (post
> features freeze). It sounds like a possible maintenance pain. Taking
Actually, it's not.

previously we have ADD_STRING/CHAR/VAR and CONCAT

the 2nd branch cleanup these, and now we only deal with one type concat_list. :)

thanks

> more time to actually experiment and implement this idea sounds safer
> to me (read: we have a bit less than a year to valid it then).
>
> Cheers,
> --
> Pierre
>
> @pierrejoye | http://www.libgd.org



-- 
Xinchen Hui
@Laruence
http://www.laruence.com/

---

## #85432 — Pierre Joye — 2015-03-24T05:54:12+00:00

URL: https://externals.io/message/85428#85432 · In reply to: #85431

> Hey:
>
> 
> > […]
> Actually, it's not.
>
> previously we have ADD_STRING/CHAR/VAR and CONCAT
>
> the 2nd branch cleanup these, and now we only deal with one type concat_list. :)

Right, it simplifies part of the existing implementation and add some
complexities to other. It only adds this OP and keep other with the
"old" implementation, that's actually the only part where I am not
totally convinced. It may make sense to do it all at once, if that's
the long term plan, easier to maintain.

But if we do prefer to add this now, then the sooner the better, it
may have some hard to catch bugs. Now, we have one issue, we cannot
have a RFC (deadline behind us) and this is still a rather big change
:/

Cheers,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #85433 — Xinchen Hui — 2015-03-24T06:01:05+00:00

URL: https://externals.io/message/85428#85433 · In reply to: #85432

Hey:


> 
> > […]
>
> Right, it simplifies part of the existing implementation and add some
> complexities to other. It only adds this OP and keep other with the
> "old" implementation, that's actually the only part where I am not
> totally convinced. It may make sense to do it all at once, if that's
> the long term plan, easier to maintain.
>
> But if we do prefer to add this now, then the sooner the better, it
> may have some hard to catch bugs. Now, we have one issue, we cannot
> have a RFC (deadline behind us) and this is still a rather big change
> :/
from user land.  this won't change anything..

and regarding to the object overriden concat.....

I doubt it is not used at all :)

thanks
>
> Cheers,
> --
> Pierre
>
> @pierrejoye | http://www.libgd.org



-- 
Xinchen Hui
@Laruence
http://www.laruence.com/

---

## #85434 — Pierre Joye — 2015-03-24T06:04:41+00:00

URL: https://externals.io/message/85428#85434 · In reply to: #85433

> Hey:
>
> 
> > […]
> from user land.  this won't change anything..

Nothing to do with userland or not but code stabilization

> and regarding to the object overriden concat.....
>
> I doubt it is not used at all :)

-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #85435 — Xinchen Hui — 2015-03-24T06:14:29+00:00

URL: https://externals.io/message/85428#85435 · In reply to: #85434

Hey:


> 
> > […]
>
> Nothing to do with userland or not but code stabilization
In that case, yeah. you might be right.

but from my opinion, simpler always means easier for maintaining....

anyway, I hope this could be merged to 7.0(the second branch) :)

thanks
>
> > […]
>
> --
> Pierre
>
> @pierrejoye | http://www.libgd.org



-- 
Xinchen Hui
@Laruence
http://www.laruence.com/

---

## #85436 — Rasmus Lerdorf — 2015-03-24T07:13:45+00:00

URL: https://externals.io/message/85428#85436 · In reply to: #85435

> > […]
> In that case, yeah. you might be right.
> 
> but from my opinion, simpler always means easier for maintaining....
> 
> anyway, I hope this could be merged to 7.0(the second branch) :)

If you and Dmitry are comfortable with it for 7.0, go for it. This is
entirely internal and in your domain and it isn't something we could
have a sensible RFC about since there is no question it is a good
change. The only question is about implementation stability and frankly
we only have a handful of people able to make an intelligent call on
code at this level. If one of those people were to raise a flag, and so
far they haven't, then we might pause, otherwise full steam ahead.

-Rasmus

---

## #85437 — Pierre Joye — 2015-03-24T07:50:10+00:00

URL: https://externals.io/message/85428#85437 · In reply to: #85435

> Hey:
>
> 
> > […]
> In that case, yeah. you might be right.
>
> but from my opinion, simpler always means easier for maintaining....
>
> anyway, I hope this could be merged to 7.0(the second branch) :)

Me too :)

However I do not want to have double standards. We want a strict time
stable to ensure the delivery of 7 final in time. Other RFCs are less
intrusive (read, more self contained) and have been rejected. It is
not very correct in my opinion. I do not mind much in this case as we
can see this patch as part as the white card we gave when we accepted
phpng, but I like to hear other voices as well.

Cheers,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #85438 — Nikita Popov — 2015-03-24T09:11:18+00:00

URL: https://externals.io/message/85428#85438 · In reply to: #85428

> Hi,
>
> Recently, Xinchen and me worked on optimization that eliminates useless
> reallocations and copying during string concatenation (ZEND_ADD_STRING and
> family + ZEND_CONCAT).
>
> The idea comes from ropes, but adopted especially for our needs.
> Rope is popular data structure in languages with immutable strings.
> http://en.wikipedia.org/wiki/Rope_%28data_structure%29
>
> We don't try to use ropes everywhere in the engine (at least it's too
> later for 7.0), only for concatenation.
>
> The first branch uses ropes only instead of ZEND_ADD_STRING and family.
> This must be safe. The only problem is possible memory leaks on exception
> (but we already have this problem anyway). The simplest way to understand
> the patch - read code for new opcodes in zend_vm_def.h.
>
> https://github.com/php/php-src/pull/1194/files
>
> The second branch in addition uses ropes for series of ZEND_CONCAT. It
> disables calls to do_operation(ZEND_CONCAT) handler of custom internal
> classes.
>
> https://github.com/php/php-src/pull/1195/files
>
> Both make slight speed improvement (first +0.3%, second +0.6% on wordpress
> home page).
>
> We don't currently use ability to override CONCAT behavior in internal
> classes, and I'm not sure if it may be useful at all. (For example Lua
> doesn't provide concat meta-method). May be remove it?
>

Overloading concat operator will be useful in the future for the
implementation of the UString class, for example.

Nikita

---

## #85439 — Dmitry Stogov — 2015-03-24T09:28:25+00:00

URL: https://externals.io/message/85428#85439 · In reply to: #85438

I thought about something like this :)
In my opinion UString is really not a proper way to implement Unicoide, but
I agree not break anything in current stage.
Anyway, please review the first PR (in my opinion it is safe to commit),
but you may find some other issues.

Thanks. Dmitry.





> 
>
> > […]
>
> Overloading concat operator will be useful in the future for the
> implementation of the UString class, for example.
>
> Nikita

---

## #85440 — Pierre Joye — 2015-03-24T09:28:33+00:00

URL: https://externals.io/message/85428#85440 · In reply to: #85438

>
> 
>
> > […]
and
> > […]
exception
> > […]
understand
> > […]
wordpress
> > […]
>
> Overloading concat operator will be useful in the future for the
> implementation of the UString class, for example.

Indeed :)

Which will be 7.1, at best, no matter which one. Hence a bit my thoughts
about waiting a bit and spend more time on that, if other ops make sense
too.

But again, if everyone agrees, no issue to get that part in already.

---

## #85441 — Xinchen Hui — 2015-03-24T09:28:48+00:00

URL: https://externals.io/message/85428#85441 · In reply to: #85438

Hey

Sent from my iPhone

> 
> 
> > […]
> 
> Overloading concat operator will be useful in the future for the implementation of the UString class, for example.
> 
then we can implement is in rope_end handler, and don't convert op to string in rope add var handler.

Thanks
> Nikita

---

## #85442 — Xinchen Hui — 2015-03-24T10:30:08+00:00

URL: https://externals.io/message/85428#85442 · In reply to: #85441

Hey:


> Hey
>
> Sent from my iPhone
>
> 
>
> 
> > […]
>
>
> Overloading concat operator will be useful in the future for the
> implementation of the UString class, for example.
>
> then we can implement is in rope_end handler, and don't convert op to string
> in rope add var handler.
Never mind, lets stict to the first banch instead.

thanks for reviewing,  :)

thanks
>
> Thanks
>
> Nikita



-- 
Xinchen Hui
@Laruence
http://www.laruence.com/

---

## #85444 — Nikita Popov — 2015-03-24T11:51:30+00:00

URL: https://externals.io/message/85428#85444 · In reply to: #85439

> I thought about something like this :)
> In my opinion UString is really not a proper way to implement Unicoide,
> but I agree not break anything in current stage.
> Anyway, please review the first PR (in my opinion it is safe to commit),
> but you may find some other issues.
>
> Thanks. Dmitry.
>

First PR looks okay to me. One question: Why the separate INIT and ADD
opcodes? They seem pretty much the same, just one using a hardcoded 0
instead of ex_val.

Regarding exception-safety - is the problem that doing an EG(exception)
check and releasing the rope is too expensive?

Nikita

---

## #85445 — Xinchen Hui — 2015-03-24T11:58:22+00:00

URL: https://externals.io/message/85428#85445 · In reply to: #85444

Hey:


> 
> > […]
>
>
> First PR looks okay to me. One question: Why the separate INIT and ADD
> opcodes? They seem pretty much the same, just one using a hardcoded 0
> instead of ex_val.
>
> Regarding exception-safety - is the problem that doing an EG(exception)
> check and releasing the rope is too expensive?
that won't work if :

<?php
function a() {
    throw  new exception($a);
    return "xxx";
}


try {
   $a = "a ${a()} ";
} catch (Exception $a) {

}


thanks
thanks
>
> Nikita



-- 
Xinchen Hui
@Laruence
http://www.laruence.com/

---

## #85446 — Dmitry Stogov — 2015-03-24T12:08:12+00:00

URL: https://externals.io/message/85428#85446 · In reply to: #85444

> 
>
> > […]
>
> First PR looks okay to me. One question: Why the separate INIT and ADD
> opcodes? They seem pretty much the same, just one using a hardcoded 0
> instead of ex_val.
>

Oh. It's historical, at first we allocated rope on heap. I'll check if
INIT_ROPE is still necessary.
Most probably we still need it, to know the size of rope vector.


> Regarding exception-safety - is the problem that doing an EG(exception)
> check and releasing the rope is too expensive?
>

No. It's a common problem. Because exception may be thrown in some other
opcode and we don't clean IS_VAR/IS_TMP_VAR zvals.
For example the following script leaks independently from the patch

<?php
function foo() {
  throw new Exception();
}
try {
        $a = "a";
        $a = $a . $a . $a . foo() . $a . "\n";
} catch (Exception $e) {
}
?>

Thanks. Dmitry.


>
> Nikita

---

## #85453 — Nikita Popov — 2015-03-24T19:45:14+00:00

URL: https://externals.io/message/85428#85453 · In reply to: #85446

>
>
> On Tue, Mar 24, 2015 at 2:51 PM, Nikita Popov <nikita.ppv@gmail.com>
> wrote:
>
> > […]
>
> Oh. It's historical, at first we allocated rope on heap. I'll check if
> INIT_ROPE is still necessary.
> Most probably we still need it, to know the size of rope vector.
>
>
> > […]
>
> No. It's a common problem. Because exception may be thrown in some other
> opcode and we don't clean IS_VAR/IS_TMP_VAR zvals.
> For example the following script leaks independently from the patch
>
> <?php
> function foo() {
>   throw new Exception();
> }
> try {
>         $a = "a";
>         $a = $a . $a . $a . foo() . $a . "\n";
> } catch (Exception $e) {
> }
> ?>
>

Ah yes, I forgot about this issue. However, shouldn't we at least properly
release memory if the exception occurs in the opcode?

Nikita

---

## #85456 — Dmitry Stogov — 2015-03-24T21:22:15+00:00

URL: https://externals.io/message/85428#85456 · In reply to: #85453

These opcodes hardly ever would throw exceptions their selves.

This real problem should be fixed in HANDLE_EXCEPTION handler.
There we will need to get the list of "active" temporary variables.
I don't have a good solution for this yet.

Thanks. Dmitry.



> 
>
> > […]
>
> Ah yes, I forgot about this issue. However, shouldn't we at least properly
> release memory if the exception occurs in the opcode?
>
> Nikita