The specialized-function Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The specialized-function Reference Manual

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.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction


* 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: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 specialized-function

Author

Masataro Asai

Contact

guicho2.71828@gmail.com

License

LGPL

Description

Provides a Julia-like function that automatically compiles a type-specific version of the function from the same code

Version

0.1

Dependencies
Source

specialized-function.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 specialized-function.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/specialized-function-20200325-git/specialized-function.asd

Systems

specialized-function (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 specialized-function/0package.lisp

Parent

specialized-function (system)

Location

0package.lisp

Packages

specialized-function


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 specialized-function/1common.lisp

Parent

specialized-function (system)

Location

1common.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.4 specialized-function/2find-lexical-variables.lisp

Parent

specialized-function (system)

Location

2find-lexical-variables.lisp

Internal Definitions

find-lexical-variables (function)


Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 specialized-function

Source

0package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Macros

Macro: specializing ARGS (&key VERBOSE TIME) &body DECL-AND-BODY
Package

specialized-function

Source

1common.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Functions

Function: register-base-type TYPE &optional *REBUILD-WIDETAG*
Package

specialized-function

Source

1common.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: *base-types*
Package

specialized-function

Source

1common.lisp (file)

Special Variable: *benchmark-size*
Package

specialized-function

Source

1common.lisp (file)

Special Variable: *rebuild-widetag*
Package

specialized-function

Source

1common.lisp (file)

Special Variable: +table-size+

the size of the table.

Package

specialized-function

Source

/builds/quickref/quickref/bin/declt


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Macros

Macro: in-compile-time (&optional ENV) &body BODY

macro for debugging

Package

specialized-function

Source

1common.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Functions

Function: array-element-types ()
Package

specialized-function

Source

1common.lisp (file)

Function: benchmark ()
Package

specialized-function

Source

1common.lisp (file)

Function: find-lexical-variables ENV
Package

specialized-function

Source

2find-lexical-variables.lisp (file)

Function: rebuild-widetag ()
Package

specialized-function

Source

1common.lisp (file)

Function: specialized-function-form VARS LEXVARS LEXVARS-TYPES DECL-AND-BODY VALS
Package

specialized-function

Source

1common.lisp (file)

Function: table SIZE
Package

specialized-function

Source

1common.lisp (file)

Function: upgraded-object-type X

Takes an object and returns a reasonable type declaration for the object. Analogous to upgraded-array-element-type, but works on an object.

Package

specialized-function

Source

1common.lisp (file)

Function: widetag ()

This function returns an integer based on the type of the object.

Package

specialized-function

Source

/builds/quickref/quickref/bin/declt

Function: widetag-lambda ()
Package

specialized-function

Source

1common.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Types

Type: table SIZE
Package

specialized-function

Source

1common.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   S  
Index Entry  Section

F
File, Lisp, specialized-function.asd: The specialized-function․asd file
File, Lisp, specialized-function/0package.lisp: The specialized-function/0package․lisp file
File, Lisp, specialized-function/1common.lisp: The specialized-function/1common․lisp file
File, Lisp, specialized-function/2find-lexical-variables.lisp: The specialized-function/2find-lexical-variables․lisp file

L
Lisp File, specialized-function.asd: The specialized-function․asd file
Lisp File, specialized-function/0package.lisp: The specialized-function/0package․lisp file
Lisp File, specialized-function/1common.lisp: The specialized-function/1common․lisp file
Lisp File, specialized-function/2find-lexical-variables.lisp: The specialized-function/2find-lexical-variables․lisp file

S
specialized-function.asd: The specialized-function․asd file
specialized-function/0package.lisp: The specialized-function/0package․lisp file
specialized-function/1common.lisp: The specialized-function/1common․lisp file
specialized-function/2find-lexical-variables.lisp: The specialized-function/2find-lexical-variables․lisp file

Jump to:   F   L   S  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   A   B   F   I   M   R   S   T   U   W  
Index Entry  Section

A
array-element-types: Internal functions

B
benchmark: Internal functions

F
find-lexical-variables: Internal functions
Function, array-element-types: Internal functions
Function, benchmark: Internal functions
Function, find-lexical-variables: Internal functions
Function, rebuild-widetag: Internal functions
Function, register-base-type: Exported functions
Function, specialized-function-form: Internal functions
Function, table: Internal functions
Function, upgraded-object-type: Internal functions
Function, widetag: Internal functions
Function, widetag-lambda: Internal functions

I
in-compile-time: Internal macros

M
Macro, in-compile-time: Internal macros
Macro, specializing: Exported macros

R
rebuild-widetag: Internal functions
register-base-type: Exported functions

S
specialized-function-form: Internal functions
specializing: Exported macros

T
table: Internal functions

U
upgraded-object-type: Internal functions

W
widetag: Internal functions
widetag-lambda: Internal functions

Jump to:   A   B   F   I   M   R   S   T   U   W  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *   +  
S  
Index Entry  Section

*
*base-types*: Internal special variables
*benchmark-size*: Internal special variables
*rebuild-widetag*: Internal special variables

+
+table-size+: Internal special variables

S
Special Variable, *base-types*: Internal special variables
Special Variable, *benchmark-size*: Internal special variables
Special Variable, *rebuild-widetag*: Internal special variables
Special Variable, +table-size+: Internal special variables

Jump to:   *   +  
S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   P   S   T  
Index Entry  Section

P
Package, specialized-function: The specialized-function package

S
specialized-function: The specialized-function system
specialized-function: The specialized-function package
System, specialized-function: The specialized-function system

T
table: Internal types
Type, table: Internal types

Jump to:   P   S   T