manpagez: man pages & more
man psort_r(3)
Home | html | info | man
psort(3)                 BSD Library Functions Manual                 psort(3)


NAME

     psort, psort_b, psort_r -- parallel sort functions


SYNOPSIS

     #include <stdlib.h>

     void
     psort(void *base, size_t nel, size_t width,
         int (*compar)(const void *, const void *));

     void
     psort_b(void *base, size_t nel, size_t width,
         int (^compar)(const void *, const void *));

     void
     psort_r(void *base, size_t nel, size_t width, void *thunk,
         int (*compar)(void *, const void *, const void *));


DESCRIPTION

     The psort(), psort_b(), and psort_r() functions are parallel sort rou-
     tines that are drop-in compatible with the corresponding qsort() function
     (see qsort(3) for a description of the arguments).  On multiprocessor
     machines, multiple threads may be created to simultaneously perform the
     sort calculations, resulting in an overall faster sort result.  Overhead
     in managing the threads limits the maximum speed improvement to somewhat
     less that the number of processors available.  For example, on a 4-pro-
     cessor machine, a typical sort on a large array might result in 3.2 times
     faster sorting than a regular qsort().


RESTRICTIONS

     Because of the multi-threaded nature of the sort, the comparison function
     is expected to perform its own synchronization that might be required for
     data physically outside the two objects passed to the comparison func-
     tion.  However, no synchronization is required for the two object them-
     selves, unless some third party is also accessing those objects.

     Additional memory is temporary allocated to deal with the parallel nature
     of the computation.

     Because of the overhead of maintaining multiple threads, the psort() fam-
     ily of routines may choose to just call qsort(3) when there is no advan-
     tage to parallelizing (for example, when the number of objects in the
     array is too small, or only one processor is available).

     Like qsort(3), the sort is not stable.


RETURN VALUES

     The psort(), psort_b() and psort_r() functions return no value.


SEE ALSO

     qsort(3)


SEE ALSO

     sort(1), radixsort(3)

     Hoare, C.A.R., "Quicksort", The Computer Journal, 5:1, pp. 10-15, 1962.

     Williams, J.W.J, "Heapsort", Communications of the ACM, 7:1, pp. 347-348,
     1964.

     Knuth, D.E., "Sorting and Searching", The Art of Computer Programming,
     Vol. 3, pp. 114-123, 145-149, 1968.

     McIlroy, P.M., "Optimistic Sorting and Information Theoretic Complexity",
     Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992.

     Bentley, J.L.  and McIlroy, M.D., "Engineering a Sort Function",
     Software--Practice and Experience, Vol. 23(11), pp. 1249-1265,
     November 1993.


STANDARDS

     The qsort() function conforms to ISO/IEC 9899:1990 (``ISO C90'').

Mac OS X                         Nov 25, 2008                         Mac OS X

Mac OS X 10.8 - Generated Wed Aug 29 19:46:54 CDT 2012
© manpagez.com 2000-2024
Individual documents may contain additional copyright information.