Dear Simon,
You note:
On the other hand when sorting it
again, i.e. when the vector is already fully sorter, Emacs is quite a
bit faster than SBCL—maybe Emacs chose to optimize for partly-sorted
vectors at the expense of a bit of performance for random input.
You are so right. 'msa' kills 'stable sort' on a few examples, namely an array
that is all 0's and an array that is 1, 2, 3, ...
Below is some info on sorting arrays that are 21 million long.
But I should mention that I regard what my 'msa' does to catch the easy cases may be nothing in comparison to what sorting pros can do.
Best,
Bob
Running (test-msa-0 21,000,000).
Timing (MSA TEST-MSA-AR1 '< :KEY 'CAR).
WARNING: redefining COMMON-LISP-USER::KEY in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-EQUAL in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-PREDICATE in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-1 in DEFUN
Evaluation took:
3.334 seconds of real time
3.267129 seconds of total run time (2.323391 user, 0.943738 system)
[ Run times consist of 0.154 seconds GC time, and 3.114 seconds non-GC time. ]
97.99% CPU
31 forms interpreted
115 lambdas converted
5,990,145,243 processor cycles
174,860,640 bytes consed
Timing (STABLE-SORT TEST-MSA-AR2 '< :KEY 'CAR).
Evaluation took:
12.729 seconds of real time
12.562949 seconds of total run time (11.935063 user, 0.627886 system)
[ Run times consist of 0.232 seconds GC time, and 12.331 seconds non-GC time. ]
98.70% CPU
22,870,125,432 processor cycles
168,006,352 bytes consed
Running (test-msa-ascending 21,000,000).
Timing (MSA TEST-MSA-AR1 '< :KEY 'CAR).
WARNING: redefining COMMON-LISP-USER::KEY in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-EQUAL in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-PREDICATE in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-1 in DEFUN
Evaluation took:
2.525 seconds of real time
2.514507 seconds of total run time (2.471494 user, 0.043013 system)
99.60% CPU
31 forms interpreted
115 lambdas converted
4,536,551,428 processor cycles
6,823,488 bytes consed
Timing (STABLE-SORT TEST-MSA-AR2 '< :KEY 'CAR).
Evaluation took:
12.914 seconds of real time
12.823063 seconds of total run time (12.407732 user, 0.415331 system)
[ Run times consist of 0.227 seconds GC time, and 12.597 seconds non-GC time. ]
99.30% CPU
23,203,467,086 processor cycles
168,006,128 bytes consed