[lkml]   [2002]   [Sep]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    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

    > But there are lots of other solutions.

    such as? ...


    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:22    [W:0.021 / U:41.776 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site