Re: quadratic behaviour

[William Lee Irwin III <wli@holomorphy.com>]

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

On Sat, Sep 21, 2002 at 10:06:02AM -0700, Linus Torvalds wrote:
> 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).

Okay, I'm in trouble. My end-users use processes. But /proc/ needs some
more tweaking before they can use it during larger runs anyway.


On Sat, Sep 21, 2002 at 10:06:02AM -0700, Linus Torvalds wrote:
> 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...

This also sounds like an excellent idea. I may take a stab at this.


Thanks,
Bill