Re: quadratic behaviour

[Linus Torvalds]

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

		Linus