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/
This archive was generated by hypermail 2b29 : Mon Sep 23 2002 - 22:00:23 EST