| Message ID | CAF1bQ=RnCQGRrdUxV0Mpj9wAiB=fUy+fzouGOf0Rj_YWt2TMoA@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
> Hi, > > Current default probably for builtin_expect is 0.9996. > This makes the freq of unlikely bb very low (4), which > suppresses the inlining of any calls within those bb. > > We used FDO data to measure the branch probably for > the branch annotated with builtin_expert. > For google > internal benchmarks, the weight average > (the profile count value as the weight) is 0.9081. > > Linux kernel is another program that is heavily annotated > with builtin-expert. We measured its weight average as 0.8717, > using google search as > the workload. This is interesting. I was always unsure if programmers use builtin_expect more often to mark an impossible paths (as those leading to crash) or just unlikely paths. Your data seems to suggest the second. We probably also ought to get analyze_brprob working again. It was always useful to get such a data. > > > This patch sets the alternate hirate probability for > builtin_expert > to 90%. With the alternate hirate, we measured performance > improvement for google > benchmarks and Linux kernel. > > > -Rong > 2013-09-26 Rong Xu <xur@google.com> > > * params.def (DEFPARAM): New. > * params.def: New. > * predict.c (tree_predict_by_opcode): Alternate > probablity hirate for builtin_expect. This also seems resonable for mainline. Please add a comment to the parameter explaining how the value was determined. Please also add invoke.texi documentation. For patches that seems resonable for mainline in FDO/IPA area, i would apprechiate if you just added me to CC, so I do not lose track of them. Honza
This patch improves linux kernel performance with a large workload, so it is good to first submit this to trunk and backport it. thanks, David On Thu, Sep 26, 2013 at 3:27 PM, Jan Hubicka <hubicka@ucw.cz> wrote: >> Hi, >> >> Current default probably for builtin_expect is 0.9996. >> This makes the freq of unlikely bb very low (4), which >> suppresses the inlining of any calls within those bb. >> >> We used FDO data to measure the branch probably for >> the branch annotated with builtin_expert. >> For google >> internal benchmarks, the weight average >> (the profile count value as the weight) is 0.9081. >> >> Linux kernel is another program that is heavily annotated >> with builtin-expert. We measured its weight average as 0.8717, >> using google search as >> the workload. > > This is interesting. I was always unsure if programmers use builtin_expect > more often to mark an impossible paths (as those leading to crash) or just > unlikely paths. Your data seems to suggest the second. > > We probably also ought to get analyze_brprob working again. It was always > useful to get such a data. >> >> >> This patch sets the alternate hirate probability for >> builtin_expert >> to 90%. With the alternate hirate, we measured performance >> improvement for google >> benchmarks and Linux kernel. >> >> >> -Rong >> 2013-09-26 Rong Xu <xur@google.com> >> >> * params.def (DEFPARAM): New. >> * params.def: New. >> * predict.c (tree_predict_by_opcode): Alternate >> probablity hirate for builtin_expect. > > This also seems resonable for mainline. Please add a comment > to the parameter explaining how the value was determined. > Please also add invoke.texi documentation. > > For patches that seems resonable for mainline in FDO/IPA area, > i would apprechiate if you just added me to CC, so I do not lose > track of them. > Honza
it might worth extend __builtin_expect to take more parameters: 1) argument to specify actual probability: __builtin_expect (x, 10, 0.6) 2) a more general way of doing this is to allow specifying multiple values, and the probability is determined by # of occurances: __builtin_expect (x, 10, 10, 20) --> tells compiler x is expected to be 10 66% of the time, and 33% of time with value twenty. 3) a special value can be reserved to indicate if the branch is predictable or not. David On Thu, Sep 26, 2013 at 3:27 PM, Jan Hubicka <hubicka@ucw.cz> wrote: >> Hi, >> >> Current default probably for builtin_expect is 0.9996. >> This makes the freq of unlikely bb very low (4), which >> suppresses the inlining of any calls within those bb. >> >> We used FDO data to measure the branch probably for >> the branch annotated with builtin_expert. >> For google >> internal benchmarks, the weight average >> (the profile count value as the weight) is 0.9081. >> >> Linux kernel is another program that is heavily annotated >> with builtin-expert. We measured its weight average as 0.8717, >> using google search as >> the workload. > > This is interesting. I was always unsure if programmers use builtin_expect > more often to mark an impossible paths (as those leading to crash) or just > unlikely paths. Your data seems to suggest the second. > > We probably also ought to get analyze_brprob working again. It was always > useful to get such a data. >> >> >> This patch sets the alternate hirate probability for >> builtin_expert >> to 90%. With the alternate hirate, we measured performance >> improvement for google >> benchmarks and Linux kernel. >> >> >> -Rong >> 2013-09-26 Rong Xu <xur@google.com> >> >> * params.def (DEFPARAM): New. >> * params.def: New. >> * predict.c (tree_predict_by_opcode): Alternate >> probablity hirate for builtin_expect. > > This also seems resonable for mainline. Please add a comment > to the parameter explaining how the value was determined. > Please also add invoke.texi documentation. > > For patches that seems resonable for mainline in FDO/IPA area, > i would apprechiate if you just added me to CC, so I do not lose > track of them. > Honza
On Thu, Sep 26, 2013 at 3:27 PM, Jan Hubicka <hubicka@ucw.cz> wrote: >> Hi, >> >> Current default probably for builtin_expect is 0.9996. >> This makes the freq of unlikely bb very low (4), which >> suppresses the inlining of any calls within those bb. >> >> We used FDO data to measure the branch probably for >> the branch annotated with builtin_expert. >> For google >> internal benchmarks, the weight average >> (the profile count value as the weight) is 0.9081. >> >> Linux kernel is another program that is heavily annotated >> with builtin-expert. We measured its weight average as 0.8717, >> using google search as >> the workload. > > This is interesting. I was always unsure if programmers use builtin_expect > more often to mark an impossible paths (as those leading to crash) or just > unlikely paths. Your data seems to suggest the second. > I don't find an official guideline on how this should be used. Maybe some documentation in gcc user-guide helps. > We probably also ought to get analyze_brprob working again. It was always > useful to get such a data. >> >> >> This patch sets the alternate hirate probability for >> builtin_expert >> to 90%. With the alternate hirate, we measured performance >> improvement for google >> benchmarks and Linux kernel. >> >> >> -Rong >> 2013-09-26 Rong Xu <xur@google.com> >> >> * params.def (DEFPARAM): New. >> * params.def: New. >> * predict.c (tree_predict_by_opcode): Alternate >> probablity hirate for builtin_expect. > > This also seems resonable for mainline. Please add a comment > to the parameter explaining how the value was determined. > Please also add invoke.texi documentation. > Will do. > For patches that seems resonable for mainline in FDO/IPA area, > i would apprechiate if you just added me to CC, so I do not lose > track of them. Will do. > Honza
Index: params.def =================================================================== --- params.def (revision 202638) +++ params.def (working copy) @@ -483,6 +483,10 @@ DEFPARAM(TRACER_MIN_BRANCH_PROBABILITY, "tracer-min-branch-probability", "Stop forward growth if the probability of best edge is less than this threshold (in percent). Used when profile feedback is not available", 50, 0, 100) +DEFPARAM(BUILTIN_EXPECT_PROBABILITY_RELAXED, + "builtin-expect-probability-relaxed", + "Set the estimated probability for builtin expect. By default using PROB_VERY_LIKELY, while value of 1 using HIRATE(90) probability.", + 0, 0, 1) /* The maximum number of incoming edges to consider for crossjumping. */ DEFPARAM(PARAM_MAX_CROSSJUMP_EDGES, Index: params.def =================================================================== --- params.def (revision 202638) +++ params.def (working copy) @@ -483,6 +483,10 @@ DEFPARAM(TRACER_MIN_BRANCH_PROBABILITY, "tracer-min-branch-probability", "Stop forward growth if the probability of best edge is less than this threshold (in percent). Used when profile feedback is not available", 50, 0, 100) +DEFPARAM(BUILTIN_EXPECT_PROBABILITY_RELAXED, + "builtin-expect-probability-relaxed", + "Set the estimated probability for builtin expect. By default using PROB_VERY_LIKELY, while value of 1 using HIRATE(90) probability.", + 0, 0, 1) /* The maximum number of incoming edges to consider for crossjumping. */ DEFPARAM(PARAM_MAX_CROSSJUMP_EDGES, Index: predict.c =================================================================== --- predict.c (revision 202638) +++ predict.c (working copy) @@ -1950,10 +1950,17 @@ tree_predict_by_opcode (basic_block bb) BITMAP_FREE (visited); if (val) { + enum br_predictor predictor; + + if (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY_RELAXED) == 0) + predictor = PRED_BUILTIN_EXPECT; + else + predictor = PRED_BUILTIN_EXPECT_RELAXED; + if (integer_zerop (val)) - predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN); + predict_edge_def (then_edge, predictor, NOT_TAKEN); else - predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN); + predict_edge_def (then_edge, predictor, TAKEN); return; } /* Try "pointer heuristic."
Hi, Current default probably for builtin_expect is 0.9996. This makes the freq of unlikely bb very low (4), which suppresses the inlining of any calls within those bb. We used FDO data to measure the branch probably for the branch annotated with builtin_expert. For google internal benchmarks, the weight average (the profile count value as the weight) is 0.9081. Linux kernel is another program that is heavily annotated with builtin-expert. We measured its weight average as 0.8717, using google search as the workload. This patch sets the alternate hirate probability for builtin_expert to 90%. With the alternate hirate, we measured performance improvement for google benchmarks and Linux kernel. -Rong 2013-09-26 Rong Xu <xur@google.com> * params.def (DEFPARAM): New. * params.def: New. * predict.c (tree_predict_by_opcode): Alternate probablity hirate for builtin_expect.