New inline stable sort for vectors (!28) · Merge requests · Embeddable Common-Lisp / ECL

This PR should improve on the current stable sorting of vectors, fixing issues such as #217 (closed) (bug) and #101 (closed) (performance).

Full disclosure: The merge sort algorithm was completely stolen from sbcl.

I'm sure the new version can be optimized, for example by inlining stable-sort-merge-vectors, and by treating simple-arrays differently.

But for now, it already has slightly better performance on the sequences that I tested with, for example running:

(time (dotimes (x 50000)
	(defparameter *my-arr* 
		(make-array 9 :initial-contents
		(list
		  (cons 3 'a)
		  (cons 2 'b)
		  (cons 2 'c)
		  (cons 2 'd)
		  (cons 3 'e)
		  (cons 2 'f)
		  (cons 2 'g)
		  (cons 2 'h)
		  (cons 1 'i))))

	(stable-sort *my-arr* #'< :key #'car)))

gave me 0.34 sec in the old version, and 0.28sec in the new one (even with the overhead of the make-array call, which is the same for both). But most importantly, the new version leaves the array sorted, which fixes bug #217 (closed):

> *my-arr*
#A(T (9) ((1 . I) (2 . B) (2 . C) (2 . D) (2 . F) (2 . G) (2 . H) (3 . A) (3 . E)))

while in the old-version:

> *my-arr*
#A(T (9) ((3 . A) (2 . B) (2 . C) (2 . D) (3 . E) (2 . F) (2 . G) (2 . H) (1 . I)))

The example in #217 (closed) also works now, of course:

> (let ((a (copy-seq "BCA")))
        (stable-sort a #'char<)
        a)

"ABC"

New inline stable sort for vectors

Merge request reports