removeChild is super-slow

[brianmhunt]

For no reason apparent to me, removeNode is painfully slow in the following test: Performance Comparison for React, Angular and Knockout.

Look at this:

And here, you can see that removeChild is taking over 22% of the time:

In that same profile, appendChild takes 0.33% of the processing time.

I'm not sure how we can optimize removeNode, but something's definitely awry.

[brianmhunt]

... I wonder if we could use replaceChild instead of removeChild

[brianmhunt]

We might consider running cleanNode on every node, then removeChild on every node.

[brianmhunt]

For the record, I tried (around line 357 of index.js):

  var removeFn = function () {
    var parent = nodes[0].parentNode;
    for (var i = nodes.length - 1; i >= 0; --i) {
      ko.cleanNode(nodes[i]);
      parent.removeChild(nodes[i]);
    }
  };

It appears to be marginally faster (having cut out some function calls), but remains a third of the recalculation. I would expect removeNode to generally be near-instantaneous, not an average of 13ms with each call. Strange.

[brianmhunt]

Well. That's unexpected: Rendering faster by hiding DOM elements instead of removing them (Or at least it would've been until I started looking into this problem)

Rougly 80 ms was spent in removeChild. The entire renderCells call took 137 ms. So I thought, are removeChild calls something I eliminate?

...

So, I tried out hiding exiting cells instead of removing them ... Now renderCells takes about 30 ms.

I wonder if that's an effective strategy for us. We could also make the removal lazy (and power-friendly with animationFrame).

[krnlde]

@brianmhunt in your implementation, now that you are iterating via a decrement, be careful with array holes.

[brianmhunt]

Thanks @krnlde – We construct the nodes (being nodes corresponding to an item in the given list at getNodesForIndex), so my expectation is that there should never be holes in that array. But I might be missing something. :)

Do you perceive a risk here based on a use case? If so, do you have any suggestions on how best to deal with them?

Thanks & Cheers

[krnlde]

The best way to deal with holes is utilizing Object.keys() afaik, but this is only supported since IE 9.

I'm not too much into the code to know whether there will be holes at any time.

Edit: as Axel quotes you could also use the for in loop, which works everywhere.

In your code this would look like this:

for (var key in nodes) {
  ko.cleanNode(nodes[key]);
  parent.removeChild(nodes[key]);
}

if you need to start right, you'll need to reverse the array first:

for (var key in nodes.reverse()) {
  ko.cleanNode(nodes[key]);
  parent.removeChild(nodes[key]);
}

(untested)

[cervengoc]

Hiding the nodes and then removing them on next queue flush may improve the situation. But I don't know, can't get into it right now more deeply but as I'm thinking it should be faster to remove hidden elements because no need to reflow.

On the other hand I don't know how other libraries can be faster, aren't they using the same native removeChild method?

[brianmhunt]

@cervengoc I rooted through React and Angular and didn't see any references to removeChild, so I'm guessing they must be doing something different. But it's just a guess. :smile:

The only alternative to removeChild would be to muck with innerHTML every time, which we cannot really do without re-applying the bindings to everything not removed, which would be slow for cases where there's only one or two deletes.

[krnlde]

Also take into account: having a loose DomNode which is not appended elsewhere that could catch all the removed DomNodes for a while by trash.appendChild(NodeToBeRemoved)ing them. That way only a repaint is necessary, no heavy DOM cleanup. You could then bring out the trash later.

Btw: Angular actually uses parent.removeChild(element);. I tested this in the TodoMVC app (Angular 1.4.3): http://todomvc.com/examples/angularjs/node_modules/angular/angular.js line 2969.

So does react: https://github.com/facebook/react/blob/master/src/renderers/dom/client/utils/DOMChildrenOperations.js#L120

[brianmhunt]

Thanks @krnlde – Great finds re. the removeChild ... my searching skills leave something to be desired! :wink:

I think it's definitely worth checking out the performance of a batch-move (to a DOM node with display: none) + lazy-remove.

[cervengoc]

@brianmhunt Due to a desired super-optimization I started re-reading this thread too. What exactly do you mean by "lazy-remove"? I'll try to implement it if we get to a good idea.

[brianmhunt]

Thanks @cervengoc Lazy-remove would be, at its most basic, a two-step process:

1. Set display: none in one animation cycle; to deals with the rendering
2. Remove the elements in another cycle; this deals with events/DOM structure, etc.

Theoretically this would break up the browser work into two separate loads. One would need to experiment though.

Another option that may help is to remove all the DOM nodes from the document (or clone them, but then one would have to re-apply bindings), manipulate them, then re-insert them. That'd be problematic for very large lists, but in the average case might be faster. Possibly. Not sure. :)

Another optimization (and I'm getting really derailed here), when a list is made to be empty, we could write a shortcut that empties all the DOM nodes in a much faster cycle.

[AllSeeingEye]

Thanks @cervengoc Lazy-remove would be, at its most basic, a two-step process:

Set display: none in one animation cycle; to deals with the rendering Remove the elements in another cycle; this deals with events/DOM structure, etc.

Here's a patch for the current brianmhunt/knockout-fast-foreach that does just that:

https://gist.github.com/AllSeeingEye/b25b338ebf76131ff5e128aa8c43505e

Updates are now made with the same speed as initial array deployment. Please look at it - I'll create a pull request if you like it.

[AllSeeingEye]

... I wonder if we could use replaceChild instead of removeChild

I've given it a try (though I admit my implementation was pretty naive), and it didn't bring any noticeable improvements. Hiding the nodes + deleting inside animateFrame + clustering fixes things.