Bug 1356282 - Change Sync's Utils.arraySub to be O(n) using Set. r=tcsc
authortiago <tiago.paez11@gmail.com>
Fri, 05 May 2017 03:16:30 -0300
changeset 359387 afee0d3c7aab0f98bf3c2084a5b891c9e319234e
parent 359386 563a164d255a85725b56a9cf8d453bec07370501
child 359388 f8c14563b37d26afff2db80daff5ee36474440bb
push id31854
push userarchaeopteryx@coole-files.de
push dateSat, 20 May 2017 16:46:00 +0000
treeherdermozilla-central@51736db67723 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerstcsc
bugs1356282
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1356282 - Change Sync's Utils.arraySub to be O(n) using Set. r=tcsc Sync's Utils.arrayUnion and Utils.arraySub are O(n^2) because Utils.arraySub uses indexOf inside a loop. This patch makes Utils.arraySub use a Set, and by doing so, Utils.arrayUnion and Utils.arraySub become O(n). MozReview-Commit-ID: DDqjRWalfP9
services/sync/modules/util.js
--- a/services/sync/modules/util.js
+++ b/services/sync/modules/util.js
@@ -547,17 +547,18 @@ this.Utils = {
 
   /**
    * Create an array like the first but without elements of the second. Reuse
    * arrays if possible.
    */
   arraySub: function arraySub(minuend, subtrahend) {
     if (!minuend.length || !subtrahend.length)
       return minuend;
-    return minuend.filter(i => subtrahend.indexOf(i) == -1);
+    let setSubtrahend = new Set(subtrahend);
+    return minuend.filter(i => !setSubtrahend.has(i));
   },
 
   /**
    * Build the union of two arrays. Reuse arrays if possible.
    */
   arrayUnion: function arrayUnion(foo, bar) {
     if (!foo.length)
       return bar;