Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the specialized-function Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Mar 25 19:12:56 2020 GMT+0.
| • Introduction | What specialized-function is all about | |
| • Systems | The systems documentation | |
| • Files | The files documentation | |
| • Packages | The packages documentation | |
| • Definitions | The symbols documentation | |
| • Indexes | Concepts, functions, variables and data types |
* Specialized-Function [[https://travis-ci.org/numcl/specialized-function][https://travis-ci.org/numcl/specialized-function.svg?branch=master]]
This library is part of NUMCL. It provides a macro `SPECIALIZED`
that performs a Julia-like dispatch on the arguments, lazily compiling a
type-specific version of the function from the same code.
*The main target of this macro is the speed.*
It supports SBCL, CCL, and LispWorks (untested), and provides a limited support to other lisps.
On other lisps, the code inside =specialized= is not able to read
the variables that are not specified to be the dispatched arguments.
This is because it relies on the implementation-specific interface to the
environment object to collect the list of all lexical variables.
[[https://asciinema.org/a/RW5a3mKqAYvOTvBp3i1x5yqoK][https://asciinema.org/a/RW5a3mKqAYvOTvBp3i1x5yqoK.svg]]
*NEWS* (2019/09/28): lexical variables NOT specialized by the user are type-annotated inside specialized-function based on the information available from cltl2.
** Why?
Suppose computing a vector dot:
#+begin_src lisp
(defun dot-original (a b c)
(declare (optimize (speed 3) (safety 0) (debug 0)))
(loop
for ai across a
for bi across b
do (incf c (* ai bi)))
c)
#+end_src
This function is untyped and thus slow due to the calls to =generic-*= and
=generic-+=. While we could write a macro that automatically duplicates this
code with some additional type declaration, notice that the number of types that
this function accepts is large --- =a= could be a simple or non-simple array of
4 float types, 4 float complex types, and the integer subtypes for the
specialized arrays, such as =(unsigned-byte 4)=. On SBCL x64, there are at
least 56 variants -- 2*(4+4+12+7+1) -- and since there are 2 arguments, it
should compile more than 2500 specialized variants. This wastes the compilation
time because most combinations are not actually used in the user code.
# 4 floats
# 4 complex floats
# unsigned-byte 1 2 3 4 7 8 15 16 31 32 63 64 -- 12
# signed-byte 1 2 4 8 16 32 64 -- 7
# fixnum
Julia language has chosen a strategy that lazily compiles the typed variant of the function
when the function was invoked with a new combination of types.
Specialized-function provides this same functionality in Common Lisp ---
lazy compilation of the type-specific variant of the same function.
Note that this cannot be achieved by CLOS and the behavior is
*orthogonal/complimentary* to the CLOS dispatch. One critical difference is
that CLOS generally assumes that the *different code/algorithm*
is used for implementing each method,
while specialized-function assumes that
*all specialized functions share the same code*.
Another reason it cannot be achieved by CLOS is that CLOS in general cannot specify the
array element types, which is critical in the high-performance code (while it is
subject to a debate --- MOP can extend it to support array specifiers).
Since they are orthogonal, you could also *combine CLOS and specialized-function* as follows:
#+begin_src lisp
(defmethod print-all ((obj array) (s stream))
(specialized (obj) ()
(loop for c across obj do (write-char c s))))
(defmethod print-all ((obj list) (s stream))
(loop for elem in obj do (write elem s)))
#+end_src
Note that the first =print-all= for an =array= could dispatch between the
=base-string= (with =base-char= elements) and =string= (with =character=
elements).
** How?
We compile each dispatched branch lazily and store them in a tree of vectors (each node is called a /table/).
The number of entries in each table depends on the implementation's type-upgrading rule
and the number of supported specialized array element types.
There is a =widetag= function containing a nested =etypecase= rule
which takes an object, investigate its type and returns the corresponding index in the table.
If the function is not available at the leaf node, it compiles
a new version of the function. The overhead of performing a dispatch is
: [simple-array access]x[number of arguments]+[single function call].
CCL does not obtain much speedup on the numerical code as it cannot infer the
return type of =(aref A ...)= from the element-type declaration of =A=.
On unsupported implementations, =SPECIALIZED= is +equivalent to =PROGN=.+
not able to pass values of lexical variables to the body inside =SPECIALIZED=.
** Caveats
For array types, it dispatches based on the (upgraded) element
type and the simpleness of the runtime array object.
It *does not* dispatch based on the *rank* and the *dimensions*.
Also, once each function is called/compiled for the arrays of a certain rank,
*this rank information is fixed*. This is based on a heuristic that *the same code/algorithm
does not work for an array of the different ranks*. For example, it is unreasonable to
assume that a code for matrix multiplication can process a 1D vector or a 3D tensor.
For integer types, all values that can be expressed within fixnum
will dispatch to the fixnum-specialized branch. That is, entering a
=(specialized (n) ...)= with =n= being =12= does not dispatch to =(unsinged-byte 4)=
but simply to =fixnum=.
=specialized= dispatches to the branches for =standard-object= and
=structure-object=, but does not provide any dispatch for their subtypes.
This should be handled by CLOS mainly because, as a heuristic, different
classes would require the different code/algorithm.
However, for specific purposes, we expose a function =register-base-type=
which allows you to add a specific type to the tables.
** Author, License, Copyright
Masataro Asai (guicho2.71828@gmail.com)
Licensed under LGPL v3.
Copyright (c) 2019 IBM Corporation
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The specialized-function system |
Masataro Asai
LGPL
Provides a Julia-like function that automatically compiles a type-specific version of the function from the same code
0.1
specialized-function.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files |
| • The specialized-function.asd file | ||
| • The specialized-function/0package.lisp file | ||
| • The specialized-function/1common.lisp file | ||
| • The specialized-function/2find-lexical-variables.lisp file |
Next: The specialized-function/0package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
/home/quickref/quicklisp/dists/quicklisp/software/specialized-function-20200325-git/specialized-function.asd
specialized-function (system)
Next: The specialized-function/1common․lisp file, Previous: The specialized-function․asd file, Up: Lisp files [Contents][Index]
specialized-function (system)
0package.lisp
Next: The specialized-function/2find-lexical-variables․lisp file, Previous: The specialized-function/0package․lisp file, Up: Lisp files [Contents][Index]
specialized-function (system)
1common.lisp
Previous: The specialized-function/1common․lisp file, Up: Lisp files [Contents][Index]
specialized-function (system)
2find-lexical-variables.lisp
find-lexical-variables (function)
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The specialized-function package |
0package.lisp (file)
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions | ||
| • Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported macros | ||
| • Exported functions |
Next: Exported functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
1common.lisp (file)
Previous: Exported macros, Up: Exported definitions [Contents][Index]
1common.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal special variables | ||
| • Internal macros | ||
| • Internal functions | ||
| • Internal types |
Next: Internal macros, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
1common.lisp (file)
1common.lisp (file)
1common.lisp (file)
the size of the table.
/builds/quickref/quickref/bin/declt
Next: Internal functions, Previous: Internal special variables, Up: Internal definitions [Contents][Index]
macro for debugging
1common.lisp (file)
Next: Internal types, Previous: Internal macros, Up: Internal definitions [Contents][Index]
1common.lisp (file)
1common.lisp (file)
2find-lexical-variables.lisp (file)
1common.lisp (file)
1common.lisp (file)
1common.lisp (file)
Takes an object and returns a reasonable type declaration for the object. Analogous to upgraded-array-element-type, but works on an object.
1common.lisp (file)
This function returns an integer based on the type of the object.
/builds/quickref/quickref/bin/declt
1common.lisp (file)
Previous: Internal functions, Up: Internal definitions [Contents][Index]
1common.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index | ||
| • Function index | ||
| • Variable index | ||
| • Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | F L S |
|---|
| Jump to: | F L S |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | A B F I M R S T U W |
|---|
| Jump to: | A B F I M R S T U W |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | *
+
S |
|---|
| Jump to: | *
+
S |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | P S T |
|---|
| Jump to: | P S T |
|---|