[armedbear-ticket] [armedbear] #187: Stack Overflow for Worst-case Vector Sort

[armedbear]

#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.

-- 
Ticket URL: <http://trac.common-lisp.net/armedbear/ticket/187>
armedbear <http://common-lisp.net/project/armedbear>
armedbear