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    [W:0.019 / U:30.372 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site