Bug 1310554 - Simplify `BookmarkSyncUtils.order` and use map lookups in `Bookmarks.reorder`. r=mak
authorKit Cambridge <kit@yakshaving.ninja>
Wed, 19 Oct 2016 19:06:34 -0700
changeset 318773 3b93af82598a9b975f166fc0da5607ad80ad2a8d
parent 318772 cbf9f5b47d561b51a014976f1f475629199c9417
child 318774 4d50a677b98973910b94eddf4753c2209d017efc
push id33364
push userkcambridge@mozilla.com
push dateThu, 20 Oct 2016 16:30:36 +0000
treeherderautoland@3b93af82598a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmak
bugs1310554, 1293365
milestone52.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 1310554 - Simplify `BookmarkSyncUtils.order` and use map lookups in `Bookmarks.reorder`. r=mak Bug 1293365 fixed the query in `Bookmarks.reorder` to leave missing entries in place, instead of moving them to the end of the folder. It also correctly ignores nonexistent children, so we can remove all the extra logic in `PlacesSyncUtils`. We can also use a map instead of two linear searches to look up indices in the `Bookmarks.reorder` sorting function. This reduces the time to sort an array of 10k children from 30 seconds to less than a second on my dev machine. MozReview-Commit-ID: G9vuC12JXq4
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/PlacesSyncUtils.jsm
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -1156,25 +1156,38 @@ function removeBookmark(item, options) {
 function reorderChildren(parent, orderedChildrenGuids) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: updateBookmark",
     db => db.executeTransaction(function* () {
       // Select all of the direct children for the given parent.
       let children = yield fetchBookmarksByParent({ parentGuid: parent.guid });
       if (!children.length)
         return undefined;
 
+      // Build a map of GUIDs to indices for fast lookups in the comparator
+      // function.
+      let guidIndices = new Map();
+      for (let i = 0; i < orderedChildrenGuids.length; ++i) {
+        let guid = orderedChildrenGuids[i];
+        guidIndices.set(guid, i);
+      }
+
       // Reorder the children array according to the specified order, provided
       // GUIDs come first, others are appended in somehow random order.
       children.sort((a, b) => {
-        let i = orderedChildrenGuids.indexOf(a.guid);
-        let j = orderedChildrenGuids.indexOf(b.guid);
         // This works provided fetchBookmarksByParent returns sorted children.
-        if (i == -1 && j == -1)
+        if (!guidIndices.has(a.guid) && !guidIndices.has(b.guid)) {
           return 0;
-        return (i != -1 && j != -1 && i < j) || (i != -1 && j == -1) ? -1 : 1;
+        }
+        if (!guidIndices.has(a.guid)) {
+          return 1;
+        }
+        if (!guidIndices.has(b.guid)) {
+          return -1;
+        }
+        return guidIndices.get(a.guid) < guidIndices.get(b.guid) ? -1 : 1;
        });
 
       // Update the bookmarks position now.  If any unknown guid have been
       // inserted meanwhile, its position will be set to -position, and we'll
       // handle it later.
       // To do the update in a single step, we build a VALUES (guid, position)
       // table.  We then use count() in the sorting table to avoid skipping values
       // when no more existing GUIDs have been provided.
--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -104,67 +104,36 @@ const BookmarkSyncUtils = PlacesSyncUtil
     let db = yield PlacesUtils.promiseDBConnection();
     let children = yield fetchAllChildren(db, parentGuid);
     return children.map(child =>
       BookmarkSyncUtils.guidToSyncId(child.guid)
     );
   }),
 
   /**
-   * Reorders a folder's children, based on their order in the array of GUIDs.
-   * This method is similar to `Bookmarks.reorder`, but leaves missing entries
-   * in place instead of moving them to the end of the folder.
+   * Reorders a folder's children, based on their order in the array of sync
+   * IDs.
    *
    * Sync uses this method to reorder all synced children after applying all
    * incoming records.
    *
    */
   order: Task.async(function* (parentSyncId, childSyncIds) {
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(parentSyncId);
     if (!childSyncIds.length) {
       return;
     }
-    for (let syncId of childSyncIds) {
-      PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(syncId);
-    }
     let parentGuid = BookmarkSyncUtils.syncIdToGuid(parentSyncId);
-
     if (parentGuid == PlacesUtils.bookmarks.rootGuid) {
       // Reordering roots doesn't make sense, but Sync will do this on the
       // first sync.
       return;
     }
-    yield PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: order",
-      Task.async(function* (db) {
-        let children = yield fetchAllChildren(db, parentGuid);
-        if (!children.length) {
-          return;
-        }
-
-        // Reorder the list, ignoring missing children.
-        let delta = 0;
-        for (let i = 0; i < childSyncIds.length; ++i) {
-          let guid = BookmarkSyncUtils.syncIdToGuid(childSyncIds[i]);
-          let child = findChildByGuid(children, guid);
-          if (!child) {
-            delta++;
-            BookmarkSyncLog.trace(`order: Ignoring missing child ${
-              childSyncIds[i]}`);
-            continue;
-          }
-          let newIndex = i - delta;
-          updateChildIndex(children, child, newIndex);
-        }
-        children.sort((a, b) => a.index - b.index);
-
-        // Update positions.
-        let orderedChildrenGuids = children.map(({ guid }) => guid);
-        yield PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
-      })
-    );
+    let orderedChildrenGuids = childSyncIds.map(BookmarkSyncUtils.syncIdToGuid);
+    return PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
   }),
 
   /**
    * Removes an item from the database.
    */
   remove: Task.async(function* (syncId) {
     let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
     if (guid in ROOT_GUID_TO_SYNC_ID) {
@@ -368,41 +337,16 @@ var fetchAllChildren = Task.async(functi
     id: row.getResultByName("id"),
     parentId: row.getResultByName("parent"),
     index: row.getResultByName("position"),
     type: row.getResultByName("type"),
     guid: row.getResultByName("guid"),
   }));
 });
 
-function findChildByGuid(children, guid) {
-  return children.find(child => child.guid == guid);
-}
-
-function findChildByIndex(children, index) {
-  return children.find(child => child.index == index);
-}
-
-// Sets a child record's index and updates its sibling's indices.
-function updateChildIndex(children, child, newIndex) {
-  let siblings = [];
-  let lowIndex = Math.min(child.index, newIndex);
-  let highIndex = Math.max(child.index, newIndex);
-  for (; lowIndex < highIndex; ++lowIndex) {
-    let sibling = findChildByIndex(children, lowIndex);
-    siblings.push(sibling);
-  }
-
-  let sign = newIndex < child.index ? +1 : -1;
-  for (let sibling of siblings) {
-    sibling.index += sign;
-  }
-  child.index = newIndex;
-}
-
 // A helper for whenever we want to know if a GUID doesn't exist in the places
 // database. Primarily used to detect orphans on incoming records.
 var GUIDMissing = Task.async(function* (guid) {
   try {
     yield PlacesUtils.promiseItemId(guid);
     return false;
   } catch (ex) {
     if (ex.message == "no item found for the given GUID") {