| Subject | Re: [patch 1/13] Qsort | Date | Mon, 24 Jan 2005 00:48:45 -0300 | From | Horst von Brand <> |
| |
Andreas Gruenbacher <agruen@suse.de> said: > Signed-off-by: Andreas Gruenbacher <agruen@suse.de> > Acked-by: Olaf Kirch <okir@suse.de>
[...]
> +/* Order size using quicksort. This implementation incorporates > + four optimizations discussed in Sedgewick: > + > + 1. Non-recursive, using an explicit stack of pointer that store the > + next array partition to sort. To save time, this maximum amount > + of space required to store an array of SIZE_MAX is allocated on the > + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs > + only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). > + Pretty cheap, actually.
Not really, given the strict size restrictions in-kernel.
Has there been any comparison between the original and this one? Code size, stack use, speed, ...? -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513 - 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/
|