Re: [patch] Latency Tracer, voluntary-preempt-2.6.8-rc4-O6

[Ingo Molnar <mingo@elte.hu>]

* Andi Kleen <ak@muc.de> wrote:

> > > > yeah - kallsyms_lookup does a linear search over thousands of symbols. 
> > > > Especially since /proc/latency_trace uses it too it would be worthwile
> > > > to implement some sort of binary searching.
> > > 
> > > Or just stick some cond_sched()s in there. It was designed to be slow,
> > > but there are no locking issues.
> > 
> > the speedup would be important: even on a 2GHz box reading 10,000 trace
> > entries takes a couple of seconds.
> 
> That's because you're abusing it - it was never designed to process
> that much data.

i'm not abusing it. Linear searching of 20 thousand symbols is a gross
first-approximation algorithm no matter what. Yes, most users of the
symbols dont care about performance. And i'm not complaining at all, i'm
just pointing out the reason why e.g. printing a simple stack backtrace
can take milliseconds.

> With binary search you would need to backward search to find the stem
> for the stem compression. It's probably doable, but would be a bit
> ugly I guess.

yeah. Maybe someone will find the time to improve the algorithm. But
it's not a highprio thing.

	Ingo