Skip to content

Improve QCheck2 list_size shrinker #324

@jmid

Description

@jmid

From #319:

This PR takes a first step towards improving the QCheck2 list shrinker.
The current one uses the input size tree and offers only prefixes, e.g., shrinking [1;2;3;4;5;6;7;8] to [], [1;2;3;4], [1;2;3;4;5;6], [1;2;3;4;5;6;7] (or something like that). This results in needlessly large counterexamples, if the property is essentially "lists do not contain the int 7". 😬
[...]
The PR does not improve the QCheck2.Gen.{list_size, array_size, bytes_size, string_size} generators.
These take a size generator parameter, and I've not figured out how to cleanly respect that (read: preserve invariants), e.g., if a user provides a size generator of "even numbers", "multiples of 7", or "prime numbers". As such,
the shrinking behaviour and performance of those remain untouched.

and from #321:

The exception is the shrinker for QCheck2.Gen.list_size (and derivatives) which I've not attempted to improve.
For reference below I include a shrink_bench.log output for OCaml 4.14.2 on my laptop dominated by

  • long_shrink - 2.070s
  • lists shorter than 432 - 1.034s
  • lists shorter than 4332 - 7.541s
  • fold_left test, fun first - 1.908s

Of these the 3 first use QCheck2.Gen.list_size - and the last uses a function first (a known pain point also for QCheck(1)),

For a start, on a size 8 list generating say [1;2;3;4;5;6;7;8]
for a size shrink tree output of, e.g., 4, in addition to the prefix [1;2;3;4] one could try the suffix [5;6;7;8], the middle [3;4;5;6] and/or dropping elements, e.g., yielding [1;3;5;7]. For a smaller size shrink tree output of, e.g., 2, the challenge will be not to emit too many shrinking candidates as that may ruin performance as previously discussed for QCheck(1) in #268 #242 #235. The lesson from the QCheck(1) improvements is to yield in the order of O(log n) shrinking candidates, as that both (a) composes well and (b) scales better to large lists.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions