[armedbear-devel] Patch that fixes ticket #187 (Stack Overflow for Worst-case Vector Sort)

[Jorge Tavares]

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

-- 
http://jorgetavares.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: abcl-quicksort-patch.diff
Type: application/octet-stream
Size: 3004 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/armedbear-devel/attachments/20120204/67c89307/attachment.obj>