Integrated Random Testing

For a while I've been annoyed by the performance of testing libraries in general, but also with how random testing and performance testing are not better integrated and multithreaded. Testing libraries like Expecto do a great job of improving performance by running unit tests in parallel while also opening up useful functionality like stress testing. I want to take this further with a new prototype.

The goal is a simpler, more lightweight testing library with faster, more integrated parallel random testing with automatic parallel shrinking.

The library aims to encourage the shift from a number of unit and regression tests with hard coded input and output data to fewer more general random tests. This idea is covered well by John Hughes in Don't write tests! and the idea of One test to rule them all. Key takeaways are general random tests can provide more coverage for less test code, and larger test cases have a higher probability of finding a failure for a given execution time.

Features

• Asserts are no longer exception based and all are evaluated - More than one per test is encouraged. Simpler setup and faster for multi part testing.

test "PCG demo 1" {
    let pcg = PCG.TryParse "36185706b82c2e03f8" |> Option.get
    Test.equal pcg.Stream 54 "stream"
    Test.equal pcg.State 0x185706b82c2e03f8UL "state"
    let expectedNext = [|0xa15c02b7u;0x7b47f409u|] // ...
    let expectedState = [|0x2b47fed88766bb05UL;0x8b33296d19bf5b4eUL|] // ...
    for i = 0 to expectedNext.Length-1 do
        Test.equal (pcg.Next()) expectedNext.[i] ("n"+string i)
        Test.equal pcg.State expectedState.[i] ("s"+string i)
}

• Integrated random testing - Simpler syntax. Easier to move to more general random testing. Run in fine grained parallel.

    test "gen" {
        test "int" {
            let! s = Gen.int
            let! l = Gen.int.[0..Int32.MaxValue-s]
            let! i = Gen.int.[s..s+l]
            Test.between i s (s+l) "between"
        }
        test "int distribution" {
            let freq = 10
            let buckets = 1000
            let! ints = Gen.seq.[freq * buckets] Gen.int.[0..buckets-1]
            let actual = Array.zeroCreate buckets
            Seq.iter (fun i -> actual.[i] <- actual.[i] + 1) ints
            let expected = Array.create buckets freq
            Test.chiSquared actual expected "chi-squared"
        }

• No sizing or number of runs for random tests - Instead use distributions. More realistic large test cases.

test "list rev does nothing not" {
    let! list =
        let f ma mi bu = Version (int ma,int mi,int bu)
        Gen.map3 f Gen.byte Gen.byte Gen.byte
        |> Gen.list.[0..100]
    Test.equal (List.rev list) list "rev equal"
}

• Automatic parallel random shrinking giving a reproducible seed - Smaller candidates found using a fast PCG loop. Simpler reproducible examples.
• Stress testing in parallel across unit and random tests using PCG streams - Low sync, high performance, fine grained parallel testing.

test "multithreading" {
    let n = 10
    let ms = MapSlim()
    test "update" {
        let! i = Gen.int.[..n-1]
        let v = &ms.GetRef i
        v <- 1-v
    }
    test "get" {
        let! i = Gen.int.[..n-1]
        let v = defaultValueArg (ms.GetOption i) 0
        Test.isTrue (v=0 || v=1) "get is 0 or 1"
    }
    test "item" {
        if ms.Count > 0 then
            let! i = Gen.int.[..ms.Count-1]
            let k,v = ms.Item i
            Test.lessThan k n "key is ok"
            Test.isTrue (v=0 || v=1) "value is 0 or 1"
    }
}

• Integrated performance testing - Performance tests can be random and run in parallel with statistics collected across all threads.

test "mapslim" {
    test "performance" {
        test "get" {
            let ms = MapSlim()
            let dict = Dictionary()
            let! n = Gen.int.[1..100]
            let! keys =
                Gen.array.[n] Gen.int.[-1000..1000]
                |> Gen.map (
                    Array.mapi (fun i h ->
                        let k = KeyWithHash(uint64 i, h)
                        ms.Set(k,k)
                        dict.Add(k,k)
                        k
                    )
                )
            Test.faster
                (fun () ->
                    for i = 0 to n-1 do
                        ms.GetOption keys.[i] |> ignore
                )
                (fun () ->
                    for i = 0 to n-1 do
                        dict.TryGetValue keys.[i] |> ignore
                )
                "get"
        }
        // ...
    }
    // ...
}

• Tests are run in parallel using continuations - Fine grained, in test asynchronous code to make each test faster.

test "reference" {
    let getTest name (gen:Gen<'a>) = test name {
        let! items = Gen.tuple gen Gen.int
                        |> Gen.list.[..100]
        let! check = gen
        let! expectedFork =
            io {
                return
                List.fold (fun m (k,v) -> Map.add k v m) Map.empty items
                |> Map.tryFind check
            } |> IO.fork
        let actual =
            let ms = MapSlim()
            List.iter ms.Set items
            ms.GetOption check
            |> function | ValueSome i -> Some i | ValueNone -> None
        let! expected = expectedFork
        Test.equal actual expected "check value equal"
    }
    getTest "get byte" Gen.byte
    getTest "get char" Gen.char
    getTest "get int" Gen.int.[..10]
    getTest "get uint" Gen.uint.[..10u]
    getTest "get string" Gen.string
}

Conclusion

The prototype currently has no dependencies and is a single file for the library, one for Gen and one for Test. They can easily be copied into a project to try them out, and new Gen and Test functions added.

The library is still in an early stage. It is missing more tests, label functionality, async io and needs a tidy and performance work.

I am keen to share it now to see if there are further ideas. Some of the functionality if successful could be added to existing projects or it could form its own. It is unclear at this point.

The code can be found here.