Re: quadratic behaviour

From: Linus Torvalds (
Date: Sat Sep 21 2002 - 12:06:02 EST

On Sat, 21 Sep 2002, Andries Brouwer wrote:
> >
> > So, why do you think this problem has been fixed?
> Let me repeat this, and call it an observation instead of a question,
> so that you do not think I am in doubt.

The reason Ingo thinks it is fixed is that it is fixed for the case of
having millions of threads - because the threads (with the new thread
library) won't show up on the "for_each_process()" loop. Which makes
threaded apps look a lot better on ps and top (we'll have to expose them
some day under /proc/<pid>/thread/<tid>/, but that's another matter)

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).

The only "obvious" thing to do is to insert markers into the process list,
and have "for_each_process()" automatically skip the marker entries. There
probably wouldn't be all that many things that would ever notice if that
were done (excatly because most things that want to traverse the list use
"for_each_process()" already). And then instead of using "index", you
carry the marker thing around...


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