stdlib/FreeBSD/psort.3

   1 .\" Copyright (c) 1990, 1991, 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   4 .\" This code is derived from software contributed to Berkeley by
   5 .\" the American National Standards Committee X3, on Information
   6 .\" Processing Systems.
   7 .\"
   8 .\" Redistribution and use in source and binary forms, with or without
   9 .\" modification, are permitted provided that the following conditions
  10 .\" are met:
  11 .\" 1. Redistributions of source code must retain the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer.
  13 .\" 2. Redistributions in binary form must reproduce the above copyright
  14 .\"    notice, this list of conditions and the following disclaimer in the
  15 .\"    documentation and/or other materials provided with the distribution.
  16 .\" 4. Neither the name of the University nor the names of its contributors
  17 .\"    may be used to endorse or promote products derived from this software
  18 .\"    without specific prior written permission.
  19 .\"
  20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30 .\" SUCH DAMAGE.
  31 .\"
  32 .\"     @(#)qsort.3     8.1 (Berkeley) 6/4/93
  33 .\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $
  34 .\"
  35 .Dd Nov 25, 2008
  36 .Dt PSORT 3
  37 .Os "Mac OS X"
  38 .Sh NAME
  39 .Nm psort ,
  40 #ifdef UNIFDEF_BLOCKS
  41 .Nm psort_b ,
  42 #endif
  43 .Nm psort_r
  44 .Nd parallel sort functions
  45 .Sh SYNOPSIS
  46 .In stdlib.h
  47 .Ft void
  48 .Fo psort
  49 .Fa "void *base"
  50 .Fa "size_t nel"
  51 .Fa "size_t width"
  52 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  53 .Fc
  54 #ifdef UNIFDEF_BLOCKS
  55 .Ft void
  56 .Fo psort_b
  57 .Fa "void *base"
  58 .Fa "size_t nel"
  59 .Fa "size_t width"
  60 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  61 .Fc
  62 #endif
  63 .Ft void
  64 .Fo psort_r
  65 .Fa "void *base"
  66 .Fa "size_t nel"
  67 .Fa "size_t width"
  68 .Fa "void *thunk"
  69 .Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
  70 .Fc
  71 .Sh DESCRIPTION
  72 The
  73 #ifdef UNIFDEF_BLOCKS
  74 .Fn psort ,
  75 .Fn psort_b ,
  76 #else
  77 .Fn psort
  78 #endif
  79 and
  80 .Fn psort_r
  81 functions are parallel sort routines that are drop-in compatible with the
  82 corresponding
  83 .Fn qsort
  84 function (see
  85 .Xr qsort 3
  86 for a description of the arguments).
  87 On multiprocessor machines, multiple threads may be created to simultaneously
  88 perform the sort calculations, resulting in an overall faster sort result.
  89 Overhead in managing the threads limits the maximum speed improvement to
  90 somewhat less that the number of processors available.
  91 For example, on a 4-processor machine, a typical sort on a large array might
  92 result in 3.2 times faster sorting than a regular
  93 .Fn qsort .
  94 .Sh RESTRICTIONS
  95 Because of the multi-threaded nature of the sort, the comparison function
  96 is expected to perform its own synchronization that might be required for
  97 data physically
  98 .Em outside
  99 the two objects passed to the comparison function.
 100 However, no synchronization is required for the two
 101 object themselves, unless some third party is also accessing those objects.
 102 .Pp
 103 Additional memory is temporary allocated to deal with the parallel nature
 104 of the computation.
 105 .Pp
 106 Because of the overhead of maintaining multiple threads, the
 107 .Fn psort
 108 family of routines may choose to just call
 109 .Xr qsort 3
 110 when there is no advantage to parallelizing (for example, when the number of
 111 objects in the array is too small, or only one processor is available).
 112 .Pp
 113 Like
 114 .Xr qsort 3 ,
 115 the sort is not stable.
 116 .Sh RETURN VALUES
 117 The
 118 #ifdef UNIFDEF_BLOCKS
 119 .Fn psort ,
 120 .Fn psort_b
 121 #else
 122 .Fn psort
 123 #endif
 124 and
 125 .Fn psort_r
 126 functions
 127 return no value.
 128 .Sh SEE ALSO
 129 .Xr qsort 3
 130 .Sh SEE ALSO
 131 .Xr sort 1 ,
 132 .Xr radixsort 3
 133 .Rs
 134 .%A Hoare, C.A.R.
 135 .%D 1962
 136 .%T "Quicksort"
 137 .%J "The Computer Journal"
 138 .%V 5:1
 139 .%P pp. 10-15
 140 .Re
 141 .Rs
 142 .%A Williams, J.W.J
 143 .%D 1964
 144 .%T "Heapsort"
 145 .%J "Communications of the ACM"
 146 .%V 7:1
 147 .%P pp. 347-348
 148 .Re
 149 .Rs
 150 .%A Knuth, D.E.
 151 .%D 1968
 152 .%B "The Art of Computer Programming"
 153 .%V Vol. 3
 154 .%T "Sorting and Searching"
 155 .%P pp. 114-123, 145-149
 156 .Re
 157 .Rs
 158 .%A McIlroy, P.M.
 159 .%T "Optimistic Sorting and Information Theoretic Complexity"
 160 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 161 .%V January 1992
 162 .Re
 163 .Rs
 164 .%A Bentley, J.L.
 165 .%A McIlroy, M.D.
 166 .%T "Engineering a Sort Function"
 167 .%J "Software--Practice and Experience"
 168 .%V Vol. 23(11)
 169 .%P pp. 1249-1265
 170 .%D November\ 1993
 171 .Re
 172 .Sh STANDARDS
 173 The
 174 .Fn qsort
 175 function
 176 conforms to
 177 .St -isoC .