quadratic behaviour

quadratic behaviour

[Andries Brouwer]

On Thu, Sep 19, 2002 at 03:11:57PM +0200, Andries Brouwer wrote:
> On Thu, Sep 19, 2002 at 05:05:17AM +0200, Ingo Molnar wrote:

> > because, as mentioned before, that particular loop i fixed in 2.5.35.
> 
> But now that I look at patch-2.5.35
> I don't see any improvement: for_each_task() is now called
> for_each_process(), but otherwise base.c is just as quadratic
> as it was.
> 
> 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.

If you have 20000 processes, and do ps, then get_pid_list() will be
called 1000 times, and the for_each_process() loop will examine
10000000 processes.

Unlike the get_pid() situation, which was actually amortized linear with a very
small coefficient, here we have a bad quadratic behaviour, still in 2.5.37.

Andries

Re: quadratic behaviour

[Manfred Spraul]

> Let me repeat this, and call it an observation instead of a question,
> so that you do not think I am in doubt.
> 
> If you have 20000 processes, and do ps, then get_pid_list() will be
> called 1000 times, and the for_each_process() loop will examine
> 10000000 processes.
> 
> Unlike the get_pid() situation, which was actually amortized linear with a very
> small coefficient, here we have a bad quadratic behaviour, still in 2.5.37.
> 
One solution would be to replace the idtag hash with an idtag tree.

Then get_pid_list() could return an array of sorted pids, and finding 
the next pid after unlocking the task_lock would be just a tree lookup 
(find first pid larger than x).

And a sorted tree would make it possible find the next safe range for 
get_pid() with O(N) instead of O(N^2).

--
	Manfred

Re: quadratic behaviour

[William Lee Irwin III]

At some point in the past, 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.
>> If you have 20000 processes, and do ps, then get_pid_list() will be
>> called 1000 times, and the for_each_process() loop will examine
>> 10000000 processes.
>> Unlike the get_pid() situation, which was actually amortized linear with a 
>> very
>> small coefficient, here we have a bad quadratic behaviour, still in 2.5.37.

On Sat, Sep 21, 2002 at 04:15:10PM +0200, Manfred Spraul wrote:
> One solution would be to replace the idtag hash with an idtag tree.
> Then get_pid_list() could return an array of sorted pids, and finding 
> the next pid after unlocking the task_lock would be just a tree lookup 
> (find first pid larger than x).
> And a sorted tree would make it possible find the next safe range for 
> get_pid() with O(N) instead of O(N^2).

There are incremental / O(1) methods for filling the directory as well.

Also, a tree does not preclude additional hashing. Personally, I'd
consider O(N) catastrophic as well, especially when done on multiple
cpus simultaneously. In fact, a large chunk of this is obtaining hard
bounds on the hold time of the tasklist_lock so writers have a remote
chance of getting into critical sections.

Another very important aspect of it is that the tasklist cachelines
aren't incessantly pounded, which is important even for UP.

At any rate, if you care to send something to me I will doublecheck
whether it NMI oopses on my machines.


Cheers,
Bill

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

Re: quadratic behaviour

[William Lee Irwin III]

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

Re: quadratic behaviour

[William Lee Irwin III]

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

On Sat, Sep 21, 2002 at 07:49:49PM +0200, Ingo Molnar wrote:
> 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 ...

This sounds more attractive still. I'll forego the strategy of my prior
post and try to squeeze some more benchmark numbers out of things over
the weekend.


Cheers,
Bill

Re: quadratic behaviour

[Ingo Molnar]

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

	Ingo