Optimizing native hit testing of DOM elements (Chrome)

Question

I have a heavily optimized JavaScript app, a highly interactive graph editor. I now started profiling it (using Chrome dev-tools) with massive amounts of data (thousands of shapes in the graph), and I'm encountering a previously unusual performance bottleneck, Hit Test.

| Self Time       | Total Time      | Activity            | |-----------------|-----------------|---------------------| | 3579 ms (67.5%) | 3579 ms (67.5%) | Rendering           | | 3455 ms (65.2%) | 3455 ms (65.2%) |   Hit Test          | <- this one |   78 ms  (1.5%) |   78 ms  (1.5%) |   Update Layer Tree | |   40 ms  (0.8%) |   40 ms  (0.8%) |   Recalculate Style | | 1343 ms (25.3%) | 1343 ms (25.3%) | Scripting           | |  378 ms  (7.1%) |  378 ms  (7.1%) | Painting            | 

This takes up 65% of everything (!), remaining a monster bottleneck in my codebase. I know this is the process of tracing the object under the pointer, and I have my useless ideas about how this could be optimized (use fewer elements, use fewer mouse events, etc.).

Context: The above performance profile shows a "screen panning" feature in my app, where the contents of the screen can be moved around by dragging the empty area. This results in lots of objects being moved around, optimized by moving their container instead of each object individually. I made a demo.

---

Before jumping into this, I wanted to search for the general principles of optimizing hit testing (those good ol' "No sh*t, Sherlock" blog articles), as well as if any tricks exist to improve performance on this end (such as using translate3d to enable GPU processing).

I tried queries like js optimize hit test, but the results are full of graphics programming articles and manual implementation examples -- it's as if the JS community hadn't even heard of this thing before! Even the chrome devtools guide lacks this area.

• Edit: there is this question, but it doesn't help much: What is the Chrome Dev Tools "Hit Test" timeline entry?

So here I am, proudly done with my research, asking: how do I get about optimizing native hit testing in JavaScript?

---

I prepared a demo that demonstrates the performance bottleneck, although it's not exactly the same as my actual app, and numbers will obviously vary by device as well. To see the bottleneck:

1. Go to the Timeline tab on Chrome (or the equivalent of your browser)
2. Start recording, then pan around in the demo like a mad-man
3. Stop recording and check the results

---

A recap of all significant optimizations I have already done in this area:

• moving a single container on the screen instead of moving thousands of elements individually
• using transform: translate3d to move container
• v-syncing mouse movement to screen refresh rate
• removing all possible unnecessary "wrapper" and "fixer" elements
• using pointer-events: none on shapes -- no effect

Additional notes:

• the bottleneck exists both with and without GPU acceleration
• testing was only done in Chrome, latest
• the DOM is rendered using ReactJS, but the same issue is observable without it, as seen in the linked demo

Answer 1

Interesting, that pointer-events: none has no effect. But if you think about it, it makes sense, since elements with that flag set still obscure other elements' pointer events, so the hittest has to take place anyways.

What you can do is put a overlay over critical content and respond to mouse-events on that overlay, let your code decide what to do with it.

This works because once the hittest algorithm has found a hit, and I'm assuming it does that downwards the z-index, it stops.

---

With overlay

// ================================================  // Increase or decrease this value for testing:  var NUMBER_OF_OBJECTS = 40000;  // Wether to use the overlay or the container directly  var USE_OVERLAY = true;  // ================================================    var overlay = document.getElementById("overlay");  var container = document.getElementById("container");  var contents = document.getElementById("contents");    for (var i = 0; i < NUMBER_OF_OBJECTS; i++) {      var node = document.createElement("div");      node.innerHtml = i;      node.className = "node";      node.style.top = Math.abs(Math.random() * 2000) + "px";      node.style.left = Math.abs(Math.random() * 2000) + "px";      contents.appendChild(node);  }    var posX = 100;  var posY = 100;  var previousX = null;  var previousY = null;    var mousedownHandler = function (e) {      window.onmousemove = globalMousemoveHandler;      window.onmouseup = globalMouseupHandler;      previousX = e.clientX;      previousY = e.clientY;  }    var globalMousemoveHandler = function (e) {      posX += e.clientX - previousX;      posY += e.clientY - previousY;      previousX = e.clientX;      previousY = e.clientY;      contents.style.transform = "translate3d(" + posX + "px, " + posY + "px, 0)";  }    var globalMouseupHandler = function (e) {      window.onmousemove = null;      window.onmouseup = null;      previousX = null;      previousY = null;  }    if(USE_OVERLAY){  	overlay.onmousedown = mousedownHandler;  }else{  	overlay.style.display = 'none';  	container.onmousedown = mousedownHandler;  }      contents.style.transform = "translate3d(" + posX + "px, " + posY + "px, 0)";

#overlay{    position: absolute;    top: 0;    left: 0;    height: 400px;    width: 800px;    opacity: 0;    z-index: 100;    cursor: -webkit-grab;    cursor: -moz-grab;    cursor: grab;    -moz-user-select: none;    -ms-user-select: none;    -webkit-user-select: none;    user-select: none;  }    #container {    height: 400px;    width: 800px;    background-color: #ccc;    overflow: hidden;  }    #container:active {    cursor: move;    cursor: -webkit-grabbing;    cursor: -moz-grabbing;    cursor: grabbing;  }    .node {    position: absolute;    height: 20px;    width: 20px;    background-color: red;    border-radius: 10px;    pointer-events: none;  }

<div id="overlay"></div>  <div id="container">      <div id="contents"></div>  </div>

Without overlay

// ================================================  // Increase or decrease this value for testing:  var NUMBER_OF_OBJECTS = 40000;  // Wether to use the overlay or the container directly  var USE_OVERLAY = false;  // ================================================    var overlay = document.getElementById("overlay");  var container = document.getElementById("container");  var contents = document.getElementById("contents");    for (var i = 0; i < NUMBER_OF_OBJECTS; i++) {      var node = document.createElement("div");      node.innerHtml = i;      node.className = "node";      node.style.top = Math.abs(Math.random() * 2000) + "px";      node.style.left = Math.abs(Math.random() * 2000) + "px";      contents.appendChild(node);  }    var posX = 100;  var posY = 100;  var previousX = null;  var previousY = null;    var mousedownHandler = function (e) {      window.onmousemove = globalMousemoveHandler;      window.onmouseup = globalMouseupHandler;      previousX = e.clientX;      previousY = e.clientY;  }    var globalMousemoveHandler = function (e) {      posX += e.clientX - previousX;      posY += e.clientY - previousY;      previousX = e.clientX;      previousY = e.clientY;      contents.style.transform = "translate3d(" + posX + "px, " + posY + "px, 0)";  }    var globalMouseupHandler = function (e) {      window.onmousemove = null;      window.onmouseup = null;      previousX = null;      previousY = null;  }    if(USE_OVERLAY){  	overlay.onmousedown = mousedownHandler;  }else{  	overlay.style.display = 'none';  	container.onmousedown = mousedownHandler;  }      contents.style.transform = "translate3d(" + posX + "px, " + posY + "px, 0)";

#overlay{    position: absolute;    top: 0;    left: 0;    height: 400px;    width: 800px;    opacity: 0;    z-index: 100;    cursor: -webkit-grab;    cursor: -moz-grab;    cursor: grab;    -moz-user-select: none;    -ms-user-select: none;    -webkit-user-select: none;    user-select: none;  }    #container {    height: 400px;    width: 800px;    background-color: #ccc;    overflow: hidden;  }    #container:active {    cursor: move;    cursor: -webkit-grabbing;    cursor: -moz-grabbing;    cursor: grabbing;  }    .node {    position: absolute;    height: 20px;    width: 20px;    background-color: red;    border-radius: 10px;    pointer-events: none;  }

<div id="overlay"></div>  <div id="container">      <div id="contents"></div>  </div>

Answer 2

One of the problems is that you're moving EVERY single element inside your container, it doesn't matter if you have GPU-acceleration or not, the bottle neck is recalculating their new position, that is processor field.

My suggestion here is to segment the containers, therefore you can move various panes individually, reducing the load, this is called a broad-phase calculation, that is, only move what needs to be moved. If you got something out of the screen, why should you move it?

Start by making instead of one, 16 containers, you'll have to do some math here to find out which of these panes are being shown. Then, when a mouse event happens, move only those panes and leave the ones not shown where they are. This should reduce greatly the time used to move them.

+------+------+------+------+ |    SS|SS    |      |      | |    SS|SS    |      |      | +------+------+------+------+ |      |      |      |      | |      |      |      |      | +------+------+------+------+ |      |      |      |      | |      |      |      |      | +------+------+------+------+ |      |      |      |      | |      |      |      |      | +------+------+------+------+ 

On this example, we have 16 panes, of which, 2 are being shown (marked by S for Screen). When a user pans, check the bounding box of the "screen", find out which panes pertain to the "screen", move only those panes. This is theoretically infinitely scalable.

Unfortunately I lack the time to write the code showing the thought, but I hope this helps you.

Cheers!