lkml.org 
[lkml]   [2002]   [Apr]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [RFC] 2.5.8 sort kernel tables
Date
On Fri, 19 Apr 2002 12:38:05 +0100, 
"Randal, Phil" <prandal@herefordshire.gov.uk> wrote:
>This variation on Quicksort seems superior... Must look at the libc
>sources someday to see how it does it...
>http://www.neubert.net/Flapaper/9802n.htm

It requires extra storage which is unacceptable. The kernel tables
must be sorted before any code that might take an exception is used.
The sort must be done very early, before kernel memory management is
setup. In addition, the kernel stack has a limited size.

If the extra data size depends on the number of elements to be sorted
(flashsort1 needs 0.1n extra data) then it cannot be used for this
task. Sooner or later the extra data size will blow the limited kernel
storage at boot time. For this task, the sort must use a small and
fixed amount of extra storage.

You realize that we have probably spent more time discussing the sort
algorithm than can be saved by rewriting the sort? The sort is invoked
once per boot on tables that are almost sorted already, any savings
will be in milliseconds and do not justify the extra programming
effort. I will use arch/ppc/mm/extable.c::sort_ex_table() instead of
bubble, anything beyond that is a waste of programming time.

-
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    [W:0.077 / U:0.880 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site