On Wed, 2005-07-06 at 20:26, Richard Lynch wrote: > On Wed, July 6, 2005 3:08 pm, Robert Cummings said: > >> > Well i do find a performance issue running a heap of switches in PHP > >> so > >> > I could presume the same here. > >> > >> I believe that what's supposed to happen, in theory, is that the > >> compiler > >> *CONVERTS* the swith statement to a bunch of GOTOs behind the scenes. > >> > >> At least I think that's what Rasmus means by "simple branches" -- GOTOs. > >> > >> When this works, you get the speed of GOTOs with the syntactic sugar of > >> SWITCH for us humans to look at. :-) > > > > Switches are as fast as their counter part the if/elseif/else blocks. > > Run time is O(n) given that each switch branch is equally likely to run > > for the data set. If you know that a specific condition will occur 99.9% > > of the time, you can optimize by making it the first case in your switch > > statement (as you could also make it your first "if" check in the > > if/elseif/else scenario). If you have a very large number of options > > then you may be able to optimize using an array to hold function > > pointers, here the issue is whether the O(lg n) lookup of the function > > pointer in the array offsets the overhead incurred for invoking a > > function. You can't make it O(1) by using GOTOs unless you have constant > > data that would allow the compiler to prepared constant jumps > > beforehand. > > Which, in C, you HAVE only constant jumps. > > You're not allowed to put variables in your "case:" statements in C. * > > So a *GOOD* C pre-compiler, in theory, is going to re-write your switch() > to a bunch of GOTOs, before it hands it off to the main compiler to > actually turn it into Assembler. > > That is what, I still believe, is the optimization Rasmus was talking about. > > The C pre-compiler probably only does this optimization if it "thinks" > it's going to be "worth it", for some definition of "think" and "worth it" > as defined by the compiler writers and their reluctance to attempt to > figure out what the hell their compiler did when it converted that C code > into Assembler. > > * I believe the main reason for only constants in C "case:" statements > *IS* so the pre-compiler can take your "slow" switch and re-factor it into > a bunch of GOTOs... Or it could be just because the C guys are really > weird or something... :-) While I think the C compiler may produce gotos these would be after determining the conditional match for the switch statement, then jumping to the appropriate block. It cannot process the value being switched upon in O(1) time since to use a goto in that way would require O(1) lookup for value to code block, and that can only happen with a perfect O(1) hashing algorithm, which isn't going to happen when the value being switched upon is a long integer. Thus the compiler either converts to O(lg n) lookup, or does as I suspect and uses O(n) if/elseif/else lookup since switch statements usually have fairly few branches. The results could be fairly easily tested by creating a little C program to check difference in speed for a large number of case statements in a switch versus the same logic implemented via if/elseif/else. I don't think that you'll get O(1) time... I'm so sure, I'm not even going to bother testing for it :B Cheers, Rob. -- .------------------------------------------------------------. | InterJinn Application Framework - http://www.interjinn.com | :------------------------------------------------------------: | An application and templating framework for PHP. Boasting | | a powerful, scalable system for accessing system services | | such as forms, properties, sessions, and caches. InterJinn | | also provides an extremely flexible architecture for | | creating re-usable components quickly and easily. | `------------------------------------------------------------' -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
