License: Public Domain , Load it with Quicklisp: (ql:quickload "trivial-jumptables")
Library type: Macro , Project complexity: Simple

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.

Overview

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)

Dictionary

Dictionary » trivial-jumptables

Package trivial-jumptables

Description

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

Dictionary » ejumpcase

Macro ejumpcase

index-form &body cases &environment env => results

Arguments and Values

  • index-form -- A form.
  • cases -- A list of forms.
  • env -- An environment object.
  • results -- The values returned by the matching case form.

Description

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.

Dictionary » Internals API

Dictionary » Internals API » Expansion

...2 » Expansion » *environment*

...2 » Expansion » *ejumpcase-expander*

Variable jumpcase:*ejumpcase-expander*

Description

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

...2 » Expansion » expand-ejumpcase-linear

Function jumpcase:expand-ejumpcase-linear

index cases case-count => expansion

Description

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

...2 » Expansion » expand-ejumpcase-logarithmic

Function jumpcase:expand-ejumpcase-logarithmic

index cases case-count => expansion

Description

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

Dictionary » Internals API » Optimization

...2 » Optimization » index

Type specifier jumpcase:index

case-count

Arguments and Values

  • case-count -- An integer. The number of cases.

Description

A type (jumpcase:index case-count) expands to type (integer 0 (case-count)).

...2 » Optimization » *type-annotate-index-form*

Variable jumpcase:*type-annotate-index-form*

Description

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.

...2 » Optimization » maybe-type-annotate-index-form

Function jumpcase:maybe-type-annotate-index-form

index-form case-count => maybe-type-annotated-index-form

Arguments and Values

  • index-form -- A form.
  • case-count -- A non-negative integer.
  • maybe-type-annotated-index-form -- A form.

Description

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.

...2 » Optimization » *precompute-constant-index*

Variable jumpcase:*precompute-constant-index*

Description

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.

...2 » Optimization » *preselect-case*

Variable jumpcase:*preselect-case*

Description

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.

...2 » Optimization » make-standard-optimizations-wrapper

Function jumpcase:make-standard-optimizations-wrapper

ejumpcase-expander &key make-vectorizing-wrapper => enhanced-ejumpcase-expander

Arguments and Values

Description

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.

Dictionary » Internals API » Optimization » Vectorization

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

...3 » Vectorization » *vectorize*

Variable jumpcase:*vectorize*

Description

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.

...3 » Vectorization » *vectorization-threshold*

Variable jumpcase:*vectorization-threshold*

Description

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.

...3 » Vectorization » *vectorization-threshold-function*

...3 » Vectorization » standard-vectorization-threshold

Function jumpcase:standard-vectorization-threshold

case-count => threshold

Arguments and Values

  • case-count -- The number of cases to produce a threshold for.
  • threshold -- A non-negative integer no larger than case-count. The minimum number of cases that must be constant for vectorization to be performed.

Description

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.

...3 » Vectorization » make-standard-vectorizing-wrapper

Function jumpcase:make-standard-vectorizing-wrapper

ejumpcase-expander &key threshold-function => enhanced-ejumpcase-expander

Arguments and Values

Description

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:

  1. If jumpcase:*vectorize* is false or case-count is smaller than 2, then no vectorization is performed.
  2. If all cases are constant, then full vectorization is performed.
  3. If the number of constant cases is smaller than the result of calling threshold-function with case-count, then no vectorization is performed, else partial 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.