Re: quadratic behaviour

From: Ingo Molnar (
Date: Sat Sep 21 2002 - 12:49:49 EST

On Sat, 21 Sep 2002, Linus Torvalds wrote:

> But the quadratic behaviour wrt processes clearly isn't fixed.
> Suggestions welcome (and we'll need to avoid the same quadratic
> behaviour wrt the threads when we expose them).

in the case of threads my plan is to use the pid alloction bitmap for
this. It slightly overestimates the pids because orphan sessions and pgrps
are included as well, but this should not be a problem because procfs also
does a pid lookup when the specific directory is accessed. This method is
inherently restartable, the pid bitmap pages are never freed, and it's the
most cache-compact representation of the sorted pidlist. And it can be
accessed lockless ...


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Sep 23 2002 - 22:00:33 EST