Skip to content

Commit acfbdd4

Browse files
jfirebaughjfirebaugh
committed
Optimize selection.data(values, key)
Preallocate the keyValues array and use a single Map with the sentinel value `true` to represent a previously seen key. Before: selection.data(values, key) (enter) 1.5ms/op. selection.data(values, key) (update) 1.7ms/op. After: selection.data(values, key) (enter) 0.81ms/op. selection.data(values, key) (update) 1.1ms/op.
1 parent 1fc660a commit acfbdd4

4 files changed

Lines changed: 51 additions & 19 deletions

File tree

‎d3.js‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -762,29 +762,29 @@
762762
function bind(group, groupData) {
763763
var i, n = group.length, m = groupData.length, n0 = Math.min(n, m), updateNodes = new Array(m), enterNodes = new Array(m), exitNodes = new Array(n), node, nodeData;
764764
if (key) {
765-
var nodeByKeyValue = new d3_Map(), dataByKeyValue = new d3_Map(), keyValues = [], keyValue;
765+
var nodeByKeyValue = new d3_Map(), keyValues = new Array(n), keyValue;
766766
for (i = -1; ++i < n; ) {
767767
keyValue = key.call(node = group[i], node.__data__, i);
768768
if (nodeByKeyValue.has(keyValue)) {
769769
exitNodes[i] = node;
770770
} else {
771771
nodeByKeyValue.set(keyValue, node);
772772
}
773-
keyValues.push(keyValue);
773+
keyValues[i] = keyValue;
774774
}
775775
for (i = -1; ++i < m; ) {
776776
keyValue = key.call(groupData, nodeData = groupData[i], i);
777-
if (node = nodeByKeyValue.get(keyValue)) {
777+
node = nodeByKeyValue.get(keyValue);
778+
if (!node) {
779+
enterNodes[i] = d3_selection_dataNode(nodeData);
780+
} else if (node !== true) {
778781
updateNodes[i] = node;
779782
node.__data__ = nodeData;
780-
} else if (!dataByKeyValue.has(keyValue)) {
781-
enterNodes[i] = d3_selection_dataNode(nodeData);
782783
}
783-
dataByKeyValue.set(keyValue, nodeData);
784-
nodeByKeyValue.remove(keyValue);
784+
nodeByKeyValue.set(keyValue, true);
785785
}
786786
for (i = -1; ++i < n; ) {
787-
if (nodeByKeyValue.has(keyValues[i])) {
787+
if (nodeByKeyValue.get(keyValues[i]) !== true) {
788788
exitNodes[i] = group[i];
789789
}
790790
}

‎d3.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/selection/data.js‎

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -31,8 +31,7 @@ d3_selectionPrototype.data = function(value, key) {
3131

3232
if (key) {
3333
var nodeByKeyValue = new d3_Map,
34-
dataByKeyValue = new d3_Map,
35-
keyValues = [],
34+
keyValues = new Array(n),
3635
keyValue;
3736

3837
for (i = -1; ++i < n;) {
@@ -42,23 +41,23 @@ d3_selectionPrototype.data = function(value, key) {
4241
} else {
4342
nodeByKeyValue.set(keyValue, node);
4443
}
45-
keyValues.push(keyValue);
44+
keyValues[i] = keyValue;
4645
}
4746

4847
for (i = -1; ++i < m;) {
4948
keyValue = key.call(groupData, nodeData = groupData[i], i);
50-
if (node = nodeByKeyValue.get(keyValue)) {
49+
node = nodeByKeyValue.get(keyValue);
50+
if (!node) {
51+
enterNodes[i] = d3_selection_dataNode(nodeData);
52+
} else if (node !== true) {
5153
updateNodes[i] = node;
5254
node.__data__ = nodeData;
53-
} else if (!dataByKeyValue.has(keyValue)) { // no duplicate data key
54-
enterNodes[i] = d3_selection_dataNode(nodeData);
55-
}
56-
dataByKeyValue.set(keyValue, nodeData);
57-
nodeByKeyValue.remove(keyValue);
55+
} // otherwise duplicate data key
56+
nodeByKeyValue.set(keyValue, true);
5857
}
5958

6059
for (i = -1; ++i < n;) {
61-
if (nodeByKeyValue.has(keyValues[i])) {
60+
if (nodeByKeyValue.get(keyValues[i]) !== true) {
6261
exitNodes[i] = group[i];
6362
}
6463
}

‎test/selection/data-benchmark.js‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
var jsdom = require("jsdom");
2+
3+
global.document = jsdom.jsdom("<html><head></head><body></body></html>");
4+
5+
var d3 = require("../../");
6+
7+
var formatNumber = d3.format(",.02r"),
8+
values = d3.range(0, 1000),
9+
key = function(x) { return x; },
10+
div = d3.select(document.createElement("div")),
11+
selection,
12+
n = 1e3,
13+
then = Date.now();
14+
15+
selection = div.selectAll("div");
16+
17+
for (var i = 0; i < n; i++) {
18+
selection.data(values, key);
19+
}
20+
21+
console.log("selection.data(values, key) (enter) " + formatNumber((Date.now() - then) / i) + "ms/op.");
22+
23+
selection.data(values, key)
24+
.enter().append("div");
25+
26+
selection = div.selectAll("div");
27+
then = Date.now();
28+
29+
for (var i = 0; i < n; i++) {
30+
selection.data(values, key);
31+
}
32+
33+
console.log("selection.data(values, key) (update) " + formatNumber((Date.now() - then) / i) + "ms/op.");

0 commit comments

Comments
 (0)