"greedy traversal" test performance

[Porges]

This is the test in question:

fsharp-hedgehog/tests/Hedgehog.Tests/MinimalTests.fs

Lines 65 to 89 in 1dfb754

	// FIXME This test takes quite some time to run, it would be good to profile
	// FIXME this and find out where the hotspots are. I have a much more complex
	// FIXME version of the same test in Haskell and it finishes in a few seconds,
	// FIXME even in GHCi (the interpreter).
	[<Fact>]
	let ``greedy traversal with a predicate yields the perfect minimal shrink``() =
	Property.check <| property {
	let! xs = Gen.mapTree Tree.duplicate genExp |> Gen.resize 20
	match tryFindSmallest noAppLit10 xs with
	| None ->
	return true
	| Some (App (Lit 0, Lit 10)) ->
	return true
	| Some x ->
	return! property {
	counterexample ""
	counterexample "Greedy traversal with predicate did not yield the minimal shrink."
	counterexample ""
	counterexample "=== Minimal ==="
	counterexample (sprintf "%A" (App (Lit 0, Lit 10)))
	counterexample "=== Actual ==="
	counterexample (sprintf "%A" x)
	return false
	}
	}

I ran this under the profiler and the problem is entirely due to the sprintf in forAll:

fsharp-hedgehog/src/Hedgehog/Property.fs

Lines 276 to 281 in 1dfb754

	let forAll (gen : Gen<'a>) (k : 'a -> Property<'b>) : Property<'b> =
	let handle (e : exn) =
	Gen.constant (Journal.singleton (string e), Failure) |> ofGen
	let prepend (x : 'a) =
	bind (counterexample (sprintf "%A" x)) (fun _ -> try k x with e -> handle e) |> toGen
	Gen.bind gen prepend |> ofGen

Replacing this with x.ToString() reduces the runtime from to 40 s to 0.55 s (!)

However, ToString isn't as useful as sprintf "%A" for 'native' F# types. A better fix would be to make this function lazily-invoked, so that it's only called if needed.

[moodmosaic]

Very interesting. See also #135.

[Porges]

@moodmosaic yes, I suspect there are a bunch more easy fixes like this 🙂

[moodmosaic]

Fixed in #147 and released as Hedgehog 0.6.

[cmeeren]

Just want to let you guys know that this reduced my test suite for a small-ish project (156 tests) from 14 seconds to 4 seconds. Great job, keep it up! 👍