#196: STABLE-SORT is only stable for lists ------------------------------+--------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: new Priority: major | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Keywords: ansi-conformance | ------------------------------+--------------------------------------------- [http://article.gmane.org/gmane.lisp.armedbear.devel/2204 Jorge Tavares reports on armedbear-devel@]:
{{{ 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. }}}
#196: STABLE-SORT is only stable for lists --------------------------+------------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: closed Priority: major | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Resolution: fixed | Keywords: ansi-conformance --------------------------+------------------------------------------------- Changes (by mevenson):
* status: new => closed * resolution: => fixed
Comment:
Resolved by Jorge Tavares [r13852]
http://trac.common-lisp.net/armedbear/changeset/13852
#196: STABLE-SORT is only stable for lists --------------------------+------------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: reopened Priority: blocker | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Resolution: | Keywords: ansi-conformance --------------------------+------------------------------------------------- Changes (by mevenson):
* priority: major => blocker * status: closed => reopened * resolution: fixed =>
Comment:
Just noticed that the change of implementation for STABLE-SORT has induced the failure of the following ANSI tests:
{{{ STABLE-SORT-VECTOR.4 STABLE-SORT-VECTOR.6 STABLE-SORT-VECTOR.7 STABLE-SORT-VECTOR.8 STABLE-SORT-BIT-VECTOR.2 STABLE-SORT-BIT-VECTOR.3 STABLE-SORT-STRING.1 STABLE-SORT-STRING.2 STABLE-SORT-STRING.3 STABLE-SORT-STRING.4 }}}
Re-opening this ticket; marking as blocker for the abcl-1.1 release.
#196: STABLE-SORT is only stable for lists --------------------------+------------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: reopened Priority: blocker | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Resolution: | Keywords: ansi-conformance --------------------------+-------------------------------------------------
Comment(by mevenson):
(In [13870]) See #196: further patch for STABLE-SORT from Jorge Tavares.
easye: still seeing the ANSI failures, but this is a much more plausible "final" implementation with the appropiate optimizations which should be easier to fix modulo the possible hairy macro debugging part. But that's why they call it trunk, right?
I send in attach a patch with further improvements to sort and stable-sort for sequences other than lists. In short, the patch includes a merge sort for vectors. To allow different types I've written the algorithm using macros and these generate the appropriate code according to the vector type. This way the algorithm is in a single place avoiding duplication of code. The macros also take care of the situation of when no key is present, avoiding the use of unnecessary funcalls. The quicksort algorithm was also refactored in the same way.
I've tested the algorithms and they seem to be working correct. Stable sort is now considerably faster since the fix before converted the sequences to a list and used the sort-list function. I've made some benchmarking to verify how fast is sort and stable-sort. The tables with the results are also in a file sent in attach [1]. For stable-sort I've compare the current trunk version with the patched one while for sort I've compared 1.0.1, the trunk and with the patch. For unsorted vectors sort has a speed up of 7.5 from 1.0.1 and this considers only vectors of size 8 to 8192 (1.0.1 hits the worst-case quite fast). For stable-sort the speed up is around 90.2 from vectors of size 8 to 32768. The sort functions become even faster for the nearly sorted vectors. I think the tables clearly show t he speed-ups
Naturally these benchmarks cannot be used to draw definite conclusions since they lack rigorous testing but I think they can provide some indications. With this patch, I think ABCL gets good performant sorting functions, especially for large vectors. As for lists, I haven't looked at them so probably they can also be improved (but I really don't know).
Cheers, Jorge
[1] The tables result from the generation of simple-vectors of sizes 8 to 524288 (powers of 2 from 3 to 19) with distinct integer: unsorted, nearly sorted (distances 0, 4 and 16), sorted and reversed sorted. The nearly sorted vectors were constructed by selecting pairs where they would swap with a neighbor at a certain distance. I did 100 runs and timed only the sorting operation. The tables contain the averages of the 100 runs. They were performed in an iMac (2.5GHz i5, 4GB) with Mac OS X 10.7.3.
[1]: http://article.gmane.org/gmane.lisp.armedbear.devel/2220
#196: STABLE-SORT is only stable for lists --------------------------+------------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: reopened Priority: blocker | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Resolution: | Keywords: ansi-conformance --------------------------+-------------------------------------------------
Comment(by https://www.google.com/accounts/o8/id?id=aitoawnthushznrlieuamks3fxvzisibfmu...):
After the [http://article.gmane.org/gmane.lisp.armedbear.devel/2220 further patch from Jorge of 11-FEB-2012] commited in r13870 , easye still sees errors from the ANSI, something about unexpected types: {{{ Test STABLE-SORT-VECTOR.4 failed Form: (LET ((A (MAKE-ARRAY 10 :INITIAL-CONTENTS (QUOTE (10 40 20 50 30 15 45 25 55 35)) :FILL-POINTER 5))) (STABLE-SORT A (FUNCTION <))) Expected value: #(10 20 30 40 50) Actual value: #<TYPE-ERROR {678042C2}> [The value #(10 40 20 50 30) is not of type SIMPLE-VECTOR.] Test STABLE-SORT-VECTOR.6 failed Form: (DO-SPECIAL-INTEGER-VECTORS (V #(1 4 7 3 2 6 5) NIL) (LET ((SV (STABLE-SORT V (FUNCTION <)))) (ASSERT (EQUALP SV #(1 2 3 4 5 6 7))))) Expected value:
}}}
#196: STABLE-SORT is only stable for lists --------------------------+------------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: reopened Priority: blocker | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Resolution: | Keywords: ansi-conformance --------------------------+-------------------------------------------------
Comment(by mevenson):
(In [13873]) Restore autoload CL:MERGE as part of ANSI sort triage (See #196).
This was mistakenly removed as part of Jorge Tavares' last commit.
As an optimization, we attempt to invoke the original quicksort implementation if the new one fails while emitting a warning to the user.
#196: STABLE-SORT is only stable for lists --------------------------+------------------------------------------------- Reporter: mevenson | Owner: ehuelsmann Type: defect | Status: closed Priority: blocker | Milestone: 1.1.0 Component: interpreter | Version: 1.0.1 Resolution: fixed | Keywords: ansi-conformance --------------------------+------------------------------------------------- Changes (by mevenson):
* status: reopened => closed * resolution: => fixed
Comment:
(In [13931]) Fixes #196: STABLE-SORT is only stable for lists.
Somewhat kludgily fix the macrology submitted by Jorge Tavares to pass all the newly failing ANSI tests introduced. The macrology of MERGE-VECTORS-BODY and MERGE-SORT-BODY required that the sequences were of type SIMPLE-VECTOR. But somehow, MERGE-SORT-BODY was not working when asked to stable sort sequences of type BIT-VECTOR or STRING, both of which are subtypes of VECTOR but not SIMPLE-VECTOR.
armedbear-ticket@common-lisp.net
-
armedbear