2 {-

3 Binary search over benchmark input sizes.

5 There are many good ways to measure the time it takes to perform a

6 certain computation on a certain input. However, frequently, it's

7 challenging to pick the right input size for all platforms and all

8 compilataion modes.

10 Sometimes for linear-complexity benchmarks it is better to measure

11 /throughput/, i.e. elements processed per second. That is, fixing

12 the time of execution and measuring the amount of work done (rather

13 than the reverse). This library provides a simple way to search for

14 an appropriate input size that results in the desired execution time.

16 An alternative approach is to kill the computation after a certain

17 amount of time and observe how much work it has completed.

18 -}

19 module BinSearch

20 (

21 binSearch

22 )

23 where

33 -- | Binary search for the number of inputs to a computation that

34 -- results in a specified amount of execution time in seconds. For example:

35 --

36 -- > binSearch verbose N (min,max) kernel

37 --

38 -- ... will find the right input size that results in a time

39 -- between min and max, then it will then run for N trials and

40 -- return the median (input,time-in-seconds) pair.

43 do

44 when(verbose)$ putStrLn$ "[binsearch] Binary search for input size resulting in time in range "++ show (min,max)

49 -- At some point we must give up...

50 loop n | n > ((2::Integer) ^ (100::Integer)) = error "ERROR binSearch: This function doesn't seem to scale in proportion to its last argument."

52 -- Not allowed to have "0" size input, bump it back to one:

55 loop n =

56 do

62 -- [2010.06.09] Introducing a small fudge factor to help our guess get over the line:

67 -- TODO: We should keep more history here so that we don't re-explore input space we have already explored.

68 -- This is a balancing act because of randomness in execution time.

70 if good_trial time

71 then do

72 when(verbose)$ putStrLn$ "[binsearch] Time in range. LOCKING input size and performing remaining trials."

73 print_trial 1 n time

76 -- Here we're still in the doubling phase:

84 -- Here we've exited the doubling phase, but we're making our first guess as to how big a real execution should be:

90 -- Termination condition: Done with all trials.

96 do when(verbose)$ putStrLn$ "[binsearch]------------------------------------------------------------"

98 -- hFlush stdout

100 -- when(verbose)$ hFlush stdout

104 print_trial trialnum n time =

107 in

125 -- Could use cycle counters here.... but the point of this is to time

126 -- things on the order of a second.

128 timeit io =

130 io

131 end <- getCurrentTime

133 {-

134 test :: IO (Integer,Double)

135 test =

136 binSearch True 3 (1.0, 1.05)

137 (\n ->

138 do v <- newIORef 0

139 forM_ [1..n] $ \i -> do

140 old <- readIORef v

141 writeIORef v (old+i))

142 -}