[alexandria-devel] Optimization for whichever

[John Fremlin]

Luis Oliveira <luismbo at gmail.com> writes:

> Gustavo <gugamilare at gmail.com> writes:
>
>> Hello,I have optimized the expansion of the macro whichever.
>
> Is there anything obviously wrong with my simpler implementation?
> <http://article.gmane.org/gmane.lisp.alexandria.devel/213>

This is roughly

(case (random n)
      (0 ...)
      ...)

Which has a decision as O(n) as SBCL and related compilers are too
stupid to implement case efficiently as an indexed jump. It could easily
be O(1). It would be on AllegroCL I believe.

The patch by Gustavo is O(log(n)), which is, given the current state of
SBCL, much better. But it would require a very clever compiler to figure
out how to transform it into an O(1) jump.

Note that the ncase trick where you jump into an array of lambdas would
be an exceedingly bad idea in general, before anybody proposes it, as
the case bodies could use local variables, so promoting a non-consing
algorithm to a consing one.

Why didn't the original whichever just use case?