Generating more efficient code for while-loop

9 years ago by Benjamin Coutu — view source

unread

Hello,

Please consider the following PHP code:

while ( <CONDITION> ) {
<STATEMENT>
}

It currently compiles to something like this for the Zend Engine:

0: <CONDITION>
1: JMPZ -> 4
2: <STATEMENT>
3: JMP -> 0
4: ...

This can easily be rewritten in an equivalent but much more efficient form:

0: JMP -> 2
1: <STATEMENT>
2: <CONDITION>
3: JMPNZ -> 1

The trick is to jump to the conditional expression before the first iteration and then only having to continue with just on conditional jump on every subsequent cycle.

This would result in only 1 jump per loop iteration compared to effectively 2 jumps needed per iteration with the current implementation.

It would also make the loop tighter as upon entering the loop (after first conditional evaluation), one less opcode remains relevant to the loop.

An analogous approach can be taken for the for-loop.

Thanks,

Ben

PS: This is my first post on a PHP mailinglist - I am very excited! :)

Benjamin Coutu
Zeyon Technologies Inc.
http://www.zeyos.com

9 years ago by Dmitry Stogov — view source

unread

Hi Benjamin,

Thanks for idea.
With PHP7 AST compiler, it's quite easy to implement this (it took us 15
minutes to try :)
However, it doesn't make big improvement on our benchmarks.
We will take a look into possibilities to apply your idea to other patterns
(e.g. for and foreach loops).

Anyway, it makes full sense to include this optimization into PHP7.
I just like to try other opportunities first.

Thanks. Dmitry.

On Fri, Jan 16, 2015 at 10:56 AM, Benjamin Coutu ben.coutu@zeyos.com
wrote:

Hello,

Please consider the following PHP code:

while ( <CONDITION> ) {
<STATEMENT>
}

It currently compiles to something like this for the Zend Engine:

0: <CONDITION>
1: JMPZ -> 4
2: <STATEMENT>
3: JMP -> 0
4: ...

This can easily be rewritten in an equivalent but much more efficient form:

0: JMP -> 2
1: <STATEMENT>
2: <CONDITION>
3: JMPNZ -> 1

The trick is to jump to the conditional expression before the first
iteration and then only having to continue with just on conditional jump on
every subsequent cycle.

This would result in only 1 jump per loop iteration compared to
effectively 2 jumps needed per iteration with the current implementation.

It would also make the loop tighter as upon entering the loop (after first
conditional evaluation), one less opcode remains relevant to the loop.

An analogous approach can be taken for the for-loop.

Thanks,

Ben

PS: This is my first post on a PHP mailinglist - I am very excited! :)

--

Benjamin Coutu
Zeyon Technologies Inc.
http://www.zeyos.com

9 years ago by Xinchen Hui — view source

unread

Hey:

Hi Benjamin,

Thanks for idea.
With PHP7 AST compiler, it's quite easy to implement this (it took us 15
minutes to try :)
yeah... by handy :)

However, it doesn't make big improvement on our benchmarks.
in reallife app, IR has no significant difference while running
wordpress homepage

thanks

We will take a look into possibilities to apply your idea to other patterns
(e.g. for and foreach loops).

Anyway, it makes full sense to include this optimization into PHP7.
I just like to try other opportunities first.

Thanks. Dmitry.

On Fri, Jan 16, 2015 at 10:56 AM, Benjamin Coutu ben.coutu@zeyos.com
wrote:

Hello,

Please consider the following PHP code:

while ( <CONDITION> ) {
<STATEMENT>
}

It currently compiles to something like this for the Zend Engine:

0: <CONDITION>
1: JMPZ -> 4
2: <STATEMENT>
3: JMP -> 0
4: ...

This can easily be rewritten in an equivalent but much more efficient
form:

0: JMP -> 2
1: <STATEMENT>
2: <CONDITION>
3: JMPNZ -> 1

The trick is to jump to the conditional expression before the first
iteration and then only having to continue with just on conditional jump on
every subsequent cycle.

This would result in only 1 jump per loop iteration compared to
effectively 2 jumps needed per iteration with the current implementation.

It would also make the loop tighter as upon entering the loop (after first
conditional evaluation), one less opcode remains relevant to the loop.

An analogous approach can be taken for the for-loop.

Thanks,

Ben

PS: This is my first post on a PHP mailinglist - I am very excited! :)

--

Benjamin Coutu
Zeyon Technologies Inc.
http://www.zeyos.com

--

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

9 years ago by Dmitry Stogov — view source

unread

See the patch for "while" and "for" loops

https://gist.github.com/dstogov/9cc5767a14f3b88e1275

All tests passed.
The patch leads to 2% improvement in number of CPU instructions retired on
bench.php.
Unfortunately, It doesn't make any visible speed difference.

Anyway, I'm going to commit it on Monday.
Xinchen, Nikita, please verify me.

Thanks. Dmitry.

Hey:

Hi Benjamin,

Thanks for idea.
With PHP7 AST compiler, it's quite easy to implement this (it took us 15
minutes to try :)
yeah... by handy :)

However, it doesn't make big improvement on our benchmarks.
in reallife app, IR has no significant difference while running
wordpress homepage

thanks

We will take a look into possibilities to apply your idea to other
patterns
(e.g. for and foreach loops).

Anyway, it makes full sense to include this optimization into PHP7.
I just like to try other opportunities first.

Thanks. Dmitry.

On Fri, Jan 16, 2015 at 10:56 AM, Benjamin Coutu ben.coutu@zeyos.com
wrote:

Hello,

Please consider the following PHP code:

while ( <CONDITION> ) {
<STATEMENT>
}

It currently compiles to something like this for the Zend Engine:

0: <CONDITION>
1: JMPZ -> 4
2: <STATEMENT>
3: JMP -> 0
4: ...

This can easily be rewritten in an equivalent but much more efficient
form:

0: JMP -> 2
1: <STATEMENT>
2: <CONDITION>
3: JMPNZ -> 1

The trick is to jump to the conditional expression before the first
iteration and then only having to continue with just on conditional
jump on
every subsequent cycle.

This would result in only 1 jump per loop iteration compared to
effectively 2 jumps needed per iteration with the current
implementation.

It would also make the loop tighter as upon entering the loop (after
first
conditional evaluation), one less opcode remains relevant to the loop.

An analogous approach can be taken for the for-loop.

Thanks,

Ben

PS: This is my first post on a PHP mailinglist - I am very excited! :)

--

Benjamin Coutu
Zeyon Technologies Inc.
http://www.zeyos.com

--

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

9 years ago by Nikita Popov — view source

unread

See the patch for "while" and "for" loops

https://gist.github.com/dstogov/9cc5767a14f3b88e1275

All tests passed.
The patch leads to 2% improvement in number of CPU instructions retired on
bench.php.
Unfortunately, It doesn't make any visible speed difference.

Anyway, I'm going to commit it on Monday.
Xinchen, Nikita, please verify me.

Thanks. Dmitry.

Patch looks good to me :)

Nikita