luv

Workshop wiki

columnar.lisp

arithmetic/records/columnar.lisp

system luv/arithmetic · 20 definitions · on GitHub

Generated structure-of-arrays storage with inspectable quantity meaning.

in-package#:luv.arithmetic.records
define-conditioncolumnar-declaration-error
error
definition:initarg:definition:readercolumnar-declaration-error-definition
lane-name:initarg:lane-name:readercolumnar-declaration-error-lane-name
declaration:initarg:declaration:readercolumnar-declaration-error-declaration
reason:initarg:reason:readercolumnar-declaration-error-reason
:report
lambda
conditionstream
formatstream"Columnar declaration for ~S lane ~S is invalid: ~A."
columnar-layout-definition-name
columnar-declaration-error-definitioncondition
columnar-declaration-error-lane-namecondition
columnar-declaration-error-reasoncondition
defclasscolumnar-lane-definition
name:initarg:name:readercolumnar-lane-definition-name
initial-element:initarg:initial-element:readercolumnar-lane-definition-initial-element
clear-on-remove-p:initarg:clear-on-remove-p:readercolumnar-lane-definition-clear-on-remove-p
:documentation

One generated column's name, element representation, and retention policy.

defmethodinitialize-instance:after
unless
symbolp
columnar-lane-definition-namelane
error"A columnar lane needs a symbolic name, not ~S."
columnar-lane-definition-namelane
unless
typep
columnar-lane-definition-initial-elementlane
error"Columnar lane ~S initial element ~S is not of type ~S."
columnar-lane-definition-namelane
columnar-lane-definition-initial-elementlane
defclasscolumnar-layout-definition
name:initarg:name:readercolumnar-layout-definition-name
lanes:initarg:lanes:readercolumnar-layout-definition-lanes
quantity-layout:initarg:quantity-layout:readercolumnar-layout-definition-quantity-layout
source-form:initarg:source-form:readercolumnar-layout-definition-source-form
:documentation

The physical lanes and fixed row meaning generated for a columnar type.

defmethodinitialize-instance:after
let
lanes
columnar-layout-definition-lanesdefinition
layout
columnar-layout-definition-quantity-layoutdefinition
unless
and
consplanes
every
lambda
lane
lanes
=
lengthlanes
length
remove-duplicateslanes:key#'columnar-lane-definition-name:test#'eq
error"Columnar definition ~S needs distinct physical lanes."
columnar-layout-definition-namedefinition
when
andlayout
/=
lengthlanes
math:quantity-layout-extentlayout
error"Columnar definition ~S has ~D lanes but a ~D-lane quantity layout."
columnar-layout-definition-namedefinition
lengthlanes
math:quantity-layout-extentlayout
defgenericcolumnar-layout-definition-for
name
:documentation

Return the inspectable physical row layout named by name.

defmethodcolumnar-layout-definition-for
name
declare
ignorename
nil
defuncolumnar-layout-lane-definition
definitionlane-name

Return definition's physical lane-name description, or NIL.

findlane-name
columnar-layout-definition-lanesdefinition
:key#'columnar-lane-definition-name:test#'eq
defclasscolumnar-row-declaration
layout-definition:initarg:layout-definition:readercolumnar-row-declaration-layout-definition
lane-declarations:initarg:lane-declarations:readercolumnar-row-declaration-lane-declarations
quantity-layout:initarg:quantity-layout:readercolumnar-row-declaration-quantity-layout
revision:initform
gensym"COLUMNAR-ROW-"
:readercolumnar-row-declaration-revision
:documentation

Concrete per-lane declarations retained once by a columnar materialization.

Rows remain raw array elements; this object carries their checked meaning at the aggregate boundary. #327W2B

defuncolumnar-row-lane-declaration
rowlane-name

Return row's concrete declaration for lane-name, or NIL.

cdr
assoclane-name
columnar-row-declaration-lane-declarationsrow
:test#'eq
defunsignal-columnar-declaration-error
definitionlane-namedeclarationreason
error'columnar-declaration-error:definitiondefinition:lane-namelane-name:declarationdeclaration:reasonreason
defunensure-columnar-lane-representation
definitionlane-namedeclarationphysical-lane
let
unlessactual
signal-columnar-declaration-errordefinitionlane-namedeclaration:missing-representation-type
multiple-value-bind
subtype-pknown-p
subtypepactualexpected
unless
andknown-psubtype-p
signal-columnar-declaration-errordefinitionlane-namedeclaration:incompatible-representation-type
declaration
defunfixed-columnar-lane-quantity-p
definitionlane-name
let
layout
columnar-layout-definition-quantity-layoutdefinition
position
positionlane-name
columnar-layout-definition-lanesdefinition
:key#'columnar-lane-definition-name:test#'eq
andlayoutposition
find-if
lambda
projection
memberposition
math:quantity-projection-positionsprojection
math:quantity-layout-projectionslayout
defunmake-columnar-row-declaration

Bind concrete represented declarations to definition's physical lanes.

declarations is an alist from lane names to represented-value declarations. Representation compatibility and duplicate semantic ownership are checked once; returned rows retain the concrete declarations without wrapping values.

let
seennil
bindingsnil
dolist
lane
columnar-layout-definition-lanesdefinition
unless
member
columnar-lane-definition-namelane
seen:test#'eq
push
cons
columnar-lane-definition-namelane
lane
bindings
make-instance'columnar-row-declaration:layout-definitiondefinition:lane-declarations
nreversebindings
:quantity-layout
columnar-layout-definition-quantity-layoutdefinition
eval-when
:compile-toplevel:load-toplevel:execute
defuncolumnar-generated-symbol
namecontrol&restarguments
intern
apply#'formatnilcontrol
mapcar
lambda
argument
if
symbolpargument
symbol-nameargument
argument
arguments
symbol-packagename
defunparse-columnar-lane
description
destructuring-bind
nameinitial-element&keytypeclear-on-remove
description
unless
and
symbolpname
type
error"A columnar lane needs a symbolic name and :TYPE: ~S"description
list:namename:initial-elementinitial-element:typetype:clear-on-remove-p
not
nullclear-on-remove
:source-formdescription
defunparse-columnar-name-and-quantities
name-and-options
if
symbolpname-and-options
valuesname-and-optionsnil
destructuring-bind
name&keyquantities
name-and-options
valuesnamequantities
defuncolumnar-lane-position
lane-namelanes
or
positionlane-namelanes:key
lambda
lane
getflane:name
:test#'eq
error"Unknown columnar quantity lane ~S."lane-name
defuncolumnar-quantity-layout-form
quantitieslanes
whenquantities`
math:make-quantity-layout,
lengthlanes
list,@
loopfor
lane-namesoptions
inquantitiescollect`
math:make-quantity-projection',
mapcar
lambda
lane-name
columnar-lane-positionlane-namelanes
lane-names
or
error"Columnar projection needs quantity meaning: ~S"',
listlane-namesoptions
defmacrodefine-columnar-buffer
name-and-options&bodylane-descriptions

Define a concrete synchronized structure-of-arrays buffer.

Each lane is (NAME INITIAL-ELEMENT :type type [:CLEAR-ON-REMOVE T]). Optional :QUANTITIES on name-and-options groups named physical lanes into fixed quantity projections. The generated MAKE-, -PUSH, -POP, and -RESET functions operate on raw specialized arrays with one shared length and capacity. #LDP5UR

multiple-value-bind
namequantities
parse-columnar-name-and-quantitiesname-and-options
let*
lanes
mapcar#'parse-columnar-lanelane-descriptions
lane-names
mapcar
lambda
lane
getflane:name
lanes
internal-constructor
columnar-generated-symbolname"%%MAKE-~A"name
constructor
columnar-generated-symbolname"MAKE-~A"name
grow
columnar-generated-symbolname"%~A-GROW"name
push-name
columnar-generated-symbolname"~A-PUSH"name
pop-name
columnar-generated-symbolname"~A-POP"name
reset-name
columnar-generated-symbolname"~A-RESET"name
length-slot
columnar-generated-symbolname"LENGTH"
capacity-slot
columnar-generated-symbolname"CAPACITY"
row-slot
columnar-generated-symbolname"ROW-DECLARATION"
length-reader
columnar-generated-symbolname"~A-LENGTH"name
capacity-reader
columnar-generated-symbolname"~A-CAPACITY"name
lane-slots
mapcar
lambda
lane
columnar-generated-symbolname"~A-LANE"
getflane:name
lanes
lane-readers
mapcar
lambda
slot
columnar-generated-symbolname"~A-~A"nameslot
lane-slots
new-lane-variables
looprepeat
lengthlanes
collect
gensym"NEW-LANE"
source-form`
define-columnar-buffer,name-and-options,@lane-descriptions
layout-form
columnar-quantity-layout-formquantitieslanes
unless
=
lengthlane-names
length
remove-duplicateslane-names:test#'eq
error"Columnar lane names must be distinct: ~S"lane-names
`
progn
eval-when
:compile-toplevel:load-toplevel:execute
defmethodcolumnar-layout-definition-for
layout-name
eql',name
declare
ignorelayout-name
load-time-value
make-instance'columnar-layout-definition:name',name:lanes
list,@
loopforlaneinlanescollect`
make-instance'columnar-lane-definition:name',
getflane:name
:representation-type',
getflane:type
:initial-element,
getflane:initial-element
:clear-on-remove-p,
getflane:clear-on-remove-p
:source-form',
getflane:source-form
:quantity-layout,layout-form:source-form',source-form
defstruct
,name
:constructor,internal-constructor
,length-slot,capacity-slot,row-slot,@lane-slots
:copiernil
,length-slot0:typefixnum
,capacity-slot0:typefixnum
,row-slotnil:typecolumnar-row-declaration:read-onlyt

Each lane slot carries its precise specialized array type, so

the generated push and every direct lane access store and

load raw elements without boxing them.

,@
loopforslotinlane-slotsforlaneinlanescollect`
,slot
make-array0:element-type',
getflane:type
:type
simple-array,
upgraded-array-element-type
getflane:type
defun,constructor
&key
capacity16
declarationsrow-declaration
check-typecapacity
integer0#.most-positive-fixnum
when
anddeclarationsrow-declaration
error"Supply DECLARATIONS or ROW-DECLARATION, not both."
let*
unless
eqdefinition
columnar-row-declaration-layout-definitionrow
signal-columnar-declaration-errordefinitionnilrow:foreign-row-declaration
,internal-constructor0capacityrow,@
loopforlaneinlanescollect`
make-arraycapacity:element-type',
getflane:type
:initial-element,
getflane:initial-element
defun,grow
bufferminimum-capacity

Growth is rare, and one inlined REPLACE per lane over precisely

typed arrays makes SBCL's constraint propagation take minutes on

a buffer with a few dozen lanes. Call REPLACE instead.

declare
notinlinereplace
let*
old-capacity
,capacity-readerbuffer
new-capacity
maxminimum-capacity1
*2old-capacity
length
,length-readerbuffer
,@
loopforlaneinlanesforreaderinlane-readersfornewinnew-lane-variablescollect`
,new
let
array
make-arraynew-capacity:element-type',
getflane:type
:initial-element,
getflane:initial-element
replacearray
,readerbuffer
:end1length:end2length
array
setf,@
loopforreaderinlane-readersfornewinnew-lane-variablesappend
list`
,readerbuffer
new
setf
,capacity-readerbuffer
new-capacity
buffer
declaim
inline,push-name,pop-name
defun,push-name
buffer,@lane-names
,@
loopforlaneinlanescollect`
check-type,
getflane:name
,
getflane:type
let
position
,length-readerbuffer
when
=position
,capacity-readerbuffer
,growbuffer
setf,@
loopforreaderinlane-readersforlane-nameinlane-namesappend`
aref
,readerbuffer
position
,lane-name
setf
,length-readerbuffer
buffer
defun,pop-name
buffer
let
position
1-
,length-readerbuffer
when
minuspposition
return-from,pop-name
values,@
looprepeat
lengthlanes
collectnil
nil
let
,@
loopforlane-nameinlane-namesforreaderinlane-readerscollect`
,lane-name
aref
,readerbuffer
position
,@
loopforlaneinlanesforreaderinlane-readerswhen
getflane:clear-on-remove-p
collect`
setf
aref
,readerbuffer
position
,
getflane:initial-element
setf
,length-readerbuffer
position
values,@lane-namest
defun,reset-name
buffer
,@
let
clear-lanes
loopforlaneinlanesforreaderinlane-readerswhen
getflane:clear-on-remove-p
collect
conslanereader
whenclear-lanes`
let
length
,length-readerbuffer
,@
loopfor
lane.reader
inclear-lanescollect`
fill
,readerbuffer
,
getflane:initial-element
:endlength
setf
,length-readerbuffer
0
buffer
',name
defmacrodefine-columnar-materialization
name-and-options&bodylane-descriptions

Define fixed columnar storage whose exact extent comes from one DOMAIN.

Each lane has the same syntax as define-columnar-buffer. The generated MAKE-NAME constructor takes DOMAIN first, asks domain-cardinality for its exact extent, checks the row declaration once, and allocates one specialized array per lane. The domain, row meaning, and arrays then travel together.

multiple-value-bind
namequantities
parse-columnar-name-and-quantitiesname-and-options
let*
lanes
mapcar#'parse-columnar-lanelane-descriptions
lane-names
mapcar
lambda
lane
getflane:name
lanes
internal-constructor
columnar-generated-symbolname"%%MAKE-~A"name
constructor
columnar-generated-symbolname"MAKE-~A"name
domain-slot
columnar-generated-symbolname"DOMAIN"
row-slot
columnar-generated-symbolname"ROW-DECLARATION"
domain-reader
columnar-generated-symbolname"~A-DOMAIN"name
lane-slots
mapcar
lambda
lane
columnar-generated-symbolname"~A-LANE"
getflane:name
lanes
source-form`
define-columnar-materialization,name-and-options,@lane-descriptions
layout-form
columnar-quantity-layout-formquantitieslanes
unless
=
lengthlane-names
length
remove-duplicateslane-names:test#'eq
error"Columnar lane names must be distinct: ~S"lane-names
`
progn
eval-when
:compile-toplevel:load-toplevel:execute
defmethodcolumnar-layout-definition-for
layout-name
eql',name
declare
ignorelayout-name
load-time-value
make-instance'columnar-layout-definition:name',name:lanes
list,@
loopforlaneinlanescollect`
make-instance'columnar-lane-definition:name',
getflane:name
:representation-type',
getflane:type
:initial-element,
getflane:initial-element
:clear-on-remove-p,
getflane:clear-on-remove-p
:source-form',
getflane:source-form
:quantity-layout,layout-form:source-form',source-form
defstruct
,name
:constructor,internal-constructor
,domain-slot,row-slot,@lane-slots
:copiernil
,domain-slotnil:typet:read-onlyt
,row-slotnil:typecolumnar-row-declaration:read-onlyt
,@
loopforslotinlane-slotsforlaneinlanescollect`
,slot
make-array0:element-type',
getflane:type
:type
simple-array,
upgraded-array-element-type
getflane:type
:read-onlyt
defun,constructor
domain&keydeclarationsrow-declaration
when
anddeclarationsrow-declaration
error"Supply DECLARATIONS or ROW-DECLARATION, not both."
let*
check-typeextent
integer0#.most-positive-fixnum
unless
eqdefinition
columnar-row-declaration-layout-definitionrow
signal-columnar-declaration-errordefinitionnilrow:foreign-row-declaration
,internal-constructordomainrow,@
loopforlaneinlanescollect`
make-arrayextent:element-type',
getflane:type
:initial-element,
getflane:initial-element
declaim
inline,domain-reader
',name
defmacrowith-columnar-buffer-storage
bindingsbufferbuffer-type
&bodybody

Borrow BUFFER-TYPE's active extent, row declaration, and raw lane arrays.

bindings is (length ROW-DECLARATION (ARRAY LANE-NAME) ...). The buffer is evaluated once, and every array receives its precise specialized array type. This is the checked aggregate boundary for closed scalar or SIMD kernels; the kernel traverses the borrowed arrays without row objects. #VKLLPR

destructuring-bind
length-bindingrow-binding&restarray-bindings
bindings
let*
lanes
anddefinition
columnar-layout-definition-lanesdefinition
unlessdefinition
error"There is no columnar buffer definition named ~S."buffer-type
let
resolved-bindings
loopforbindinginarray-bindingscollect
destructuring-bind
variablelane-name
binding
let
lane
findlane-namelanes:key#'columnar-lane-definition-name:test#'eq
unlesslane
error"There is no ~S lane in ~S."lane-namebuffer-type
listvariablelane
let
buffer-value
gensym"BUFFER"
`
let
,buffer-value,buffer
let
,length-binding
,
columnar-generated-symbolbuffer-type"~A-LENGTH"buffer-type
,buffer-value
,row-binding
,
columnar-generated-symbolbuffer-type"~A-ROW-DECLARATION"buffer-type
,buffer-value
,@
loopforinresolved-bindingscollect`
,variable
,
columnar-generated-symbolbuffer-type"~A-~A-LANE"buffer-type
columnar-lane-definition-namelane
,buffer-value
declare
typefixnum,length-binding
,@
loopforinresolved-bindingscollect`
type
simple-array,
upgraded-array-element-type
,variable
,@body
defmacrowith-columnar-materialization-storage
bindingsmaterializationmaterialization-type
&bodybody

Borrow a fixed materialization's domain, extent, row, and raw lane arrays.

bindings is (DOMAIN EXTENT ROW-DECLARATION (ARRAY LANE-NAME) ...). The materialization is evaluated once and each array receives its precise specialized array type.

destructuring-bind
domain-bindingextent-bindingrow-binding&restarray-bindings
bindings
let*
lanes
anddefinition
columnar-layout-definition-lanesdefinition
unlessdefinition
error"There is no columnar layout definition named ~S."materialization-type
let
resolved-bindings
loopforbindinginarray-bindingscollect
destructuring-bind
variablelane-name
binding
let
lane
findlane-namelanes:key#'columnar-lane-definition-name:test#'eq
unlesslane
error"There is no ~S lane in ~S."lane-namematerialization-type
listvariablelane
let
materialization-value
gensym"MATERIALIZATION"
`
let
,materialization-value,materialization
let*
,domain-binding
,
columnar-generated-symbolmaterialization-type"~A-DOMAIN"materialization-type
,materialization-value
,extent-binding
,row-binding
,
columnar-generated-symbolmaterialization-type"~A-ROW-DECLARATION"materialization-type
,materialization-value
,@
loopforinresolved-bindingscollect`
,variable
,
columnar-generated-symbolmaterialization-type"~A-~A-LANE"materialization-type
columnar-lane-definition-namelane
,materialization-value
declare
typefixnum,extent-binding
,@
loopforinresolved-bindingscollect`
type
simple-array,
upgraded-array-element-type
,variable
,@body
defmacrowith-columnar-buffer-row
bindingsbufferindexbuffer-type
&bodybody

Bind one BUFFER-TYPE row's raw lane values at INDEX without allocation.

let*
lanes
anddefinition
columnar-layout-definition-lanesdefinition
unlessdefinition
error"There is no columnar buffer definition named ~S."buffer-type
unless
=
lengthbindings
lengthlanes
error"~S needs ~D row bindings, not ~D."buffer-type
lengthlanes
lengthbindings
let
buffer-value
gensym"BUFFER"
index-value
gensym"INDEX"
`
let
,buffer-value,buffer
,index-value,index
let
,@
loopforbindinginbindingsforlaneinlanesforreader=
columnar-generated-symbolbuffer-type"~A-~A-LANE"buffer-type
columnar-lane-definition-namelane
collect`
,binding
aref
,reader,buffer-value
,index-value
declare,@
loopforbindinginbindingsforlaneinlanescollect`
,@body
defmacrodo-columnar-buffer-rows
bindingsbufferbuffer-type&optionalresult
&bodybody

Visit BUFFER-TYPE's active rows without constructing row objects.

let
buffer-value
gensym"BUFFER"
index
gensym"INDEX"
`
let
,buffer-value,buffer
loopfor,indexfixnumbelow
,
columnar-generated-symbolbuffer-type"~A-LENGTH"buffer-type
,buffer-value
do
with-columnar-buffer-row
,bindings,buffer-value,index,buffer-type
,@body
finally
return,result