Hi,
I'm sending a patch that solves the issue reported in ticket #187. The quicksort function picks the pivot by selecting a midpoint and also sorts the smaller partition first. These are enough to avoid the stack overflow problem as reported. I've performed some tests and it looks it is correct.
Below I include a sample session, including the test case in the ticket:
idesk:abcl jast$ ./abcl Armed Bear Common Lisp 1.1.0-dev-svn-13848M Java 1.6.0_29 Apple Inc. Java HotSpot(TM) 64-Bit Server VM Low-level initialization completed in 0.307 seconds. Startup completed in 0.945 seconds. Loading /Users/jast/.abclrc completed in 4.528 seconds. Type ":help" for a list of available commands. CL-USER(1): (ql:quickload "alexandria") To load "alexandria": Load 1 ASDF system: alexandria ; Loading "alexandria" ("alexandria") CL-USER(2): (defparameter *sorted* (make-array 1000000 :initial-contents (alexandria:iota 1000000))) *SORTED* CL-USER(3): (defparameter *numbers* (alexandria:shuffle (copy-seq *sorted*))) *NUMBERS* CL-USER(4): (equalp *sorted* *numbers*) NIL CL-USER(5): (time (progn (setf *numbers* (sort *numbers* #'<)) nil)) 2.157 seconds real time 3 cons cells NIL CL-USER(6): (equalp *sorted* *numbers*) T CL-USER(7): (let ((a (map-into (make-array 10000) (let ((x 0)) (lambda () (incf x)))))) (sort a #'<) nil) NIL CL-USER(8): (time (progn (setf *numbers* (sort *numbers* #'<)) nil)) 1.074 seconds real time 3 cons cells NIL CL-USER(9):
With these changes, sort seems to be a little faster (for vectors) although I was not worried with optimizations. In ABCL 1.0.1, in my machine, sorting 1000000 random integers takes around 10s on average while now it takes 2s. However, I must point out I didn't do any serious and proper benchmarking, just some runs.
I will be happy to answer any questions if necessary.
Cheers, Jorge Tavares
On Feb 4, 2012, at 11:57 AM, Jorge Tavares wrote:
[…]
I'm sending a patch that solves the issue reported in ticket #187. The quicksort function picks the pivot by selecting a midpoint and also sorts the smaller partition first. These are enough to avoid the stack overflow problem as reported. I've performed some tests and it looks it is correct.
[…]
Great! [This will ship as part of abcl-1.1][1].
Nice to move away from code copied from ECL…
[1]: http://trac.common-lisp.net/armedbear/changeset/13852
Thanks for the contribution!
-- "A screaming comes across the sky. It has happened before, but there is nothing to compare to it now."
On Saturday, February 4, 2012 at 20:11 , Mark Evenson wrote:
[…]
Great! [This will ship as part of abcl-1.1][1].
Nice to move away from code copied from ECL…
Thanks for the contribution!
Thanks for accepting the patch! I think I will work on improving more the sort code. There are some things than can be cleaned and optimized and although it's not a priority, it can be nice.
Cheers, Jorge
armedbear-devel@common-lisp.net