Announcing `purescript-backend-optimizer`

I am extremely excited to announce the release of purescript-backend-optimizer!

purescript-backend-optimizer is a backend-agnostic optimization pipeline for PureScript, written in PureScript. By backend-agnostic, I mean that it works on it’s own IR which is a touch more mid-level than CoreFn to support the sorts of optimizations performed by the current JS backend, but is otherwise minimal. It has a fully featured inlining pipeline, which can aggressively eliminate abstraction taxes when given the proper encouragement.

Notably, it ships with a working alternative to the current JS backend, which emits more modern ES code (arrows, let/const, etc). Our preliminary testing shows that you can expect a baseline 25-35% performance improvement with a 20-25% reduction in minified bundle size.

Please check out the README, which includes a few juicy examples and comparisons. I’m really excited to see what kinds of things y’all can throw together with this, and we really want to hear your thoughts for features and improvements (especially if you’ve ever tried to write a backend :stuck_out_tongue_winking_eye:).

Special shout out to @JordanMartinez who implemented pattern tree optimizations and included some nice docs on the algorithm.

29 Likes

I’m curious what this example:

would compile to if instead of >>>, you used QualifiedDo.Semigroupoid. Would it be able to inline everything all the way and get the same output?

1 Like

>>> vs <<< should make no difference anywhere regarding optimizations firing.

I would expect all the QualifiedDo variants to inline without a problem. The HTML example kind of showcases this even if it’s not literally the QualifiedDo library.

1 Like

Ooh, very nice. Was just looking through the examples, haven’t gotten to the HTML one yet. Will be sure to check that one out

There’s another variant example too which is quite nice. I didn’t include it because it doesn’t use the stock onMatch (which can’t inline well due to dynamic dispatch).

Amazing work. Is there any reason why this wouldn’t become the default?

Mega-excited to dive in - already the untweaked build is noticeably faster for a couple of my projects.

I’m trying the inliner for the first time and I think I’m writing the directives incorrectly. It’s for sure picking up on the file (it complains when there’s a syntax error, so I know it’s reading it), but I don’t see inlining happening.

Here’s the directives.txt file:

-- @inline export FRP.Event.applicativeEvent.pure
-- @inline export FRP.Event.eventIsEvent.keepLatest
-- @inline export FRP.Event.altEvent.alt

And here’s a line of output where I would have expected inlining for both altEvent and applicativeEvent:

  const $1 = FRP$dEvent.altEvent(Effect.applicativeEffect).alt(FRP$dEvent.applicativeEvent(Control$dMonad$dST$dClass.monadSTEffect).pure(makeLeap.initialDims))(makeLeap.resizeEvent);

One thing to note is that these instances rely themselves on instance dictionaries for which I’m not (yet) requesting inlining, like Effect.applicativeEffect. Perhaps that’s the issue?

Thanks in advance for any tips!

For export, you don’t qualify it.

We could definitely use some sort of warning mechanism for when rules don’t match anything.

Also worth nothing that I believe you don’t use the export directive within a directive.txt file - that would only be used in a module header.

Oh yes, if it’s a directives file, each line is a fully qualified name and directive. No need for comments or @inline.

If I make my directives.txt file:

FRP.Event.applicativeEvent.pure
FRP.Event.eventIsEvent.keepLatest
FRP.Event.altEvent.alt

(removing the -- and @inline), I get:

Invalid directive [1:32]
  FRP.Event.applicativeEvent.pure
  Unexpected end of file
Invalid directive [2:34]
  FRP.Event.eventIsEvent.keepLatest
  Unexpected end of file
Invalid directive [3:23]
  FRP.Event.altEvent.alt
  Unexpected end of file

One thing that could help is an example directives.txt file showing the various things one can do (for example, inlining a function, an instance, etc).

Aha - you’re missing the last piece of the directive, which is when to inline. In your case, you probably are looking for always or arity=N

FRP.Event.applicativeEvent.pure always
FRP.Event.eventIsEvent.keepLatest arity=2
FRP.Event.altEvent.alt always

You’re right - an example would be very helpful here.

Ah nice, thanks for this!

The rules are still not kicking in when using always, perhaps because I’m messing up the auto-gen instance names.

If it’s helpful to see it in action, you can check out this branch: GitHub - mikesol/joyride at inliner (I’ve checked directives.txt into version control), run npm install && npm run build:prod and then inspect ie output-es/Joyride.Visual.Basic/index.js. The functions don’t wind up getting inlined there.

I’m probably screwing up something super basic here, so apologies in advance & thanks for your help!

My general suggestions to get started are (and this should probably wind up in a doc somewhere):

  • always probably is not going to give you the result you want. Honestly, the use case for this is pretty rare in terms of how the inliner is implemented. It’s really only useful for actual “values” you want to inline, ie, things that don’t take arguments.
  • Otherwise you should count the number of =>s and ->s in the type signature and use that as the arity=....
  • If you have specific staging expectations, you can count only the number of =>s and use that as the arity=....

So in your case, I would try:

FRP.Event.applicativeEvent.pure arity=1
FRP.Event.eventIsEvent.keepLatest arity=1
FRP.Event.altEvent.alt arity=2

I tried it and unfortunately it doesn’t work yet.

I think inlining could be a game changer here, as all of the FRP.Event stuff is just CPS over Effect and a lot of it, when expanded out by hand, resembles imperative code.

Everything is on the branch I put above, so if you have the energy (after pushing out this amazing lib!) to build the repo and inspect the file, it could perhaps be useful as a trial-by-fire example.

Regardless of how the inlining pans out, many thanks, it’s already worked its :magic_wand: on my repo so I’m a happy camper!

2 Likes

One thing I would do is work backwards. Look at the code that is generated, and see what you want improved. It’s important to remember that inlining by itself is not an interesting optimization. Especially with a JS JIT, calls to known functions (even curried) are probably going to be inlined without overhead (it’s the dynamic calls to unknown functions that have overhead). Applying directives without a clear goal and purpose is going to feel like whack-a-mole. There’s no kismet here. Event is a lot of callback stuff with closures that have to be put in data structures (and retained by other closures), so I’m not sure very many callbacks will be eliminated, since they necessarily need to exist at runtime. If you have specific desired results, you might need to work towards that with specific representations.

Regarding your directives and why they aren’t quite right, if you look at the generated code for your file, you’ll see stuff like this at the top:

const alt = /* #__PURE__ */ (() => FRP$dEvent.altEvent(Effect.applicativeEffect).alt)();
const pure = /* #__PURE__ */ (() => FRP$dEvent.applicativeEvent(Control$dMonad$dST$dClass.monadSTEffect).pure)();
const filter = /* #__PURE__ */ (() => FRP$dEvent.filterableEvent(Effect.applicativeEffect).filter)();
const eventIsEvent = /* #__PURE__ */ FRP$dEvent.eventIsEvent(Control$dMonad$dST$dClass.monadSTEffect);

This is the main compiler’s CSE pass hoisting dictionary applications. keepLatest in particular is having to go through eventIsEvent. All of these are constrained instances, so you probably want to start by adding directives to the instances themselves since they are functions which produce a dictionary.

FRP.Event.eventIsEvent arity=1
FRP.Event.applicativeEvent arity=1
FRP.Event.altEvent arity=1
FRP.Event.keepLatest arity=2

Seemed to do alright. pure sticks around, but I don’t think you get any benefit from that without more inlining rules to other functions (the result needs to be passed in to other stuff, ie it’s not a control structure).

2 Likes

Amazing results! Some examples really deserve a tattoo (I will stop on a t-shirt print though ;-)). Thanks a lot!

2 Likes

Congrats!
I’ve given it a test on my project and I noticed that some files came out bigger in size using it, making the final bundle more or less the same size.

I’ve put up a minimal case which I think highlights the issue. I couldn’t spend too much time on this, so maybe I’ve completely missed the mark but I hope that it’s till helping a bit.

module Components.Debug where

import Prelude

import Data.Tuple.Nested ((/\))
import Halogen as H
import Halogen.HTML as HH
import Halogen.HTML.Events as HE
import Halogen.Hooks as Hooks
import Halogen.Hooks.Extra.Hooks (usePutState)

component :: forall q o m. H.Component q Unit o m
component =
  Hooks.component \_ _ -> Hooks.do
    bar /\ setBar <- usePutState 0
    Hooks.pure do
      HH.div_
        [ HH.button
            [ HE.onClick \_ -> updateBar bar setBar ]
            [ HH.text "+" ]
        , HH.button
            [ HE.onClick \_ -> updateBar bar setBar ]
            [ HH.text "+" ]
        ]
  where
  updateBar bar setBar =
    setBar (bar + 1)

Here’s the output without the optimizer:

import * as Halogen_HTML_Core from "../Halogen.HTML.Core/index.js";
import * as Halogen_HTML_Elements from "../Halogen.HTML.Elements/index.js";
import * as Halogen_HTML_Events from "../Halogen.HTML.Events/index.js";
import * as Halogen_Hooks_Component from "../Halogen.Hooks.Component/index.js";
import * as Halogen_Hooks_Extra_Hooks_UseStateFn from "../Halogen.Hooks.Extra.Hooks.UseStateFn/index.js";
import * as Halogen_Hooks_Hook from "../Halogen.Hooks.Hook/index.js";
var component = /* #__PURE__ */ (function () {
    var updateBar = function (bar) {
        return function (setBar) {
            return setBar(bar + 1 | 0);
        };
    };
    return Halogen_Hooks_Component.component(function (v) {
        return function (v1) {
            return Halogen_Hooks_Hook.bind(Halogen_Hooks_Extra_Hooks_UseStateFn.usePutState(0))(function (v2) {
                return Halogen_Hooks_Hook.pure(Halogen_HTML_Elements.div_([ Halogen_HTML_Elements.button([ Halogen_HTML_Events.onClick(function (v3) {
                    return updateBar(v2.value0)(v2.value1);
                }) ])([ Halogen_HTML_Core.text("+") ]), Halogen_HTML_Elements.button([ Halogen_HTML_Events.onClick(function (v3) {
                    return updateBar(v2.value0)(v2.value1);
                }) ])([ Halogen_HTML_Core.text("+") ]) ]));
            });
        };
    });
})();
export {
    component
};

And this is the output with the optimizer:

// @inline export updateBar arity=2
import * as $runtime from "../runtime.js";
import * as Control$dMonad$dFree from "../Control.Monad.Free/index.js";
import * as Data$dCatList from "../Data.CatList/index.js";
import * as Data$dMaybe from "../Data.Maybe/index.js";
import * as Data$dTuple from "../Data.Tuple/index.js";
import * as Halogen$dHooks from "../Halogen.Hooks/index.js";
import * as Halogen$dHooks$dComponent from "../Halogen.Hooks.Component/index.js";
import * as Halogen$dHooks$dHook from "../Halogen.Hooks.Hook/index.js";
import * as Halogen$dHooks$dHookM from "../Halogen.Hooks.HookM/index.js";
import * as Halogen$dQuery$dInput from "../Halogen.Query.Input/index.js";
import * as Halogen$dVDom$dDOM$dProp from "../Halogen.VDom.DOM.Prop/index.js";
import * as Halogen$dVDom$dTypes from "../Halogen.VDom.Types/index.js";
const component = /* #__PURE__ */ Halogen$dHooks$dComponent.memoComponent(v => v1 => false)(v => v1 => Halogen$dHooks$dHook.bind(Halogen$dHooks$dHook.functorHook.map(Data$dTuple.functorTuple.map(Halogen$dHooks$dHookM.put))(Halogen$dHooks.useState(0)))(v2 => Control$dMonad$dFree.$Free(
  Control$dMonad$dFree.$FreeView(
    "Return",
    Halogen$dVDom$dTypes.$VDom(
      "Elem",
      Data$dMaybe.Nothing,
      "div",
      [],
      [
        Halogen$dVDom$dTypes.$VDom(
          "Elem",
          Data$dMaybe.Nothing,
          "button",
          [Halogen$dVDom$dDOM$dProp.$Prop("Handler", "click", ev => Data$dMaybe.$Maybe("Just", Halogen$dQuery$dInput.$Input("Action", v2._2(v2._1 + 1 | 0))))],
          [Halogen$dVDom$dTypes.$VDom("Text", "+")]
        ),
        Halogen$dVDom$dTypes.$VDom(
          "Elem",
          Data$dMaybe.Nothing,
          "button",
          [Halogen$dVDom$dDOM$dProp.$Prop("Handler", "click", ev => Data$dMaybe.$Maybe("Just", Halogen$dQuery$dInput.$Input("Action", v2._2(v2._1 + 1 | 0))))],
          [Halogen$dVDom$dTypes.$VDom("Text", "+")]
        )
      ]
    )
  ),
  Data$dCatList.CatNil
)));
export {component};

Just did some other quick test and I noticed that the optimized bundle has some runtime errors. They all seem related to Data.Formatter.DateTime unformatCommandParser