Learning F#: Case study with branch and bound – PART III
OpCoast © 2016
Part III: Testing and Timing
There are many points in the software development process where testing and reviews can occur (see wiki). Typically, we would have integrated unit testing with the development process, but this may have obfuscated the process of reaching a functional approach to the problem, so I relegated testing to this separate section. Indeed in the ‘Agile’ or ‘Extreme’ software development processes, test goals and testing functions may be written before the actual code, which is then developed to meet the testing goals — see the concept of test driven development (TDD). This page describes an amusing story of how TDD can go wrong, that is if the software developer is simply providing code that passes the provided tests, but where the code does not really provide correct functionality (e.g. when the tests are insufficient). This page also introduces us to property-based testing which we will look at later.
In any event, it is important to provide a measure of testing to help ensure that your code operates correctly, so let’s start by doing some unit testing of our own. xUnit is a unit test tool that integrates with Visual Studio and other platforms. FsUnit extends xUnit to provide a more functional feel for F# testing, so we will focus on this. We will also use FsCheck later, so I show the setup with that installed as well. For Visual Studio and other platforms, you can use nuget to install the appropriate version. Although not necessary, I created separate testing and timing projects that refer to our development project BandB
. You can combine the unit tests into a single project, but I prefer to have the development project contain only that which will be deployed/delivered.
Visual Studio setup for testing
The figure above points out the references to FsCheck
, FsCheck.XUnit
, FsUnit.XUnit
and xunit.execution.desktop
in the test project BandB.Test
, the latter of these is the so-called test runner from within Visual Studio. Also note that you must make sure that the test project is referencing the project that you want to test, here BandB
. You will have to determine how to install and run such tools in your environment if different from mine. As can be seen, a new project called BandB.Test
was added to the solution which references the unit testing tools and libraries as well as the BandB
project. I also show a third project called BandB.Timing
as well. This project has references to BandB
and BandB.Test
so that it can use the functions defined therein.
In BandB.Test
, we create a main program file (Program.fs
here) that defines tests to run, rather than code. Since there is no main entry point for this project (only tests), you will likely get a warning about this when the project is built — its OK to ignore the warning.
Let’s start testing reverseSort
, we will start with a few simple tests and then refine these more properly later. For our basic xUnit tests, each test (of a function) is expressed as a Fact using the annotation syntax in F#.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: |
namespace BandBTestopen BandBapplicationopen Xunitopen FsUnit.Xunitmodule TestFunctions = let randList count = let rnd = System.Random(100) // use a seed so that everytime we run we get the same values List.init count (fun _ -> rnd.Next ()) let rec isListReversed li = match li with | [] | [_] -> true | a::ls -> if a < ls.Head then false else isListReversed ls [<Fact>] let ``List reverseSort []`` () = [] |> List.reverseSort |> should equal [] [<Fact>] let ``List reverseSort [1]`` () = [1] |> List.reverseSort |> should equal [1] [<Fact>] let ``List reverseSort [1; 2]`` () = [1; 2] |> List.reverseSort |> should equal [2; 1] [<Fact>] let ``List reverseSort [2; 1; 7; 9; 11; 14; 16; 3; -6; 0]`` () = [2; 1; 7; 9; 11; 14; 16; 3; -6; 0] |> List.reverseSort |> should equal [16; 14; 11; 9; 7; 3; 2; 1; 0; -6] [<Fact>] let ``List reverseSort random 100`` () = let list1 = randList 100 list1 |> List.reverseSort |> isListReversed |> should equal true [<Fact>] let ``List reverseSort random 10000`` () = let list1 = randList 10000 list1 |> List.reverseSort |> isListReversed |> should equal true [<Fact>] let ``List reverseSort floats`` () = [5.5; 6.2; -2.0; 14.7; 20.1e10; 7.7; 0.0; 4.9] |> List.reverseSort |> should equal [20.1e10; 14.7; 7.7; 6.2; 5.5; 4.9; 0.0; -2.0] [<Fact>] let ``List reverseSort strings`` () = ["abc"; "def"; "ghi"; "jkl"; "mno"; "pqr"; "stu"; "vwx"; "yz"] |> List.reverseSort |> should equal ["yz"; "vwx"; "stu"; "pqr"; "mno"; "jkl"; "ghi"; "def"; "abc"] |
Be careful when introducing extra functions for test purposes – more on this later
As can be seen, the file has eight tests indicated, where each test uses the should equal
function to see if the result is what is expected (the FsUnit site lists other test types that can be defined). Note that the ``string``
syntax allows us to define the function name to test with an arbitrary string that might include spaces instead of a single name, this will make the test result output more readable. Here are some comments on the tests:
- The reverse sort of
[]
should be[]
. This tests ourList.reverseSort
with empty lists - The reverse sort of
[1]
should be[1]
. This tests for a single element. Along with the above, its always important to test special cases like empty lists or lists of one element. - The reverse sort of
[1; 2]
should be[2; 1]
- The
``List reverseSort random *xxx*``
tests uses a function we created that returns a random list of integers of a given length. Since we can’t explicitly write what the reverse sort should be, we test the result by using a helper function that tests to see if the elements are indeed in reverse order. You might wonder – do we need to test this test function, which is called a test oracle? More on that later. - A test with float elements.
- We test string elements as well as integers in one test, even though in the application we only apply (so far) the
reverseSort
function to lists of ints and floats.
The test runner will gather the tests to be conducted, here the functions that are annotated with [<Fact>]
, and execute each one. Here are my results
Test results
We see that one of our tests failed, and also an indication of how long each test was. Since there are many factors involved, we need to be careful about timing results, we will get to this next section — also the test time shown here includes the whole test execution time, not just the function being tested (reverseSort
).
So what went wrong with our simplest test, reversing the empty list? Our current implementation of reverseSort
is just using List.sort
followed by List.rev
which seems like it should work fine on an empty list, and of course it does work fine for the other tests. The problem lies in handling of generic types. For example, let’s look at the types of []
and the result of []
with reverseSort applied with this snippet:
1: 2: 3: 4: 5: 6: 7: |
let x = [].GetType()let y = ([] |> List.reverseSort).GetType()printfn "x is %Any is %A" x y(* I WILL GET THIS AS OUTPUT *)x is Microsoft.FSharp.Collections.FSharpList`1[System.Object]y is Microsoft.FSharp.Collections.FSharpList`1[System.IComparable] |
Notice that the type of variable , which is defined simply as
[]
, is of type FSharp list of any object while variable , defined as
([] |> List.reverseSort)
, is of type FSharp list of IComparable. That is, after the function List.reverseSort is applied the elements of resulting list, although empty, must be of comparable types since sorting requires elements to be comparible. So the should equal
phrase fails since the data types of these empty lists are different. We can fix this test by instead testing as:
1: 2: 3: |
[<Fact>] let ``List reverseSort []`` () = [] |> List.reverseSort |> should be Empty |
With this change, all of our tests pass. Now the first test reads that the reverse-sorted empty list should be empty. We could instead fix this by explicitly typing the elements of the empty list, something like ([]:int list) |> List.reverseSort |> should equal ([]:int list)
which would test that empty lists of int elements work, but the should be Empty
test is more general. We now need to consider testing BandB
and possibly the and
functions for each of the three problem types that we created, but before we move to that, let’s consider some performance ideas.
Timing
Visual Studio provides a nice facility for performance testing of code, the example below shows some of the output. Execution time for functions and sub-functions can be explored dynamically. This can be seen in the next figure where we see that queue management is taking the bulk of the time for the runs that we did as defined in Program.fs
at the end of Part II in BandB
, not for BandB.Test
Visual Studio performance testing
If you are using Visual Studio, this is a powerful feature that you should get acquainted with. However, since not everyone is developing F# with Visual Studio, I will focus on simpler timer-based performance testing (rather than instrumented performance testing as VS is doing).
One must be careful to get valid timings, as many system factors and dynamic conditions can effect the result. Even more so with timer based testing, there are issues such as cache warmup, virtual memory swapping that may occur at any time, on-demand system library loading, variations in input/output (I/O) operation (if I/O is present), interference from other processes, the data itself (can definitely be significant in sorting), and other factors.
In addition to the reverseSort
method we used and tested before, let’s consider other implementations as well. The code is:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187: 188: 189: 190: 191: 192: 193: 194: 195: 196: 197: 198: 199: 200: 201: 202: 203: 204: 205: 206: 207: 208: 209: 210: 211: 212: 213: |
open BandBapplicationopen BandBTest.TestFunctions // to get randListopen Knapsack01open MaxSatopen TSPopen BandBopen Xunitopen FsUnit.Xunitmodule Timing = (* * New list generation functions *) (* create list of 'count' random strings of 'n' chars each, providing a random seed *) let randStringList n count seed = let rnd = System.Random(seed) // use a seed so that everytime we run we get the same values let randNstring n = String.init n (fun i -> sprintf "%c" (char (rnd.Next(26) + int 'A'))) List.init count (fun _ -> (randNstring n)) (* create list of 'count' random floats, providing a random seed *) let randFloatList count seed = let rnd = System.Random(seed) List.init count (fun _ -> 20.0 * (rnd.NextDouble() - 0.5)) // num range is plus/minus 10 (* create list of 'count' ints, providing a random seed*) let randIntList count seed = let rnd = System.Random(seed) List.init count (fun _ -> rnd.Next ()) (* * New reverseSort methods *) (* Create a new reverseSort method that uses the negative of the value to sort *) module List = let reverseSort2 x = match box x with | :? (float list) as floatList -> floatList |> List.sortBy (fun elem -> -(elem)) :> obj | :? (int list) as intList -> intList |> List.sortBy (fun elem -> -(elem)) :> obj | _ -> failwith "reverseSort2 inapplicable" let reverseCompare x y = if y < x then // still only requires the (<) operator, but uses it on the compare args backwards 1 else -1 (* Use the sortWith function with reverseCompare to get a reverseSort *) let reverseSort3 x = x |> List.sortWith reverseCompare (* * Timer function, that vary the random seed from 0 .. *) let timeThis listGen count func nSeeds = let stopWatch = System.Diagnostics.Stopwatch.StartNew() stopWatch.Reset() for seed in 0..nSeeds do let lst = listGen count seed stopWatch.Start() lst |> func |> ignore // this is what we're timing stopWatch.Stop() stopWatch.Elapsed.TotalMilliseconds (* Add some testing for our rand functions *) [<Fact>] let ``randStringList different`` () = let s0 = randStringList 10 100 0 let s1 = randStringList 10 100 1 s0 |> should not' (equal s1) [<Fact>] let ``randIntList different`` () = let s0 = randIntList 100 0 let s1 = randIntList 100 1 s0 |> should not' (equal s1) [<Fact>] let ``randFloatList different`` () = let s0 = randFloatList 100 0 let s1 = randFloatList 100 1 s0 |> should not' (equal s1) [<Fact>] let ``randStringList correct len`` () = (randStringList 10 101 0).Length |> should equal 101 [<Fact>] let ``randIntList correct len`` () = (randIntList 101 0).Length |> should equal 101 [<Fact>] let ``randFloatList correct len`` () = (randFloatList 101 0).Length |> should equal 101 [<EntryPoint>] let main argv = for _ in 1..2 do let mutable count = 100 let nSeeds = 100 (* int 100 cases *) printfn "nint %d:" count let t_int_100_rs1 = timeThis randIntList count List.reverseSort nSeeds let t_int_100_rs = timeThis randIntList count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_int_100_rs let t_int_100_rs2 = timeThis randIntList count List.reverseSort2 nSeeds printfn " reverseSort2 time = %8.3f ms" t_int_100_rs2 let t_int_100_rs3 = timeThis randIntList count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_int_100_rs3 let t_int_100_ds = timeThis randIntList count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_int_100_ds (* float 100 cases *) printfn "nfloat %d:" count let t_flt_100_rs = timeThis randFloatList count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_flt_100_rs let t_flt_100_rs2 = timeThis randFloatList count List.reverseSort2 nSeeds printfn " reverseSort2f time = %8.3f ms" t_flt_100_rs2 let t_flt_100_rs3 = timeThis randFloatList count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_flt_100_rs3 let t_flt_100_ds = timeThis randFloatList count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_flt_100_ds (* string 10 / 100 cases *) printfn "nstring 10 %d:" count let t_str_100_rs = timeThis (randStringList 10) count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_str_100_rs let t_str_100_rs3 = timeThis (randStringList 10) count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_str_100_rs3 let t_str_100_ds = timeThis (randStringList 10) count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_str_100_ds (* int 1000 cases *) count <- 1000 printfn "nint %d:" count let t_int_1000_rs = timeThis randIntList count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_int_1000_rs let t_int_1000_rs2 = timeThis randIntList count List.reverseSort2 nSeeds printfn " reverseSort2 time = %8.3f ms" t_int_1000_rs2 let t_int_1000_rs3 = timeThis randIntList count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_int_1000_rs3 let t_int_1000_ds = timeThis randIntList count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_int_1000_ds (* float 1000 cases *) printfn "nfloat %d:" count let t_flt_1000_rs = timeThis randFloatList count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_flt_1000_rs let t_flt_1000_rs2 = timeThis randFloatList count List.reverseSort2 nSeeds printfn " reverseSort2f time = %8.3f ms" t_flt_1000_rs2 let t_flt_1000_rs3 = timeThis randFloatList count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_flt_1000_rs3 let t_flt_1000_ds = timeThis randFloatList count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_flt_1000_ds (* string 10 / 1000 cases *) printfn "nstring 10 %d:" count let t_str_1000_rs = timeThis (randStringList 10) count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_str_1000_rs let t_str_1000_rs3 = timeThis (randStringList 10) count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_str_1000_rs3 let t_str_1000_ds = timeThis (randStringList 10) count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_str_1000_ds (* int 10000 cases *) count <- 10000 printfn "nint %d:" count let t_int_10000_rs = timeThis randIntList count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_int_10000_rs let t_int_10000_rs2 = timeThis randIntList count List.reverseSort2 nSeeds printfn " reverseSort2 time = %8.3f ms" t_int_10000_rs2 let t_int_10000_rs3 = timeThis randIntList count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_int_10000_rs3 let t_int_10000_ds = timeThis randIntList count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_int_10000_ds (* float 10000 cases *) printfn "nfloat %d:" count let t_flt_10000_rs = timeThis randFloatList count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_flt_10000_rs let t_flt_10000_rs2 = timeThis randFloatList count List.reverseSort2 nSeeds printfn " reverseSort2f time = %8.3f ms" t_flt_10000_rs2 let t_flt_10000_rs3 = timeThis randFloatList count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_flt_10000_rs3 let t_flt_10000_ds = timeThis randFloatList count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_flt_10000_ds (* string 10 / 10000 cases *) printfn "nstring 10 %d:" count let t_str_10000_rs = timeThis (randStringList 10) count List.reverseSort nSeeds printfn " reverseSort time = %8.3f ms" t_str_10000_rs let t_str_10000_rs3 = timeThis (randStringList 10) count List.reverseSort3 nSeeds printfn " reverseSort3 time = %8.3f ms" t_str_10000_rs3 let t_str_10000_ds = timeThis (randStringList 10) count List.sortDescending nSeeds printfn " sortDescending time = %8.3f ms" t_str_10000_ds printfn "nDONE" System.Console.ReadKey() |> ignore // don't close the output window until a key is hit 0 // return an integer exit code |
Three new random list creation functions are shown, each with a last parameter seed
that is the seed for the random number generator. The new function randStringList
was created to form randomized string lists. It’s parameters are the number of characters in each entry and the number of entries (count), and seed. Also, similar to the randList
function that was defined in BandB.Test
to create random int lists, a function randFloatList
was created to create randomized lists of floating point values, the range for these is ± 10. Also a function randIntList
was created like randList
but with a seed argument.
You can’t overload non-inline or non-member functions based on argument types as in other languages, so instead we use type based pattern matching of arguments
We also created new sorting methods. The first reverseSort2
uses the List.sortBy
method where the element is negated. An increasing sort with element values negated will result in a reverse (descending) sort. As was mentioned before, the unary minus causes the element argument to change from a generic to an int, so using this approach for floating point values must be handled differently. The function reverseSort2
uses pattern matching of the argument type to apply the List.sortBy function. On line 43 we see the pattern match for box x
, the box function converts the argument (which is a list hopefully) to its type and we then match this type to either
int list
or float list
so that we can then apply List.sortBy
. Since we are using our ‘negative element value’ technique to achieve the reverse sort, we only apply this to lists of ints or floats, and otherwise fail. The final discussion point is the final cast to obj
as the result for each case (the :>
operator). Without this, the result for the two cases are different, as they should be, either an int or float list respectively. But this is not allowed, so we cast each result to the generic obj
(this is the base class for all items); we could alternatively unbox
each result (reverse of box
), although the :> obj
seems to be more prevalent in F# documentation, as:
The reverseSort2
function shows how to handle generic arguments and result types
1: 2: 3: 4: 5: |
let reverseSort2 x = match box x with | :? (float list) as floatList -> floatList |> List.sortBy (fun elem -> -(elem)) |> unbox | :? (int list) as intList -> intList |> List.sortBy (fun elem -> -(elem)) |> unbox | _ -> failwith "reverseSort2 inapplicable" |
With either implementation, reverseSort2
reverse sorts a list of either ints or floats providing as output the same.
The final new reverse sort is reverseSort3
which uses the standard List.sortWith
F# method. This method takes a comparison function that compares two elements and returns either a positive, negative or zero result (see sortWith). In our case we used a function reverseCompare
(a lambda could be used of course) that still only requires the operator but compares the arguments in the reverse order. This will result in a reverse sorted list.
A timing function timeThis
was created, that takes as arguments: a list generation function; a count of the length of the list to be created; the function to be timed (in the sense that the lists created by the generation function are the argument); a number of seeds. The idea is that sorting can be quite data dependent so this function will create nSeeds
random lists such that each uses a different random seed. For timing, this function makes use of a standard .NET feature, the stopwatch to time (elapsed) the nSeeds
calls of func
Important Make sure to build the release mode code and run it outside of Visual Studio — just find and run the .exe
file for the build. As running it ‘attached’ to VS can cause additional overheads and variations.
The timing results for running BandB.Timing
are below. Note that I run each peice of code I am timing twice on a quiet system and take the lower of the two produced values for each case to avoid initialization issues (.NET libraries are loaded, just-in-time compiler conversions). Admittedly, this is a bit un-scientific and the results will vary a bit from different runs. Using an instrumented-code approach would give more definitive measures, but since we are using 100 random cases of various lengths for various types the results are sufficient for our purposes.
int 100 | 0.717 | 13.176 | 2.366 | 2.769 |
float 100 | 0.731 | 1.305 | 13.278 | 2.713 |
string 10 100 | 2.477 | n/a | 10.573 | 3.592 |
int 1000 | 7.102 | 8.291 | 196.312 | 32.013 |
float 1000 | 9.170 | 16.096 | 189.267 | 37.706 |
string 10 1000 | 33.671 | n/a | 158.000 | 50.895 |
int 10000 | 94.006 | 98.858 | 2488.893 | 417.657 |
float 10000 | 113.801 | 187.927 | 2499.322 | 479.842 |
string 10 10000 | 449.967 | n/a | 2062.173 | 706.218 |
Of course the ‘negative element value’ approach for sorting in reverseSort2
can’t be used for strings so that is shown as ‘n/a’. Perhaps surprisingly, our initial implementation of reverseSort
, which did a forward sort and then reversed the list is best in all cases — the best case is shown in red. I might have thought that reverseList2
would be better as it avoids the extra list reversal and directly sorts, but perhaps the overhead of invoking a user defined function for the sort is too high; and our reverseSort (and reverseSort2) is faster than the built in sortDescending
as well. We could look into the the compiled code to see why this is happening, but that is beyond our scope here.
I also note that in the final Part 2 BandB
code, the sortBy
method is used as the search nodes are a tuple of the estimated function value and the variable settings. So that timing is probably more in line with reverseSort2
and not reverseSort
which was deemed the fastest. But we needed to use the tuple to implement other features in the code — so we aren’t using the fastest implementation (nor the slowest).
Additional tests
Finally, note that I added some tests to this file, see lines 69-89. Stepping back, such tests could have been added directly to the BandB
project, rather than creating a new project, but I like to keep the project that is going to be the subject of deployment with just the actual code needed. However, I don’t mind adding tests to this timing project as it is not to be deployed either.
The idea of these tests is to test the code we are using for timing, in this case the random list generators. Since the generated data is random, the only things I am testing are that the lists generated are of the correct, requested length and that the lists created with two different random seeds (0 and 1) are indeed different. If the list generation were truly random, I suppose there could be a chance that these might come out the same, but as we know that the random generator is actually a pseudo-random sequence generator there isn’t a chance of this in actuality. These tests pass as well when the test runner is executed, and are shown in the figure on the next page.
Download this code
On to page 2