lkml.org 
[lkml]   [2002]   [Sep]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK

On Wed, 18 Sep 2002, Andries Brouwer wrote:

> Collisions cost time. In a large space there are few collisions.
>
> Now suppose you start 10^4 tasks at boot time and after 10^9 forks you
> have to come back. Do you necessarily have to come across this bunch of
> 10^4 tasks that are still sitting there? That would be unfortunate.

If you think you can outrun this O(N^2) algorithm with Moore's law in both
CPU performance and RAM space then you need to reconsider. I considered
solving this problem a few years ago, but it was clearly too much fuss for
too little gain. Now wli did the work and i think it's important, even if
taking the PID allocation issue completely out of the picture.

there's a good reason why this problem started to trigger and slowly made
its way on my radar as well, after so many years of passivity (we've had
this algorithm since day 1 i believe) - O(N^2) algrithms do tend to show
up sooner or later, there's no escape.

> But, you see, there are really many ways to avoid that.
>
> Let me just invent one on the spot. Pick a random generator with period
> 2^128 - 1 and each time you want a new pid pick the last 30 bits of its
> output. Why is that nice? Next time you come around to the same pid,
> pids that were close together first are far apart the second time.

actually now you've moved entirely out of the problem space. Ie. some nice
looking ps output:

mingo 1205341178 0.0 1689.3 123485616 tty5 S 16:26 0:00 -bash
mingo 21123326 0.0 1682.9 212345112 tty6 S 16:26 0:00 -bash
mingo 81430573 0.0 2074.9 1096872604 tty5 S 19:11 0:00 slogin x
mingo 579584 0.0 323.1 9833960 tty3 S 20:07 0:00 lynx
mingo 2690291337 0.1 2748.7 861737004 tty2 S 20:36 0:00 pine -i
mingo 1560603 0.0 1622.2 4431396 tty2 SN 20:39 0:00 -bash

just to solve the lameness of an algorithm that can be fixed nicely? Wow.

> You see, no data structures, no bitmaps, and very good behaviour on
> average, even after 10^9 forks.

just an occasional blip of 1-2-10 millisecs every few seconds, perhaps 100
millisecs if unlucky, even with just a 0.1% fill rate of the PID space.
Lowlatency patches? Why the need, we've got this get_pid() game of
roulette...

> But there are lots of other solutions.

such as? ...

Ingo

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

\
 
 \ /
  Last update: 2005-03-22 13:22    [from the cache]
©2003-2011 Jasper Spaans