Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve fast checking for empty objects #23

Open
mikemitchel opened this issue Aug 9, 2019 · 1 comment
Open

Improve fast checking for empty objects #23

mikemitchel opened this issue Aug 9, 2019 · 1 comment

Comments

@mikemitchel
Copy link

In pairing with @justinbmeyer we found that overwriting an object property on a ViewModel was very slow to cleanup the old prop value. Main symptom wascan-reflect iterating 500k times to tear down bindings and the final 'real' solution was to improve can-key-tree's ability to know the size of the bindings to be cleaned up, and also do better Fast Checking of empty objects (see this link: http://js-unit-testing.com/2013/05/10/fast-checking-for-empty-objects-in-javascript/)

His quick notes of possible solution here (Justin please fix the lingo above as needed):

{
    [addKeyValue]: function(key, value){
        this[key] = value;

        this[countSymbol]++;
    },
    [addKeyValue]: function(key, value){
        this[key] = value;

        this[countSymbol]--;
    }
    [size](){
    
    }
}
@mikemitchel
Copy link
Author

mikemitchel commented Aug 9, 2019

TLDR;
over 3 tests:
current code: 222,731 count, 3190ms avg of 3548ms, 2924ms, 3098ms
isEmpty code: 222,727 count, 2744ms avg of 2823ms, 2623ms, 2787ms

Some updates after pairing session two:
First, the CALI app is making a lot of calls (200k) to delete which needs to be investigated separately.

Second, the above code idea to track size internally did not cause a performance boost as expected. implemented this way:

  var ObjectWithSize = function () {
      Object.defineProperty(this, "___count", {
          value: 0,
          enumerable: false,
          writable: true
      })
  };

  ObjectWithSize.prototype[Symbol.for('can.size')] = function () {
      return this.___count
  }
  ObjectWithSize.prototype[Symbol.for('can.getKeyValue')] = function (prop) {
      return this[prop]
  }
  ObjectWithSize.prototype[Symbol.for('can.setKeyValue')] = function (prop, value) {
      this.___count++
      return this[prop] = value
  }
  ObjectWithSize.prototype[Symbol.for('can.deleteKeyValue')] = function (prop) {
      this.___count--
      delete this[prop]
  }
  ObjectWithSize.prototype[Symbol.for('can.getOwnEnumerableKeys')] = function () {
      return Object.keys(this)
  }
  ObjectWithSize.prototype[Symbol.for('can.empty')] = function () {
      return this.___count === 0
  }

Third: The isEmpty initial attempt to optimize testing for empty objects seemed to be a bit faster than the above ObjectWithSize code. the delete function was converted to an IIFE with window.deleteCount and window.deleteTime using performance.now() to produce some metrics for testing speed improvements.
It looked like this:

      delete: (function () {
          window.deleteTime = 0
          window.deleteCount = 0
          var isEmptySymbol = Symbol.for('can.empty')
          var isEmpty = function (obj) {
              if (!obj) {
                  return true;
              }
              var isEmptyMethod = obj[isEmptySymbol]
              if (isEmptyMethod !== undefined) {
                  return isEmptyMethod.call(obj)
              }
              if (Array.isArray(obj)) {
                  return obj.length === 0
              }
              if (reflect.isPlainObject(obj) === true) {
                  for (var prop in obj) {
                      if (Object.prototype.hasOwnProperty.call(obj, prop)) {
                          return false;
                      }
                  }
                  return true;
              }
              return Object.keys(obj).length === 0
          }

          return function (keys, deleteHandler) {
          window.deleteCount++
          var startTime = performance.now()
          var parentNode = this.root, path = [this.root], lastKey = keys[keys.length - 1];
          for (var i = 0; i < keys.length - 1; i++) {
              var key = keys[i];
              var childNode = reflect.getKeyValue(parentNode, key);
              if (childNode === undefined) {
                  return false;
              } else {
                  path.push(childNode);
              }
              parentNode = childNode;
          }
          if (!keys.length) {
              clearDeep(parentNode, [], this.treeStructure.length - 1, deleteHandler);
          } else if (keys.length === this.treeStructure.length) {
              if (reflect.isMoreListLikeThanMapLike(parentNode)) {
                  if (deleteHandler) {
                      deleteHandler.apply(null, keys.concat(lastKey));
                  }
                  reflect.removeValues(parentNode, [lastKey]);
              } else {
                  throw new Error('can-key-tree: Map types are not supported yet.');
              }
          } else {
              var nodeToRemove = reflect.getKeyValue(parentNode, lastKey);
              if (nodeToRemove !== undefined) {
                  clearDeep(nodeToRemove, keys, this.treeStructure.length - 1, deleteHandler);
                  reflect.deleteKeyValue(parentNode, lastKey);
              } else {
                  window.deleteTime = window.deleteTime + performance.now() - startTime
                  return false;
              }
          }
          for (i = path.length - 2; i >= 0; i--) {
              // if (reflect.size(parentNode) === 0) {
              if (isEmpty(parentNode) === true) {
                  parentNode = path[i];
                  reflect.deleteKeyValue(parentNode, keys[i]);
              } else {
                  break;
              }
          }
          // if (reflect.size(this.root) === 0) {
          if (isEmpty(this.root) === true) {
              this.empty = true;
              if (this.callbacks.onEmpty) {
                  this.callbacks.onEmpty.call(this);
              }
          }
          window.deleteTime = window.deleteTime + performance.now() - startTime
          return true;
          }
      })(),

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant