Messages in this thread | | | Date | Wed, 18 Sep 2002 22:11:34 +0200 | From | Andries Brouwer <> | Subject | Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK |
| |
On Wed, Sep 18, 2002 at 09:00:37PM +0200, Ingo Molnar wrote:
> If you think you can outrun this O(N^2) algorithm
Last month or so I already showed how to make it O(N log N). (Also without any new data structures.) But there is no hurry. The constant in your O(N^2) is very small, since in reality it is better than O(N^2 / pid_max).
Really, now that pid_max is large, there is no problem with get_pid.
Much more interesting is thinking about for_each_task.
In a number of places we search for all tasks with a certain property. It would be nice to arrange things in such a way that these are found in some efficient way so that not the entire task list is searched.
For ordinary Unix semantics we need to be able to find all tasks with a given p->pgrp or p->session or p->pid or p->uid or p->tty. Some kernel routines come with a given pointer tsk and want p == tsk. Some places need p->mm or p->mm->context or CTX_HWBITS(p->mm->context)
In procfs we have a very quadratic algorithm in proc_pid_readdir()/ get_pid_list(). Not a potential hiccup after 2^30 processes that some may want to smoothe, but every single "ls /proc" or "ps". What shall we do with /proc for all these people with 10^5 processes?
Andries
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |