Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#187 closed defect (fixed)

Stack Overflow for Worst-case Vector Sort

Reported by: Evenson Not Org Owned by: nobody
Priority: major Milestone: 1.1.0
Component: java Version: 1.0
Keywords: array, CL:SORT, optimization Cc:
Parent Tickets:

Description

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.

Subtickets

Change History (4)

comment:1 Changed 8 years ago by Evenson Not Org

Milestone: unscheduled1.0.1

comment:2 Changed 8 years ago by Evenson Not Org

Milestone: 1.0.11.1.0

comment:3 Changed 8 years ago by Evenson Not Org

Resolution: fixed
Status: newclosed

A new implementation that addresses this problem was provided by Jorge Tavares in r13852.

comment:4 Changed 8 years ago by Evenson Not Org

See #196 .

Note: See TracTickets for help on using tickets.