[armedbear-devel] stack overflow for worst-case vector sort

[James M. Lawrence]

ABCL-1.0.0

    (let ((a (map-into (make-array 10000)
                       (let ((x 0))
                         (lambda () (incf x))))))
      (sort a #'<)
      nil)
=>
Stack overflow.
   [Condition of type STORAGE-CONDITION]

  0: (#<FUNCTION {7F535BDF}> #<STORAGE-CONDITION {74A2B3B8}>
#<FUNCTION {7F535BDF}>)
  1: (APPLY #<FUNCTION {7F535BDF}> (#<STORAGE-CONDITION {74A2B3B8}>
#<FUNCTION {7F535BDF}>))
  2: (SYSTEM::RUN-HOOK SYSTEM::*INVOKE-DEBUGGER-HOOK*
#<STORAGE-CONDITION {74A2B3B8}> #<FUNCTION {7F535BDF}>)
  3: (INVOKE-DEBUGGER #<STORAGE-CONDITION {74A2B3B8}>)
  4: org.armedbear.lisp.Lisp.error(Lisp.java:374)
  5: org.armedbear.lisp.Java$pf_jrun_exception_protected.execute(Java.java:1315)
  6: org.armedbear.lisp.Symbol.execute(Symbol.java:785)
  7: org.armedbear.lisp.LispThread.execute(LispThread.java:649)
  8: org.armedbear.lisp.swank_469.execute(swank.lisp:2116)
  9: org.armedbear.lisp.LispThread.execute(LispThread.java:683)
 10: org.armedbear.lisp.Primitives$pf_apply.execute(Primitives.java:2797)
 11: (JAVA:JRUN-EXCEPTION-PROTECTED #<FUNCTION {39B4CEC7}>)

It looks like the quick-sort function (attributed to ECL) pivots off
the first element. I would suggest using a midpoint instead.

ABCL's sort also seems a little slow. The psort benchmarks show too
much speedup for only 2 cores (http://lparallel.com/download).

size   1000 | op <        | SORT               11
size   1000 | op <        | SORT               11
size   1000 | op <        | SORT               12
size   1000 | op <        | SORT               12
size   1000 | op <        | PSORT               5
size   1000 | op <        | PSORT               4
size   1000 | op <        | PSORT               5
size   1000 | op <        | PSORT               4

size  50000 | op <        | SORT             1014
size  50000 | op <        | SORT             1011
size  50000 | op <        | SORT             1012
size  50000 | op <        | SORT             1013
size  50000 | op <        | PSORT             413
size  50000 | op <        | PSORT             417
size  50000 | op <        | PSORT             415
size  50000 | op <        | PSORT             416

size 200000 | op <        | SORT             4703
size 200000 | op <        | SORT             4701
size 200000 | op <        | SORT             4715
size 200000 | op <        | SORT             4712
size 200000 | op <        | PSORT            1977
size 200000 | op <        | PSORT            1975
size 200000 | op <        | PSORT            1979
size 200000 | op <        | PSORT            1994

psort is based upon the following (posted to usenet by Roger Corman;
free license).

(defun quicksort (vec lo hi comp-func)
  (if (> hi lo)
      (let* ((mid (round (+ lo hi) 2))
             (i lo)
             (j (+ hi 1))
             (p (elt vec mid)))
        (rotatef (elt vec mid) (elt vec lo)) ;; swap mid element to first
        (loop
           (loop do (incf i)
              until (or (> i hi) (funcall comp-func p (elt vec i))))
           (loop do (decf j)
              until (or (<= j lo) (funcall comp-func (elt vec j) p)))
           (if (< j i) (return))
           (rotatef (elt vec i)(elt vec j)))
        (rotatef (elt vec lo) (elt vec j)) ;;put partition element in place
        (quicksort vec lo (- j 1) comp-func)  (quicksort vec i hi
comp-func)))  vec)

(defun qsort (sequence comp-func)
  (quicksort sequence 0 (- (length sequence) 1) comp-func))