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

trivial-jumptables provides efficient O(1) jumptables on supported
Common Lisp implementations and falls back to O(log(n)) on others.

trivial-jumptables » Overview

If you need a jumptable 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 jumptable. 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.

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

trivial-jumptables » Dictionary

...2 » 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)!

...2 » ejumpcase

Macro ejumpcase

index-form &body cases => results

Arguments and Values

  • index-form -- A form.
  • cases -- A list of forms.
  • 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 calls jumpcase:*ejumpcase-expander* with index-form, cases and the number of cases.

trivial-jumptables » Dictionary » Internals API

...3 » *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.

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.

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) jumptable primitive.
On other implementations, the default value is the result of (jumpcase:make-standard-optimizations-wrapper 'jumpcase:expand-ejumpcase-logarithmic).

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

...3 » 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 '(trivial-jumptables: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
             '(trivial-jumptables:index 8))))

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

...3 » *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.

...3 » 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.

...3 » *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.

...3 » *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.

...3 » make-standard-optimizations-wrapper

Function jumpcase:make-standard-optimizations-wrapper

ejumpcase-expander => enhanced-ejumpcase-expander

Arguments and Values

Description

This function conveniently wraps some "standard" optimizations around 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 ejumpcase-expander will not be called.

In the third stage, the ejumpcase-expander is called.

Further standard optimizations may be defined in the future.