Messages in this thread | | | From | Hubertus Franke <> | Subject | Re: Analysis for Linux-2.5 fix/improve get_pid(), comparing various approaches | Date | Fri, 9 Aug 2002 14:14:58 -0400 |
| |
On Friday 09 August 2002 11:36 am, Andries Brouwer wrote:
!!!!!!!!!!! You are in a different space !!!!!!!! All work was done under the assumption of 16-bit pid_t. I stated yesterday already that for NumTasks substantially smaller than the pid_t supported size, this won't be a problem as your analysis states and my data also states. You have two choices (a) move Linux up to 32-bit pid_t (b) stick within the current 16-bit discussion.
> On Fri, Aug 09, 2002 at 07:22:08AM -0400, Hubertus Franke wrote: > > Particulary for large number of tasks, this can lead to frequent exercise > > of the repeat resulting in a O(N^2) algorithm. We call this : <algo-0>. > > Your math is flawed. The O(N^2) happens only when the name space for pid's > has the same order of magnitude as the number N of processes. > Now consider N=100000 with 31-bit name space. In a series of > 2.10^9 forks you have to do the loop fewer than N times and > N^2 / 2.10^9 = 5. You see that on average for each fork there > are 5 comparisons. > For N=1000000 you rearrange the task list as I described yesterday > so that each loop takes time sqrt(N), and altogether N.sqrt(N) > comparisons are needed in a series of 2.10^9 forks. > That is 0.5 comparisons per fork. > > You see that thanks to the large pid space things get really > efficient. Ugly constructions are only needed when a large fraction > of all possible pids is actually in use, or when you need hard > real time guarantees. > > Andries
-- -- Hubertus Franke (frankeh@watson.ibm.com) - 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/
| |