Everything
php
Learn Community Releases The PHP Project
Home » Project » Newsgroups » php.internals » messing with branch prediction »

messing with branch prediction

php.internals

Nuno Lopes

20 years ago
Hello, Yesterday I was playing with branch prediction in the Zend VM executor. Although I didn't have any noticeable performance improvement within the bench.php script, I've put the patch on-line, because someone else might want to mess with it too :) (but with care..) patch: http://mega.ist.utl.pt/~ncpl/zend_branch_prediction.txt gcc docs: http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005fexpect-2440 the zend.h part of the patch is based on the similar macros (with the same name, too) found in the Linux kernel. I made & tested the patch in a Centrino laptop with gcc 3.4, so it might be the cause of getting no relevant performance increase. On CPUs with longer pipelines (like Pentium 4/NetBurst architecture), the performance increase might be noticeable. Happy hacking :) Nuno

Ilia A.

20 years ago
Looks like an interesting patch, if it does not cost us any performance and only offers either no gain or a small gain I'd say it would be worth inclusion. Perhaps branch prediction will work better with newer versions of gcc like 4.0 or 4.1 On 18-Jun-06, at 9:49 AM, Nuno Lopes wrote:
> Hello, > > Yesterday I was playing with branch prediction in the Zend VM > executor. Although I didn't have any noticeable performance > improvement within the bench.php script, I've put the patch on- > line, because someone else might want to mess with it too :) (but > with care..) > > patch: http://mega.ist.utl.pt/~ncpl/zend_branch_prediction.txt > gcc docs: http://gcc.gnu.org/onlinedocs/gcc/Other- > Builtins.html#index-g_t_005f_005fbuiltin_005fexpect-2440 > > the zend.h part of the patch is based on the similar macros (with > the same name, too) found in the Linux kernel. > > I made & tested the patch in a Centrino laptop with gcc 3.4, so it > might be the cause of getting no relevant performance increase. On > CPUs with longer pipelines (like Pentium 4/NetBurst architecture), > the performance increase might be noticeable. > > > Happy hacking :) > Nuno > -- > PHP Internals - PHP Runtime Development Mailing List > To unsubscribe, visit: http://www.php.net/unsub.php > >
Ilia Alshanetsky

Zeev Suraski

20 years ago
Definitely looks nice. I actually like how it makes the code more readable hinting which branches are rare. Zeev At 16:49 18/06/2006, Nuno Lopes wrote:

Andi Gutmans

20 years ago
I think it's a nice idea but I doubt it's very useful at this point. It doesn't seem to significantly affect performance, which is inline with some tests that we have done in the past, where it's really the hardware management of branch prediction and cache size which affect this. I doubt that make such code changes will affect that in a significant way. We are playing around with some memory management issues, and are relying on some hardware branch predicition there (i.e. hoping that the hardware will play nice with if() statements that always evaluate the same). It seems that the hardware is playing pretty nice with us.

Leon Matthews

20 years ago
> Andi Gutmans wrote: > I think it's a nice idea but I doubt it's very useful at this point. It > doesn't seem to significantly affect performance, which is ... <snip>
I concur. Instead of guessing branch probabilities, why not measure them? http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Optimize-Options.html -fprofile-generate -freorder-functions -fbranch-probabilities -fprofile-use I've seen decent speedups (5-10%) using these options on my own programs. Leon

Sascha Schumann

20 years ago
> Instead of guessing branch probabilities, why not measure them?
Or, simply tell the compiler what you expect. Sometimes, GCC predicts incorrectly - if-branches are usually assumed _not_ to be executed. if (expect_true(x)) { foo(); } with.. #ifdef HAVE_BUILTIN_EXPECT # define expect_true(x) __builtin_expect((x), 1) # define expect_false(x) __builtin_expect((x), 0) #else # define expect_true(x) (x) # define expect_false(x) (x) #endif - Sascha

Zeev Suraski

20 years ago
I still don't see how it can hurt, and even if it doesn't do anything performance wise, it adds clarity to the code. Zeev At 20:34 19/06/2006, Andi Gutmans wrote:

Andi Gutmans

20 years ago
The source code is already hard to maintain. I think the more macros, uncommon and compiler specific things we have in there, the harder it will get. That's why I think that if it doesn't give much benefit it actually hurts to have it in because maintenance keeps on getting harder. Again, I think it's a cool effort by Nuno and I'll be interested to watch more fine-tuned results but I've been down this patch and it seems the CPUs do their work fairly OK.

Zeev Suraski

20 years ago
Well, as I said I think it actually makes the code more readable, by hinting you what you can ignore if you're running through the 'common case' (i.e., even if this macro was a no-op). Diving into a big block of code is easier if you can ignore parts of it to get the general understanding of what it does. And if we might get some performance boost out of it, that's even better. It boils down to whether the people who are actively hacking on the engine code today feel that it's really making the code less readable, or the other way around. It's not such a big deal either way. Zeev At 18:00 20/06/2006, Andi Gutmans wrote:

Derick Rethans

20 years ago
On Wed, 21 Jun 2006, Zeev Suraski wrote:
> Well, as I said I think it actually makes the code more readable, by hinting > you what you can ignore if you're running through the 'common case' (i.e., > even if this macro was a no-op). Diving into a big block of code is easier if > you can ignore parts of it to get the general understanding of what it does. > And if we might get some performance boost out of it, that's even better.
Actually, this is why C has the concept of comments in code. regards, Derick
-- Derick Rethans http://derickrethans.nl | http://ez.no | http://xdebug.org

Nuno Lopes

20 years ago
>I think it's a nice idea but I doubt it's very useful at this point. It > doesn't seem to significantly affect performance, which is inline with > some > tests that we have done in the past, where it's really the hardware > management of branch prediction and cache size which affect this. I doubt > that make such code changes will affect that in a significant way. > We are playing around with some memory management issues, and are relying > on > some hardware branch predicition there (i.e. hoping that the hardware will > play nice with if() statements that always evaluate the same). It seems > that > the hardware is playing pretty nice with us.
First, let me thank you all that reviewed the patch. When I first sent the patch to the list I didn't meant I wanted it to be integrated with the main php sources. At least before running some benchmarks and double-checking it. That patch was just a quick&dirty write of my initial idea. Its also interesting because I was thinking in extending the patch to the memory management part, too. About the gcc heuristics on branch prediction.. Well they seem to be somewhat good, but they are just heuristics. Surely gcc can decide about this: ptr = malloc(3); if (!ptr) return NULL; that's pretty obvious that branch isn't likely to execute.. But others might not be so obvious. The Linux kernel and the GNU libc (where performance is really important) have been using similar macros to mark the branch probability. When I finish my exams, I'll spend some more time tweaking and benchmarking the patch on several computers with different gcc versions and different cpus architectures (my Centrino isn't surely a good place to benchmark server applications..) Other thing that may raise some concerns is the recent addition of reflection data to internal functions. While it is nice to have it, it may cause too much cache trashing. While previously there was about 10 global ARG_INFO vars, now they have exploded to 1 per function. It may have some impact on performance. But I can't talk too much here, because I don't know if that data is used only in compile time or in run-time (on each function call or similar). Nuno

Andi Gutmans

20 years ago
Comments bellow:
>-----Original Message----- > >First, let me thank you all that reviewed the patch. >When I first sent the patch to the list I didn't meant I >wanted it to be integrated with the main php sources. At least >before running some benchmarks and double-checking it. That >patch was just a quick&dirty write of my initial idea. Its >also interesting because I was thinking in extending the patch >to the memory management part, too. > >About the gcc heuristics on branch prediction.. Well they seem >to be somewhat good, but they are just heuristics. Surely gcc >can decide about >this: >ptr = malloc(3); >if (!ptr) return NULL;
Yep and CPUs are good at exactly this repetitive case. We checked this also when we did some MM changes.
>that's pretty obvious that branch isn't likely to execute.. >But others might not be so obvious. The Linux kernel and the >GNU libc (where performance is really important) have been >using similar macros to mark the branch probability. > >When I finish my exams, I'll spend some more time tweaking and >benchmarking the patch on several computers with different gcc >versions and different cpus architectures (my Centrino isn't >surely a good place to benchmark server applications..) > >Other thing that may raise some concerns is the recent >addition of reflection data to internal functions. While it is >nice to have it, it may cause too much cache trashing. While >previously there was about 10 global ARG_INFO vars, now they >have exploded to 1 per function. It may have some impact on >performance. But I can't talk too much here, because I don't >know if that data is used only in compile time or in run-time >(on each function call or similar).
This would be very interesting to find out. It'd be great if you could check it out. Andi

Dmitry Stogov

20 years ago
The patch looks good. I already did some experiments with __builtin_expect() in the past, but didn't get any visible speedup. As I understand __builtin_expect() helps only in case if branch is not in BTB and static branch prediction is used. In case if branch instruction was already executed (and didn't go out from BTB), __builtin_expect() has no effect. It just reorders basic-blocks according to static branch prediction algorithm. Thanks. Dmitry.