Optimizing Guile Scheme

https://dthompson.us/posts/optimizing-guile-scheme.html

by avvvv • 2 years ago

168 80 2 years ago

As soon as I saw the title, I thought of the streetfighter character, but this was actually an interesting read on a programming language, I had never heard of before

abound• 2 years ago

A prominent use of Guile is as the configuration language for Guix, GNU's version of Nix

pxc• 2 years ago

It's the official GNU extension language, so it's fairly widely used in the GNU world I think.

It's also the language of the init system/service manager on GuixSD (the full OS distribution based on Guix), GNU Shepherd (a.k.a. dmd), and IIRC their initrd runs a Guile program instead of a shell script.

bitwize3• 2 years ago

The slogan I've proposed for the language is "Guile goes with everything." Because Guile was designed from the outset to run embedded or standalone, and to transpile other extension languages to Scheme or a Scheme-compatible representation, I think that fitting. See: https://knowyourmeme.com/memes/guiles-theme-goes-with-everyt...

davexunit7• 2 years ago

I think the Guile community of yore would have no idea what Street Fighter was but now we should embrace it as long as Capcom doesn't get mad.

fwip• 2 years ago

Should it be "Guile Scheme goes with everything" for the rhyme?

pjmlp2• 2 years ago

Great overview on how to approach improving code performance, without going down the usual route of rewriting into something else.

throwaway17_172• 2 years ago

Solid blog overall and I think it is pitched at the right level of granularity for the topic. However, if I were offering criticism, the place I think more detail would be super interesting is the 'Please Inline' section. In particular, I would really be interested in a slightly more detailed description of the optimizer's algorithm for inlining. I think the "define_inlinable" macro is a great example of macro usage, but it is clearly a way to circumvent the inliner's apparent short comings. I would like to be able to understand what heuristic the optimizer is using to see if there is a sensible default function construction style/idiom that is more appealing to the optimizer for inlining. However, I am reminded of the inlining discussion in Chandler Carruth's talk (Understanding Compiler Optimization) from a few years ago where he discusses how obscure and seemingly arbitrary, in general, inlining heuristics and their optimization passes are in practice. [1]

1 - https://youtu.be/FnGCDLhaxKU?si=J3MhvJ-BmX5SG2N6&t=1550

davexunit7• 2 years ago

A walkthrough of Guile's optimization passes and the inlining heuristics would be great. I've been meaning to do a "part two" here but you know how these things go.

atemerev• 2 years ago

These sorts of optimizations can and should be handled by a (sufficiently smart (tm)) compiler.

Common Lisp/SBCL is usually sufficiently smart. I know not everyone likes Common Lisp, but at least I would have tested it with something more performant that Guile, like Chicken Scheme (my favorite!), Chez Scheme, etc.

I like Guile and its purpose as a universal scripting language. However, its performance issues are well known. Even compared to other scripting-first languages (Lua, Perl, Python etc).

throwaway17_172• 2 years ago

I think that is why this blog is particularly interesting to me. As one of the other comments to this posting said, it is nice to see an analysis/detailed description of working to optimize code where the first step is not to rewrite in a language with a presumed better performance baseline. Also, I think there is also some props to be given for continuing to work within Guile's somewhat spartan tooling to do the optimization work, instead of switching to a language that may have more/better tooling for the task.

Not to take away from the general comparisons between various Lisp flavors and between various scripting languages (an activity I engage in quite often), but your lead off line is more prescriptive than I find advisable. I don't think a blanket statement that optimizations of runtime behavior of code "should" only be done via a compiler. Some devs enjoy the work, others have varied reasons for doing performance sensitive work in a given language/environment. But at the end of day, doing optimization is a valid usage of developer effort and time if that developer judges it so.

eru5• 2 years ago

Isn't Racket the 'default' Scheme? (Even though it's no longer called Scheme.)

medo-bear2• 2 years ago

umanwizard2• 2 years ago

Extremely easy interop with native code is the main selling point of guile IMO. You just link in guile as a library and can have C code call scheme code and vice versa. Makes it great for any native program that needs an embedded scripting language (much like Lua). Does Racket support that use-case?

mepian• 2 years ago

At this point it's a separate language from Scheme. I think Chez Scheme tends to be the "default" recommendation.

tmtvl3• 2 years ago

I don't think there's a real 'default' Scheme, like Chez is probably the implementation which generates the fastest code, but if I'm not mistaken it only implements the R6RS spec, Guile is quite performant and supports both R6RS and R7RS Small, Chicken has a bunch of libraries (the 'eggs'), but I think it's R5RS (I may be wrong), and of course GNU/MIT Scheme is what you want to follow along with MIT publications working in Scheme (like Structure and Interpretation of Computer Programs, Structure and Interpretation of Classical Mechanics, and The Art of the Propagator). There's also Gauche, which I believe is the most conformant implementation to the various Colour Dockets for R7RS Large (Gerbil may also be fully conformant).

davexunit7• 2 years ago

Guile has come a long way in the past decade or so! I think your info is quite out of date. Guile's compiler performs a number of state of the art optimizations. It compiles to bytecode so native code compilers like Chez win the race, naturally. The JIT is pretty good, though! Native compilation is on the roadmap for Guile, but maybe somewhat surprisingly we're getting AOT compilation to WebAssembly first. https://spritely.institute/hoot/

armitron• 2 years ago

It's still much much slower than SBCL which is not surprising given the time & effort that went into the latter. User-guided optimizations (type declarations, stack allocation, intrinsics, machine code generation) in SBCL are also more flexible and better integrated.

tmtvl3• 2 years ago

I switched from Guile to SBCL because I really like having things such as (declare (inline my-function)) and (declare (type Double-Float x y z)). Now if only it had case-lambda, named let, and a better deftype which can specify members of classes and/or structs.

dannyobrien• 2 years ago

The language-hack of the "the" operator in Common Lisp, whereby `(the fixnum (+ 5 7))` signals that the result of (+ 5 7) should be an integer is so ... lispy.

shawn_w3• 2 years ago

named let

Serapeum has you covered: https://github.com/ruricolist/serapeum/blob/master/REFERENCE...

whartung• 2 years ago

Part of the problem is that raw Scheme is spectacularly underspecified.

It also doesn't help that Schemes like Guile are also interactive. The domain of an interactive language and a "compiled" language are quite different.

Given the entirety of the program made available to the compiler all at once, there are high level derivations that can happen notably through flow analysis to let the compiler make better decisions. But do that in an interactive environment when the rug can be pulled out of any of the assumption the compiler made, and things get messy quite quickly.

One interesting tidbit for Java is that the developers of the compiler advocate "idiomatic" Java. Simply, write Java like Java, and don't try to trick the compiler. Let the compiler developers trick the compiler.

That's evident here in this article when they wrote the function that tests the types of the parameters. Raw Scheme, naturally, doesn't allow you to specify parameter types, not the way you can in Common Lisp, for example. And, either Guile does not have an specific extension to support this, or simply the compiler looks for this type checking pattern at the top of a function to make optimization determinations. On the one hand, it could be more succinct with a specialized facility, but on the other, this is "just Scheme".

So, in effect by checking for the type of the variable, they're implicitly declaring the type of the variable for the "sufficiently smart" compiler to make better decisions.

The counter example is the "define-inline" construct, and thus not standard Scheme (though readily replaced by a "no-op" macro if one was interested in porting the code).

eru5• 2 years ago

Given the entirety of the program made available to the compiler all at once, there are high level derivations that can happen notably through flow analysis to let the compiler make better decisions. But do that in an interactive environment when the rug can be pulled out of any of the assumption the compiler made, and things get messy quite quickly.

Haskell's GHC does quite well with its 'ghci' interactive environment. GHC is a compiler first and foremost, and as far as I can tell, ghci works by compiling each line you give it one by one? (But even in ghci, you have to abide by the type system of Haskell, so that might help.)

The Common Lisps were always pretty good at combining compiled and interpreted parts, even in the same program. And I think OCaml also does a good job of combining the two approaches?

hayley-patton• 2 years ago

But do that in an interactive environment when the rug can be pulled out of any of the assumption the compiler made, and things get messy quite quickly.

https://bibliography.selflanguage.org/_static/dynamic-deopti...

shawn_w3• 2 years ago

In my experience, guile these days is often faster than chicken, even compiled (the csi interpreter is dog slow and not suitable for anything but interactive exploration). Chicken is just not a fast implementation.

Plus guile comes with a more comprehensive standard library; on the other hand, chicken's package manager and available packages do make up for that.

munificent2• 2 years ago

I have such mixed feelings about dynamically typed languages. I've designed a whole pile of hobby programming languages, and dynamically typed languages are at least an order of magnitude simpler to design and for users to learn and start using.

At the same time, they inevitably seem to lead to user stories like this where a user really does know exactly what types they're working with and wants the language to know that too (for performance or correctness), and they end up jumping through all sorts of insane hoops to get the optimizer to do exactly what they want.

sctb• 2 years ago

I like dynamic languages too. But I don't like the idea of "optimization", and I would be super interested in a dynamic language that didn't attempt to divorce performance from correctness. The worst part about jumping through insane hoops to enchant the optimizer is that it can all go wrong with the tiniest change--a flag here, a different usage pattern there, a new version, etc., and suddenly your program doesn't do what you need it to, as though an operation taking 1000x longer is just a matter of degree.

munificent2• 2 years ago

I agree completely.

At the same time, no one wants their code to run 100x slower than it would in any typical statically typed language. Unoptimized dynamic languages are sloooooow.

zem• 2 years ago

stanza (https://lbstanza.org/) is a very interesting experiment in designing for gradual types rather than retrofitting them onto a dynamic language

davexunit7• 2 years ago

I'm happy with dynamic languages for almost everything I do and generally do not want to sacrifice flexibility, which is the price to pay for a static type system. However, certain parts of a program become more crystalline over time, whether for performance or correctness reasons, and being able to express those parts using a static type system makes a lot of sense. PreScheme [0] is an example of a statically typed Scheme that composes with the host Scheme. I'd like to see more work in this direction as Scheme already works well as a multi-paradigm language.

[0] https://prescheme.org/

ristos3• 2 years ago

Yeah prescheme is really interesting, I really liked the SystemCrafters exploration of it:

https://www.youtube.com/watch?v=QqKuHylIqBs

cardanome2• 2 years ago

I think Common Lisp got it exactly right. Strongly typed dynamic language where you can optionally specify types for the extra performance/correctness if need be (especially with SBCL).

Honestly, I think weak typing is more of an issue than dynamic typing and people cry for static types when they suffer mostly from the former.

Dynamic typing is great because it allows you to have extremely complex types for basically free. It allows for insane expressiveness. It also makes prototyping much easier and does not force you into over-specifying in you types early on. In dynamic language most of your types are the most general type that would work by default while static types forces you to use very specific types (especially when lacking structural typing.)

If you want to allow just half the expressiveness of dynamic languages in your static language you will quickly find huge complexity with dependent types, long compile time, cryptic error messages and whatnot.

Generally, I think gradual typing is rising in popularity for good reason. It allows for quick prototyping but also to drill down on your types when you want to. Best of both worlds.

wavemode• 2 years ago

I find much the same to be true. I'm a big fan of Racket's define/contract and clojure's Malli/guardrails. You get one of the biggest benefits of static types (code that self-documents the expected shape of data) while enjoying all the benefits of a dynamic language (like creating types at runtime, and repl-driven development).

erik_seaberg• 2 years ago

I wish Common Lisp had integrated type declarations with TYPEP and CHECK-TYPE, instead of punting with "consequences are undefined if the value of the declared variable is not of the declared type," i.e., sucks to be you.

imiric2• 2 years ago

As a long-time Python and JavaScript user, I've come to the conclusion that dynamic typing is just not a good idea for anything beyond exploratory or very small projects.

The problem is that you invariably have to think about types. If you mistakenly pass a string to a function expecting an integer, you better hope that that is properly handled, otherwise you risk having type errors at runtime, or worse—no errors, and silent data corruption. That function also needs to be very explicit about this, but often the only way to do that is via documentation, which is often not good enough, or flat out wrong. All of this amounts to a lot of risk and operational burden.

Python's answer has historically been duck typing, which doesn't guarantee correctness so it's not a solution, and is more recently addressing it with gradual typing, which has its own issues and limitations. Primarily that if specifying types is optional, most programmers will not bother, or will just default to `any` to silence the type checker. While for JS we had to invent entirely new languages that compile to it, and we've reached the point where nobody sane would be caught working with plain JS in 2024.

Static typing, in turn, gives you a compile time safety net. It avoids a whole host of runtime issues, reduces the amount of exhaustive and mechanical tests you need to write, while also serving as explicit documentation. Code is easier to reason about and maintain, especially on large projects. You do lose some of the expressiveness and succinctness of dynamic typing, but what you gain with static typing is far more helpful than these minor benefits.

farhanhubble• 2 years ago

Dynamic typing with deeply nested data forces you to put type bandaids all over the code. For example you end up defining Pydantic schemas and then validating the same thing more than once since you can't guarantee that the type of a thing was not changed somewhere in the middle.

Dynamic typing forces you to test behavior which could be tested much more thoroughly by a type checker, at compile time, with zero development time.

Dynamic typing does offer much faster time to early prototyping but then drags you down with each bug.

Static typing does force some early commitments to the structure of the data but it also allows faster iteration and refactoring.

Static typing with good type inference seems the best to me.

ristos3• 2 years ago

I was strongly in the static typing camp for a long time, with Haskell, Purescript, Idris, OCaml, and Typescript, but over time I realized that the costs mostly outweigh the benefits.

The problem is that you invariably have to think about types. If you mistakenly pass a string to a function expecting an integer, you better hope that that is properly handled, otherwise you risk having type errors at runtime, or worse—no errors, and silent data corruption.

The silent data corruption is really only a problem with weak dynamic typing, that usually automatically coerces types. A lot of dynamically typed languages still have strong typing and will immediately error out. And usually in practice you end up testing all of the code you're writing anyone, so this almost never happens in practice except when someone is refactoring without thoroughly testing what they did, which should be done anyway whether there are types or not.

Primarily that if specifying types is optional, most programmers will not bother, or will just default to `any` to silence the type checker.

They probably do bother when it's an important module, or a an edge boundary that needs to be documented with a contract, or during times of significant refactoring. And these days LLMs can generate the specs, optional types, and tests pretty easily for any sort of self-contained, modular, reasonably well written code.

So now with LLMs I think there's even better reasons to use dynamic typing. And type completion in an IDE still exists for a bunch of dynamically typed languages anyway, like javascript.

zellyn• 2 years ago

I bounced off learning Haskell a few times (infinite regress to downloading category theory textbooks), but almost the moment I saw its type inference, I immediately wanted that in lisp.

Roc is looking pretty nice (especially once your editor can paste in the inferred type like they want to do), but I still think there’s an empty space for an imperative language where type inference makes it feel as untyped (or at least as unceremonious) as (pre-annotation) Python

samatman• 2 years ago

If you want to read just an enormous amount of well-written bloggage about optimizing Guile Scheme, this is the spot: https://wingolog.org

Andy Wingo is the maintainer and I get a kick out of everything he posts.

davexunit7• 2 years ago

Andy's blog is on another level. He's also leading the Hoot project to compile Guile to WebAssembly and I work with him on that and try to absorb whatever compiler knowledge I can while doing so.

exitb2• 2 years ago

You probably shouldn’t do those things. The point of a high level language is to not have to think about such details. If you can’t get the performance you need, you should use a different tool, instead of trying to circumvent implicit limitations.

gus_massa3• 2 years ago

Sometimes you can write mostly high level code and only add trick and annotations for speed to very hot loops.

exitb2• 2 years ago

There are two major problems with this approach. First of all, the intent is implicit, so it won't be clear for a new set of eyes. Second, by peeking behind the curtain you can get some gains, but only as long as everything behind this curtain stays the same. Author written about Guile 3, but is it also true of Guile 2 or 1? Will it hold true for Guile 4? Anybody's guess really.

In contrast to this approach, I'd point at Numpy. It optimises specific cases in Python code, but does so in an explicit way and its interface is even sufficiently high level to match Python well.

anthk• 2 years ago

I prefer Common Lisp with SBCL and Lem, but this is good too.

On SICP, Guile badly needs a module for the picture language from the book (and srfi-203 + srfi-216).

pmkary• 2 years ago

Makes me happy when I see Guile is alive and going.

ristos3• 2 years ago

The monomorphic vs polymorphic argument is an interesting one. I think that you could explicitly get unboxing if you used something like CLOS style multimethods to dispatch based on the type, so that (add <float> <float>) would dispatch to the function that uses fadd on those operands. I never realized that you could use this kind functionality, multimethods or free monad interpreters, to write in-code optimizations that are conveniently abstracted away in actual code usage.

Edit: nevermind, that's also dynamic dispatch. You'd have to add static dispatch via macros or some external transpilation step.

bjoli• 2 years ago

The guile source->source Optimizer is such a nice tool to see what is going on. Especially when writing macros. I really recommend Kent Dybvig's "the macro writer's bill of rights" to see how useful it can be.

tightbookkeeper2• 2 years ago

The full numeric tower sounds like a great idea. But in retrospect you almost never want uint32 silently converting to bignum, or ending up with a low precision float.

Has anyone had a positive experience?

davexunit7• 2 years ago

I love the numeric tower most of the time. Not having to worry about integer overflow bugs is great. I like that I can express the fraction 1/3 exactly rather than approximately with a float. It's only in the cases of very sensitive code that I have to worry about the details of how numbers are represented at runtime.

tmtvl3• 2 years ago

That's funny, my impression was the opposite: that you'd almost always want a fixed-width integer to promote to bignum when it transcends the limit. It's a lot more sensible than adding a bunch of integers together and ending up with one which is smaller than any of the ones in the input.

pkkm• 2 years ago

I would say the opposite: In a high-level language for "everyday programming", as opposed to systems programming or high-performance programming, arbitrary precision signed integers are the right choice. They let you do math on things like a large file size in bytes, or a nanosecond-precision timestamp, without having to think about integer widths. You only need to think about "is this an integer or is this floating-point", which takes less mental effort than using a language like C with its large selection of integer types.

Optimizing Guile Scheme

Related Stories