[PATCH] Use a more efficient algorithm for list shuffling

[salvador fandino]

On Sun, May 10, 2015 at 2:02 AM, Svante v. Erichsen <
Svante.v.Erichsen at web.de> wrote:

>
> How did you determine the threshold to switch to Fisher-Yates?
>
>
Mostly, I inferred it from my previous experience with similar
algorithms... and it is completely wrong!

I have been benchmarking an instrumentalized version of the shuffle-sublist
function (code attached) with several FLOSS common-lisp implementations and
found the following results:

For SBCL and Clozure CL, the optimal cut-point is around 200 and 150
respectively. I have run it with different list sizes and in a couple of
machines, and the results seem consistent.

For ECL, the optimal cut-point seems to be around 10000. In any case, it
runs much slower than in SBCL or in CCL.

For GCL, the optimal cut-point seems to be around 5000 and it is also much
slower than SBCL or CCL.

Considering those results I would choose 200 as the best cut point because
it is where SBCL and CCL perform best without incurring in a great penalty
for ECL and GCL (~40%). Note also that performance degrades quite fast for
SBCL and CCL once the optimal cut point is surpassed.

I would also be interested to see how commercial Lisp implementations
behave.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20150511/e18813f7/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: list-shuffling.lisp
Type: application/octet-stream
Size: 1445 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20150511/e18813f7/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: list-shuffling.sbcl.out
Type: application/octet-stream
Size: 1279 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20150511/e18813f7/attachment-0001.obj>