Optimization Questions

[abirmingham]

Hello!

Thank you so much for the library! It's worked great for smaller sets, but for a set of 8k events I'm starting to see longer execution times (~10s). I'd like to optimize it, but have some questions first...

1. It looks like findLane() is O(n^2) because it iterates through the bands already present in the lane. I've had promising results (10s->3s) using a WeakMap to reduce this to O(n). Does this seem like a reasonable solution? Am I missing anything? See WeakMap solution at the bottom of this post.
2. In timeline.js:186 we call processedTimelines.sort() before returning them. What would be the effect of removing this sort()?

Thanks!

WeakMap solution

$ git diff /tmp/timeline.old.js /tmp/timeline.new.js
diff --git a/tmp/timeline.old.js b/tmp/timeline.new.js
index cbad47fd1..339d68719 100644
--- a/tmp/timeline.old.js
+++ b/tmp/timeline.new.js
@@ -98,13 +98,27 @@ module.exports = function() {
         });
     }

-    function fitsIn(lane, band) {
+    var laneIdMap = new WeakMap();
+    var laneOutOfRangeDataMap = {};
+    var laneIdCounter = 0;
+    function addToLane(lane, band) {
+        if (!laneIdMap.has(lane)) {
+            laneIdMap.set(lane, laneIdCounter++);
+        }
+        var hasOutOfRangeData = laneOutOfRangeDataMap[laneIdMap.get(lane)];
+        if (!hasOutOfRangeData && (
+            !(lane.end < band.start || lane.start > band.end)
+        )) {
+            laneOutOfRangeDataMap[laneIdMap.get(lane)] = true;
+        }
+        lane.push(band);
+    }

+    function fitsIn(lane, band) {
       if (lane.end < band.start || lane.start > band.end) {
         return true;
       }
-      var filteredLane = lane.filter(function (d) {return d.start <= band.end && d.end >= band.start});
-      if (filteredLane.length === 0) {
+      if (!laneOutOfRangeDataMap[laneIdMap.get(lane)]) {
         return true;
       }
       return false;
@@ -118,7 +132,8 @@ module.exports = function() {
         }

         if (swimlane === undefined) {
-            swimlanes[band.parent.id] = [[band]];
+            swimlanes[band.parent.id] = [[]];
+            addToLane(swimlanes[band.parent.id][0][0], band)
             swimlane = swimlanes[band.parent.id];
             swimlaneNumber++;
             return;
@@ -128,12 +143,13 @@ module.exports = function() {

       while (x <= l) {
         if (fitsIn(swimlane[x], band)) {
-          swimlane[x].push(band);
+          addToLane(swimlane[x], band);
           return;
         }
         x++;
       }
-      swimlane[x] = [band];
+      swimlane[x] = [];
+      addToLane(swimlane[x], band);
       return;
     }