quadratic behaviour
Quoted 10 lines
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 thefor_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
Quoted 8 lines · Andries Brouwer
Quoted 8 lines
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, thenget_pid_list()will be called 1000 times, and thefor_each_process()loop will examine 10000000 processes.
Unlike theget_pid()situation, which was actually amortized linear with a very
small coefficient, here we have a bad quadratic behaviour, still in 2.5.37.
Quoted 6 lines · Manfred Spraul
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 thetask_lockwould be just a tree lookup (find first pid larger than x).
And a sorted tree would make it possible find the next safe range forget_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