Object Cycle Detection (v2)

Revision 2 of this benchmark created by vjeux on September 23, 2011

Preparation HTML

<script>
  /* Build the recursive object */
  function generateRecursiveObject(n) {
    var root = {};
    var obj = root;
    for (var i = 0; i < n; ++i) {
      obj['child'] = {};
      obj = obj['child'];
    }
    obj['child'] = root;
    return root;
  }
  var o100 = generateRecursiveObject(100);
  var o1000 = generateRecursiveObject(1000);
  var o10000 = generateRecursiveObject(10000);
  
  
  function CycleDetection() {
    this.seenObjects = [];
  }
  CycleDetection.prototype = {
    detect: function (obj) {
       if (typeof obj === 'object') {
         if ('mark' in obj) {
           return false;
         }
         obj.mark = true;
         this.seenObjects.push(obj);
         for (var key in obj) {
           if (obj.hasOwnProperty(key) && !this.detect(obj[key])) {
             return false;
           }
         }
       }
       return true;
    },
  
    test: function (obj) {
      var result = this.detect(obj);
      for (var i = 0; i < this.seenObjects.length; ++i) {
        delete this.seenObjects[i].mark;
      }
      return result;
    }
  }
  
  
  var isNativeJSON = typeof JSON !== 'undefined' && JSON.stringify.toString().match(/\{ \[native code\] \}$/);
  if (isNativeJSON) {
    JSONCycleDetection = function (obj) {
      try {
        JSON.stringify(obj);
        return true;
      } catch (e) {
        return false;
      }
    }
  } else {
    JSONCycleDetection = function (obj) {
      throw 'Not native JSON.stringify';
    }
  }
</script>

Test runner

(new CycleDetection).test(o100);

JSONCycleDetection(o100);

(new CycleDetection).test(o1000);

JSONCycleDetection(o1000);

(new CycleDetection).test(o10000);

JSONCycleDetection(o10000);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by vjeux on September 23, 2011
• Revision 2: published by vjeux on September 23, 2011
• Revision 3: published by vjeux on September 24, 2011