lkml.org 
[lkml]   [2005]   [Jan]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [patch 1/13] Qsort
Date
From
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/

\
 
 \ /
  Last update: 2005-03-22 14:09    [from the cache]
©2003-2014 Jasper Spaans. Advertise on this site