Messages in this thread | | | From | Keith Owens <> | Subject | Re: [RFC] 2.5.8 sort kernel tables | Date | Sat, 20 Apr 2002 15:19:15 +1000 |
| |
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/
| |