Shrink recursive structures efficiently

[graue]

Gentest has a hard time with this property, converted from a ClojureScript double-check example by @jamii, and run with 1000 tests (-n 1000):

forAll([t.arrayOf(t.tuple([t.string, t.string, t.string]))],
       'simulate sparse/complex failure',
       function(_) {
         return Math.random() < 0.999;
       });

If all tests pass, it's fine. But sometimes (maybe 2 in every 10 test runs), Gentest tries hundreds of thousands of shrinks before running out of memory and crashing. This variant, where the inner array can be of any length instead of always 3, is even worse:

forAll([t.arrayOf(t.arrayOf(t.string))],
       'simulate sparse/complex failure',
       function(_) {
         return Math.random() < 0.999;
       });

Example output:

$ time gentest -n 1000 gtboom2.js 
Testing gtboom2.js
736/1000 simulate sparse/complex failure, shrinking 224/232359FATAL ERROR: CALL_AND_
RETRY_2 Allocation failed - process out of memory
Aborted (core dumped)

real    1m21.912s
user    1m0.212s
sys     0m2.467s

Perhaps what we need is a limit on either the total number of shrinks tried, the branching factor of the shrink tree, or both.

[reiddraper]

Related: jamii/dcboom#1.

[jamii]

What exactly is happening to cause the OOM error? In my naive mental model, the process should be able to gc all the old shrink attempts when it runs out of memory. Is there some interaction with thunks in js that causes problems?

[jamii]

@graue I wonder if this applies to your thunks? Are they hanging on to all previous shrink results? Or maybe something is just hanging on to the head of the tree somewhere?

[graue]

Good question, it may be. I'll take a look when I get home tonight.
On Sep 8, 2014 3:08 PM, "Jamie Brandon" notifications@github.com wrote:

@graue https://github.com/graue I wonder if this
https://www.meteor.com/blog/2013/08/13/an-interesting-kind-of-javascript-memory-leak
applies to your thunks? Are they hanging on to all previous shrink results?

—
Reply to this email directly or view it on GitHub
#11 (comment).

[graue]

It's nothing so fancy as the closure memory leak discussed in that blog post. Rather, there were simply careless references sticking around to the root of the shrink tree in local variables within Runner.prototype.run. As a result, all the structure was being kept around indefinitely until the entire shrink process finished though most of it would never be used again. I've pushed a fix.

With that said, the example mentioned in this issue has been spinning my CPU for 11 minutes now trying to shrink a test case, with no end in sight. While it's fantastic that the memory usage is not growing (has stayed steady around 12-16% the whole time), this goes to show there's more to this problem than the OOM issue. There's no way shrinking should ever encounter a pathological case like this, so I still think we need:

a limit on either the total number of shrinks tried, the branching factor of the shrink tree, or both.

Thanks for prodding me to fix the OOM, though!

[jamii]

Where is the time spent? A limit on the total number of shrinks makes sense, but it still shouldn't be so slow.

For reference, with our gens this takes 1-20s with shortcuts disabled (eg no shrinking to []) (not sure yet why it is so variable):

var x = array(tuple([number, number, number])).grow(10000);

console.time("foo");
for (var j = 0; j < 100; j++) {
  var y = x;
  for (var i = 0; i < 10000; i ++) {
    y = y.shrink(y.value, 0);
  }
}
console.timeEnd("foo");

[jamii]

I'm probably going to stick random shrinking myself, but I also played around with a different formulation of lazy lists which seemed promising. Something like IdleList 'a = Int -> Maybe 'a. The client promises to never call with n+1 until it has called with n, which allows concat to look like:

function concat(as, bs) {
  var size;
  return function(i) {
    if (size && (i > size)) {
     return bs(i - size);
    } else {
      var output = as(i);
      if (as === null) {
        size = i;
        return bs(0); 
      } else {
        return output;
      }
   }
}

[jamii]

That way traversing the list has pretty low overhead and doesn't require allocating closures all over the place. Holding onto the head of the list also doesn't hold on to any of the elems so it's easy to avoid leaking.

[graue]

I shrink arrays only by removing one element at a time, not throwing away half the list as I've since heard of other quickchecks doing. Maybe that's at issue. Also, I was testing using the more pessimistic version that creates an array of arrays, not an array of triples, because the latter only rarely triggers the slow behavior.

[graue]

Also, fixing #10 will allow testing optimizations without randomness, so that's next on my list.

[jamii]

It occured to me that the whole point of these trees is to close over state from bind/fmap. If I require bind/fmap to be reversible ie bind' :: Gen a -> (a -> Gen b) -> (b -> a) -> Gen b then I don't need to track any state while shrinking. So now my interface is:

function Generator(grow, shrink) {
  this.grow = grow; // size -> Shrinkable
  this.shrink = shrink; // value, bias -> Shrinkable
}

That cuts down on the shrinking over head, so now I have:

console.time("Random tuple failure");
foralls(array(tuple([number, number, number])),
       function(_) {
         return Math.random() < 0.999;
       }).check({maxTests: 10000, maxShrinks: 20000, bias: 0});
console.timeEnd("Random tuple failure");
// 10-20 ms
console.time("Random array failure");
foralls(array(array(number)),
       function(_) {
         return Math.random() < 0.999;
       }).check({maxTests: 10000, maxShrinks: 20000, bias: 0});
console.timeEnd("Random array failure");
// 5000-50000 ms

Note that bias: 0 prevents it from trying things like dropping half the array - these times are for dropping/shrinking single elements.

I'm going to try this on some more complex failing tests like 'random graphs have no cycles' and see how well the random shrinking copes with actually finding a good counterexample.

[jamii]

So this is around 8-10s:

console.time("Arrays are not strictly sorted");
foralls(array(number, 9),
       function(nums) {
         for (var i = 0; i < nums.length - 1; i++) {
           if (nums[i] >= nums[i+1]) return true;
         }
         return false;
       }).check({maxTests: 10000000, maxShrinks: 20000000, bias: 0});
console.timeEnd("Arrays are not strictly sorted");

[jamii]

And returns:

{"size":88948,"numTests":88948,"numShrinks":20000000,"shrunkInput":[[-6,-5,-4,-3,-2,-1,0,1,2]],"shrunkOutput":false,"inputs":[[-69727.16291431151,-55212.27623556182,-43946.77461897954,-18731.191785626113,-16522.434840338305,-16140.821281293407,-9239.386977022514,-404.77836262993515,53609.66097328067]],"output":false}

[jamii]

I did have to give up (non-reversible) bind though, which is a shame.

[graue]

@jamii Would you like to meet/hack in person on this sometime?

I'm optimistic that we can make gentest performant without abandoning general bind. I would, however, like to see more of your approach and the sorts of tests where you're hitting performance issues, and pair programming may be a good way to do that.

[jamii]

Sure. Maybe this weekend? I'm not sure what our plans are right now.

[graue]

Hey @jamii are you still interested in this? I'm planning to hack on it this weekend (or at least, I'm hacking on it now). It would be cool to get a yes/no from you on whether I fixed your problem.

[jamii]

Sorry, I didn't get an email for that last message for some reason :S

[shamrin]

@jamii Do you plan to open source your quickcheck implementation? You've mentioned a thing called bigcheck in your "Eve so far" post. I'd love to play with it :)

[jamii]

@shamrin

var bigcheck = (function () {
  var exports;

  function isInteger(n) {
    return n === +n && n === (n|0);
  }

  // GENERATORS

  function resize(size) {
    return size; // TODO
  }

  function rebias(bias) {
    return bias; // TODO
  }

  function Generator(grow, shrink) {
    this.grow = grow; // size -> Shrinkable
    this.shrink = shrink; // value, bias -> Shrinkable
  }

  var integer = new Generator(
    function numberGrow(size) {
      return Math.floor(size * ((Math.random() * 2) - 1));
    },
    function numberShrink(value, bias) {
      if (Math.random() < bias) {
        return 0;
      } else {
        return Math.floor(value * ((Math.random() * 2) - 1));
      }
    }
  );

  var number = new Generator(
    function numberGrow(size) {
      return size * ((Math.random() * 2) - 1);
    },
    function numberShrink(value, bias) {
      if (isInteger(value)) {
        return integer.shrink(value, bias);
      } else if (Math.random() < bias) {
        return Math.floor(value);
      } else {
        return value * ((Math.random() * 2) - 1);
      }
    });

  function array(elem, length) {
    return new Generator(
      function arrayGrow(size) {
        var len = length || Math.random() * size;
        var value = [];
        for (var i = 0; i < len; i++) {
          value[i] = elem.grow(resize(size));
        }
        return value;
      },
      function arrayShrink(value, bias) {
        if ((value.length === 0) || ((length === undefined) && (Math.random() < bias))) {
          return [];
        } else {
          var newValue = value.slice();
          var i = Math.floor(Math.random() * newValue.length);
          if ((length === undefined) && (Math.random() < 0.5)) {
            newValue.splice(i, 1);
          } else {
            newValue[i] = elem.shrink(newValue[i], rebias(bias));
          }
          return newValue;
        }
      });
  }

  function tuple(elems) {
    return new Generator(
      function tupleGrow(size) {
        var len = elems.length;
        var value = [];
        for (var i = 0; i < len; i++) {
          value[i] = elems[i].grow(resize(size));
        }
        return value;
      },
      function tupleShrink(value, bias) {
        var newValue = value.slice();
        var i = Math.floor(Math.random() * newValue.length);
        newValue[i] = elems[i].shrink(newValue[i], rebias(bias));
        return newValue;
      });
  }

  var value = integer; // TODO any valid eve value

  function facts(numColumns) {
    return array(array(value, numColumns));
  }

  // PROPERTIES

  function Success(numTests, options, prop) {
    this.numTests = numTests;
    this.options = options;
    this.prop = prop;
  }

  function Failure(size, numTests, numShrinks, shrunkInput, shrunkOutput, input, output, options, prop) {
    exports.lastFailure = this;
    this.size = size;
    this.numTests = numTests;
    this.numShrinks = numShrinks;
    this.shrunkInput = shrunkInput;
    this.shrunkOutput = shrunkOutput;
    this.inputs = input;
    this.output = output;
    this.options = options;
    this.prop = prop;
  }

  function ForAll(name, gen, fun) {
    this.name = name;
    this.gen = gen;
    this.fun = fun;
  }

  function forall(name, gen, fun) {
    return new ForAll(name, gen, fun);
  }

  function foralls() {
    var gens = Array.prototype.slice.call(arguments);
    var name = gens.shift();
    var fun = gens.pop();
    var gen = tuple(gens);
    return new ForAll(name, gen, function (values) {fun.apply(null, values)});
  }

  ForAll.prototype = {
    check: function (options) {
      console.info("Testing: " + this.name);
      console.time(this.name);

      options = options || {};

      var numTests = 0;
      var maxTests = options.maxTests || 100;
      var maxSize = options.maxSize || maxTests;
      var input;
      var output;

      while (true) {
        var size = maxSize * (numTests / maxTests);
        input = this.gen.grow(size);
        try {
          output = this.fun.call(null, input);
        } catch (exception) {
          output = exception;
        }
        if (output !== true) break;
        numTests += 1;
        if (numTests >= maxTests) {
          console.timeEnd(this.name);
          return new Success(numTests, options, this);
        }
      }

      var numShrinks = 0;
      var maxShrinks = options.maxShrinks || (2 * maxTests);
      var bias = options.bias || 0.25; // TODO grow/shrink bias
      var shrunkInput = input;
      var shrunkOutput;

      while (true) {
        var tryInput = this.gen.shrink(shrunkInput, bias);
        var tryOutput;
        try {
          tryOutput = this.fun.call(null, tryInput);
        } catch (exception) {
          tryOutput = exception;
        }
        if (tryOutput !== true) {
          shrunkInput = tryInput;
          shrunkOutput = tryOutput;
        }
        numShrinks += 1;
        if (numShrinks >= maxShrinks) {
          console.timeEnd(this.name);
          return new Failure(size, numTests, numShrinks, shrunkInput, shrunkOutput, input, output, options, this);
        }
      }
    },

    assert: function(options) {
      var result = this.check(options);
      if (result instanceof Failure) {
        if (result.output instanceof Error) result.output = result.output.toString(); // Errors don't JSONify nicely
        throw new Error(JSON.stringify(result));
      } else {
        return result;
      }
    },

    recheck: function(input) {
      var input = input || exports.lastFailure.shrunkInput;
      if (input) {
        return this.fun.call(null, input);
      } else {
        return true;
      }
    }
  };

  // TESTS

  //   foralls(number, number,
  //          function (a, b) {
  //            return (a + b) >= a;
  //          }).assert();

  // console.time("Random tuple failure");
  // foralls(array(tuple([number, number, number])),
  //        function(_) {
  //          return Math.random() < 0.999;
  //        }).check({maxTests: 10000, maxShrinks: 20000, bias: 0});
  // console.timeEnd("Random tuple failure");

  // console.time("Random array failure");
  // foralls(array(array(number)),
  //        function(_) {
  //          return Math.random() < 0.999;
  //        }).check({maxTests: 10000, maxShrinks: 20000, bias: 0});
  // console.timeEnd("Random array failure");

  // console.time("Arrays are not strictly sorted");
  // foralls(array(number, 9),
  //        function(nums) {
  //          for (var i = 0; i < nums.length - 1; i++) {
  //            if (nums[i] >= nums[i+1]) return true;
  //          }
  //          return false;
  //        }).check({maxTests: 10000000, maxShrinks: 20000000, bias: 0});
  // console.timeEnd("Arrays are not strictly sorted");

  exports = {number: number, integer: integer, array: array, tuple: tuple, value: value, facts: facts, forall: forall, foralls: foralls};

  return exports;
})();

The MIT License (MIT)

Copyright (c) 2014 Kodowa Inc

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

[shamrin]

@jamii wow, thank you!

[graue]

Well, time to throw in the towel on my silly implementation ;)

Seriously though, thanks @jamii, look forward to browsing through this and stealing any good ideas I find :)

[jamii]

@graue It doesn't have fmap or bind. I think fmap is doable if the inverse function is provided. Bind is probably not going to work out this way. There is probably some way to support both with decent performance but I went for the quick 80% solution.

[jamii]

I certainly wouldn't mind switching to a fast, featureful quickcheck if one should happen to fall out of the sky ;)

[shamrin]

@jamii @graue I've made a couple of fixes to allow running (commented out) tests: updated to new foralls API, added return in foralls implementation. And Node modules compatibility. Nothing serious, just basic stuff:

https://github.com/shamrin/bigcheck

@jamii Are these commented out tests enough to make sure featureful quickcheck implemention is good enough?

[shamrin]

@jamii I've tried the approach you suggested. It works! I've implemented map(elems, to, from) and then char/string on top of it. I haven't touched any of the core stuff, so performance should be the same. Providing to/from reversible pairs could be error-prone, so I've added forall check in my map implementation:

forall('check map', elems, function(e) { return _.isEqual(from(to(e)), e); }).assert();

See my repo. It's not polished enough yet: tests are little messy, there's unnecessary dependency on underscore for map parameters checking. But it should work.

[jamii]

@shamrin cool!

The tests in there are a basic sanity check. The tests @graue added at the start of this issue are closer to what I use bigcheck for - generating random databases and then testing incremental view maintenance over them. The minimum failing cases sometimes have 40+ rows so the normal quickcheck shrinking tree eats all my memory and then crashes the browser. Unfortunately I can't publish any of that code for testing yet :S

[graue]

I'm gonna close this because I don't feel like it's clear something is broken, or what would need to happen to consider it fixed. After 2051ca7, the out-of-memory bug is gone and even the pathological example in this issue performs mostly alright.