luft/z-fiber-benchmark.lisp
defpackage#:luft.z-fiber-benchmark
:use#:cl
:export#:available-kernel-families#:run-z-fiber-benchmark
in-package#:luft.z-fiber-benchmark
defconstant+fiber-words+4
defconstant+direction-count+6
defconstant+plus-x+0
defconstant+minus-x+1
defconstant+plus-y+2
defconstant+minus-y+3
defconstant+plus-z+4
defconstant+minus-z+5
defconstant+u64-mask+#xffffffffffffffff
defconstant+low-63-mask+#x7fffffffffffffff
defconstant+low-62-mask+#x3fffffffffffffff
defstruct
air-workspace
reachable-areachable-bcell-queuerun-offsetsrun-startsrun-endsrun-ownersrun-reachedrun-queue:constructor%make-air-workspace
reachable-areachable-bcell-queuerun-offsetsrun-startsrun-endsrun-ownersrun-reachedrun-queue
deftypeu64-vector'
defstruct
fiber-case
:constructor%make-fiber-case
width0:typefixnum:read-onlyt
pattern:terrain:typekeyword:read-onlyt
stride0:typefixnum:read-onlyt
occupancy:typeu64-vector:read-onlyt
solid-count0:typefixnum
total-runs0:typefixnum:read-onlyt
maximum-runs0:typefixnum:read-onlyt
output:typeu64-vector:read-onlyt
air-workspacenil:typeair-workspace
defstruct
atmosphere-edit-case
:constructor%make-atmosphere-edit-case
casexyzair-run
casenil:typefiber-case:read-onlyt
x0:typefixnum:read-onlyt
y0:typefixnum:read-onlyt
z0:typefixnum:read-onlyt
air-run0:typefixnum:read-onlyt
defstructfiber-sample
width0:typefixnum
pattern:terrain:typekeyword
phase:surface-scalar:typekeyword
simd-family:scalar:typekeyword
index0:typefixnum
iterations1:typefixnum
fiber-count0:typefixnum
solid-count0:typefixnum
run-count0:typefixnum
air-run-count0:typefixnum
face-count0:typefixnum
elapsed-seconds0d0:typedouble-float
bytes-consed0:typeinteger
gc-seconds0d0:typedouble-float
garbage-collections0:typefixnum
defvar*z-fiber-benchmark-sink*0
declaim
defuninput-base
stridelocal-xlocal-y
declare
optimize
speed3
safety0
defunoutput-base
defunoccupancy-word
occupancybasez
defunsolid-bit-p
occupancybasez
defunpattern-solid-p
patternxyz
ecasepattern
:solidt
:terrain
:architecture
:caves
:checkerboard
evenp
defunmake-fiber-occupancy
widthpattern
let*
occupancy
origin-x128
origin-y128
solid-count0
dotimes
local-ystride
dotimes
local-xstride
let
dotimes
word+fiber-words+
valuesoccupancystridesolid-count
defunfiber-run-count-scan
occupancybase
let
runs1
previous
declare
runsdefunfiber-run-count-bits
occupancybase
let
transitions0
declare
dotimes
word+fiber-words+
let*
bits
internal-mask
incftransitions
logcount
logandinternal-mask
logxorbits
ashbits-1
1+transitions
defunoccupancy-run-statistics
let
total0
maximum0
declare
dotimes
dotimes
valuestotalmaximum
defunmake-air-workspace
occupancystride
Index every maximal empty Z interval in every haloed fiber.
let*
fiber-count
run-offsets
make-array
1+fiber-count
:element-type'fixnumstarts
make-array64:element-type'
unsigned-byte8
:adjustablet:fill-pointer0ends
make-array64:element-type'
unsigned-byte8
:adjustablet:fill-pointer0owners
make-array64:element-type'fixnum:adjustablet:fill-pointer0
dotimes
fiberfiber-count
setf
arefrun-offsetsfiber
lengthstarts
let
base
z0
loopwhiledo
if
incfz
let
startz
vector-push-extendstartstarts
vector-push-extend
1-z
endsvector-push-extendfiberowners
setf
arefrun-offsetsfiber-count
lengthstarts
let
run-count
lengthstarts
%make-air-workspacerun-offsets
make-arrayrun-count:element-type'bit:initial-element0
make-arrayrun-count:element-type'fixnum
defunmake-fiber-case
widthpattern
unless
memberpattern'
:solid:terrain:architecture:caves:checkerboard
error"Unknown Z-fiber benchmark pattern ~S."pattern
multiple-value-bind
occupancystridesolid-count
multiple-value-bind
total-runsmaximum-runs
declaim
inlinewrite-vertical-masks
defunwrite-vertical-masks
dotimes
outputword+fiber-words+
let*
solid
previous
next
above
logior
ashsolid-1
ash
logandnext1
63below
setf
logandsolid
lognotabove
logandsolid
lognotbelow
defunsurface-masks-scalar
case
let
width
fiber-case-widthcase
stride
fiber-case-stridecase
occupancy
fiber-case-occupancycase
output
fiber-case-outputcase
dotimes
outputdotimes
defmacrodefine-simd-surface-kernel
namepackagelanes
flet
sym
name
internnamepackage
let`
aref-wide
sym
formatnil"U64.~D-AREF"lanes
and-wide
sym
formatnil"U64.~D-AND"lanes
not-wide
sym
formatnil"U64.~D-NOT"lanes
defun,name
case
let
width
fiber-case-widthcase
stride
fiber-case-stridecase
occupancy
fiber-case-occupancycase
output
fiber-case-outputcase
dotimes
outputdotimes
#+x86-64
#+x86-64
#+arm64
(define-simd-surface-kernel surface-masks-neon #:sb-simd-neon 2)
defuninstruction-set-available-p
name
sb-simd-internals:instruction-set-available-p
sb-simd-internals:find-instruction-setname
defunavailable-kernel-families
Return the runnable Z-fiber kernels, fastest first.
append#+x86-64#+x86-64#+arm64(and (instruction-set-available-p :neon) '(:neon))'
:scalar
defunfastest-simd-family
defunsurface-kernel
family
ecasefamily
:scalar#'surface-masks-scalar
#+x86-64:avx2#'surface-masks-avx2
#+x86-64:sse2#'surface-masks-sse2
#+arm64(:neon #'surface-masks-neon)declaim
inlineset-output-bit
defunset-output-bit
outputbasedirectionz
let
index
setf
arefoutputindex
logior
arefoutputindex
ash1
logandz63
defunsurface-masks-cell-scan
case
Slow per-cell oracle for the bit-fiber surface masks.
let
width
fiber-case-widthcase
stride
fiber-case-stridecase
occupancy
fiber-case-occupancycase
output
fiber-case-outputcase
filloutput0
dotimes
outputdotimes
Camera-connected air is a different question from the complete boundary. The complete boundary includes sealed caves. These kernels seed the air containing a camera above the center fiber, discover only that component, and then write the solid faces incident to it. AIR-CELL is the obvious oracle, AIR-BITS propagates directly through the four-word fibers, and AIR-RUNS traverses maximal empty Z intervals joined by horizontal overlap.
declaim
defunreachable-bit-p
reachablefiberz
defunmark-reachable-bit
reachablefiberz
let
index
setf
arefreachableindex
logior
arefreachableindex
ash1
logandz63
defuncamera-air-seed
case
Return the center fiber's top air cell, or NIL when the camera is obstructed.
let*
stride
fiber-case-stridecase
center
base
z
declaim
inlinewrite-reachable-range
defunwrite-camera-boundary
casereachable
Write solid faces incident to reachable air into case's output buffer.
let
width
fiber-case-widthcase
stride
fiber-case-stridecase
occupancy
fiber-case-occupancycase
output
fiber-case-outputcase
dotimes
outputdotimes
let*
declare
dotimes
word+fiber-words+
let*
solid
air
previous
next
air-above
logior
ashair-1
ash
logandnext1
63air-below
setf
logandsolidair-above
logandsolidair-below
defunwrite-camera-boundary-cell-scan
casereachable
Slow, direct oracle for the packed camera-boundary writer.
let
width
fiber-case-widthcase
stride
fiber-case-stridecase
occupancy
fiber-case-occupancycase
output
fiber-case-outputcase
filloutput0
dotimes
outputdotimes
defuncamera-boundary-cell-flood
case
Reference breadth-first search over individual empty cells.
let*
stride
fiber-case-stridecase
fiber-count
occupancy
fiber-case-occupancycase
workspace
fiber-case-air-workspacecase
reachable
air-workspace-reachable-aworkspace
queue
air-workspace-cell-queueworkspace
head0
tail0
declare
optimize
speed3
safety0
fillreachable0
labels
multiple-value-bind
seed-fiberseed-z
camera-air-seedcase
whenseed-fiber
visitseed-fiberseed-z
defuncamera-boundary-bit-waves
case
Propagate reachable air through packed masks one cell per fixed-point wave.
let*
stride
fiber-case-stridecase
fiber-count
occupancy
fiber-case-occupancycase
workspace
fiber-case-air-workspacecase
source
air-workspace-reachable-aworkspace
destination
air-workspace-reachable-bworkspace
fillsource0
filldestination0
multiple-value-bind
seed-fiberseed-z
camera-air-seedcase
whenseed-fiber
loop
let
changednil
dotimes
fiberfiber-count
let
base
x
declare
dotimes
word+fiber-words+
let*
index
current
arefsourceindex
previous
if
pluspword
arefsource
01-index
next
neighbors
logiorcurrent
logior
ashcurrent-1
ash
logandnext1
63valid
new
logandvalidneighbors
lognot
arefoccupancyindex
setf
arefdestinationindex
newunless
setfchangedt
unlesschanged
rotatefsourcedestination
defuncamera-boundary-run-flood
case
Flood maximal air intervals; horizontal overlap is the adjacency test.
let*
stride
fiber-case-stridecase
workspace
fiber-case-air-workspacecase
offsets
air-workspace-run-offsetsworkspace
starts
air-workspace-run-startsworkspace
ends
air-workspace-run-endsworkspace
owners
air-workspace-run-ownersworkspace
reached
air-workspace-run-reachedworkspace
queue
air-workspace-run-queueworkspace
reachable
air-workspace-reachable-aworkspace
head0
tail0
declare
optimize
speed3
safety0
fillreached0
fillreachable0
Maintaining the atmosphere chain is cheap when an edit is known not to change the component topology. The benchmark below repeatedly removes and restores one exposed terrain cell. Only that cell and its six solid neighbors can gain or lose boundary faces. Arbitrary edits still require dynamic-connectivity machinery or the full rebuild used here as an oracle.
declaim
defunset-packed-bit
wordsindexvalue
let*
word
ashindex-6
mask
ash1
logandindex63
setf
arefwordsword
ifvalue
logior
arefwordsword
masklogand
arefwordsword
lognotmask
defunset-output-bit-value
outputbasedirectionzvalue
defunreachable-cell-p
caselocal-xlocal-yz
and
let*
defunrefresh-atmosphere-cell-faces
casexyz
Refresh every camera-air face owned by one central-domain cell.
let
casewidth
fiber-case-widthcase
when
let*
local-x
1+x
local-y
1+y
input
solid
output
fiber-case-outputcase
defuntoggle-edit-occupancy
edit
Toggle edit's voxel and return true when its new state is solid.
let*
case
atmosphere-edit-case-caseedit
x
atmosphere-edit-case-xedit
y
atmosphere-edit-case-yedit
z
atmosphere-edit-case-zedit
base
occupancy
fiber-case-occupancycase
was-solid
word
mask
ash1
logandz63
declare
optimize
speed3
safety0
setf
arefoccupancyword
logxor
arefoccupancyword
maskifwas-solid
decf
fiber-case-solid-countcase
incf
fiber-case-solid-countcase
notwas-solid
defunmake-atmosphere-edit-case
Make a terrain case whose edit removes and restores one exposed cell.
let*
case
base
occupancy
fiber-case-occupancycase
z
unless
let*
unlessair-run
error"No atmosphere run above edit cell (~D,~D,~D)."xyz
%make-atmosphere-edit-casecasexyzair-run
defunmaintain-atmosphere-surface-edit
edit
Toggle a topology-preserving surface cell and update its boundary locally.
let*
case
atmosphere-edit-case-caseedit
x
atmosphere-edit-case-xedit
y
atmosphere-edit-case-yedit
z
atmosphere-edit-case-zedit
stride
fiber-case-stridecase
reachable
air-workspace-reachable-a
fiber-case-air-workspacecase
now-solid
declare
optimize
speed3
safety0
setf
aref
air-workspace-run-starts
fiber-case-air-workspacecase
atmosphere-edit-case-air-runedit
ifnow-solid
1+z
zfiber-case-outputcase
defunrebuild-atmosphere-after-edit
edit
Toggle edit, rebuild the air-run index, and rediscover the atmosphere.
let
case
atmosphere-edit-case-caseedit
setf
fiber-case-air-workspacecase
defuncopy-output
case
let*
source
fiber-case-outputcase
copy
replacecopysource
copydefunvalidate-case
case
let*
cell-output
scalar-output
simd-families
camera-cell-output
unless
equalpcell-outputscalar-output
error"Cell and scalar-fiber masks disagree for ~D-wide ~(~A~)."
fiber-case-widthcase
fiber-case-patterncase
dolist
simd-familysimd-families
unless
equalpscalar-output
fiber-case-outputcase
error"Scalar and ~A masks disagree for ~D-wide ~(~A~)."simd-family
fiber-case-widthcase
fiber-case-patterncase
unless
equalpcamera-cell-output
fiber-case-outputcase
error"Cell and bit-wave camera boundaries disagree for ~D-wide ~(~A~)."
fiber-case-widthcase
fiber-case-patterncase
unless
equalpcamera-cell-output
fiber-case-outputcase
error"Cell and air-run camera boundaries disagree for ~D-wide ~(~A~)."
fiber-case-widthcase
fiber-case-patterncase
dotimes
y
fiber-case-widthcase
dotimes
x
fiber-case-widthcase
let
base
unless
error"Run counters disagree at (~D,~D) for ~(~A~)."xy
fiber-case-patterncase
defparameter+benchmark-phases+'
:runs-scan:runs-bits:surface-cell:surface-scalar:surface-simd:air-cell:air-bits:air-runs
defparameter+atmosphere-edit-phases+'
:air-edit-maintain:air-edit-rebuild
defuncamera-air-phase-p
phase
memberphase'
:air-cell:air-bits:air-runs
defunphase-zone
phase
ecasephase
:runs-scan:luft/z-fiber/runs-scan
:runs-bits:luft/z-fiber/runs-bits
:surface-cell:luft/z-fiber/surface-cell
:surface-scalar:luft/z-fiber/surface-scalar
:surface-simd:luft/z-fiber/surface-simd
:air-cell:luft/z-fiber/camera-air-cell
:air-bits:luft/z-fiber/camera-air-bits
:air-runs:luft/z-fiber/camera-air-runs
:air-edit-maintain:luft/z-fiber/atmosphere-edit-maintain
:air-edit-rebuild:luft/z-fiber/atmosphere-edit-rebuild
defuncount-runs-with
casefunction
defuninvoke-phase
casephasesimd-family
luv:with-cpu-trace-zone
phase-zonephase
:tracy-valuefiber-case-solid-countcase
setf*z-fiber-benchmark-sink*
ecasephase
:runs-scan
:runs-bits
:surface-cell
:surface-scalar
:surface-simd
:air-cell
:air-bits
:air-runs
defuncalibrate-iterations
casephasesimd-family
loopwithiterationsfixnum=1withtarget-seconds=0.025d0do
let
observation
luv:make-runtime-observation
luv:with-runtime-observation
observation
defunmeasure-phase
formatstream" ~18A "phase
force-outputstream
dotimes
indexwarmup-count
declare
ignoreindex
write-char#\wstream
force-outputstream
let
iterations
formatstream" x~D "iterations
force-outputstream
sb-ext:gc:fullt
let
samples
make-arraysample-count
dotimes
indexsample-count
write-char#\.stream
force-outputstream
let
observation
luv:make-runtime-observation
luv:with-runtime-observation
observation
setf
arefsamplesindex
make-fiber-sample:width
fiber-case-widthcase
:patternfiber-case-patterncase
:phasephase:simd-familysimd-family:indexindex:iterationsiterations:fiber-count:solid-countfiber-case-solid-countcase
:run-countfiber-case-total-runscase
:air-run-countlength
:face-countface-count:elapsed-seconds:bytes-consedair-workspace-run-starts
fiber-case-air-workspacecase
round
:gc-seconds:garbage-collectionsluv:runtime-observation-garbage-collectionsobservation
terpristream
samplesdefuninvoke-atmosphere-edit-phase
editphase
setf*z-fiber-benchmark-sink*
aref
ecasephase
0:air-edit-maintain
:air-edit-rebuild
defuncalibrate-atmosphere-edit-iterations
widthphase
loopwithiterationsfixnum=1withtarget-seconds=0.025d0do
let
observation
luv:make-runtime-observation
luv:with-runtime-observation
observation
defunmeasure-atmosphere-edit-phase
formatstream" ~18A "phase
force-outputstream
let
dotimes
indexwarmup-count
declare
ignoreindex
write-char#\wstream
force-outputstream
let
iterations
formatstream" x~D "iterations
force-outputstream
sb-ext:gc:fullt
let
samples
make-arraysample-count
dotimes
indexsample-count
write-char#\.stream
force-outputstream
let*
case
atmosphere-edit-case-caseedit
face-count
output-face-count
fiber-case-outputcase
air-run-count
length
air-workspace-run-starts
fiber-case-air-workspacecase
observation
luv:make-runtime-observation
luv:with-runtime-observation
observation
luv:with-cpu-trace-zone
phase-zonephase
:tracy-valueiterationssetf
arefsamplesindex
make-fiber-sample:widthwidth:pattern:terrain:phasephase:simd-family:scalar:indexindex:iterationsiterations:fiber-count:solid-count
fiber-case-solid-countcase
:run-countfiber-case-total-runscase
:air-run-countair-run-count:face-countface-count:elapsed-seconds:bytes-consedround
:gc-seconds:garbage-collectionsluv:runtime-observation-garbage-collectionsobservation
terpristream
samplesdefunpercentile
valuesfraction
defunprint-phase-summary
casephasesamplesstream
let
milliseconds
bytes
map'vector#'fiber-sample-bytes-consedsamples
if
formatstream" p50 ~,1F ns/edit p95 ~,1F ns/edit ~,3F KiB/edit~%"
formatstream" p50 ~,4F ms p95 ~,4F ms ~,3F ns/fiber ~,3F KiB~%"
defunwrite-csv-header
stream
formatstream"width,pattern,phase,simd_family,sample,iterations,fibers,cells,solid_cells,runs,air_runs,faces,output_bytes,elapsed_ms,allocated_bytes,gc_ms,batch_gc_count~%"
defunwrite-sample-csv
samplestream
formatstream"~D,~(~A~),~(~A~),~(~A~),~D,~D,~D,~D,~D,~D,~D,~D,~D,~,6F,~D,~,6F,~D~%"
fiber-sample-widthsample
fiber-sample-patternsample
fiber-sample-phasesample
fiber-sample-simd-familysample
fiber-sample-indexsample
fiber-sample-iterationssample
fiber-sample-fiber-countsample
fiber-sample-solid-countsample
fiber-sample-run-countsample
fiber-sample-air-run-countsample
fiber-sample-face-countsample
fiber-sample-bytes-consedsample
fiber-sample-garbage-collectionssample
defunrun-z-fiber-benchmark
&key
widths'
1632
patterns'
:solid:terrain:architecture:caves:checkerboard
warmup-count3
csv-pathname#P"build/luft-z-fiber-benchmark.csv"
stream*standard-output*
Benchmark Z-fiber extraction, camera air, and maintained surface edits.
let
unlesssimd-family
formatstream"LUFT Z fibers: kernels ~{~(~A~)~^, ~}; benchmarking ~A.~%"simd-family
ensure-directories-existcsv-pathname
with-open-file
csvcsv-pathname:direction:output:if-exists:supersede:if-does-not-exist:create
dolist
widthwidths
dolist
patternpatterns
force-outputstream
let
case
multiple-value-bind
face-countcamera-face-countvalidated-families
validate-casecase
declare
ignorevalidated-families
formatstream" ~:D solids, ~:D faces (~:D camera-air), ~:D runs (~,2F/fiber, max ~D), ~:D halo air runs; exact masks~%"
fiber-case-solid-countcase
face-countcamera-face-countfiber-case-total-runscase
fiber-case-maximum-runscase
length
air-workspace-run-starts
fiber-case-air-workspacecase
dolist
phase+benchmark-phases+
let*
phase-face-count
samples
force-outputcsv
values
coerce
csv-pathnamenreverseall-samples
'vectordefine-arithmetic-operator *
Multiplication and scalar scaling.
defun input-base
(stride local-x local-y)defun output-base
(width x y)defun occupancy-word
(occupancy base z)defun solid-bit-p
(occupancy base z)define-style type
Headings, paragraphs, figures and their IDs, mentions, marks.
define-arithmetic-operator +
Addition over compatible quantities.
define-arithmetic-operator and
Logical conjunction of tests and raw truth values.
define-arithmetic-operator <=
Test whether one compatible scalar is at most another.
define-arithmetic-operator <
Test whether one compatible scalar is less than another.
defun terrain-height
(x y)define-arithmetic-operator max
The maximum of compatible quantities.
define-arithmetic-operator min
The minimum of compatible quantities.
define-arithmetic-operator /
Division of two represented quantities.
define-arithmetic-operator -
Subtraction or unary negation.
defun architecture-solid-p
(x y z)define-arithmetic-operator or
Logical disjunction of tests and raw truth values.
define-arithmetic-operator =
Test whether two compatible scalars are equal.
define-arithmetic-operator mod
The non-negative remainder of integer division.
defun cave-solid-p
(x y z)define-arithmetic-operator >
Test whether one compatible scalar is greater than another.
defun pattern-solid-p
(pattern x y z)defun make-fiber-occupancy
(width pattern)defun fiber-run-count-scan
(occupancy base)defun fiber-run-count-bits
(occupancy base)define-shader-operator ldb
Extract the unsigned bit field (BYTE SIZE POSITION) of one unsigned scalar.
defun occupancy-run-statistics
(occupancy stride width)defun make-air-workspace
(occupancy stride)define-arithmetic-operator not
Logical negation of one test or raw truth value.
defun make-fiber-case
(width pattern)defun write-vertical-masks
(occupancy input-base output output-base)defmacro define-simd-surface-kernel
(name package lanes)defun surface-kernel
(family)defun set-output-bit
(output base direction z)defun reachable-bit-p
(reachable fiber z)defun mark-reachable-bit
(reachable fiber z)defun camera-air-seed
(case)defun write-reachable-range
(reachable fiber low high)defun write-camera-boundary
(case reachable)defun write-camera-boundary-cell-scan
(case reachable)define-arithmetic-operator >=
Test whether one compatible scalar is at least another.
defun run
(arguments)defun set-packed-bit
(words index value)defun set-output-bit-value
(output base direction z value)defun reachable-cell-p
(case local-x local-y z)defun refresh-atmosphere-cell-faces
(case x y z)defun output-face-count
(output)defun copy-output
(case)defun validate-case
(case)defun camera-air-phase-p
(phase)defun phase-zone
(phase)defun count-runs-with
(case function)defun invoke-phase
(case phase simd-family)defmacro with-cpu-trace-zone
((name &key (tracy-value nil tracy-value-supplied-p)) &body body)Measure BODY as nested zone NAME for whichever measurement is watching. TRACY-VALUE, when supplied, is attached to the Tracy zone at exit. It does not affect the bounded CPU trace, whose zones retain time and runtime costs. Two independent things may be: a Tracy viewer attached to this image, and an opt-in…
defun calibrate-iterations
(case phase simd-family)defmacro with-runtime-observation
((observation) &body body)Measure time, allocation, GC time, and collections while executing BODY. OBSERVATION is reset in place and BODY's values are preserved. SBCL's byte and GC clocks are process-wide; in a multithreaded image this deliberately attributes concurrent runtime activity during the observed extent too.
defun measure-phase
(case phase simd-family sample-count warmup-count stream face-count)defun invoke-atmosphere-edit-phase
(edit phase)defun calibrate-atmosphere-edit-iterations
(width phase)defun measure-atmosphere-edit-phase
(width phase sample-count warmup-count stream)defun percentile
(values fraction)define-shader-operator sample
Sample a two-dimensional texture through a sampler at a UV coordinate.
defun print-phase-summary
(case phase samples stream)defun write-csv-header
(stream)defun write-sample-csv
(sample stream)defun run-z-fiber-benchmark
(&key (widths '(16 32))
(patterns '(:solid :terrain :architecture :caves :checkerboard))
(sample-count 15) (warmup-count 3)
(csv-pathname #P"build/luft-z-fiber-benchmark.csv")
(stream *standard-output*))
CPU experiments for full-height
luftoccupancy fibers.