Message-ID: <alpine.DEB.2.00.0903251227360.5675@gandalf.stny.rr.com>
Date:	Wed, 25 Mar 2009 12:34:02 -0400 (EDT)
From:	Steven Rostedt <rostedt@...dmis.org>
To:	Matt Mackall <mpm@...enic.com>
cc:	Pekka Enberg <penberg@...helsinki.fi>,
	Hua Zhong <hzhong@...il.com>, linux-kernel@...r.kernel.org,
	Ingo Molnar <mingo@...e.hu>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Peter Zijlstra <peterz@...radead.org>,
	Roland McGrath <roland@...hat.com>,
	Nick Piggin <nickpiggin@...oo.com.au>,
	Steven Rostedt <srostedt@...hat.com>,
	Christoph Lameter <cl@...ux-foundation.org>,
	Al Viro <viro@...iv.linux.org.uk>
Subject: Re: [PATCH 2/5] mm: remove unlikly NULL from kfree


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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists