PHP: why GOTO instead of recursion?
github.com
github.com
These machine-readable instructions can be executable directly, but not necessarily. Is a cross-compiler not a true compiler because you can't execute the resulting code directly? Not at all. So by the same token, one that produces byte code is no different.
It didn't take long for this to prove itself to be terribly inefficient.
Regardless of which word you wish to use (compiler, interpreter, lexer, etc) or which part of the process you wish to shift the workload into, that work (finding redundancies and removing them) is still being performed in real time after a request arrives (i.e. a user has to wait while we do this).
If the redundancy check costs more than the redundancy itself then removing them is utterly fruitless. The only way to avoid that is to take it out of that pipeline (i.e. pre-optimise the PHP OPCodes before a request arrives).
PHP pre-compilers and other optimisers absolutely exist and are readily used (e.g. HipHop). Within which case it might not matter if you used GOTO or While(true) as they'd both likely get optimised down to the GOTO OPCodes. However if you're using the original PHP interpreter then leaving them in might be the most optimal/cheap path to follow.
Most production installations of PHP pretty much mandate a bytecode cache and the official distribution bundles one since 5.5[0], so the redundancy check is done once but the optimisation works for any request thereafter.
> PHP pre-compilers and other optimisers absolutely exist and are readily used (e.g. HipHop).
HHVM is a completely separate VM which does not use (or consume, or care for in any way) the Zend bytecode produced by the Zend VM. HHVM has its own separate and incompatible bytecode format called HHBC[1]. It's neither a "pre-compiler" nor an "optimiser" for the Zend VM.
[0] http://php.net/manual/en/opcache.installation.php
[1] https://github.com/facebook/hhvm/blob/master/hphp/doc/byteco...
Nobody claimed otherwise.
You provided HHVM as an example[0] of "PHP pre-compilers and other optimisers".
[0] that's literally what 'e.g.' means, it's an abbreviation for "exempli gratia", latin for "for example"
You tacked on "for the Zend VM." Which was not something I said.
I said:
> PHP pre-compilers and other optimisers absolutely exist and are readily used (e.g. HipHop).
You then said:
> HHVM is a completely separate VM which does not use (or consume, or care for in any way) the Zend bytecode produced by the Zend VM. HHVM has its own separate and incompatible bytecode format called HHBC[1]. It's neither a "pre-compiler" nor an "optimiser" for the Zend VM.
Which is really answering a point nobody made. It is just completely out of the blue. My post literally does not contain the term "Zend." Nor does it make any claim to what OPCode formats different things use (and really the only reason you could even talk about HipHop was that it was given as a unqualified example).
So to this:
> It's neither a "pre-compiler" nor an "optimiser" for the Zend VM.
Is answering a point nobody made. It is like me saying, "You're wrong, the White House isn't blue, it is white!" When no claims to the blueness of the White House were made by yourself.
"HHVM" is a VM. "HipHop [for PHP]" was a compiler[0], although it compiled down to C++ rather than Zend's VM (much like ShedSkin for Python[1])
[0] http://en.wikipedia.org/wiki/HipHop_for_PHP [1] http://en.wikipedia.org/wiki/Shed_Skin
> The Zend Engine compiles PHP source code on-the-fly into an internal format that it can execute, thus it works as an interpreter.
I won't get drawn into a highly dull debate on the definition of what an interpreter is or isn't. Instead let's just agree that PHP by default generates the OPCodes every single time a request comes in. That's all we need to understand for this context (that OPCode generation is in-line with requests, not pre-compiled or otherwise cached).
Also, yes, there are tons and tons of implementations of PHP caching/precompilation/JIT/etc.
Because PHP's compiler component, which he refers to as "compiler", did not generate efficient byte code for the interpreter, he had to use GOTO to force the compiler to generate it.
Whether the byte codes get cached or not might be irrelevant to his goals. We cannot be certain what proportion of time is wasted in network, compilation or serving the request. It could be one way or another.
USUALLY this is a waste of time. The developer's time that is.
Don't try to out-clever the compiler. You might be able to do it, but there's no guarantee that tomorrow's compiler update won't be smarter than your today's workaround, leaving you with code that is both "weird" and slow.
Yeah, there is no guarantee, but let's be realistic here. That bug for PHP's incorrect parsing of octal integer literals has been unfixed for what, a decade now?
I think that's definitely true in the general case.
However, for a 19 line library whose focus is "fast retrying" where the goto construct is "goto beginning of function", I don't think it's really hugely "weird".
In this case it's also extremely unlikely to get slower.
Fast retrying of network operations, generally. This optimization should save a few nanoseconds per call to a network service that might take a few hundred or thousand milliseconds. When the payoff is so vanishingly tiny as to be immeasurable, I'd take idiomatic code over clever interpreter-specific optimizations any day.
Here's the current version of the retry function:
function retry($retries, callable $fn)
{
beginning:
try {
return $fn();
} catch (\Exception $e) {
if (!$retries) {
throw new FailingTooHardException('', 0, $e);
}
$retries--;
goto beginning;
}
}
And if gotos are inherently, irredeemably evil, then why do we use switch statements? Because each case label in a switch statement is a goto.
Dijsktra in his original letter condemned the "unbridled" use of gotos. At that time, there was -- according to Dijsktra -- a growing trend in programming, where gotos were used to jump from one area of a program to the next, and into and out of loops, making the program flow very difficult to follow. (A good review of Dijsktra's "Goto considered harmful" is at http://david.tribble.com/text/goto.html .) Dijsktra proposed abolishing goto altogether as a knee-jerk reaction to the habits of that era's programmers, but only because in his view it was too great of a temptation for abuse. I doubt Dijsktra would have even raised an eyebrow at the use of goto in the example above.
It's also bad because you're effectively lying to the interpreter. Suppose a future optimization involves some super efficient loop unrolling or such. Well, too bad: because you've hand-rolled your own looping construct, the compiler probably won't be able to use it.
In general, just write idiomatic code that other programmers can readily work with. If (and only if!) a profiler identifies a problem, tweak just that part of the code. Leave liberal comments about what and why you did so that future programmers can evaluate whether your trickery is still worthwhile.
You argued earlier that there was no point in making this optimization in the first place, since it probably wasn't contributing a significant delay in the application (which I disagree with on the grounds that we don't know what retry() might be used for), but now you're saying that it shouldn't be done this way because the compiler might later do a better job of optimizing a standard loop.
As others have pointed out, there are some good reasons not to expect PHP's bytecode runtime to match the optimizations of other software compilers. Without knowing in advance exactly how many times the function call embedded in retry() will be repeated -- which seems pretty unlikely -- there's no good way for the compiler to unroll the loop more efficiently than has already been done here with the straightforward application of a goto.
Sure, in general, don't be too clever. (Rather, "don't be cruel to future programmers".) I agree. But, I think there's a far greater danger of programmers blindly following guidelines like "don't use goto" without consideration.
So while there probably isn't a good argument for writing this function this way, there also isn't a good argument against it -- which is what makes all of the discussion around it so funny.
There is actually a difference between "while (true)" and "while (\true)", and it's not even capable to optimize this as a standard JMP. I can't believe that really simple things like this are still not optimized in the interpreter.
It has been a long time since I last wrote PHP code, but is it possible to dynamically redefine the value of `true`? That would (partially) explain why you can't statically evaluate it to `\true`.
runkit_constant_redefine("true", false) == false in success and failure (as success results in true, which equals false now).
Yes, but that only requires a guard clause. That's what CPython 2 does in the same situation:
>>> import dis
>>> def foo():
... while True:
... print "ok"
...
>>> dis.dis(foo)
2 0 SETUP_LOOP 15 (to 18)
>> 3 LOAD_GLOBAL 0 (True)
6 POP_JUMP_IF_FALSE 17
3 9 LOAD_CONST 1 ('ok')
12 PRINT_ITEM
13 PRINT_NEWLINE
14 JUMP_ABSOLUTE 3
>> 17 POP_BLOCK
>> 18 LOAD_CONST 0 (None)
21 RETURN_VALUE
Take this example, it is one extra OP Code instruction, which might generate a handful of ASM that actually gets run. How many ASM instructions would it take to detect this (and make sure there are no externalities) and remove it? I'd imagine considerably more.
And worse still you're also performing all of these redundancy checks even when there is nothing to remove. So now you've increased the cost to ALL loops, not just static ones with no purpose.
TL;DR: It is more expensive to detect and remove than to ignore.
The detection is only done one while generating the bytecode, but the extraneous bytecode instructions have to be executed every time the loop… loops.
Not only that but it's a very simple optimisation to apply (even CPython is able to discover it).
That isn't how PHP natively works. It is an interpreted language with compiler addons. It has to be done per every single request (as the CGI process may collapses after each one).
If you use something like HipHop or PHP accelerator then you can get cached OPCodes, and can also perform optimisation at that stage. But you cannot assume PHP will be executed in those environments.
PHP is not Java.
Yes it is.
> It has to be done per every single request
Yes? And the loop will most likely loop multiple times per request, which is my point.
> If you use something like HipHop or PHP accelerator then you can get cached OPCodes
HHVM is a completely separate and unrelated product. And you don't need "PHP accelerator" because the Zend VM bundles a bytecode cache since 5.5[0], not that it has any relevance to my point.
> But you cannot assume PHP will be executed in those environments.
Good thing I wasn't assuming anything then.
I said that natively PHP doesn't cache and the OPCodes are generated every request. You said "Yes it is." meaning presumably you don't feel like that is the case.
You then go on to link to Zend Opcache which is, by all accounts, an extension which provides caching and which wasn't even bundled with PHP until 5.5 (according to yourself). So from 0.1 through 5.4 PHP shipped with zero caching and thus a core part of the language at that time was that it was generated every request.
Now, 5.5 was released in June 2013.
So for a lot of users PHP remains a language which is interpreted when a user makes a request. And even users on 5.5+, the first request per page is effectively interpreted as the cache isn't pre-populated.
So really what is it that we are even discussing? Seems like a debate about semantics at this stage.
[Edit] Maybe a whole new world of possible optimizations has just opened up.
Since when do you backtrack to a completely different subtread (or to a subthread which does not exist)?
* I said that the detection (optimisation) would be performed while generating the bytecode
* You asserted that it's not how PHP works by default
* I replied that it is
You've asserted that Zend PHP does not use an intermediate bytecode during normal operation, do you stand by it? Because that's where we end up if we backtrack, not about the fact that it doesn't cache bytecode by default which is not actually relevant to my point (the existence and widespread use of bytecode cache merely supports said point by further improving the ROI).
I never made that claim, and no I don't stand by a claim I never made.
You've asserted that PHP is actually JavaScript with style, do you stand by it?
Sorry to report that yes you did, let me quote exactly (rather than paraphrase):
>> The detection is only done one while generating the bytecode
> That isn't how PHP natively works.
Since "the detection" is obviously a hypothetical assumed in case the compiler ever got a peephole optimizer, the only part of the phrase you could object to is that Zend PHP generates intermediate bytecode.
So every time a loop is compiled (which by default is every request) there is the added overhead of "if opcode is JMPNZ and the first operand is the literal true, replace opcode with JMP and remove first operand".
This saves the "if operand is non-zero" check for all iterations of loops where the first operand is a constant "true".
Which means you've increased the cost of every loop on every request by a constant amount to decrease the cost of each iteration of "while (\true)".
Obviously you'd have to measure the actual costs, but it doesn't seem worth it to me.
Yup. And remove FETCH_CONSTANT as well.
> So every time a loop is compiled (which by default is every request) there is the added overhead of "if opcode is JMPNZ and the first operand is the literal true, replace opcode with JMP and remove first operand".
Sure, or perform it while compiling the bytecode itself.
> This saves the "if operand is non-zero" check for all iterations of loops where the first operand is a constant "true".
It also saves loading the operand, because I expect most PHP code trying to loop forever doesn't use `\true`, and it can be applied to `for(;;)` to boot (a pretty common construct for those coming from C).
> Obviously you'd have to measure the actual costs
Obviously.
Great explanation!
I'd like to hear of any other PHP performance gotchas people know of. One of my favorites: passing function arguments by value is faster than passing by reference.
Why is it inexperienced programmers go through a phase where they think goto is evil incarnate? I wish Dijkstra had never written that damn paper.
They can be described with if, while, for, case, pattern matching, recursion, etc. There is almost always a better alternative.
>Why is it inexperienced programmers go through a phase where they think goto is evil incarnate?
It seems to me that most people who support general usage of GOTO are inexperienced and don't necessarily realize it. They lack knowledge of better control structures. See the blub paradox.
Besides, the justification here is performance, not readability. I'm saying that performance in particular is a bad justification for using GOTO.
>> "Why is it inexperienced programmers go through a phase where they think goto is evil incarnate? I wish Dijkstra had never written that damn paper."
You seem to be referencing my comments. I'm not inexperienced, and I don't think goto is evil incarnate. I do believe that optimizing for individual CPU cycles in PHP is generally pointless.
Programmers who use tail recursion instead of a loop are very annoying. Looking at you justincormack ;-)
Seriously, when I first saw recursion explained using the fibonacci sequence I was really scratching my head. I wondered why anyone would do that. Now that I'm older and wiser, I can see that it's natural to a mathematician. Why anyone who claims to be a programmer or compsci person would do it is beyond me. I suppose it's a simple example, but I'm a fan of introducing concepts with examples that really want the technique in question as a solution.
Erlang:
fib(1) -> 1;
fib(2) -> 1;
fib(N) when N > 2 -> fib(fib(1), fib(2), N - 2).
fib(_A, B, 0) -> B;
fib(A, B, N) when N > 0 -> fib(B, A + B, N - 1).
int fib(int count) {
int a = 1, b =1;
while (--count >= 2) {
int next = a + b;
a = b;
b = next;
}
return b;
}
(I shrunk the C code a bit more than originally written, and it's now pretty similar in length... I guess it's about the same... which is the point :)
https://www.google.com/trends/explore#q=php%2C%20javascript%...