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

[Mark Evenson]

On Nov 7, 2011, at 14:48 , James M. Lawrence wrote:

> 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]
> 

Filed as [ticket #187][1].  Thanks for the reproducible bug report.

[1]: http://trac.common-lisp.net/armedbear/ticket/187

[…]

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

> […]

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

[…]

We'll definitely check psort out for inclusion in our CL:SORT implementation.  Thanks for the tip!

And I might have an alternate implementation for workers threads
for the JVM to replace what [lparallel]() that should "spread"
nicely across all available cores that uses [the
java.util.concurrent][ThreadPoolExecutor].  But my time is currently
over-committed between non-ABCL work and perfecting the abcl-1.0.1
release, so this will probably not happen in the next couple days.
That ABCL is not performant with lparallel indicates I need to look
at the efficiency of our Bordeaux Threads implementation.

[lparallel]: http://lparallel.com/overview/
[ThreadPoolExecutor]: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ThreadPoolExecutor.html