Dear ABCL developers,
Recently I started to investigate the different CL sort implementations and found that stable-sort in ABCL does not execute as required. The problem is that stable-sort is only stable for lists and not for all type of sequences (i.e., elements considered equal by the predicate should stay in their original order).
A very simple test shows this error:
idesk:~ jast$ abcl Armed Bear Common Lisp 1.0.1 Java 1.6.0_29 Apple Inc. Java HotSpot(TM) 64-Bit Server VM Low-level initialization completed in 0.399 seconds. Startup completed in 1.069 seconds. Loading /Users/jast/.abclrc completed in 4.8 seconds. Type ":help" for a list of available commands. CL-USER(1): (defparameter *stuff* #((1 0.31648433) (0 0.2704757) (0 0.48931926) (1 0.9958766) (0 0.49251676))) *STUFF* CL-USER(2): (setf *stuff* (stable-sort *stuff* #'< :key #'first)) #((0 0.49251676) (0 0.2704757) (0 0.48931926) (1 0.31648433) (1 0.9958766))
The above test is short and simple to understand: *stuff* contains an array where each element is a pair. The first element of a pair is the key and the second the data. With this in mind, the expected result should have been: #((0 0.2704757) (0 0.48931926) (0 0.49251676) (1 0.31648433) (1 0.9958766)).
The same error happens with larger arrays and other types of data. I also tested it in SBCL, CCL, ECL and CLisp and for these implementations the results are the expected. Only ABCL differs form the major open source implementations (I didn't test in ACL or LW).
The reason for this bug is actually quite simple. In sort.lisp, in the definition of stable-sort, seq-dispatch calls for the non-list sequences the quicksort algorithm, which is not stable. For lists it calls merge sort (which is stable) and the problem does not arise.
As a quick fix, I send in attach a patch that uses in stable-sort merge sort for all sequences. This is done by coercing the sequence to list, calling merge sort and coercing it back to the original sequence type. However, as a long term improvement, the best solution would be to implement a merge sort for non-list sequences.
Cheers, Jorge Tavares
On Jan 31, 2012, at 16:54 , Jorge Tavares wrote:
Dear ABCL developers,
Recently I started to investigate the different CL sort implementations and found that stable-sort in ABCL does not execute as required. The problem is that stable-sort is only stable for lists and not for all type of sequences (i.e., elements considered equal by the predicate should stay in their original order).
Filed as [ticket #196][#196] with your [patch committed in r13838][r13838].
Thanks for the succinct report, test case, and quick patch!
[#196]: http://trac.common-lisp.net/armedbear/ticket/196 [r13838]: http://trac.common-lisp.net/armedbear/changeset/13838
On Wednesday, February 1, 2012 at 09:26 , Mark Evenson wrote:
On Jan 31, 2012, at 16:54 , Jorge Tavares wrote:
Dear ABCL developers,
Recently I started to investigate the different CL sort implementations and found that stable-sort in ABCL does not execute as required. The problem is that stable-sort is only stable for lists and not for all type of sequences (i.e., elements considered equal by the predicate should stay in their original order).
Filed as [ticket #196][#196] with your [patch committed in r13838][r13838].
Thanks for the succinct report, test case, and quick patch!
Thanks! It's only a quick fix. I will see if I can prepare a better solution for the long term.
Cheers, Jorge Tavares
armedbear-devel@common-lisp.net
-
Jorge Tavares -
Mark Evenson