Repository: blitz-js/superjson
Pull request #96 (2021-01-24 14:51:22)

Performance regression (simonedelmann's work)


Patch:
diff --git a/src/annotator.ts b/src/annotator.ts
index b739367..aadaeec 100644
--- a/src/annotator.ts
+++ b/src/annotator.ts
@@ -48,6 +48,7 @@ class ValueAnnotationFactory {
   }
 
   create() {
+    PathTree.compress(this.tree);
     return PathTree.collapseRoot(this.tree);
   }
 }
diff --git a/src/pathtree.ts b/src/pathtree.ts
index 6701e8c..a042d88 100644
--- a/src/pathtree.ts
+++ b/src/pathtree.ts
@@ -1,20 +1,6 @@
 import { stringifyPath, parsePath } from './pathstringifier';
 import { isUndefined, isNull, isArray, isPlainObject } from './is';
-import { forEach, every, find } from 'lodash';
-
-function startsWith(prefix: string, v: string) {
-  if (prefix.length > v.length) {
-    return false;
-  }
-
-  for (let i = 0; i < prefix.length; i++) {
-    if (v[i] !== prefix[i]) {
-      return false;
-    }
-  }
-
-  return true;
-}
+import { forEach, every } from 'lodash';
 
 export type Tree<T> = InnerNode<T> | Leaf<T>;
 type Leaf<T> = [T];
@@ -71,24 +57,7 @@ export module PathTree {
     if (tree.length === 1) {
       ((tree as any) as InnerNode<T>)[1] = { [stringifyPath(path)]: [value] };
     } else {
-      const [, children] = tree;
-      const availablePaths = Object.keys(children);
-
-      const stringifiedPath = stringifyPath(path);
-
-      // due to the constraints mentioned in the functions description,
-      // there may be prefixes of `path` already set, but no extensions of it.
-      // If there's such a prefix, we'll find it.
-      const prefix = find(availablePaths, candidate =>
-        startsWith(candidate + '.', stringifiedPath)
-      );
-
-      if (isUndefined(prefix)) {
-        tree[1][stringifyPath(path)] = [value];
-      } else {
-        const pathWithoutPrefix = path.slice(parsePath(prefix).length);
-        append(children[prefix], pathWithoutPrefix, value);
-      }
+      tree[1][stringifyPath(path)] = [value];
     }
   }
 
@@ -192,4 +161,52 @@ export module PathTree {
 
     return [null, tree];
   }
+
+  /**
+   * @description Compress nested trees for smaller output
+   */
+  export function compress<T>(tree: Tree<T | null>) {
+    if (tree.length === 1) {
+      // tree root is Leaf
+      return;
+    }
+
+    const origin = tree[1];
+    const keys = Object.keys(origin).sort((a, b) => a.length - b.length);
+    const transformed: Record<string, Tree<T | null>> = {};
+
+    for (let i = 0; i < keys.length; i++) {
+      const key = keys[i];
+
+      let parentKey = undefined;
+      let splittedKey = key.split('.');
+      while (splittedKey.length > 0) {
+        splittedKey.pop();
+        const possibleParentKey = splittedKey.join('.');
+        if (transformed.hasOwnProperty(possibleParentKey)) {
+          parentKey = possibleParentKey;
+          break;
+        }
+      }
+      if (parentKey && transformed[parentKey]) {
+        transformed[parentKey][1] = Object.assign(
+          transformed[parentKey][1] || {},
+          {
+            [key.substring(parentKey.length + 1)]: origin[key],
+          }
+        );
+        continue;
+      } else {
+        transformed[key] = origin[key];
+      }
+    }
+
+    // Recursive optimization
+    const transformedKeys = Object.keys(transformed);
+    for (let i = 0; i < transformedKeys.length; i++) {
+      compress(transformed[transformedKeys[i]]);
+    }
+
+    tree[1] = transformed;
+  }
 }


Test patch:
diff --git a/src/pathtree.test.ts b/src/pathtree.test.ts
index 3b99bf8..cb642c7 100644
--- a/src/pathtree.test.ts
+++ b/src/pathtree.test.ts
@@ -8,14 +8,17 @@ test('pathtree', () => {
   expect(tree).toEqual([null, { abc: ['1'] }]);
 
   PathTree.append(tree, ['abc', 'd'], '2');
+  PathTree.compress(tree);
 
   expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }] }]);
 
   PathTree.append(tree, ['foo', 'bar'], '3');
+  PathTree.compress(tree);
 
   expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }], 'foo.bar': ['3'] }]);
 
   PathTree.append(tree, ['foo', 'bar', 'lel', 'lol'], '4');
+  PathTree.compress(tree);
 
   expect(tree).toEqual([
     null,