Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Fri, 19 Apr 2002 12:38:05 +0100, 
"Randal, Phil" <[e-mail]> 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.