You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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, 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, (fl* (fl+ x y) z) will allocate a new float to hold the intermediate
result of fl+ that gets thrown away after the fl* 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:
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:
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.”
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:
(define(magnitudexy)(sqrt(+(*xx)(*yy))))
Would you believe me if I told you the bytecode is less than perfect?
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:
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.
(define(normalizexy)(let((mag(magnitudexy)))(when(=mag0.0)(error"cannot normalize vector with 0 magnitude"xy))(values(/xmag)(/ymag))))
It would be great if all the unboxed float goodness from magnitude
spilled over to normalize. Let’s see if that happened (it didn’t):
scheme@(guile-user)> ,disassemble normalize
Disassembly of #<procedure normalize (x y)> at #x16609b0:
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:
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.
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.
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.
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. 🙏
via Recent Blog Posts — dthompson
September 26, 2024 at 07:07PM
The text was updated successfully, but these errors were encountered:
Optimizing Guile Scheme
https://ift.tt/izXG4QK
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, 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 ofx
.If
x
is42
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, ifx
is42.0
then Guile will allocate a float on the heap to store the result43.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+
andfl+
. These procedures remove the overhead of generic dispatching, but they don't help with the allocation problem; Without a sufficiently advanced compiler,(fl* (fl+ x y) z)
will allocate a new float to hold the intermediate result offl+
that gets thrown away after thefl*
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:x
,y
, andz
are used directly.+
and*
are compiled to specializedfadd
andfmul
primitives.(+ 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 ofstatprof
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:
Let's profile it and see how well it performs:
Nearly half of our time was spent in GC. Let's find out why by taking a look at the disassembly:
Note instruction 3,
bind-rest
. The Guile manual says: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 usecase-lambda
:Let’s re-run the profiler to see if this is actually better:
I'd say that nearly 17x faster with no GC is an improvement!
Let’s see what's changed in the disassembly:
There are more instructions now, but the branches for the known arity cases do not contain a
bind-rest
instruction. Only branchL4
, the one that handles the final clause of thecase-lambda
, usesbind-rest
.Example 2: Floating point math
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:
Would you believe me if I told you the bytecode is less than perfect?
Note the
call-scm<-scm-scm
instructions calling generic math primitivesmul
andadd
.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:
And the stats:
Our code now runs about 6x faster, but GC is still taking up most of that time. Let's examine the disassembly:
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
andfmul
are being used. It's not made very clear, but instruction 46,call-f64<-f64
, is a call to asqrt
primitive specialized for floats. Since our inputs have to be floats, Guile unboxes them as f64s via thecall-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 likef64-set!
set the contents of the heap object to the result of thesqrt
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.It would be great if all the unboxed float goodness from
magnitude
spilled over tonormalize
. Let’s see if that happened (it didn’t):Instruction 20 is
call
, so inlining didn’t happen. Furthermore, the two/
calls (instructions 28 and 30) use the generic division primitive rather thanfdiv
. No unboxing for us.The profiler confirms that things aren’t so great:
To force the compiler to inline
magnitude
, we’ll change the definition of to usedefine-inlinable
:define-inlinable
is a handy little macro that will substitute the procedure body into its call sites.Now let’s see the disassembly:
Much better! All of the instructions for
magnitude
are now part ofnormalize
./
is compiled tofdiv
just like we had hoped.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.
Here’s the disassembly for
normalize
now: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 withf32-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 ofnormalize
that mutates another 2D vector to store the result.We can then define the functional version in terms of the imperative version:
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:
And now the imperative API:
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. 🙏via Recent Blog Posts — dthompson
September 26, 2024 at 07:07PM
The text was updated successfully, but these errors were encountered: