Re: Fwd: [Lse-tech] get_pid() performance fix

From: Hubertus Franke <frankeh@watson.ibm.com>
To: OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>
Cc: "Rajan Ravindran" <rajancr@us.ibm.com>,
	linux-kernel@vger.kernel.org, lse-tech@lists.sourceforge.net
Subject: Re: Fwd: [Lse-tech] get_pid() performance fix
Date: Tue, 5 Mar 2002 18:40:46 -0500	[thread overview]
Message-ID: <20020305233943.F157B3FE06@smtp.linux.ibm.com> (raw)
In-Reply-To: <OF810580E6.8672B341-ON85256B73.005AF9B8@pok.ibm.com> <20020305215759.21E623FFD3@smtp.linux.ibm.com> <87vgcazl4a.fsf@devron.myhome.or.jp>
In-Reply-To: <87vgcazl4a.fsf@devron.myhome.or.jp>

On Tuesday 05 March 2002 05:48 pm, OGAWA Hirofumi wrote:
> Hubertus Franke <frankeh@watson.ibm.com> writes:
> > > > @@ -153,13 +155,18 @@
> > > >                               if(last_pid & 0xffff8000)
> > > >                                     last_pid = 300;
> > > >                               next_safe = PID_MAX;
> > > > +                             goto repeat;
> > > >                         }
> > > > -                       goto repeat;
> > > > +                       if(unlikely(last_pid == beginpid))
> > > > +                             goto nomorepids;
> > > > +                       continue;
> > >
> > > You changed it. No?
> >
> > Yes, we changed but only the logic that once a pid is busy we start
> > searching for every task again. This is exactly the O(n**2) problem.
> > Run the program and you'll see.
>
> Run the attached file.
>
> Result,
> 	new pid: 301, 300: pid 300, pgrp 301
>
> new pid == task(300)->pgrp. This get_pid() has bug.
> I'm missing something?

Yipp you are right. 
I stay corrected, we are missing something. Will work on it and see
whether we can correct it, either way we should be able to
get ride of the o(n**2) effect.

-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)