ordering metrics & single compute [WIP]

[Borda]

Actual situaltion

the actual version takes any set of metrics and computes it almost in random order; if it needs another metric (it is depending on it) it computes it on the fly... this introduces several duplicities, which can be simply fixed and speed up the process

Solution

This change does:

1. order metrics according to min dependences
2. if a metric was already compted because of dependence, it is skipped later

Process

it is a successor of #71 due to changed target branch... see https://github.com/cheind/py-motmetrics/pull/71#issuecomment-577618013

[cheind]

I've had a quick look at your changes. Two questions come into mind: a.) is the number of dependencies are good measure for determining the order of metrics? Let's say metric M dependends on N only, but N itself requires [A..F] to be computed, then len(dep) of M would be just 1, right? b.) do you have benchmarks of some kind that illustrate the improvement?

Best, Chris

On Thu, Jan 23, 2020 at 11:34 AM Jirka Borovec notifications@github.com wrote:

@Borda https://github.com/Borda requested your review on: #72 https://github.com/cheind/py-motmetrics/pull/72 ordering metrics & single compute.

— You are receiving this because your review was requested. Reply to this email directly, view it on GitHub https://github.com/cheind/py-motmetrics/pull/72?email_source=notifications&email_token=AAAJNJOXHDPAMGT3EJP3TUDQ7FXCNA5CNFSM4KKUEMB2YY3PNVWWK3TUL52HS4DFWZEXG43VMVCXMZLOORHG65DJMZUWGYLUNFXW5KTDN5WW2ZLOORPWSZGOWE34S7I#event-2973223293, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAJNJLFCWI3ZKGPC6UXR4LQ7FXCNANCNFSM4KKUEMBQ .

[Borda]

add 1) is really simple and based on a naive assumption that there are some cross dependences

well, I run int on out a day-long tracking with 109k time frames and it seems that there is no speed-up... the times are almost the same, just influenced by what I was doing in parallel with it...

Case 0: 376.627423 Case 2: 375.972485 Case 1: 377.017050 Case 1&2: 378.482628

Anyway I would keep the 2) change as the 1) did not have any impact in terms of speed or readability

[Borda]

Well if it is so, that there are almost no dependencies, to compute it in parallel... I will do it in this PR

[cheind]

@Borda do you have new timings for the parallelization? I'd also like to get Jack's opinion on this PR @jvlmdr.

[Borda]

well, it tuned out that the parallel does not help either, so I am thinking about dropping this pr or just keep the minor formatting updates?

Time sequnetial: 352.22149634361267 Time parallel: 392.333087682724

probably the overhead with duplicating pandas DataFrame is too large...

[jvlmdr]

Thanks @Borda ! I will take a look this weekend

[jvlmdr]

Hey, thanks a lot for the proposals.

First, for the "single compute" contribution: It isn't necessary to check mname in cache in MetricsHost.compute() because that is the first thing that is done in MetricsHost._compute(). I am against adding this check because it means that the same condition is checked in multiple places, making the code more complicated. Maybe it saves one function call, but that is negligible.

Second, for the metric ordering: As you said, it doesn't really matter in what order the metrics are listed because the code will recursively compute all dependencies (exactly once). The only effect that the order could have is to change the depth of the recursion stack. If we wanted to minimize this, we should not sort the metrics by the number of dependencies, but order them such that dependencies appear before the metrics which depend on them (i.e. according to the partial order defined by the dependency DAG). However, since the number of metrics is expected to remain small (< 100), I don't think the complication is justified.

I will look at the multiprocessing contribution soon.

[jvlmdr]

Thanks for trying out a parallel implementation. Yeah, if it's slower than the series computation, then never mind. Maybe you need to be a bit more careful with the dependency analysis and how the cache is passed around in order to obtain a benefit. Feel free to ping us if you are able to make it faster using multiprocessing! If you like, you could measure how much time is spent in each individual metric and then find the critical path (maximum time) through the DAG, and compare this to the simple sum.

[jvlmdr]

Feel free to re-open if there is an update

[Borda]

sorry, there is no option like reopen, just create a new PR...

[jvlmdr]

Oh, sorry! You can just write here and ask us to re-open it instead :)