Memoize doesn't appreciably improve performance

[jazmit]

I've been experimenting with improving the render performance of my Pux app, and it seems that most of the CPU time is spent in repeated unnecessary view rendering. However, after experimenting with memoize, the performance just won't improve significantly. After poking around a while, I think I've found the culprit: the free monad. Take the following snippet:

myView = memoize \state -> do
  expensiveViewA state.partA
  expensiveViewB state.partB

What occurs when myView is evaluated is that expensiveViewA is evaluated, but expensiveViewB is not, because it's in a thunk in the free monad, and so only evaluated when the monad is interpreted. Therefore memoize is only caching the first calculation in every do statement, which results in virtually no performance improvement.

Have I understood this correctly? If so, is there any way of fixing this? I've got a week to spend on this, so am happy to work on a PR if you'll offer me some guidelines.

[jazmit]

I've made some progress on this, getting a ~10x speed-up with the following 'de-thunking' function, which evaluates all views and child views, returning pure markup. I'll integrate it properly into memoizeand submit a PR in the next couple of days if you like?

evalMarkupThunks :: ∀ e. Markup e -> Markup e
evalMarkupThunks = foldFree pushNode >>> execWriter >>> sequence_
  where
  pushNode :: ∀ a. MarkupM e a -> Writer (Array (Markup e)) a
  pushNode (Element n children attrs handlers rest) = do
    let newChildren = evalMarkupThunks children
    tell [ liftF $ Element n newChildren attrs handlers unit ]
    pure rest
  pushNode (Content text rest) = do
    tell [ liftF $ Content text unit ]
    pure rest
  pushNode (Empty rest) = do
    tell [ liftF $ Empty unit ]
    pure rest

I've only just about got my head around Free this morning, so let me know if I'm on the right lines!

[alexmingoia]

This looks like a promising approach. Is it possible to integrate it into the renderer, so that memoize is no longer needed?

[jazmit]

In the end we abandoned the above solution, foldFree is still being run over the entire DOM on every update, which is surprisingly expensive even if the view functions are no longer being reevaluated.

We implemented a different solution using a global cache with an explicit supplied cache key and an explicit shouldRender function. It's hack city and relies on using React as the renderer so I don't think it should be included in Pux, but results in great performance (reduced a 1000ms render to 5ms). I'm documenting it here as I don't know of any other way of getting good render performance, and perhaps it could help as a basis of further discussion.

cache :: ∀ st ev. String -> (st -> st -> Boolean) -> (st -> HTML ev) -> (st -> HTML ev)
cache key shouldRender = cache_ cached (cached empty) key shouldRender
  where
  cached = reactClass cacheWrapper "cacheWrapper" ! attribute "cacheKey" key

It works by directly co-ordinating between a custom react component and a wrapper around the view through global state (yuck!), when the wrapper knows that the react component has rendered, it returns empty instead of the view markup, thus avoiding foldFree over the markup:

exports.cache_ =
  function (wrapper) { return function(empty) {
    return function(key) {
      return function(shouldRender) {
        return function (view) {
          return function (state) {
            var cached = cache[key];
            if (cached === undefined || (cached.state !== state && shouldRender(cached.state)(state))) {
              // Cache miss, calculate the smolder markup and await render
              cached = {
                state: state,
                markup: wrapper(view(state)),
                awaitingRender: true
              };
              cache[key] = cached;
              return cached.markup;
            }
            else if (cached.awaitingRender == true) {
              // Still awaiting render, return the markup again
              return cached.markup;
            }
            else {
              // Already cached and rendered, we return empty smolder dom
              // to avoid uselessly walking and rendering it to react dom
              return empty;
            }
          };
        };
      };
    };
  };};


exports.cacheWrapper = React.createClass({
  shouldComponentUpdate: function (nextProps) {
    // Only render when the 'awaitingRender' flag is set
    return cache[nextProps.cacheKey].awaitingRender;
  },
  render: function () {
    return this.props.children;
  },
  componentDidUpdate: function() {
    // Record that render is done
    cache[this.props.cacheKey].awaitingRender = false;
  },
  componentWillUnmount: function () {
    var key = this.props.cacheKey;
    delete cache[key];
  }
});