Re: [patch 1/13] Qsort

[Horst von Brand]

Andreas Gruenbacher <agruen@xxxxxxx> said:
> Signed-off-by: Andreas Gruenbacher <agruen@xxxxxxx>
> Acked-by: Olaf Kirch <okir@xxxxxxx>

[...]

> +/* 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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/