Integer shrinking is less efficient than it could be.

[jonaskoelker]

See https://gist.github.com/jonaskoelker/4390fcc8bec868cd3b4f4ef43f29b830, in particular in run the sbt command testOnly DefaultShrinking -- -f triple and testOnly FancyShrinking -- -f triple to compare.

The current shrinking shrinks n to n/2, n/4, n/8, ..., interleaved with the negation of this stream. Ideally (I guess?) the shrinking process does a binary search for the smallest failing value. However, given that shrinking is restarted every time a failing example is found, the tail of the shrink stream is only looked at if running the test on the first shrink succeeds.

Thus, if we want to approximate a binary search, we can use the knowledge that prior shrinks succeeded to decide the next shrunk. In particular, I think 0, n - n/2, n - n/4, n - n/8, ... is a better stream of candidates (for positive n): it repeatedly bisects a range which is known to contain a boundary case until the next failure is found, at which point it repeats this effective search for a boundary value. (This is also, perhaps approximately, the integral-type shrinking used in rust-quickcheck.)

If you run the commands I mentioned above, you will see that my suggested shrinking reduces the failing example in fewer shrinks (easy to eyeball for small values of n) than the current built-in shrinker.

[ashawley]

Yes, there is room for improvement with shrinking. It's simplistic, as is. You're suggesting 1) the shrink should be able to run in the other direction, not just to zero, and 2) that when the property fails and then succeeds it could start a new and different shrink. It's not just about either the arithmetic ScalaCheck uses for numerics or the binary search for the shrink function of integers.

[jonaskoelker]

You're suggesting 1) the shrink should be able to run in the other direction, not just to zero, and 2) that when the property fails and then succeeds it could start a new and different shrink.

Maybe I explained myself poorly or maybe I failed at code reading comprehension.

When I look at the shrinker sub-function of Prop.forAllShrink, it seems to me that it calls shrink, and finds the first failing element of the shrunk stream. If there are none we're done shrinking, otherwise we recursively call shrinker with the shrunk element, which calls shrink on the shrunk element.

That's the part where ScalaCheck already, in some sense, restarts the shrinking process (and which I suggest keeping as-is). The implication of this is that if you include n / 2 in your shrinker's output, there's really no need to also include n / 4, at least not if the test case fails for n / 2: in that case, the recursive shrink of n / 2 will include (n / 2) / 2, i.e. n / 4, and the next recursive call will include ((n / 2) / 2) / 2 and so on. If the test case fails, that is.

The implication of this is that when you choose what to put as the second element of a shrink stream, you know that either it will never be considered, or else the test case succeeded on the first stream element. We can use that knowledge to shrink more cleverly: we know that the test succeeds on n / 2 and fails on n, thus there exists some smallest value k between those two extremes for which the test case fails. If we were to binary search for it, n - (n / 4) (approx. n/2 + (n - n/2)/2) would be the next obvious choice, then n - (n / 8) and so on, so long as the test case keeps succeeding.

I think

You're suggesting the shrink should be able to run in the other direction, not just to zero

is a fair characterization, but I would like to add some detail: it should look for a smallest failure value, searching below the most recent query value if the most recent query value resulted in a test failure and above it if the most recent query value resulted in a test success, and preferably in the middle each time so as to resemble binary search.

On the other hand,

[You're suggesting] that when the property fails and then succeeds it could start a new and different shrink

doesn't sound quite like any proposal I had in mind; this sounds like your restatement of my reading of what existing code already does.

It's not just about either the arithmetic ScalaCheck uses for numerics or the binary search for the shrink function of integers.

My suggestion is to output a different stream of numbers such that the behavior of the whole search process more closely resembles binary search, the benefit of which is that it's faster (measured for example in the number of test cases run in my fairly simple example).

[ashawley]

we know that the test succeeds on n / 2 and fails on n, thus there exists some smallest value k between those two extremes for which the test case fails

Right, this is the optimization you're looking for. The type signature for ScalaCheck shrinking takes a single value. There is a second implied parameter which is the nil value (empty list, zero, etc. depending on the type) that it's assumed the stream reduces to. Shrinking should instead shrink to a range, and not just to zero, empty list, etc.

[jonaskoelker]

The type signature for ScalaCheck shrinking takes a single value [...] to a range, and not just to zero, empty list, etc.

I don't understand the significance of this. I suspect we might be talking past each other. Would you restate with more details how you're interpreting what I'm suggesting, and whether you (a) are on board with that change; (b) suggest a different change which achieves the same goals, presumably in a better way; (c) oppose that change; or (d) something else?

[ashawley]

I was moving on to imaginging what the implementation would need to be, but I'm probably incorrect.

Is there any documentation for how this is done in Rust's QuickCheck?

[jonaskoelker]

I was moving on to imaginging what the implementation would need to be, but I'm probably incorrect.

I linked to a gist. To bake my suggested idea into ScalaCheck, all you'd need to do is copy-paste shrinkInt and have it replace the current shrinking for Int. Well, copy-paste and consider what the edge cases are and battle-harden it a little, but it's just a different Shrink instance, that's it.

Is there any documentation for how this is done in Rust's QuickCheck?

It's done with a stateful iterator, remembering x and initializing i to x / 2. On every call to next it yields x - i and sets i = i / 2. See https://github.com/BurntSushi/quickcheck/blob/32d8b0383b5cedb5e6dd8fd3dd1494f734e49d6e/src/arbitrary.rs#L732.

[jonaskoelker]

See #743.