wingolog

a baseline compiler for guile

3 June 2020 8:39 PM (guile | gnu | compilers | igalia | scheme | baseline | optimizing | guix)

Greets, my peeps! Today's article is on a new compiler for Guile. I made things better by making things worse!

The new compiler is a "baseline compiler", in the spirit of what modern web browsers use to get things running quickly. It is a very simple compiler whose goal is speed of compilation, not speed of generated code.

Honestly I didn't think Guile needed such a thing. Guile's distribution model isn't like the web, where every page you visit requires the browser to compile fresh hot mess; in Guile I thought it would be reasonable for someone to compile once and run many times. I was never happy with compile latency but I thought it was inevitable and anyway amortized over time. Turns out I was wrong on both points!

The straw that broke the camel's back was Guix, which defines the graph of all installable packages in an operating system using Scheme code. Lately it has been apparent that when you update the set of available packages via a "guix pull", Guix would spend too much time compiling the Scheme modules that contain the package graph.

The funny thing is that it's not important that the package definitions be optimized; they just need to be compiled in a basic way so that they are quick to load. This is the essential use-case for a baseline compiler: instead of trying to make an optimizing compiler go fast by turning off all the optimizations, just write a different compiler that goes from a high-level intermediate representation straight to code.

So that's what I did!

it don't do much

The baseline compiler skips any kind of flow analysis: there's no closure optimization, no contification, no unboxing of tagged numbers, no type inference, no control-flow optimizations, and so on. The only whole-program analysis that is done is a basic free-variables analysis so that closures can capture variables, as well as assignment conversion. Otherwise the baseline compiler just does a traversal over programs as terms of a simple tree intermediate language, emitting bytecode as it goes.

Interestingly the quality of the code produced at optimization level -O0 is pretty much the same.

This graph shows generated code performance of the CPS compiler relative to new baseline compiler, at optimization level 0. Bars below the line mean the CPS compiler produces slower code. Bars above mean CPS makes faster code. You can click and zoom in for details. Note that the Y axis is logarithmic.

The tests in which -O0 CPS wins are mostly because the CPS-based compiler does a robust closure optimization pass that reduces allocation rate.

At optimization level -O1, which adds partial evaluation over the high-level tree intermediate language and support for inlining "primitive calls" like + and so on, I am not sure why CPS peels out in the lead. No additional important optimizations are enabled in CPS at that level. That's probably something to look into.

Note that the baseline of this graph is optimization level -O1, with the new baseline compiler.

But as I mentioned, I didn't write the baseline compiler to produce fast code; I wrote it to produce code fast. So does it actually go fast?

Well against the -O0 and -O1 configurations of the CPS compiler, it does excellently:

Here you can see comparisons between what will be Guile 3.0.3's -O0 and -O1, compared against their equivalents in 3.0.2. (In 3.0.2 the -O1 equivalent is actually -O1 -Oresolve-primitives, if you are following along at home.) What you can see is that at these optimization levels, for these 8 files, the baseline compiler is around 4 times as fast.

If we compare to Guile 3.0.3's default -O2 optimization level, or -O3, we see bigger disparities:

Which is to say that Guile's baseline compiler runs at about 10x the speed of its optimizing compiler, which incidentally is similar to what I found for WebAssembly compilers a while back.

Also of note is that -O0 and -O1 take essentially the same time, with -O1 often taking less time than -O0. This is because partial evaluation can make the program smaller, at a cost of being less straightforward to debug.

Similarly, -O3 usually takes less time than -O2. This is because -O3 is allowed to assume top-level bindings that aren't exported from a module can be transformed to lexical bindings, which are more available for contification and inlining, which usually leads to smaller programs; it is a similar debugging/performance tradeoff to the -O0/-O1 case.

But what does one gain when choosing to spend 10 times more on compilation? Here I have a gnarly graph that plots performance on some microbenchmarks for all the different optimization levels.

Like I said, it's gnarly, but the summary is that -O1 typically gets you a factor of 2 or 4 over -O0, and -O2 often gets you another factor of 2 above that. -O3 is mostly the same as -O2 except in magical circumstances like the mbrot case, where it adds an extra 16x or so over -O2.

worse is better

I haven't seen the numbers yet of this new compiler in Guix, but I hope it can have a good impact. Already in Guile itself though I've seen a couple interesting advantages.

One is that because it produces code faster, Guile's boostrap from source can take less time. There is also a felicitous feedback effect in that because the baseline compiler is much smaller than the CPS compiler, it takes less time to macro-expand, which reduces bootstrap time (as bootstrap has to pay the cost of expanding the compiler, until the compiler is compiled).

The second fortunate result is that now I can use the baseline compiler as an oracle for the CPS compiler, when I'm working on new optimizations. There's nothing worse than suspecting that your compiler miscompiled itself, after all, and having a second compiler helps keep me sane.

stay safe, friends

The code, you ask? Voici.

Although this work has been ongoing throughout the past month, I need to add some words on the now before leaving you: there is a kind of cognitive dissonance between nerding out on compilers in the comfort of my home, rain pounding on the patio, and at the same time the world on righteous fire. I hope it is clear to everyone by now that the US police are an essentially racist institution: they harass, maim, and murder Black people at much higher rates than whites. My heart is with the protestors. Godspeed to you all, from afar. At the same time, all my non-Black readers should reflect on the ways they participate in systems that support white supremacy, and on strategies to tear them down. I know I will be. Stay safe, wear eye protection, and until next time: peace.

62 responses

  1. Biuro Poltax says:

    But what does one gain when choosing to spend 10 times more on compilation? I hope it is clear to everyone by now that the US police are an essentially racist institution or biuro rachunkowe Toruń

  2. 192.168.1.1 says:

    192.168.1.1 router login and password for your device at 192.168.1.1 We will help you get into your router or other devices on your network.

  3. ome.tv says:
  4. safari for pc says:

    help you get into your router safari for pc

  5. hotmail login says:

    But what does one gain when choosing hotmail login

  6. download kik for pc says:

    nic posterdgfhvnjhu

  7. discord for windows pc says:

    nic posterdgvnmvb jkdckjsdfkjdkfjk

  8. ometv ban says:
  9. safari for windows 10 says:
  10. hotmail.com says:

    But what does one gain when choosing to spend 10 times more on compilation? I hope it is c hotmail.com

  11. kik for windows 10 says:

    one gain when choosing to spend 10 times more on kik for windows 10

  12. discord app says:
  13. spin rewriter download says:

    best tool for article spin rewriter download

  14. Crusaders Chiefs game says:

    They also are having a 7-day trial event. There is no pressure to start a contract or anything like that. They want you to test out what they are offering and after 7 days, cancel the subscription. You can watch TV the way you want to watch. Super Rugby Aotearoa stream free

  15. write my assignment review says:

    Hi, You have a gift of instant assignment help uk explaining everything so well everyone understands! Thanks for the sharing.

  16. house painters Fredericton says:

    Great comparison!

  17. Carpet Repair Calgary says:

    This is a nice post. I am so lucky today to find something nice to read on your website. Thanks for a wonderful blog. Carpet Repair Calgary

  18. Click here says:

    Have to admit that you really are one of the greatest bloggers I ever saw.Nice one for publishing this interesting article. Click here

  19. Visit our site says:

    Article appreciated, thank you for sharing the information. Visit our site

  20. electrician odessa tx says:

    The funny thing is that it's not important that the package definitions be optimized; they just need to be compiled in a basic way so that they are quick to load.

  21. vex 3 says:

    My friend's blog I have read, I am very impressed with your blog, I hope you will have more blogs or more articles to bring to readers.

  22. www.tampacardetail.com says:

    Hey! Thank you for the fantastic article about your Guile Baseline Compiler. Although my business in Tampa Bay doesn't need to compile code to detail cars, I really enjoy learning new things. Obviously, most of the article went over my head... but thanks anyways! If you're ever near Tampa Bay, Florida, then give Tampa Car Detailing a call! :)

  23. electricians northern va says:

    Bars below the line mean the CPS compiler produces slower code. Bars above mean CPS makes faster code.

  24. site says:

    We'll see how the compiler goes.

  25. Temas Personalizados * Produtos Personalizados says:

    A Brindes Personalizados Produtos Personalizados é uma empresa que transforma suas ideias de personalização em realidade de forma rápida e simples.
    O nosso diferencial é atender a qualquer pedido de quantidade, para isso utilizamos as várias técnicas de estamparia.Atender as necessidades dos Clientes, com tecnologia de ponta, qualidade, rapidez e confiabilidade dos serviços, buscando a total satisfação dos nossos Clientes, Fornecedores e Comunidade com responsabilidade e respeito.camisetas personalizadas em curitiba

  26. TreatAssignment Help says:

    Under TreatAssignmentHelp we provide many types of help to the students. We are the most reliable assignment helpers. We have gained our specialization after spending most of our times in making ourselves perfect. We provide you 100% plagiarism free assignment.UK Assignment Writing Services

  27. synthetic grass says:

    ​ If you are tired of wasting your weekends cutting lawns and spending such an incredible sum on watering, seeding, compost and potentially hazardous pesticides and fertilizers; by then a synthetic option is definitely for you.

  28. quality websites says:

    backlinks, quality websites, backlinking, do follow backlinks

  29. Floor repair Perth says:

    Floor repair Perth, Timber floors, Floor sanding, floor polishing, decks, wooden floors, timber floor repairs.
    If you want your timber floors to look their best, we can help.

  30. website automation says:

    At Mike Howell digital we use one of the most progressive and up to date chatbots on the market.
    Our Bots are continually being updated with the latest advances, and when you are on a monthly plan with us, you are privy to all these technological advances as they happen. Chatbots, chatbots Perth, Digital marketing, Facebook ads, conversational marketing, lead generation, website automation.

  31. Julia M. Jones says:

    The post is interesting. It explores a baseline compiler for guile. Do you know about the baseline compiler? The article explains in detail about the baseline compiler. So, if you go through the content, you will be able to get to know about the baseline compiler. The content says that a baseline compiler omits any type of flow analysis, and there is no closing optimization, no contification, no unboxing of tagged numbers, no type inference, etc.

  32. OMG카지노 says:

    PLAY NEW CASINO GAMES ONLINE:

    https://www.omgqq.com 우리카지노사이트
    https://www.omgqq.com/thekingcasino 더킹카지노
    https://www.omgqq.com/sandscasino 샌즈카지노
    https://www.omgqq.com/firstcasino 퍼스트카지노
    https://www.omgqq.com/yescasino 예스카지노
    https://www.omgqq.com/supercaisno 슈퍼카지노
    https://www.omgqq.com/gatsbycasino 개츠비카지노
    https://www.omgqq.com/33casino 33카지노
    https://www.omgqq.com/worldcasino 월드카지노
    https://www.omgqq.com/blog

  33. Alex says:

    Bars. below the line mean the CPS compiler produces slower code. Bars above mean CPS makes faster code....

  34. Lucas Miller says:

    Skipped your Matlab classes because of other commitments of a busy job schedule? You don’t have to worry. At Matlab assignment experts, we offer tuition classes to ensure that you catch up with your classmates or even understand the area you did not understand in class. We offer classes based on your topics of need and we work based on your schedule. Our Matlab Assignment Experts are available to ensure that your grades are soaring high.

  35. Frank Miller says:

    If you really need Matlab Assignment Help, then you need to contact an expert like me. I am a Matlab Assignment Helper with years of experience. I have been working with Matlab assignment experts for the last five years. Within that time, I have helped lots of students with their challenging assignments. I have completed numerous assignments on Communication Systems, control systems, data analysis.

  36. Sasha Robin says:

    There used to be the point at which you could go through a ton of cash and purchase Adobe PhotoShop inside and out, getting a never-ending permit with your container of plates. colloidal silver supplier

  37. josh welsh says:

    Thanks for this infomration, I am glad to read your blogs, Thanks man.Skip Hire in Wollongong

  38. Paver Installer Santa Rosa says:

    godbless to you and your friends paver installer santa Rosa

  39. Website says:

    Very informative post. I really do hope and pray this stuff works!

  40. GraceJordan says:

    Look for a college paper example ? You can find tons of samples of various academic assignments on this website. They are free to use.

  41. brandon says:

    We're always talking about the trade-off between optimization and debugging. I understand why: the flow-graph analysis done by the compiler can reorder or constant fold code in such a way that a source level-debugger behaves poorly. But I've never been particularly fond of using such tools.

    Your blog posts hint at a possible solution: can we not embedd some information from the optimization passes into the debugging section which can highlight which expressions have been inlined, constant folded, partially applied, etc. The compiler could, in fact, provide an actual *trace* of exactly how constant folded code was evaluated to the debugger.

    If there's one thing that godbolt proves, it's that many many programmers are very interested in derailed feedback about what the compiler has chosen to do with their code. We could be on the threshold of a new era of "static debugging".

    Speaking of a hot mess, the spam in your comments somehow manages to get past the numeric captcha. Time to evolve.

  42. Itemx says:

    Bars. below the line mean the CPS compiler produces slower code. Bars above mean CPS makes faster code....

  43. top 10 sixes of IPL says:

    https://3tfaa.blogspot.com/2010/06/blog-post.html?showComment=1600681295937#c821148866504160821

  44. Martina says:

    Thanks for sharing!

    Best regards,
    Martina from acad-profy.com

  45. mapquest driving directions says:

    A very creative and great idea, I think your idea will be implemented and invented many other ideas.

  46. celeb networth says:

    Thank you! It's nice to find this article..

  47. Nathan says:

    I find this article very informative.

  48. Stream Sports for free says:

    Thanks

  49. Sensation says:

    Nice Information. Thanks for sharing

  50. Sensation says:

    Nice Information. Thanks for sharing

  51. temple run says:

    Unfortunately! I really like this girl's style but unfortunately there is no chance anymore, thank you for creating a better style.

  52. Private Tutors says:

    Very quickly this site will be famous amid all blogging and site-building viewers, due to it’s pleasant articles.

  53. elsevier says:

    In this article, we are going to introduce the site of 20 DJs, which provides ready-made projects, plugins, transitions, titles and sound effects of After Effects and Premier software.

  54. Dissertation Writing Service UK says:

    This is news information for me that I have not read before it and now I want to share it with the writers of dissertation writing service

  55. IT Support Fort Lauderdale says:

    I really love to read such a nice article. Managed IT Services Fort Lauderdale

  56. Tree Service Denver says:

    I really love to read such a nice article.

  57. Daisy Simpson says:

    We provide subject tutorial consultation to our clients be it accounting, finance, marketing, healthcare, hospitality, business studies, marketing, etc with the use of our diverse expert research teams.

  58. Painter Joliet IL says:

    Thanks for the great read.

  59. Quirinus Solution Ltd says:

    QuirinusSoft is best Betfair API Developers team that provide lives odds, live results and where you can get betfair api at affordable price! We provide current market odds of all sports including cricket,soccer,tennis etc. Betfair API can be used to fetch data from betfair to your own exchange. Ask for demo Now!

  60. McKinney Car Detail says:

    Thank you! At McKinney Car Detail we pride ourselves on our professional car detailing. If you're in McKinney, TX, then we'd love to detail your car!

  61. Fencing Wilmington NC says:

    Thanks for taking the time to discuss this.

  62. IT Services West Palm Beach says:

    I really love to read such a nice article.

Leave a Reply