trivial-jumptables provides efficient O(1) jump tables on supported
Common Lisp implementations and falls back to O(log(n)) on others.
Important optimizations are performed even on unsupported implementations,
notably "vectorization" which allows O(1) dispatch if all cases are constant.
If you need a jump table in Common Lisp, the naive way is to just expand to the equivalent ecase form:
(ecase index
(0 foo)
(1 bar)
(2 baz))Unfortunately, in most Common Lisp implementations, this simply expands to a linear series of checks for each value in turn, which is really not great if there are more than just a few cases.
This library provides ejumpcase, which is much more efficient. On CCL, it actually expands to an ecase which expands to a bunch of ifs, but a later stage of compilation actually detects the repeated comparisons on the index variable and converts them into a nice jump table. So ejumpcase is ultimately O(1) on CCL. On other Common Lisp implementations, ejumpcase expands to a binary search implemented as a tree of if forms, offering still vastly superior performance compared to the typical ecase expansion (if there are more than a few cases). But this really ought to be O(1), so help is requested to add such support for other Common Lisp implementations. Please open an issue or pull request if you know how to add support for this on other Common Lisp implementations.
Note that since version 1.1, when all cases are constant we can achieve O(1) dispatch even on unsupported implementations, thanks to vectorization. We can also achieve nearly O(1) dispatch if most cases are constant.
You can quickly get some rough test results like this:
;;If necessary, ensure we have a recent enough Quicklisp dist.
(ql:update-dist "quicklisp")
;;Download the library.
(ql:quickload "trivial-jumptables")
;;The REPL stuff is in the test suite system, so load that.
(asdf:load-system '#:trivial-jumptables_tests)
;;Or you could just run the test suite,
;;which will first load it if necessary.
(asdf:test-system '#:trivial-jumptables)
;;See to what compiled (assembly) code ejumpcase
;;ultimately expands to on your Common Lisp implementation.
(jumpcase_tests:disassemble-example)
;;You might like to compare the results of these.
(jumpcase_tests:disassemble-example
:ejumpcase-expander 'jumpcase:expand-ejumpcase-linear)
(jumpcase_tests:disassemble-example
:ejumpcase-expander 'jumpcase:expand-ejumpcase-logarithmic)
;;You can roughly compare performance across various ejumpcase backends
;;on the same or different Common Lisp implementations with this.
;;The default is a million executions of a 1000 entries jump table.
(jumpcase_tests:benchmark)
;;You might like to compare the results of these.
(jumpcase_tests:benchmark
:ejumpcase-expander 'jumpcase:expand-ejumpcase-linear)
(jumpcase_tests:benchmark
:ejumpcase-expander 'jumpcase:expand-ejumpcase-logarithmic)This package is also nicknamed jumpcase.
One should normally import a single symbol from this package, ejumpcase.
Any other symbols from this package should normally be explicitly qualified, such as jumpcase:*ejumpcase-expander*.
Don't (:use)!
index-form &body cases &environment env => results
First, index-form is evaluated to produce index.
If index is a non-negative integer below the number of cases provided, then the matching case form is executed and ejumpcase returns any values it returns.
Else, index is invalid so a type-error is signaled.
ejumpcase is semantically equivalent to the corresponding ecase form, but more efficient. (Typically drastically more efficient if there are many cases.)
(ejumpcase index
foo
bar
baz)
==
(ecase index
(0 foo)
(1 bar)
(2 baz))To determine its expansion, ejumpcase simply binds jumpcase:*environment* to env then calls jumpcase:*ejumpcase-expander* with index-form, cases and the number of cases.
An environment object. The initial value is nil, designating the null lexical environment.
Bound by ejumpcase before calling jumpcase:*ejumpcase-expander*.
Very few ejumpcase expanders need to inspect this value, so it's nice not to have to pass it explicitly through all of them.
The value of this variable is a function designator that ejumpcase calls to determine its expansion. Suitable values for this variable are called ejumpcase expanders.
ejumpcase expanders have 3 required parameters, index-form, cases and case-count, and return expansion. They also receive an environment object through the jumpcase:*environment* variable.
The case-count is simply the number of cases, and is passed around to avoid having to recompute it through the various stages of expansion. case-count == (length cases)
The consequences are undefined if any function that accepts cases and case-count arguments is passed an inaccurate case-count.
The functions jumpcase:expand-ejumpcase-linear and jumpcase:expand-ejumpcase-logarithmic are ejumpcase expanders, as well as any function returned by jumpcase:make-standard-optimizations-wrapper or jumpcase:make-standard-vectorizing-wrapper.
On supported Common Lisp implementations, the initial value of this variable is a function that returns an expansion that takes advantage of an implementation-specific O(1) jump table primitive.
On other implementations, the default value is the result of (.jumpcase:make-standard-optimizations-wrapper 'jumpcase:expand-ejumpcase-logarithmic)
index cases case-count => expansion
This ejumpcase expander simply expands to an ecase form.
(let ((jumpcase:*type-annotate-index-form* nil))
(jumpcase:expand-ejumpcase-linear 'my-index '(foo bar baz) 3))
=>
(ecase my-index (0 foo) (1 bar) (2 baz))index cases case-count => expansion
This ejumpcase expander returns an expansion that implements a binary search with a tree of if forms for drastically improved performance over jumpcase:expand-ejumpcase-linear when there are more than just a few cases.
(jumpcase:expand-ejumpcase-logarithmic
'my-index '(:zero :one :two :three :four :five :six :seven) 8)
=>
(let ((#:index579 my-index))
(if (typep #:index579 '(jumpcase:index 8))
(if (< #:index579 4)
(if (< #:index579 2)
(if (< #:index579 1)
:zero
:one)
(if (< #:index579 3)
:two
:three))
(if (< #:index579 6)
(if (< #:index579 5)
:four
:five)
(if (< #:index579 7)
:six
:seven)))
(error 'type-error :datum #:index579 :expected-type
'(jumpcase:index 8))))case-count
A type ( expands to type jumpcase:index case-count)(integer 0 (case-count)).
This generalized boolean, which defaults to true, indicates whether or not jumpcase:maybe-type-annotate-index-form should annotate its index-form argument with its type argument with a the form.
index-form case-count => maybe-type-annotated-index-form
If jumpcase:*type-annotate-index-form* is true, returns (the (.jumpcase:index case-count) index-form), else returns index-form
Notably used by jumpcase:expand-ejumpcase-linear.
This generalized boolean, which defaults to true, indicates whether or not the function returned by jumpcase:make-standard-optimizations-wrapper should evaluate its index-form argument if it is known to be a constant form as determined by constantp.
This generalized boolean, which defaults to true, indicates whether or not the function returned by jumpcase:make-standard-optimizations-wrapper should simply return the matching case form if the index-form is a known integer that is valid according to case-count.
ejumpcase-expander &key make-vectorizing-wrapper => enhanced-ejumpcase-expander
jumpcase:make-standard-vectorizing-wrapper.This function conveniently wraps some "standard" optimizations around ejumpcase-expander.
make-vectorizing-wrapper is called with ejumpcase-expander to produce vectorizing-ejumpcase-expander.
enhanced-ejumpcase-expander operates in 3 stages, in order. Previous stages affect later stages.
In the first stage, index-form is precomputed if jumpcase:*precompute-constant-index* is true and constantp determines index-form to be a constant.
In the second stage, if jumpcase:*preselect-case* is true and index-form is a known integer that is valid according to case-count, then the matching case is immediately returned and the vectorizing-ejumpcase-expander will not be called.
In the third stage, the vectorizing-ejumpcase-expander is called.
Further standard optimizations may be defined in the future.
In a perfect world, all Common Lisp implementations would export a O(1) jump table primitive, and trivial-jumptables would integrate with all of them.
In a less than perfect world, even on unsupported implementations where we have to fall back to O(log(n)) in the general case, we can still get O(1) dispatch when all cases are constant by evaluating all the values into a vector at compile-time. We can also achieve similar performance when only most cases are constant, falling back to O(log(n)) (where n is the number of non-constant cases) when we hit a non-constant case.
(Note that "vectorization" is a bit of a misnomer, as it generally refers to a different technique, but we'll roll with it.)
This generalized boolean, which defaults to false on supported (native O(1)) implementations and to true on unsupported (portable O(log(n))) implementations, indicates whether or not the ejumpcase expander returned by jumpcase:make-standard-vectorizing-wrapper should perform vectorization when appropriate.
A real between 0 and 1 inclusive. It represents the minimum percentage of cases that must be constant for vectorization to be performed. The initial value is implementation-dependent.
A function designator. The initial value is jumpcase:standard-vectorization-threshold.
case-count => threshold
This function is the initial value of jumpcase:*vectorization-threshold-function*.
This function returns the result of multiplying the jumpcase:*vectorization-threshold* by the case-count, rounded to the nearest integer.
ejumpcase-expander &key threshold-function => enhanced-ejumpcase-expander
jumpcase:*vectorization-threshold-function* with the case-count that it received as argument.enhanced-ejumpcase-expander is a function that performs vectorization if appropriate, else it just forwards all its arguments to ejumpcase-expander and returns what it returns.
To determine which of no vectorization, full vectorization or partial vectorization is performed, find the first match through the following list of possibilities:
jumpcase:*vectorize* is false or case-count is smaller than 2, then no vectorization is performed.Full vectorization means that we simply evaluate all the cases (which are all constant) into a vector at compile-time, and so at runtime we just need to return the value at the given index.
Partial vectorization is similar, except that for the non-constant cases the vector holds a distinguished kind of value that points to a new index which will be used to discriminate among the non-constant cases using the ejumpcase-expander.