Re: [PATCH 2/5] mm: remove unlikly NULL from kfree

Steven Rostedt
2009-03-25T16:34:22Z

On Wed, 25 Mar 2009, Matt Mackall wrote:
> >
> > I think the theory is that gcc and the CPU can handle normal branch
> > predictions well. But if you use one of the prediction macros, gcc
> > (and some archs) behaves differently, such that taking the wrong branch
> > can cost more than the time saved with all the other correct hits.
> >
> > Again, I'm not sure. I haven't done the bench marks. Perhaps someone else
> > is more apt at knowing the details here.
>
> >From first principles, we can make a reasonable model of branch
> prediction success with a branch cache:
>
> hot cache cold cache cold cache cold cache
> w|w/o hint good hint bad hint
> p near 0 + + + -
> p near .5 0 0 0 0
> p near 1 + - + -
>
> (this assumes the CPU is biased against branching in the cold cache
> case)
>
> Branch prediction miss has a penalty measured in some smallish number of
> cycles. So the impact in cycles/sec[1] is (p(miss) * penalty) * (calls /
> sec). Because the branch cache kicks in and hides our unlikely hint with
> a hot cache, we can't get a high calls/sec, so to have much impact,
> we've got to have a very high probably of a missed branch (p near 1)
> _and_ cold cache.
>
> So for CPUs with a branch cache, unlikely hints only make sense in
> fairly extreme cases. And I think that includes most CPU families these
> days as it's pretty much required to get much advantage from making the
> CPU clock faster than the memory bus.
>
> We'd have a lot of trouble benchmarking this meaningfully as hot caches
> kill the effect. And it would of course depend directly on a given CPU's
> branch cache size and branch miss penalty, numbers that vary from model
> to model. So I think unless we can confidently state that a branch is
> rarely taken, there's very little upside to adding unlikely.
>
> On the other hand, there's also very little downside until our hint is
> grossly inaccurate. So there's a huge hysteresis here: if p is < .99,
> not much point adding unlikely. If p is > .1, not much point removing
> it.
>
> [1] Note that cycles/sec is dimensionless as cycles and seconds are both
> measures of time. So impact here is in units of very small fractions of
> a percent.

Hi Matt,

Thanks for this info!

Although gcc plays a role too. That is, if we have

if (x)
do something small;

do something large;

this can be broken into:

cmp x
beq 1f
do something small
1:
do something large

Which plays nice with the cache. But, by adding a unlikely(x), gcc will
probably choose to do:

cmp x
bne 2f

1:
do something large

ret;

2:
do something small
b 1b

which hurts in a number of ways.

-- Steve