#187: Stack Overflow for Worst-case Vector Sort ------------------------------------------+--------------------------------- Reporter: mevenson | Owner: nobody Type: defect | Status: new Priority: major | Milestone: unscheduled Component: java | Version: 1.0 Keywords: array, CL:SORT, optimization | ------------------------------------------+--------------------------------- [http://article.gmane.org/gmane.lisp.armedbear.devel/2118 James Lawrence reports on armedbear-devel that ABCL-1.0.0 overflows its stack when sorting an array of 10^4 elements]:
{{{ (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.