12 ms·
PHP: why GOTO instead of recursion?
- realusername 12y agoI knew that the php interpreter was not very clever but the most surprising part is this one : 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.
- psuter 12y agoFrom the reply: "This requires doing a namespace lookup against igorw\true". 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`.
- jbrooksuk 12y agoI've never tried, but this (http://us2.php.net/manual/en/function.runkit-constant-redefine.php http://us2.php.net/manual/en/function.runkit-constant-redefi...) seems relevant.
- richardwhiuk 12y agoSo if you redefine true to false: runkit_constant_redefine("true", false) == false in success and failure (as success results in true, which equals false now).
- masklinn 12y ago> That would (partially) explain why you can't statically evaluate it to `\true`. 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 (in Python 3, True and False are keywords so the loop prelude can be elided entirely)
- Someone1234 12y agoThe key word there is interpreter. When you compile you have near infinite time to try and optimise and remove redundancy. When you interpret (i.e. real-time compilation) you have to decide if the redundancy check is more expensive than removing the redundancy. 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.
- masklinn 12y ago> 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. 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).
- Someone1234 12y ago> The detection is only done one while generating the bytecode 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.
- masklinn 12y ago> That isn't how PHP natively works. 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. [0] http://php.net/manual/en/book.opcache.php http://php.net/manual/en/book.opcache.php
- Guvante 12y agoSo the short version is "PHP doesn't perform optimizations so I had to manually include them".
- canadaj 12y agoSure looks like it to me. Compiler can't figure out how to replace 'true' with '\true'? Better do it myself.
- Implicated 12y agoI stand corrected. Compiler.
- kyberias 12y agoCompiler.
- alayne 12y agoYou should not be getting downvoted. The article is clearly discussing the compiler. Compilers and interpreters are not mutually exclusive. Just because a compiler produces bytecode (virtual instructions) instead of machine instructions (like x86), doesn't somehow make it not a compiler.
- astrodust 12y agoExactly. A compiler transforms abstract source code into machine-readable instructions. 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.
- kyberias 12y agoI'll argue with myself here a bit if you allow... When considering PHP, we can think of The PHP Interpreter as a hybrid of two components: 1) a translator/compiler and 2) a bytecode interpreter. Therefore, when someone says "PHP Interpreter" he may indeed refer to that hybrid. If this is true, it would cause these kind of confusions. ;)
- martin_ 12y agoTo add context, igorw is a contributor on php-internals has committed multiple patches/improvements[1] to php-src as recent as PHP 5.6 Great explanation! https://github.com/php/php-src/commits?author=igorw https://github.com/php/php-src/commits?author=igorw
- excitom 12y agoIt seems to me that if you're this worried about performance you should be looking at something like HipHop.
- peterwwillis 12y agoLongest explanation of "function calls [and loops] are expensive" ever. Also the best example of why over-optimization is a completely valid thing to do if you're bored and have a debugger handy.
- masklinn 12y agoThe explanation is mostly "Zend's bytecode compiler is retarded and can't do trivial optimisations so you have to handroll them".
- Piskvorrr 12y agoVery...clever[1]. http://www.catb.org/jargon/html/K/kluge.html http://www.catb.org/jargon/html/K/kluge.html
- wyager 12y agoIf you need to use GOTOs in your code for speed and you're not coding in C, you should probably find a faster platform.
- quotemstr 12y agoNot all useful control flow graphs can be described with while and if. It's perfectly fine to use goto. Look at some of the contortions people need to go through when avoiding it. Avoiding goto often makes programs harder to follow. 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.
- wyager 12y ago>Not all useful control flow graphs can be described with while and if. 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.
- jtc331 12y agoAgreed that sometimes it's right for control-flow purposes. Hence why I pointed out in the OP thread that I've used it before. But that's not the justification being used by the code author; his justification is purely performance. >> "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.
- deleted 12y ago[deleted]
- Hawkee 12y agoGreat read, but I think it's a few years too late. When you compare how PHP is trending against languages like Python it's following a similar path as perl, https://www.google.com/trends/explore#q=php%2C%20javascript%2C%20python%2C%20perl&cmpt=q https://www.google.com/trends/explore#q=php%2C%20javascript%... - I'm surprised JavaScript isn't having much of an upturn lately.
- goshx 12y agoOn a side note, Monty Python (or the snake) are not programming languages. Check the "Related searches" section at the bottom and click "Python".
- Hawkee 12y agoSilly me. I forget that not everybody lives in the world of development. Considering this it seems every language is experiencing a downturn. To me this looks more like a fault in Google's trend calculation. Maybe it doesn't consider search inflation from year to year.
- sebs__ 12y agoUsing the same kind of metric, certain male bodyparts seem to be trending as programming lang. as well. https://www.google.com/trends/explore#q=php%2C%20javascript%2C%20python%2C%20perl%2C%20Penis&cmpt=q https://www.google.com/trends/explore#q=php%2C%20javascript%...
- justincormack 12y agoLanguages without tail recursion elimination are very annoying. Looking at you JavaScript.
- phkahler 12y ago>> Languages without tail recursion elimination are very annoying. Looking at you JavaScript. 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.
- emodendroket 12y agoHow about a depth-first search, then?
- crimsonalucard 12y agoThat's not tail recursion! It's tree recursion.
- emodendroket 12y agoWell, good point, but so is the naive implementation of Fibonacci, isn't it?
- toast0 12y agoSome languages don't have loops, so you have to use tail recursion. Sometimes, tail recursion is more clear or concise than a loop: 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). C: int fib(int count) { int a = 1, b =1; while (--count >= 2) { int next = a + b; a = b; b = next; } return b; } Notes: Erlang version will crash if given value is less than 1; C version will just return 1 for anything outside of accepted range. Erlang integers become large integers automatically, C integers will overflow. If you prefer fib(0) == 0, you can adjust it, with more work for C, because I cheated the initial conditions/bounds check. (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 :)
- deleted 12y ago[deleted]
- crimsonalucard 12y ago15 years doesn't mean anything if it makes you inflexible. One GOTO statement in the right context doesn't make code unreadable. Programmers have been drilled since school never to use GOTO but if someone finds a valid case for why to use it, you as a programmer should be flexible enough to change. Clojure another language that doesn't support tail recursion optimization (TRO) uses an ugly language construct called (recur) to mimic TRO which is essentially identical to a GOTO, so I don't see what the big deal is. In the end, anything that can be done with tail recursion can be done in a loop which is way more readable then either using a GOTO or recursion. Tail recursion is only required for strict functional languages.
- wtetzner 12y ago> In the end, anything that can be done with tail recursion can be done in a loop which is way more readable then either using a GOTO or recursion. The real value in TCO isn't a function recurring on itself, it's mutual recursion.
- crimsonalucard 12y agoNo, that is not the only case where it has value. TRO is a mandatory optimization for functional languages where recursion is the only possible looping construct. Haskell, Clojure, Erlang and Lisps rely on it heavily.
- wtetzner 12y agoSorry, I didn't mean it was the only value. It's the value that you get from it that you don't get from having loops.
- powera 12y agoThe real question is: if you care that much about performance, why would you use the un-optimized PHP runtime?
- thathonkey 12y agoSometimes people optimize for fun, out of sheer curiosity, or some combination of things like that. Not everything we do as programmers has to be for some solely practical purpose. Having some fun with opcode optimization is certainly permissible and if you program a lot in PHP, learning how things work under the hood will make you a better PHP programmer in general.
- krazydad 12y agoI like including a few GOTOs just to piss off the Dijkstra acolytes, one of whom is quite vocal in the thread.
- jtc331 12y agoSince I see you're referencing my posts in that thread, you'll notice that I also point out that I understand that GOTO is not always bad, and, in fact, have used it before in production code.
- seccess 12y agoIn my experience, PHP can have really unexpected runtime performance. This site has some interesting benchmarks highlighting this: http://www.phpbench.com/ http://www.phpbench.com/ 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.