Object Cycle Detection (v3)

Revision 3 of this benchmark created by vjeux on September 24, 2011

Preparation HTML

<script>
  var CycleDetection = {
    generateCyclicObject: function (size) {
      var root = {};
      var obj = root;
      for (var i = 0; i < size; ++i) {
        obj['child'] = {};
        obj = obj['child'];
      }
      obj['child'] = root;
      return root;
    },
  
    array: function (obj) {
      var seenObjects = [];
  
      function detect (obj) {
        if (typeof obj === 'object') {
          if (seenObjects.indexOf(obj) !== -1) {
            return false;
          }
          seenObjects.push(obj);
          for (var key in obj) {
            if (obj.hasOwnProperty(key) && !detect(obj[key])) {
              return false;
            }
          }
        }
        return true;
      }
        
      return detect(obj);
    },
  
    mark: function (obj) {
      var seenObjects = [];
      var mark = String(Math.random());
  
      function detect (obj) {
        if (typeof obj === 'object') {
          if (mark in obj) {
            return false;
          }
          obj[mark] = true;
          seenObjects.push(obj);
          for (var key in obj) {
            if (obj.hasOwnProperty(key) && !detect(obj[key])) {
              return false;
            }
          }
        }
        return true;
      }
  
      var result = detect(obj);
      
      for (var i = 0; i < seenObjects.length; ++i) {
        delete seenObjects[i][mark];
      }
      
      return result;
    },
    
    json: function (obj) {
      var isNativeJSON = typeof JSON !== 'undefined' && JSON.stringify.toString().match(/\{ \[native code\] \}$/);
      if (!isNativeJSON) {
        throw 'Native JSON.stringify is not available, can\'t use this technique.';
      }
      try {
        JSON.stringify(obj);
        return true;
      } catch (e) {
        return false;
      }
    }
  };
  
  var o100 = CycleDetection.generateCyclicObject(100);
  var o1000 = CycleDetection.generateCyclicObject(1000);
  var o10000 = CycleDetection.generateCyclicObject(10000);
</script>

Test runner

CycleDetection.array(o100);

CycleDetection.json(o100);

CycleDetection.mark(o100);

CycleDetection.array(o1000);

CycleDetection.json(o1000);

CycleDetection.mark(o1000);

CycleDetection.array(o10000);

CycleDetection.json(o10000);

CycleDetection.mark(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