path: root/posts/2024-02-25-optimizing-guile.md

title: Optimizing Guile Scheme
date: 2024-02-26 08:30:00
tags: guile, scheme
summary: An overview of how I optimize Guile code with examples
---

[Guile](https://gnu.org/software/guile) is a rather niche language
that I love dearly.  Guile is a Scheme dialect that features an
advanced optimizing bytecode compiler, a JIT compiler, and a modest
set of developer tools for inspecting and debugging.  Through my time
spent developing [Chickadee](/projects/chickadee.html), a game
programming library, I have gotten quite familiar with how to get the
most out of Guile in terms of performance.  Every now and then I share
a tip or two with someone on IRC or the fediverse and think “I should
blog about this” so now I’m finally doing that.  These tips are quite
simple and apply to optimizing any dynamic language.  The only
difference is that there isn’t much in the way of helpful examples
specifically for Guile… until now.

Scheme is a dynamic language which means that there is a limited
amount of compile-time information that can be used by Guile to
optimize the resulting bytecode.  When we put on our optimizer hat,
our job is to give the compiler a hand so the optimization passes can
do their thing.  I should stress that the level of code scrutiny we’re
about to get into is usually unnecessary and the result doesn’t always
look like the beautiful, functional Scheme you may be used to.
However, most programs have some core loop or kernel, a small piece of
the larger program, that would be benefit from being optimized to its
fullest.  In Chickadee, the most performance sensitive code is in the
graphics layer, where lots of floating point math happens.

### Rule 1: Don’t allocate

If you can avoid allocation, you will probably have at least decent
throughput without doing much else.  Some allocations are explicit;
`(vector 1 2 3)` clearly allocates a vector.  Other allocations are
implicit; `(+ x 1)` may or may not allocate depending on the value of
`x`.

If `x` is `42` then there is no allocation because the result, `43`,
is in the fixnum range (`[-2^63, 2^63)` on 64-bit machines.)  Guile
stores fixnums as “immediate” values; values which are not heap
allocated.  However, if `x` is `42.0` then Guile will allocate a float
on the heap to store the result `43.0`.  Did you know that floats were
heap allocated in Guile?  I didn’t when I was getting started!  All
numbers besides fixnums are heap allocated.

Now that you know the hard truth about Guile’s floats, you might think
that math is doomed to be slow on Guile; that any realtime graphics
program will be a stuttery mess.  Keep reading and I will explain why
this isn’t the case!

### Rule 2: Prefer monomorphic over polymorphic

The base Scheme environment mostly provides monomorphic procedures;
`append` is for lists, `string-append` is for strings, etc.  The big
exception to this rule is the numeric tower.  While beautiful, it can
be a hinderance to performant code.  All of the arithmetic operators
are polymorphic; `+` adds any two numbers together and there are many
types of numbers.

Compiled as-is, it means that multiple dispatch on the operands needs
to happen at runtime to determine which specialized “add $type-a and
$type-b” routine needs to be called.

The R6RS specification introduced monomorphic procedures for fixnums
and floats such as `fx+` and `fl+`.  These procedures remove the
overhead of generic dispatching, but they don't help with the
allocation problem; Without a sufficiently advanced compiler, `(fx*
(fx+ x y) z)` will allocate a new float to hold the intermediate
result of `fx+` that gets thrown away after the `fx*` call.  But I
wouldn’t be writing this if Guile *didn’t* have a sufficiently
advanced compiler!

### Why not both?

We can write numeric code that is both specialized and allocates
minimally.  Guile’s compiler performs a *type inference* pass on our
code and will specialize numeric operations wherever possible.  For
example, if Guile can prove that all the variables involved in `(* (+
x y) z)` are floats, it will optimize the resulting bytecode so that:

* The floats within `x`, `y`, and `z` are used directly.
* `+` and `*` are compiled to specialized `fadd` and `fmul` primitives.
* The intermediate result of `(+ x y)` does not allocate a new heap
  object.

This is called *unboxing*.  Imagine every Scheme value as an object
stored inside a little box.  Unboxing means removing some objects from
their respective boxes, performing some sequence of operations on them
*without* storing each intermediate result in a throwaway box, and
then putting the final result into a new box.  Unboxing is how we we
can satisfy both of our optimization rules for numeric code.

Unboxed floating point math is what allows Chickadee to do things like
render thousands of sprites at 60 frames per second without constant
GC-related stutter.

### The tools

To optimize effectively, we need tools to help us identify problematic
code and tools to validate that our changes are improving things.  The
most essential tools I use are accessible via REPL commands:

* `,profile`: Evaluate an expression in the context of `statprof` and
  print the results.
* `,disassemble`: Print the bytecode disassembly of a procedure.

An additional tool that does not have it’s own REPL command is
`gcprof`, which is a profiler that can help identify code that most
frequently triggers garbage collection.  I won’t be using it here but
you should know it exists.

Now, let’s get into some examples and walk through optimizing each
one.

### Example 1: Variadic arguments

It’s common in Scheme for procedures to handle an arbitrary number of
arguments.  For example, the `map` procedure can process as many lists
as you throw at it; `(map + '(1 2 3) '(4 5 6) '(7 8 9))` produces the
result `(12 15 18)`.

Supporting an arbitrary number of arguments makes for flexible
interfaces, but a naive implementation will cause excessive GC churn
in the common case where only a few arguments are passed.

Let’s analyze a contrived example.  The following procedure computes
the average of all arguments:

```scheme
(use-modules (srfi srfi-1))

(define (average . args)
  (/ (fold + 0 args) (length args)))
```

Let's profile it and see how well it performs:

```scheme
scheme@(guile-user)> ,profile (let lp ((i 0))
                                (when (< i 100000000)
                                  (average 1 2 3)
                                  (lp (+ i 1))))
%     cumulative   self
time   seconds     seconds  procedure
 31.99     13.68      4.43  <current input>:1918:16:average
 23.43      7.94      3.25  srfi/srfi-1.scm:452:2:fold
 22.73      3.15      3.15  +
  8.22      1.14      1.14  length
  5.94      0.82      0.82  list?
  5.24      0.73      0.73  procedure?
  1.22     13.85      0.17  <current input>:1979:9
  1.22      0.17      0.17  %after-gc-thunk
  0.00      0.17      0.00  anon #x19675c0
---
Sample count: 572
Total time: 13.853321979 seconds (6.297763116 seconds in GC)
```

Nearly half of our time was spent in GC.  Let's find out why by taking
a look at the disassembly:

```
scheme@(guile-user)> ,disassemble average
Disassembly of #<procedure average args> at #x1a9cbd0:

   0    (instrument-entry 240)                                at (unknown file):1918:16
   2    (assert-nargs-ge 1)
   3    (bind-rest 1)                   ;; 2 slots
   4    (alloc-frame 9)                 ;; 9 slots
   5    (static-ref 8 189)              ;; #<variable 7fa802ccba40 value: #<procedure fold (kons knil list1) | (kons kni…> at (unknown file):1919:6
   7    (immediate-tag=? 8 7 0)         ;; heap-object?
   9    (je 9)                          ;; -> L1
  10    (static-ref 8 162)              ;; #<directory (guile-user) 7fa802cf8c80>
  12    (static-ref 6 192)              ;; fold
  14    (call-scm<-scm-scm 8 8 6 111)   ;; lookup-bound
  16    (static-set! 8 178)             ;; #<variable 7fa802ccba40 value: #<procedure fold (kons knil list1) | (kons kni…>
L1:
  18    (scm-ref/immediate 8 8 1)
  19    (static-ref 6 187)              ;; #<variable 7fa802c36a40 value: #<procedure + (#:optional _ _ . _)>> at (unknown file):1919:11
  21    (immediate-tag=? 6 7 0)         ;; heap-object?
  23    (je 7)                          ;; -> L2
  24    (call-scm<-scmn-scmn 6 194 198 113);; lookup-bound-private
  28    (static-set! 6 178)             ;; #<variable 7fa802c36a40 value: #<procedure + (#:optional _ _ . _)>>
L2:
  30    (scm-ref/immediate 2 6 1)
  31    (make-immediate 1 2)            ;; 0                  at (unknown file):1919:13
  32    (mov 3 8)                                             at (unknown file):1919:5
  33    (mov 0 7)
  34    (handle-interrupts)
  35    (call 5 4)
  37    (receive 0 5 9)
  39    (static-ref 6 191)              ;; #<variable 7fa802c2d990 value: #<procedure length (_)>> at (unknown file):1919:21
  41    (immediate-tag=? 6 7 0)         ;; heap-object?
  43    (je 7)                          ;; -> L3
  44    (call-scm<-scmn-scmn 6 174 188 113);; lookup-bound-private
  48    (static-set! 6 182)             ;; #<variable 7fa802c2d990 value: #<procedure length (_)>>
L3:
  50    (scm-ref/immediate 4 6 1)
  51    (mov 3 7)
  52    (handle-interrupts)
  53    (call 4 2)
  55    (receive 1 4 9)
  57    (call-scm<-scm-scm 8 8 7 5)     ;; div                at (unknown file):1919:2
  59    (reset-frame 1)                 ;; 1 slot
  60    (handle-interrupts)
  61    (return-values)
```

Note instruction 3, `bind-rest`.  The Guile manual says:

> Instruction: bind-rest f24:DST
>
> Collect any arguments at or above DST into a list, and store that
> list at DST.

So, for each call, a sequence of pairs is allocated to hold all of the
arguments.  That's probably where a lot of our allocation is coming
from.  To optimize this, let’s first assume that `average` is
typically called with 3 arguments or less.  It would be great if we
could make these common cases fast while still allowing the
flexibility of passing an arbitrary number of arguments.  To do this,
we’ll use `case-lambda`:

```scheme
(define average
  (case-lambda
    (() 0)
    ((x) x)
    ((x y) (/ (+ x y) 2))
    ((x y z) (/ (+ x y z) 3))
    ;; ... and so on, add as many cases as you'd like!
    (args
     (/ (fold + 0 args) (length args)))))
```

Let’s re-run the profiler to see if this is actually better:

```
%     cumulative   self
time   seconds     seconds  procedure
 76.47      0.63      0.63  <current input>:2055:2:average
 23.53      0.82      0.19  <current input>:2073:9
---
Sample count: 51
Total time: 0.82462725 seconds (0.0 seconds in GC)
```

I'd say that nearly 17x faster with no GC is an improvement!

Let’s see what's changed in the disassembly:

```
scheme@(guile-user)> ,disassemble average
Disassembly of #<procedure average () | (x) | (x y) | (x y z) | args> at #x1ab4c70:

   0    (instrument-entry 278)                                at (unknown file):2055:2
   2    (arguments<=? 1)
   3    (jne 6)                         ;; -> L1
   4    (alloc-frame 9)                 ;; 9 slots
   5    (make-immediate 8 2)            ;; 0                  at (unknown file):2056:8
   6    (reset-frame 1)                 ;; 1 slot
   7    (handle-interrupts)
   8    (return-values)
L1:
   9    (arguments<=? 2)
  10    (jne 6)                         ;; -> L2
  11    (alloc-frame 9)                 ;; 9 slots
  12    (mov 8 7)
  13    (reset-frame 1)                 ;; 1 slot
  14    (handle-interrupts)
  15    (return-values)
L2:
  16    (arguments<=? 3)
  17    (jne 10)                        ;; -> L3
  18    (alloc-frame 9)                 ;; 9 slots
  19    (call-scm<-scm-scm 8 7 6 0)     ;; add                at (unknown file):2058:14
  21    (make-immediate 7 10)           ;; 2                  at (unknown file):2058:22
  22    (call-scm<-scm-scm 8 8 7 5)     ;; div                at (unknown file):2058:11
  24    (reset-frame 1)                 ;; 1 slot
  25    (handle-interrupts)
  26    (return-values)
L3:
  27    (arguments<=? 4)
  28    (jne 12)                        ;; -> L4
  29    (alloc-frame 9)                 ;; 9 slots
  30    (call-scm<-scm-scm 8 7 6 0)     ;; add                at (unknown file):2059:16
  32    (call-scm<-scm-scm 8 8 5 0)     ;; add
  34    (make-immediate 7 14)           ;; 3                  at (unknown file):2059:26
  35    (call-scm<-scm-scm 8 8 7 5)     ;; div                at (unknown file):2059:13
  37    (reset-frame 1)                 ;; 1 slot
  38    (handle-interrupts)
  39    (return-values)
L4:
  40    (assert-nargs-ge 1)
  41    (bind-rest 1)                   ;; 2 slots
  42    (alloc-frame 9)                 ;; 9 slots
  43    (static-ref 8 189)              ;; #f                 at (unknown file):2061:9
  45    (immediate-tag=? 8 7 0)         ;; heap-object?
  47    (je 9)                          ;; -> L5
  48    (static-ref 8 162)              ;; #<directory (guile-user) 7fa802cf8c80>
  50    (static-ref 6 192)              ;; fold
  52    (call-scm<-scm-scm 8 8 6 111)   ;; lookup-bound
  54    (static-set! 8 178)             ;; #f
L5:
  56    (scm-ref/immediate 8 8 1)
  57    (static-ref 6 187)              ;; #f                 at (unknown file):2061:14
  59    (immediate-tag=? 6 7 0)         ;; heap-object?
  61    (je 7)                          ;; -> L6
  62    (call-scm<-scmn-scmn 6 194 198 113);; lookup-bound-private
  66    (static-set! 6 178)             ;; #f
L6:
  68    (scm-ref/immediate 2 6 1)
  69    (make-immediate 1 2)            ;; 0                  at (unknown file):2061:16
  70    (mov 3 8)                                             at (unknown file):2061:8
  71    (mov 0 7)
  72    (handle-interrupts)
  73    (call 5 4)
  75    (receive 0 5 9)
  77    (static-ref 6 191)              ;; #f                 at (unknown file):2061:24
  79    (immediate-tag=? 6 7 0)         ;; heap-object?
  81    (je 7)                          ;; -> L7
  82    (call-scm<-scmn-scmn 6 174 188 113);; lookup-bound-private
  86    (static-set! 6 182)             ;; #f
L7:
  88    (scm-ref/immediate 4 6 1)
  89    (mov 3 7)
  90    (handle-interrupts)
  91    (call 4 2)
  93    (receive 1 4 9)
  95    (call-scm<-scm-scm 8 8 7 5)     ;; div                at (unknown file):2061:5
  97    (reset-frame 1)                 ;; 1 slot
  98    (handle-interrupts)
  99    (return-values)
```

There are more instructions now, but the branches for the known arity
cases do not contain a `bind-rest` instruction.  Only branch `L4`, the
one that handles the final clause of the `case-lambda`, uses
`bind-rest`.

### Example 2: Floating point math

> “Nothing brings fear to my heart more than a floating point number.”
>
> — [Gerald Sussman](https://youtu.be/HB5TrK7A4pI?t=672)

Programs that need to crunch numbers in realtime, such as games, rely
on floating point numbers.  Dedicated hardware in the form of FPUs and
GPUs make them essential for gettin’ math done quick and so we put up
with their black magic.

Consider the following code that calculates the magnitude of a 2D
vector:

```scheme
(define (magnitude x y)
  (sqrt (+ (* x x) (* y y))))
```

Would you believe me if I told you the bytecode is less than perfect?

```scheme
scheme@(guile-user)> ,disassemble magnitude
Disassembly of #<procedure magnitude (x y)> at #x1a3fad8:

   0    (instrument-entry 84)                                 at (unknown file):2106:16
   2    (assert-nargs-ee/locals 3 0)    ;; 3 slots (2 args)
   3    (call-scm<-scm-scm 2 1 1 4)     ;; mul                at (unknown file):2107:11
   5    (call-scm<-scm-scm 1 0 0 4)     ;; mul                at (unknown file):2107:19
   7    (call-scm<-scm-scm 2 2 1 0)     ;; add                at (unknown file):2107:8
   9    (call-scm<-scm 2 2 68)          ;; sqrt               at (unknown file):2107:2
  11    (reset-frame 1)                 ;; 1 slot
  12    (handle-interrupts)
  13    (return-values)
```

Note the `call-scm<-scm-scm` instructions calling generic math
primitives `mul` and `add`.

```scheme
scheme@(guile-user)> ,profile (let lp ((i 0))
                                (when (< i 100000000)
                                  (magnitude 3.0 4.0)
                                  (lp (+ i 1))))
%     cumulative   self
time   seconds     seconds  procedure
 85.12     26.94     24.50  <current input>:13:16:magnitude
  8.48      2.44      2.44  %after-gc-thunk
  6.40     28.79      1.84  <current input>:21:9
  0.00      2.44      0.00  anon #x1e9e5c0
---
Sample count: 672
Total time: 28.786191396 seconds (26.349479685 seconds in GC)
```

Oof, nearly all of our time is spent in GC!

To fix this, we need to constrain our inputs by using predicates to
guard the path to the numeric code.  This will inform Guile that
certain types of numbers will never reach this branch and allow the
compiler to choose more specialized primitives.  If we’re okay with
only working with floats (we are) then we should constrain our
procedure accordingly:

```scheme
(define (magnitude x y)
  (unless (and (real? x) (inexact? x)
               (real? y) (inexact? y))
    (error "expected floats" x y))
  (sqrt (+ (* x x) (* y y))))
```

And the stats:

```scheme
%     cumulative   self
time   seconds     seconds  procedure
 82.73      4.13      4.06  <current input>:177:16:magnitude
 15.83      4.91      0.78  <current input>:187:9
  1.44      0.07      0.07  %after-gc-thunk
  0.00      0.07      0.00  anon #x1e9e5c0
---
Sample count: 139
Total time: 4.909505945 seconds (3.970948419 seconds in GC)
```

Our code now runs about 6x faster, but GC is still taking up most of
that time.  Let's examine the disassembly:

```
Disassembly of #<procedure magnitude (x y)> at #x1f41378:

   0    (instrument-entry 206)                                at (unknown file):177:16
   2    (assert-nargs-ee/locals 3 4)    ;; 7 slots (2 args)
   3    (immediate-tag=? 5 3 2)         ;; fixnum?            at (unknown file):178:15
   5    (je 10)                         ;; -> L1
   6    (immediate-tag=? 5 7 0)         ;; heap-object?
   8    (jne 54)                        ;; -> L3
   9    (heap-tag=? 5 127 23)           ;; heap-number?
  11    (jne 51)                        ;; -> L3
  12    (heap-tag=? 5 4095 791)         ;; compnum?
  14    (je 48)                         ;; -> L3
L1:
  15    (immediate-tag=? 5 3 2)         ;; fixnum?            at (unknown file):178:25
  17    (je 45)                         ;; -> L3
  18    (heap-tag=? 5 4095 535)         ;; flonum?
  20    (jne 42)                        ;; -> L3
  21    (immediate-tag=? 4 3 2)         ;; fixnum?            at (unknown file):179:15
  23    (je 10)                         ;; -> L2
  24    (immediate-tag=? 4 7 0)         ;; heap-object?
  26    (jne 36)                        ;; -> L3
  27    (heap-tag=? 4 127 23)           ;; heap-number?
  29    (jne 33)                        ;; -> L3
  30    (heap-tag=? 4 4095 791)         ;; compnum?
  32    (je 30)                         ;; -> L3
L2:
  33    (immediate-tag=? 4 3 2)         ;; fixnum?            at (unknown file):179:25
  35    (je 27)                         ;; -> L3
  36    (heap-tag=? 4 4095 535)         ;; flonum?
  38    (jne 24)                        ;; -> L3
  39    (call-f64<-scm 6 5 17)          ;; scm->f64           at (unknown file):181:11
  41    (fmul 6 6 6)
  42    (call-f64<-scm 5 4 17)          ;; scm->f64           at (unknown file):181:19
  44    (fmul 5 5 5)
  45    (fadd 6 6 5)                                          at (unknown file):181:8
  46    (call-f64<-f64 6 6 70)                                at (unknown file):181:2
  48    (allocate-pointerless-words/immediate 5 2)
  49    (load-u64 4 0 535)
  52    (word-set!/immediate 5 0 4)
  53    (tail-pointer-ref/immediate 4 5 1)
  54    (load-u64 3 0 0)
  57    (f64-set! 4 3 6)
  58    (mov 6 5)
  59    (reset-frame 1)                 ;; 1 slot
  60    (handle-interrupts)
  61    (return-values)
L3:
  62    (static-ref 6 134)              ;; misc-error         at (unknown file):180:4
  64    (make-immediate 3 4)            ;; #f
  65    (make-non-immediate 2 133)      ;; "expected floats ~S ~S" at (unknown file):180:11
  67    (make-immediate 1 772)          ;; ()                 at (unknown file):180:4
  68    (allocate-words/immediate 0 2)
  69    (scm-set!/immediate 0 0 4)
  70    (scm-set!/immediate 0 1 1)
  71    (allocate-words/immediate 4 2)
  72    (scm-set!/immediate 4 0 5)
  73    (scm-set!/immediate 4 1 0)
  74    (allocate-words/immediate 5 2)
  75    (scm-set!/immediate 5 0 3)
  76    (scm-set!/immediate 5 1 1)
  77    (allocate-words/immediate 1 2)
  78    (scm-set!/immediate 1 0 4)
  79    (scm-set!/immediate 1 1 5)
  80    (allocate-words/immediate 5 2)
  81    (scm-set!/immediate 5 0 2)
  82    (scm-set!/immediate 5 1 1)
  83    (allocate-words/immediate 4 2)
  84    (scm-set!/immediate 4 0 3)
  85    (scm-set!/immediate 4 1 5)
  86    (throw 6 4)
```

Important note: It seems that Guile 3.0.9, the latest stable release
as of writing, does not perform the desired optimization here.  All
the output you are seeing here is from a Guile built from commit
`fb1f5e28b1a575247fd16184b1c83b8838b09716` of the main branch.  If you
are reading this months/years into the future, then as long as you
have Guile > 3.0.9 you should be all set.

There's a lot more instructions, but starting with instruction 41 we
can see that unboxed float instrutions like `fadd` and `fmul` are
being used.  It's not made very clear, but instruction 46,
`call-f64<-f64`, is a call to a `sqrt` primitive specialized for
floats.  Since our inputs have to be floats, Guile unboxes them as
f64s via the `call-f64<-scm` instruction.  The cost of the runtime
checks is cheap compared to the cost of all the GC churn in the first
version.

The source of our time spent in GC is the
`allocate-pointerless-words/immediate` instruction at index 48.  This
allocates a new heap object and the subsequent instructions like
`f64-set!` set the contents of the heap object to the result of the
`sqrt` call.  Our optimizations are local and once we cross the
procedure call boundary we need boxed values again.

### Example 3: Please inline

Guile will automatically inline procedures it considers small enough
for the potential performance improvements to be worth the additional
code size.  It’s a nice feature, but there are times when you wish
something would be inlined but it doesn’t happen.

Let’s define a procedure that normalizes 2D vectors. To do so, we’ll
build atop the `magnitude` procedure from example 2.

```scheme
(define (normalize x y)
  (let ((mag (magnitude x y)))
    (when (= mag 0.0)
      (error "cannot normalize vector with 0 magnitude" x y))
    (values (/ x mag) (/ y mag))))
```

It would be *great* if all the unboxed float goodness from `magnitude`
spilled over to `normalize`.  Let’s see it that happened (it didn’t):

```
scheme@(guile-user)> ,disassemble normalize
Disassembly of #<procedure normalize (x y)> at #x16609b0:

   0    (instrument-entry 254)                                at (unknown file):17:19
   2    (assert-nargs-ee/locals 3 6)    ;; 9 slots (2 args)
   3    (static-ref 8 211)              ;; #<variable 7f05e03e8490 value: #<procedure magnitude (x y)>> at (unknown file):18:14
   5    (immediate-tag=? 8 7 0)         ;; heap-object?
   7    (je 9)                          ;; -> L1
   8    (static-ref 8 184)              ;; #<directory (guile-user) 7f05ec481c80>
  10    (static-ref 5 214)              ;; magnitude
  12    (call-scm<-scm-scm 8 8 5 111)   ;; lookup-bound
  14    (static-set! 8 200)             ;; #<variable 7f05e03e8490 value: #<procedure magnitude (x y)>>
L1:
  16    (scm-ref/immediate 2 8 1)
  17    (mov 1 7)                                             at (unknown file):18:13
  18    (mov 0 6)
  19    (handle-interrupts)
  20    (call 6 3)
  22    (receive 0 6 9)
  24    (static-ref 5 210)              ;; 0.0                at (unknown file):19:17
  26    (=? 8 5)                                              at (unknown file):19:10
  27    (je 11)                         ;; -> L2
  28    (call-scm<-scm-scm 7 7 8 5)     ;; div                at (unknown file):21:12
  30    (call-scm<-scm-scm 8 6 8 5)     ;; div                at (unknown file):21:22
  32    (mov 6 7)                                             at (unknown file):21:4
  33    (mov 7 8)
  34    (mov 8 6)
  35    (reset-frame 2)                 ;; 2 slots
  36    (handle-interrupts)
  37    (return-values)
L2:
  38    (static-ref 8 206)              ;; misc-error         at (unknown file):20:6
  40    (make-immediate 5 4)            ;; #f
  41    (make-non-immediate 4 205)      ;; "cannot normalize vector with 0 magnitude ~S ~S" at (unknown file):20:13
  43    (make-immediate 3 772)          ;; ()                 at (unknown file):20:6
  44    (allocate-words/immediate 2 2)
  45    (scm-set!/immediate 2 0 6)
  46    (scm-set!/immediate 2 1 3)
  47    (allocate-words/immediate 6 2)
  48    (scm-set!/immediate 6 0 7)
  49    (scm-set!/immediate 6 1 2)
  50    (allocate-words/immediate 7 2)
  51    (scm-set!/immediate 7 0 5)
  52    (scm-set!/immediate 7 1 3)
  53    (allocate-words/immediate 3 2)
  54    (scm-set!/immediate 3 0 6)
  55    (scm-set!/immediate 3 1 7)
  56    (allocate-words/immediate 7 2)
  57    (scm-set!/immediate 7 0 4)
  58    (scm-set!/immediate 7 1 3)
  59    (allocate-words/immediate 6 2)
  60    (scm-set!/immediate 6 0 5)
  61    (scm-set!/immediate 6 1 7)
  62    (throw 8 6)
```

Instruction 20 is `call`, so inlining didn’t happen.  Furthermore, the
two `/` calls (instructions 28 and 30) use the generic division
primitive rather than `fdiv`.  No unboxing for us.

The profiler confirms that things aren’t so great:

```scheme
scheme@(guile-user)> ,profile (let lp ((i 0))
                                (when (< i 100000000)
                                  (normalize 3.0 4.0)
                                  (lp (+ i 1))))
%     cumulative   self
time   seconds     seconds  procedure
 52.80     21.16     11.51  <current input>:17:19:normalize
 41.01      9.36      8.94  <current input>:9:19:magnitude
  3.29      0.72      0.72  %after-gc-thunk
  2.90     21.80      0.63  <current input>:23:9
  0.00      0.72      0.00  anon #x15fd5c0
---
Sample count: 517
Total time: 21.795201408 seconds (19.704395422 seconds in GC)
```

To force the compiler to inline `magnitude`, we’ll change the
definition of to use `define-inlinable`:

```scheme
(define-inlinable (magnitude x y)
  (unless (and (real? x) (inexact? x)
               (real? y) (inexact? y))
    (error "expected floats" x y))
  (sqrt (+ (* x x) (* y y))))
```

`define-inlinable` is a handy little macro that will substitute the
procedure body into its call sites.

Now let’s see the disassembly:

```
Disassembly of #<procedure normalize (x y)> at #x16993c8:

   0    (instrument-entry 276)                                at (unknown file):58:19
   2    (assert-nargs-ee/locals 3 4)    ;; 7 slots (2 args)
   3    (immediate-tag=? 5 3 2)         ;; fixnum?            at (unknown file):59:13
   5    (je 10)                         ;; -> L1
   6    (immediate-tag=? 5 7 0)         ;; heap-object?
   8    (jne 97)                        ;; -> L4
   9    (heap-tag=? 5 127 23)           ;; heap-number?
  11    (jne 94)                        ;; -> L4
  12    (heap-tag=? 5 4095 791)         ;; compnum?
  14    (je 91)                         ;; -> L4
L1:
  15    (immediate-tag=? 5 3 2)         ;; fixnum?
  17    (je 88)                         ;; -> L4
  18    (heap-tag=? 5 4095 535)         ;; flonum?
  20    (jne 85)                        ;; -> L4
  21    (immediate-tag=? 4 3 2)         ;; fixnum?
  23    (je 10)                         ;; -> L2
  24    (immediate-tag=? 4 7 0)         ;; heap-object?
  26    (jne 79)                        ;; -> L4
  27    (heap-tag=? 4 127 23)           ;; heap-number?
  29    (jne 76)                        ;; -> L4
  30    (heap-tag=? 4 4095 791)         ;; compnum?
  32    (je 73)                         ;; -> L4
L2:
  33    (immediate-tag=? 4 3 2)         ;; fixnum?
  35    (je 70)                         ;; -> L4
  36    (heap-tag=? 4 4095 535)         ;; flonum?
  38    (jne 67)                        ;; -> L4
  39    (call-f64<-scm 6 5 17)          ;; scm->f64
  41    (fmul 3 6 6)
  42    (call-f64<-scm 2 4 17)          ;; scm->f64
  44    (fmul 1 2 2)
  45    (fadd 3 3 1)
  46    (call-f64<-f64 3 3 70)
  48    (load-f64 1 0 0)                                      at (unknown file):60:10
  51    (f64=? 3 1)
  52    (je 28)                         ;; -> L3
  53    (fdiv 6 6 3)                                          at (unknown file):62:12
  54    (allocate-pointerless-words/immediate 5 2)
  55    (load-u64 4 0 535)
  58    (word-set!/immediate 5 0 4)
  59    (tail-pointer-ref/immediate 4 5 1)
  60    (load-u64 1 0 0)
  63    (f64-set! 4 1 6)
  64    (fdiv 6 2 3)                                          at (unknown file):62:22
  65    (allocate-pointerless-words/immediate 4 2)
  66    (load-u64 3 0 535)
  69    (word-set!/immediate 4 0 3)
  70    (tail-pointer-ref/immediate 3 4 1)
  71    (load-u64 2 0 0)
  74    (f64-set! 3 2 6)
  75    (mov 6 5)                                             at (unknown file):62:4
  76    (mov 5 4)
  77    (reset-frame 2)                 ;; 2 slots
  78    (handle-interrupts)
  79    (return-values)
L3:
  80    (static-ref 6 178)              ;; misc-error         at (unknown file):61:6
  82    (make-immediate 3 4)            ;; #f
  83    (make-non-immediate 2 177)      ;; "cannot normalize vector with 0 magnitude ~S ~S" at (unknown file):61:13
  85    (make-immediate 1 772)          ;; ()                 at (unknown file):61:6
  86    (allocate-words/immediate 0 2)
  87    (scm-set!/immediate 0 0 4)
  88    (scm-set!/immediate 0 1 1)
  89    (allocate-words/immediate 4 2)
  90    (scm-set!/immediate 4 0 5)
  91    (scm-set!/immediate 4 1 0)
  92    (allocate-words/immediate 5 2)
  93    (scm-set!/immediate 5 0 3)
  94    (scm-set!/immediate 5 1 1)
  95    (allocate-words/immediate 1 2)
  96    (scm-set!/immediate 1 0 4)
  97    (scm-set!/immediate 1 1 5)
  98    (allocate-words/immediate 5 2)
  99    (scm-set!/immediate 5 0 2)
 100    (scm-set!/immediate 5 1 1)
 101    (allocate-words/immediate 4 2)
 102    (scm-set!/immediate 4 0 3)
 103    (scm-set!/immediate 4 1 5)
 104    (throw 6 4)
L4:
 105    (static-ref 6 153)              ;; misc-error         at (unknown file):59:13
 107    (make-immediate 3 4)            ;; #f
 108    (make-non-immediate 2 160)      ;; "expected floats ~S ~S" at (unknown file):54:11
 110    (make-immediate 1 772)          ;; ()                 at (unknown file):59:13
 111    (allocate-words/immediate 0 2)
 112    (scm-set!/immediate 0 0 4)
 113    (scm-set!/immediate 0 1 1)
 114    (allocate-words/immediate 4 2)
 115    (scm-set!/immediate 4 0 5)
 116    (scm-set!/immediate 4 1 0)
 117    (allocate-words/immediate 5 2)
 118    (scm-set!/immediate 5 0 3)
 119    (scm-set!/immediate 5 1 1)
 120    (allocate-words/immediate 1 2)
 121    (scm-set!/immediate 1 0 4)
 122    (scm-set!/immediate 1 1 5)
 123    (allocate-words/immediate 5 2)
 124    (scm-set!/immediate 5 0 2)
 125    (scm-set!/immediate 5 1 1)
 126    (allocate-words/immediate 4 2)
 127    (scm-set!/immediate 4 0 3)
 128    (scm-set!/immediate 4 1 5)
 129    (throw 6 4)
```

Much better!  All of the instructions for `magnitude` are now part of
`normalize`.  `/` is compiled to `fdiv` just like we had hoped.

```scheme
%     cumulative   self
time   seconds     seconds  procedure
 93.04      9.24      9.19  <current input>:58:19:normalize
  6.52      9.88      0.64  <current input>:71:9
  0.43      0.04      0.04  %after-gc-thunk
  0.00      0.04      0.00  anon #x15fd5c0
---
Sample count: 230
Total time: 9.879456057 seconds (8.858042989 seconds in GC)
```

We’re 2x faster now, though still a lot of GC.  For our final example,
we will fully embrace *mutable state*.  As much us Schemers like
functional programming, mutable state is sometimes necessary.

### Example 4: Bytevectors

For *really* performance sensitive math code, we can go one step
further to avoid allocation and use bytevectors to store the results
of numeric operations.  Chickadee uses bytevectors extensively to
minimize the number of heap allocated floats.  Bytevectors have the
advantage of unboxed getters and setters, so they’re my preferred data
structure for math intensive code.

Let's revisit the vector math of the previous two examples, but this
time using bytevectors to represent 2D vectors.

```scheme
(define-inlinable (vec2 x y)
  (let ((bv (make-f32vector 2)))
    (f32vector-set! bv 0 x)
    (f32vector-set! bv 1 y)
    bv))

(define-inlinable (vec2-x v)
  (f32vector-ref v 0))

(define-inlinable (vec2-y v)
  (f32vector-ref v 1))

(define-inlinable (magnitude v)
  (let ((x (vec2-x v))
        (y (vec2-y v)))
    (sqrt (+ (* x x) (* y y)))))

(define (normalize v)
  (let ((mag (magnitude v)))
    (when (= mag 0.0)
      (error "cannot normalize vector with 0 magnitude" v))
    (vec2 (/ (vec2-x v) mag) (/ (vec2-y v) mag))))
```

Here’s the disassembly for `normalize` now:

```
Disassembly of #<procedure normalize (v)> at #x1b05d50:

   0    (instrument-entry 492)                                at (unknown file):454:19
   2    (assert-nargs-ee/locals 2 11)   ;; 13 slots (1 arg)
   3    (make-immediate 12 2)           ;; 0                  at (unknown file):455:13
   4    (immediate-tag=? 11 7 0)        ;; heap-object?
   6    (jne 83)                        ;; -> L8
   7    (heap-tag=? 11 127 77)          ;; bytevector?
   9    (jne 80)                        ;; -> L8
  10    (word-ref/immediate 10 11 1)
  11    (load-s64 9 0 0)
  14    (imm-u64<? 10 3)
  15    (jnl 72)                        ;; -> L7
  16    (usub/immediate 10 10 3)
  17    (pointer-ref/immediate 8 11 2)
  18    (f32-ref 7 8 9)
  19    (make-immediate 6 18)           ;; 4
  20    (load-s64 5 0 4)
  23    (u64<? 5 10)
  24    (jnl 61)                        ;; -> L6
  25    (f32-ref 10 8 5)
  26    (fmul 8 7 7)
  27    (fmul 4 10 10)
  28    (fadd 8 8 4)
  29    (call-f64<-f64 8 8 70)
  31    (load-f64 4 0 0)                                      at (unknown file):456:10
  34    (f64=? 8 4)
  35    (je 48)                         ;; -> L5
  36    (fdiv 11 7 8)                                         at (unknown file):458:10
  37    (fdiv 10 10 8)                                        at (unknown file):458:29
  38    (static-ref 8 332)              ;; #f                 at (unknown file):388:13
  40    (immediate-tag=? 8 7 0)         ;; heap-object?
  42    (je 9)                          ;; -> L1
  43    (static-ref 8 305)              ;; #<directory (guile-user) 7f05ec481c80>
  45    (static-ref 7 335)              ;; make-f32vector
  47    (call-scm<-scm-scm 8 8 7 111)   ;; lookup-bound
  49    (static-set! 8 321)             ;; #f
L1:
  51    (scm-ref/immediate 1 8 1)
  52    (make-immediate 0 10)           ;; 2                  at (unknown file):388:28
  53    (handle-interrupts)                                   at (unknown file):458:4
  54    (call 11 2)
  56    (receive 4 11 13)
  58    (immediate-tag=? 8 7 0)         ;; heap-object?
  60    (jne 21)                        ;; -> L4
  61    (heap-tag=? 8 127 77)           ;; bytevector?
  63    (jne 18)                        ;; -> L4
  64    (word-ref/immediate 7 8 1)
  65    (imm-u64<? 7 3)
  66    (jnl 13)                        ;; -> L3
  67    (usub/immediate 12 7 3)
  68    (pointer-ref/immediate 7 8 2)
  69    (f32-set! 7 9 11)
  70    (u64<? 5 12)
  71    (jnl 6)                         ;; -> L2
  72    (f32-set! 7 5 10)
  73    (mov 12 8)
  74    (reset-frame 1)                 ;; 1 slot
  75    (handle-interrupts)
  76    (return-values)
L2:
  77    (throw/value+data 6 331)        ;; #(out-of-range "bytevector-ieee-single-native-set!" "Argument 2 out of rang…")
L3:
  79    (throw/value+data 12 329)       ;; #(out-of-range "bytevector-ieee-single-native-set!" "Argument 2 out of rang…")
L4:
  81    (throw/value+data 8 353)        ;; #(wrong-type-arg "bytevector-ieee-single-native-set!" "Wrong type argument …")
L5:
  83    (throw/value 11 377)            ;; #(misc-error #f "cannot normalize vector with 0 magnitude ~S") at (unknown file):457:6
L6:
  85    (throw/value+data 6 391)        ;; #(out-of-range "bytevector-ieee-single-native-ref" "Argument 2 out of range…") at (unknown file):455:13
L7:
  87    (throw/value+data 12 389)       ;; #(out-of-range "bytevector-ieee-single-native-ref" "Argument 2 out of range…")
L8:
  89    (throw/value+data 11 395)       ;; #(wrong-type-arg "bytevector-ieee-single-native-ref" "Wrong type argument i…")
```

This looks pretty good!  All the math is done with unboxed floats and
no heap floats are allocated at all.  Unboxed floats are pulled out of
the bytevector with `f32-ref` and stuffed back in with `f32-set!`.
But we’re still allocating a new bytevector at the end.  This is
generally fine, but for *reeeeaaally* performance sensitive code we
want to avoid this allocation, too.  For this case, we can write a
variant of `normalize` that mutates another 2D vector to store the
result.

```scheme
(define-inlinable (set-vec2-x! v x)
  (f32vector-set! v 0 x))

(define-inlinable (set-vec2-y! v y)
  (f32vector-set! v 1 y))

(define (normalize! v dst)
  (let ((mag (magnitude v)))
    (when (= mag 0.0)
      (error "cannot normalize vector with 0 magnitude" v))
    (set-vec2-x! dst (/ (vec2-x v) mag))
    (set-vec2-y! dst (/ (vec2-y v) mag))))
```

We can then define the functional version in terms of the imperative
version:

```scheme
(define (normalize v)
  (let ((v* (vec2 0.0 0.0)))
    (normalize! v v*)
    v*))
```

Now we have options.  We can use the less elegant, imperative variant
when we can’t afford to allocate and use the functional variant
otherwise.  This is a simplified version of how vecs, matrices, and
rects work in Chickadee.

Let’s compare the two.  First, the functional API:

```scheme
scheme@(guile-user)> ,profile (let ((v (vec2 3.0 4.0)))
                                (let lp ((i 0))
                                  (when (< i 100000000)
                                    (normalize v)
                                    (lp (+ i 1)))))
%     cumulative   self
time   seconds     seconds  procedure
 46.46      7.84      7.73  make-srfi-4-vector
 31.61      5.26      5.26  <current input>:425:19:normalize!
 12.95     16.23      2.15  <current input>:432:19:normalize
  5.87      0.98      0.98  ice-9/boot-9.scm:408:31:make-f32vector
  2.42     16.63      0.40  <current input>:439:32
  0.69      0.11      0.11  %after-gc-thunk
  0.00      0.11      0.00  anon #x15fd5c0
---
Sample count: 579
Total time: 16.633395281 seconds (12.628994384 seconds in GC)
```

And now the imperative API:

```scheme
scheme@(guile-user)> ,profile (let ((v (vec2 3.0 4.0))
                                    (dst (vec2 0.0 0.0)))
                                (let lp ((i 0))
                                  (when (< i 100000000)
                                    (normalize! v dst)
                                    (lp (+ i 1)))))
%     cumulative   self
time   seconds     seconds  procedure
 91.03      1.13      1.13  <current input>:272:19:normalize!
  8.97      1.24      0.11  <current input>:343:32
---
Sample count: 78
Total time: 1.244961515 seconds (0.0 seconds in GC)
```

13x faster and no GC!  To use this technique in your own program, you
may want to use something like a pool to reuse objects over and over;
or just stash an object somewhere to use as scratch space.

Note: Unlike example 2, these optimizations *do* happen on Guile 3.0.9
and IIRC any stable Guile 3.0.x release.

### Happy hacking

Well, that’s all I’ve got!  There are other sources of allocation to
be aware of, like closures, but I couldn’t come up with clean
examples.  If I think of something good maybe I’ll update this post
later.

To reiterate, most of the code you write doesn’t need to be examined
this closely.  Don’t rush off and use `define-inlinable` everywhere
and inflate the size of your compiled modules!  Let the profiler focus
your attention on what matters.  May your Scheme be speedy and your
GCs infrequent. 🙏