src/code/sort.lisp

   1 ;;;; SORT and friends
   2
   3 ;;;; This software is part of the SBCL system. See the README file for
   4 ;;;; more information.
   5 ;;;;
   6 ;;;; This software is derived from the CMU CL system, which was
   7 ;;;; written at Carnegie Mellon University and released into the
   8 ;;;; public domain. The software is in the public domain and is
   9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
  10 ;;;; files for more information.
  11
  12 (in-package "SB!IMPL")
  13
  14 (defun sort-vector (vector start end predicate-fun key-fun-or-nil)
  15   (sort-vector vector start end predicate-fun key-fun-or-nil))
  16
  17 ;;; This is MAYBE-INLINE because it's not too hard to have an
  18 ;;; application where sorting is a major bottleneck, and inlining it
  19 ;;; allows the compiler to make enough optimizations that it might be
  20 ;;; worth the (large) cost in space.
  21 (declaim (maybe-inline sort stable-sort))
  22 (defun sort (sequence predicate &rest args &key key)
  23   "Destructively sort SEQUENCE. PREDICATE should return non-NIL if
  24    ARG1 is to precede ARG2."
  25   (declare (truly-dynamic-extent args))
  26   (let ((predicate-fun (%coerce-callable-to-fun predicate)))
  27     (seq-dispatch sequence
  28       (stable-sort-list sequence
  29                         predicate-fun
  30                         (if key (%coerce-callable-to-fun key) #'identity))
  31       (let ((key-fun-or-nil (and key (%coerce-callable-to-fun key))))
  32         (with-array-data ((vector (the vector sequence))
  33                           (start)
  34                           (end)
  35                           :check-fill-pointer t)
  36           (sort-vector vector start end predicate-fun key-fun-or-nil))
  37         sequence)
  38       (apply #'sb!sequence:sort sequence predicate args))))
  39 \f
  40 ;;;; stable sorting
  41 (defun stable-sort (sequence predicate &rest args &key key)
  42   "Destructively sort SEQUENCE. PREDICATE should return non-NIL if
  43    ARG1 is to precede ARG2."
  44   (declare (truly-dynamic-extent args))
  45   (let ((predicate-fun (%coerce-callable-to-fun predicate)))
  46     (seq-dispatch sequence
  47       (stable-sort-list sequence
  48                         predicate-fun
  49                         (if key (%coerce-callable-to-fun key) #'identity))
  50       (if (typep sequence 'simple-vector)
  51           (stable-sort-simple-vector sequence
  52                                      predicate-fun
  53                                      (and key (%coerce-callable-to-fun key)))
  54           (stable-sort-vector sequence
  55                               predicate-fun
  56                               (and key (%coerce-callable-to-fun key))))
  57       (apply #'sb!sequence:stable-sort sequence predicate args))))
  58 \f
  59 ;;; FUNCALL-USING-KEY saves us a function call sometimes.
  60 (eval-when (:compile-toplevel :execute)
  61   (sb!xc:defmacro funcall2-using-key (pred key one two)
  62     `(if ,key
  63          (funcall ,pred (funcall ,key ,one)
  64                   (funcall ,key  ,two))
  65          (funcall ,pred ,one ,two)))
  66 ) ; EVAL-WHEN
  67 \f
  68 ;;;; stable sort of lists
  69 (declaim (maybe-inline merge-lists* stable-sort-list))
  70
  71 ;;; Destructively merge LIST-1 with LIST-2 (given that they're already
  72 ;;; sorted w.r.t. PRED-FUN on KEY-FUN, giving output sorted the same
  73 ;;; way). In the resulting list, elements of LIST-1 are guaranteed to
  74 ;;; come before equal elements of LIST-2.
  75 ;;;
  76 ;;; Enqueues the values in the right order in HEAD's cdr, and returns
  77 ;;; the merged list.
  78 (defun merge-lists* (head list1 list2 test key &aux (tail head))
  79   (declare (type cons head list1 list2)
  80            (type function test key)
  81            (optimize speed))
  82   (let ((key1 (funcall key (car list1)))
  83         (key2 (funcall key (car list2))))
  84     (macrolet ((merge-one (l1 k1 l2)
  85                  `(progn
  86                     (setf (cdr tail) ,l1
  87                           tail       ,l1)
  88                     (let ((rest (cdr ,l1)))
  89                       (cond (rest
  90                              (setf ,l1 rest
  91                                    ,k1 (funcall key (first rest))))
  92                             (t
  93                              (setf (cdr ,l1) ,l2)
  94                              (return (cdr head))))))))
  95       (loop
  96        (if (funcall test key2           ; this way, equivalent
  97                          key1)          ; values are first popped
  98            (merge-one list2 key2 list1) ; from list1
  99            (merge-one list1 key1 list2))))))
 100
 101 ;;; Convenience wrapper for CL:MERGE
 102 (declaim (inline merge-lists))
 103 (defun merge-lists (list1 list2 test key)
 104   (cond ((null list1)
 105          list2)
 106         ((null list2)
 107          list1)
 108         (t
 109          (let ((head (cons nil nil)))
 110            (declare (dynamic-extent head))
 111            (merge-lists* head list1 list2 test key)))))
 112
 113 ;;; Small specialised stable sorts
 114 (declaim (inline stable-sort-list-2 stable-sort-list-3))
 115 (defun stable-sort-list-2 (list test key)
 116   (declare (type cons list)
 117            (type function test key))
 118   (let ((second (cdr list)))
 119     (declare (type cons second))
 120     (when (funcall test (funcall key (car second))
 121                         (funcall key (car list)))
 122       (rotatef (car list) (car second)))
 123     (values list second (shiftf (cdr second) nil))))
 124
 125 (defun stable-sort-list-3 (list test key)
 126   (declare (type cons list)
 127            (type function test key))
 128   (let* ((second (cdr list))
 129          (third  (cdr second))
 130          (x (car list))
 131          (y (car second))
 132          (z (car third)))
 133     (declare (type cons second third))
 134     (when (funcall test (funcall key y)
 135                         (funcall key x))
 136       (rotatef x y))
 137     (let ((key-z (funcall key z)))
 138       (when (funcall test key-z
 139                           (funcall key y))
 140         (if (funcall test key-z
 141                           (funcall key x))
 142             (rotatef x z y)
 143             (rotatef z y))))
 144     (setf (car list)   x
 145           (car second) y
 146           (car third)  z)
 147     (values list third (shiftf (cdr third) nil))))
 148
 149 ;;; STABLE-SORT-LIST implements a top-down merge sort. See the closest
 150 ;;; intro to algorithms book.  Benchmarks have shown significantly
 151 ;;; improved performance over the previous (hairier) bottom-up
 152 ;;; implementation, particularly on non-power-of-two sizes: bottom-up
 153 ;;; recursed on power-of-two-sized subsequences, which can result in
 154 ;;; very unbalanced recursion trees.
 155
 156 ;;; The minimum length at which list merge sort will try and detect
 157 ;;; it can merge disjoint ranges (e.g. sorted inputs) in constant time.
 158 (defconstant +stable-sort-fast-merge-limit+ 8)
 159
 160 (defun stable-sort-list (list test key &aux (head (cons :head list)))
 161   (declare (type list list)
 162            (type function test key)
 163            (dynamic-extent head))
 164   (declare (explicit-check))
 165   (labels ((merge* (size list1 tail1 list2 tail2 rest)
 166              (declare (optimize speed)
 167                       (type (and fixnum unsigned-byte) size)
 168                       (type cons list1 tail1 list2 tail2))
 169              (when (>= size +stable-sort-fast-merge-limit+)
 170                (cond ((not (funcall test (funcall key (car list2))   ; stability
 171                                          (funcall key (car tail1)))) ; trickery
 172                       (setf (cdr tail1) list2)
 173                       (return-from merge* (values list1 tail2 rest)))
 174                      ((funcall test (funcall key (car tail2))
 175                                     (funcall key (car list1)))
 176                       (setf (cdr tail2) list1)
 177                       (return-from merge* (values list2 tail1 rest)))))
 178                (values (merge-lists* head list1 list2 test key)
 179                        (if (null (cdr tail1))
 180                            tail1
 181                            tail2)
 182                        rest))
 183            (recur (list size)
 184              (declare (optimize speed)
 185                       (type cons list)
 186                       (type (and fixnum unsigned-byte) size))
 187              (cond ((> size 3)
 188                     (let ((half (ash size -1)))
 189                       (multiple-value-bind (list1 tail1 rest)
 190                           (recur list half)
 191                         (multiple-value-bind (list2 tail2 rest)
 192                             (recur rest (- size half))
 193                           (merge* size list1 tail1 list2 tail2 rest)))))
 194                    ((= size 3)
 195                     (stable-sort-list-3 list test key))
 196                    ((= size 2)
 197                     (stable-sort-list-2 list test key))
 198                    (t ; (= size 1)
 199                     (values list list (shiftf (cdr list) nil))))))
 200     (when list
 201       (values (recur list (length list))))))
 202 \f
 203 ;;;; stable sort of vectors
 204
 205 ;;; Stable sorting vectors is done with the same algorithm used for
 206 ;;; lists, using a temporary vector to merge back and forth between it
 207 ;;; and the given vector to sort.
 208
 209 (eval-when (:compile-toplevel :execute)
 210
 211 ;;; STABLE-SORT-MERGE-VECTORS* takes a source vector with subsequences,
 212 ;;;    start-1 (inclusive) ... end-1 (exclusive) and
 213 ;;;    end-1 (inclusive) ... end-2 (exclusive),
 214 ;;; and merges them into a target vector starting at index start-1.
 215
 216 (sb!xc:defmacro stable-sort-merge-vectors* (source target start-1 end-1 end-2
 217                                                      pred key source-ref
 218                                                      target-ref)
 219   (let ((i (gensym))
 220         (j (gensym))
 221         (target-i (gensym)))
 222     `(let ((,i ,start-1)
 223            (,j ,end-1) ; start-2
 224            (,target-i ,start-1))
 225        (declare (fixnum ,i ,j ,target-i))
 226        (loop
 227         (cond ((= ,i ,end-1)
 228                (loop (if (= ,j ,end-2) (return))
 229                      (setf (,target-ref ,target ,target-i)
 230                            (,source-ref ,source ,j))
 231                      (incf ,target-i)
 232                      (incf ,j))
 233                (return))
 234               ((= ,j ,end-2)
 235                (loop (if (= ,i ,end-1) (return))
 236                      (setf (,target-ref ,target ,target-i)
 237                            (,source-ref ,source ,i))
 238                      (incf ,target-i)
 239                      (incf ,i))
 240                (return))
 241               ((funcall2-using-key ,pred ,key
 242                                    (,source-ref ,source ,j)
 243                                    (,source-ref ,source ,i))
 244                (setf (,target-ref ,target ,target-i)
 245                      (,source-ref ,source ,j))
 246                (incf ,j))
 247               (t (setf (,target-ref ,target ,target-i)
 248                        (,source-ref ,source ,i))
 249                  (incf ,i)))
 250         (incf ,target-i)))))
 251
 252 ;;; VECTOR-MERGE-SORT is the same algorithm used to stable sort lists,
 253 ;;; but it uses a temporary vector. DIRECTION determines whether we
 254 ;;; are merging into the temporary (T) or back into the given vector
 255 ;;; (NIL).
 256 (sb!xc:defmacro vector-merge-sort (vector pred key vector-ref)
 257   (with-unique-names
 258       (vector-len n direction unsorted start-1 end-1 end-2 temp i)
 259     `(let* ((,vector-len (length (the vector ,vector)))
 260             (,n 1)            ; bottom-up size of contiguous runs to be merged
 261             (,direction t)    ; t vector --> temp    nil temp --> vector
 262             (,temp (make-array ,vector-len))
 263             (,unsorted 0)   ; unsorted..vector-len are the elements that need
 264                                         ; to be merged for a given n
 265             (,start-1 0))   ; one n-len subsequence to be merged with the next
 266        (declare (fixnum ,vector-len ,n ,unsorted ,start-1)
 267                 (simple-vector ,temp))
 268        (loop
 269          ;; for each n, we start taking n-runs from the start of the vector
 270          (setf ,unsorted 0)
 271          (loop
 272            (setf ,start-1 ,unsorted)
 273            (let ((,end-1 (+ ,start-1 ,n)))
 274              (declare (fixnum ,end-1))
 275              (cond ((< ,end-1 ,vector-len)
 276                     ;; there are enough elements for a second run
 277                     (let ((,end-2 (+ ,end-1 ,n)))
 278                       (declare (fixnum ,end-2))
 279                       (if (> ,end-2 ,vector-len) (setf ,end-2 ,vector-len))
 280                       (setf ,unsorted ,end-2)
 281                       (if ,direction
 282                           (stable-sort-merge-vectors*
 283                            ,vector ,temp
 284                            ,start-1 ,end-1 ,end-2 ,pred ,key ,vector-ref svref)
 285                           (stable-sort-merge-vectors*
 286                            ,temp ,vector
 287                            ,start-1 ,end-1 ,end-2 ,pred ,key svref ,vector-ref))
 288                       (if (= ,unsorted ,vector-len) (return))))
 289                    ;; if there is only one run, copy those elements to the end
 290                    (t (if ,direction
 291                           (do ((,i ,start-1 (1+ ,i)))
 292                               ((= ,i ,vector-len))
 293                             (declare (fixnum ,i))
 294                             (setf (svref ,temp ,i) (,vector-ref ,vector ,i)))
 295                           (do ((,i ,start-1 (1+ ,i)))
 296                               ((= ,i ,vector-len))
 297                             (declare (fixnum ,i))
 298                             (setf (,vector-ref ,vector ,i) (svref ,temp ,i))))
 299                       (return)))))
 300          ;; If the inner loop only executed once, then there were only enough
 301          ;; elements for two subsequences given n, so all the elements have
 302          ;; been merged into one list. Start-1 will have remained 0 upon exit.
 303          (when (zerop ,start-1)
 304            (when ,direction
 305              ;; if we just merged into the temporary, copy it all back
 306              ;; to the given vector.
 307              (dotimes (,i ,vector-len)
 308                (setf (,vector-ref ,vector ,i) (svref ,temp ,i))))
 309            ;; Kill the new vector to prevent garbage from being retained.
 310            (%shrink-vector ,temp 0)
 311            (return ,vector))
 312          (setf ,n (ash ,n 1))           ; (* 2 n)
 313          (setf ,direction (not ,direction))))))
 314
 315 ) ; EVAL-when
 316
 317 (defun stable-sort-simple-vector (vector pred key)
 318   (declare (type simple-vector vector)
 319            (type function pred)
 320            (type (or null function) key))
 321   (declare (explicit-check))
 322   (vector-merge-sort vector pred key svref))
 323
 324 (defun stable-sort-vector (vector pred key)
 325   (declare (type function pred)
 326            (type (or null function) key))
 327   (declare (explicit-check))
 328   (vector-merge-sort vector pred key aref))
 329 \f
 330 ;;;; merging
 331
 332 (eval-when (:compile-toplevel :execute)
 333
 334 ;;; MERGE-VECTORS returns a new vector which contains an interleaving
 335 ;;; of the elements of VECTOR-1 and VECTOR-2. Elements from VECTOR-2
 336 ;;; are chosen only if they are strictly less than elements of
 337 ;;; VECTOR-1, (PRED ELT-2 ELT-1), as specified in the manual.
 338 (sb!xc:defmacro merge-vectors (vector-1 length-1 vector-2 length-2
 339                                result-vector pred key access)
 340   (let ((result-i (gensym))
 341         (i (gensym))
 342         (j (gensym)))
 343     `(let* ((,result-i 0)
 344             (,i 0)
 345             (,j 0))
 346        (declare (fixnum ,result-i ,i ,j))
 347        (loop
 348         (cond ((= ,i ,length-1)
 349                (loop (if (= ,j ,length-2) (return))
 350                      (setf (,access ,result-vector ,result-i)
 351                            (,access ,vector-2 ,j))
 352                      (incf ,result-i)
 353                      (incf ,j))
 354                (return ,result-vector))
 355               ((= ,j ,length-2)
 356                (loop (if (= ,i ,length-1) (return))
 357                      (setf (,access ,result-vector ,result-i)
 358                            (,access ,vector-1 ,i))
 359                      (incf ,result-i)
 360                      (incf ,i))
 361                (return ,result-vector))
 362               ((funcall2-using-key ,pred ,key
 363                                    (,access ,vector-2 ,j) (,access ,vector-1 ,i))
 364                (setf (,access ,result-vector ,result-i)
 365                      (,access ,vector-2 ,j))
 366                (incf ,j))
 367               (t (setf (,access ,result-vector ,result-i)
 368                        (,access ,vector-1 ,i))
 369                  (incf ,i)))
 370         (incf ,result-i)))))
 371
 372 ) ; EVAL-WHEN
 373
 374 (defun merge (result-type sequence1 sequence2 predicate &key key)
 375   "Merge the sequences SEQUENCE1 and SEQUENCE2 destructively into a
 376    sequence of type RESULT-TYPE using PREDICATE to order the elements."
 377   ;; FIXME: This implementation is remarkably inefficient in various
 378   ;; ways. In decreasing order of estimated user astonishment, I note:
 379   ;; full calls to SPECIFIER-TYPE at runtime; copying input vectors
 380   ;; to lists before doing MERGE-LISTS -- WHN 2003-01-05
 381   (declare (explicit-check))
 382   (let ((type (specifier-type result-type))
 383         (pred-fun (%coerce-callable-to-fun predicate))
 384         ;; Avoid coercing NIL to a function since 2 out of 3 branches of the
 385         ;; COND below optimize for NIL as the key function. Additionally
 386         ;; recognize the reverse - when you said #'IDENTITY which can be
 387         ;; turned into NIL. Also, in the generic case, don't defer a
 388         ;; type error to the method (even though it also coerces to fun).
 389         (key-fun (when (and key (neq key #'identity))
 390                    (%coerce-callable-to-fun key))))
 391     (cond
 392       ((csubtypep type (specifier-type 'list))
 393        ;; the VECTOR clause, below, goes through MAKE-SEQUENCE, so
 394        ;; benefits from the error checking there. Short of
 395        ;; reimplementing everything, we can't do the same for the LIST
 396        ;; case, so do relevant length checking here:
 397        (let ((s1 (coerce sequence1 'list))
 398              (s2 (coerce sequence2 'list))
 399              ;; MERGE-LISTS* does not contain special code for KEY = NIL.
 400              (key-fun (or key-fun #'identity)))
 401          (when (type= type (specifier-type 'list))
 402            (return-from merge (merge-lists s1 s2 pred-fun key-fun)))
 403          (when (eq type *empty-type*)
 404            (bad-sequence-type-error nil))
 405          (when (type= type (specifier-type 'null))
 406            (if (and (null s1) (null s2))
 407                (return-from merge 'nil)
 408                ;; FIXME: This will break on circular lists (as,
 409                ;; indeed, will the whole MERGE function).
 410                (sequence-type-length-mismatch-error type
 411                                                     (+ (length s1)
 412                                                        (length s2)))))
 413          (if (cons-type-p type)
 414              (multiple-value-bind (min exactp)
 415                  (sb!kernel::cons-type-length-info type)
 416                (let ((length (+ (length s1) (length s2))))
 417                  (if exactp
 418                      (unless (= length min)
 419                        (sequence-type-length-mismatch-error type length))
 420                      (unless (>= length min)
 421                        (sequence-type-length-mismatch-error type length)))
 422                  (merge-lists s1 s2 pred-fun key-fun)))
 423              (sequence-type-too-hairy result-type))))
 424       ((csubtypep type (specifier-type 'vector))
 425        (let* ((vector-1 (coerce sequence1 'vector))
 426               (vector-2 (coerce sequence2 'vector))
 427               (length-1 (length vector-1))
 428               (length-2 (length vector-2))
 429               (result (make-sequence result-type (+ length-1 length-2))))
 430          (if (and (simple-vector-p result)
 431                   (simple-vector-p vector-1)
 432                   (simple-vector-p vector-2))
 433              (merge-vectors vector-1 length-1 vector-2 length-2
 434                             result pred-fun key-fun svref)
 435              ;; Some things that could improve the fancy vector case:
 436              ;; - recognize when the only fancy aspect of both inputs
 437              ;;   is that they have fill pointers.
 438              ;; - use the specialized reffer for inputs + output
 439              (merge-vectors vector-1 length-1 vector-2 length-2
 440                             result pred-fun key-fun aref))))
 441       ((when-extended-sequence-type
 442            (result-type type :expandedp nil :prototype prototype)
 443          ;; This function has the EXPLICIT-CHECK declaration, so we
 444          ;; manually assert that it returns a SEQUENCE.
 445          (the extended-sequence
 446               ;; GF dispatch deals with the erroneous situation
 447               ;; wherein either of SEQUENCE1 or SEQUENCE2 is not a
 448               ;; sequence.  Note that the one builtin method optimizes
 449               ;; for NIL as the key fun, and we correctly preserve a
 450               ;; NIL here.
 451               (sb!sequence:merge
 452                prototype sequence1 sequence2 pred-fun :key key-fun))))
 453       (t (bad-sequence-type-error result-type)))))