HLearn.History

[tonyday567]

I was thinking of tackling a FIXME surrounding incorporation of History.Timing into the History modue. Here's a few initial thoughts and ideas.

API & HistoryT

report is the main (and only) access to the History machinery.

I'd like to include an ability to be selective in what's timed, and quickly turn an IO chunk say, into a History chunk (by adding report to a line and liftIOing other stuff). Say we have:

sumOrig = do
 let s1 = P.foldr (P.+) 0 [1..10000]
 threadDelay 1000000
 return s1

becoming

liftIO' = History . liftIO

sumHist = do
 s1 <- report $ P.foldr (P.+) 0 [1..10000]
 liftIO' $ threadDelay 1000000
 return s1

Which all seems doable and very cool. At this point, however, I jump straight to thinking about a HistoryT, so the report api can handle an IO a etc, but I lack a MonadIO to throw in there.

So question number 1 is whether to give up on a HistoryT given no MonadIO etc, or whether that would be a simple compatability patch.

Relationship to Criterion

I do a lot of benchmarking and the guts of criterion has the wrong types for stuff I often want to do (quickly annotate computations with debugging and timing information, rather than do statistical analytics of multiple runs without any continuation that criterion is based on)

I often pick apart times into GC and Mutation via some criterion functionality. I also think it would benefit the History monad if you could start and stop the timing within a report chunk, but still be able to report timings at higher levels. The report API could morph to something like this:

report "all of it" $ do
 s1 <- report "the slow bit" $ P.foldr (P.+) 0 [1..10000]
 liftIO' $ threadDelay 1000000
 return s1

SubHask versus Control.Monad

Being able to benchmark in the middle of a computation is a nice goal in the broader Haskell toolkit (there might be stuff out there that already does this, but I haven't come across it).
I'm unsure whether to head for a more general History (or HistoryT) based on Control.Monad or stick to SubHask.

My use case, however, is pretty centered on HLearn, so targetting a boiler-plate monad may not get the job done.

Very generally, to what extent can normal monads play nice with subhask?

Reportable versus Optimizable

History.Timing (one off reporting) is starting to drift away from the idea of reporting on optimization (or other) loopings. There might be a case for clear separation of looping constructs like stopping criteria versus straight reporting constructs (like when to report timings).
I haven't dug into how History is used in a looping context yet.

I'm sure there's lots of other issues I haven't thought of yet.

Tony

[mikeizbicki]

Thanks again for the detailed comments! I'll try to respond to everything point-by-point, but if I miss something let me know.

API & HistoryT

I really like the idea of a HistoryT monad and having History = HistoryT Id. I think this shouldn't be too hard to do and I'd be open to a pull request for this.

I've thought about moving this monad into a separate library to make it more general purpose. As a separate library, this wouldn't depend on subhask at all, which I think would make it much easier to adopt. I haven't done this yet because I think it would slow down my development time a bit. But if you think it'd be useful I'd be up for it. Can you say a bit more about your use case?

Relationship to Criterion

Totally agree. That's been one of my wishlist features for a while now. Another feature I wanted added is to measure perf timing events like cache misses and branch mispredicts that happen during a reporting period. I just haven't had a chance to do this yet.

SubHask

One of my goals with subhask is to make all instances of Control.Monad.Monad automatically an instance of SubHask.Monad.Monad. There's already some template haskell code that works for most monads, and it works for the History monad just fine. That's one of the reasons that moving the history monad to a separate library wouldn't be too big a deal.

I haven't yet implemented anything related to monad transformers in subhask. The reason is I haven't thought enough about the consequences of having a monad in one category transform a monad in another category. This shouldn't be an obstacle to making HistoryT though since it'll (at least at this point) on being transforming monads in Hask.

Reportable versus Optimizable

I don't think there should be any issues when using History on non-looping things. I've done some simple tests that way, although I don't think any of them made it into the repo.

The Optimizable constraint should really be called Reportable since it's not just for optimization any more.

---

Now to address a point you didn't bring up. There's an ugly side to the History monad right now in that it makes type signatures a pain. See the type signature:

fminunc :: (Optimizable a, OrdField a) => (a -> a) -> a

in the Univariate.hs file.

I want to get the Optimizable a constraint removed from the type signature. It's not needed when the History monad is evaluated using the evalHistory function. Last time I thought about this was when using ghc 7.8, so there might be some new features that would let me do this, but I haven't looked into it in a while.

[tonyday567]

My use case for History is pretty much yours, lol. See https://github.com/tonyday567/digit-recognizer/blob/master/testing/BenchKnn.hs#L208. I'd like to replace all the time and timeIOs with report and reportIOs (or similar), and include the info wrapped up in Criterion.Extended.

wrt the ugly side, that sig is due to infoType. If you gave up on automatically using the type as the report collection label, and accepted a hard coded label (of type s) eg

report :: s -> a -> History_ s a

or you could go the whole hog, and use a String as the label as beginFunction does, making it:

newtype History a = History (ReaderT DisplayFunction (StateT (String, [Report]) IO) a
report :: String -> a -> History a

or even

newtype (MonadIO m) => HistoryT m a = HistoryT (ReaderT DisplayFunction (StateT (String, [Report] m) a

[mikeizbicki]

I went back and looked at the History monad a bit more today. I managed to refactor out the Optimization constraint from all the type signatures. I'm quite a bit happier with how it looks now. I've just uploaded the changes to GitHub: https://github.com/mikeizbicki/HLearn/blob/ghc7.10/src/HLearn/Optimization/Univariate.hs

There's still a few odd constraints on some of the functions. I think I can remove them too, but I'm off to bed now :)

[tonyday567]

Looking at how to integrate History.Timing with History, I ran into a brick wall.

The problem that I'm trying to solve is that the Report/Measure thing is related to the context used in the step. So Report as written matches CountInfo as written (and also goes with the hardcoded getCPUTime in runHistory for example).
My brain then finds it difficult to abstract these relationships for the stepDisplayFunction sig, forall a. cxt a => Report -> cxt -> a -> (cxt, IO ()) given the commonalities between Report and cxt.

The ideal would be for Report/Context to be built up using disparate effects. The components look like pre-computation data gathering (eg getCPUTime), post-computation compute, a running total and display of the data. I came up with this data type:

data Measure = forall a b. (Monoid a, Monoid b) => Measure
    { measure :: b
    , prestep :: IO a
    , poststep :: a -> b -> IO b
    , display :: b -> String
    }

An experiment using this is here: https://github.com/tonyday567/HLearn/blob/ghc7.10dev/src/HLearn/History/Measure.hs

But which turned out to be a deadend - it's hard to use with the types being swallowed.

[mikeizbicki]

This change shouldn't require adding a new Measure type or really interacting with the Report type at all.

We can create two new functions that are analogues of the time and timeIO functions like:

withMsg :: (cxt String, NFData a) => String -> a -> History_ cxt s a
withMsg msg a = withMsgIO msg (return a)

withMsgIO :: (cxt String, NFData a) => String -> IO a -> History_ cxt s a
withMsgIO msg ioa = do
    a <- History $ liftIO ioa
    report $ deepseq a $ msg
    return a

I haven't actually tested these functions, but I think they should work.

Then the next step is to write a DisplayFunction_ that processes the History monad in a way that recreates the output that timeIO did. I think this should only require writing the stepDisplayFunction in a way that doesn't use the s state variable. In particular, the specialized type signature would read:

stepDisplayFunction  :: forall a. cxt a => Report -> () -> a -> ((), IO ())

Then in order to get the message printed to the screen, stepDisplayFunction will run show on the input variable of type a, requiring cxt ~ Show.

Does that explanation make sense?

[tonyday567]

I think so - will give it a try! It won't give you real time information though.

The part I left out was that I'd like (personally) to collect GC information that you can get from GHC.Stats, so I wanted to write:

import GHC.Stats

data Report = Report
    { cpuTimeStart  :: !CPUTime
    , cpuTimeDiff   :: !CPUTime
    , gcStatsStart   :: !GCStats
    , gcStatsDiff    :: !GCStats
    , numReports    :: {-#UNPACK#-}!Int
    , reportLevel   :: {-#UNPACK#-}!Int
    }
    deriving Show

but that would then involve a rewrite of runHistory and report. So I was thinking of how to generalise (adding cache misses etc, without having to rewrite all the time).

[mikeizbicki]

Ahh... I see. That's actually a really interesting idea... I'll have to start thinking about that too.

[tonyday567]

I did some testing of rdtsc and it has outstanding metrics, compared with getCPUTime and getCurrentTime. It has to be the future of high performance regressions.

https://github.com/tonyday567/perf

[mikeizbicki]

That looks super nice!

After a quick look through, this might be using the same API I was hoping to use to measure cache performance.

[tonyday567]

I don't think you're going to be that lucky, sorry.
You're looking for the rdpmc instruction. It's a lot more complicated and I haven't seen a clean *.c for this - it needs drivers and all of that guff. The linux perf tool is only a command line thing, and the haskell wrappers out there read the data file that this command creates.