In the nightly run before and after 7489112 there are wildly varying runtimes for some tests (of course, there will always be variation, but here an order of magnitude is involved).
On the four nightly-marked tests for Reach.Deadlock tasks:
- from 140436ms to 330499ms
- from 4165913ms to 5886167ms
- from 517000ms to 731504ms
- from 13292950ms to 3688968ms
There is also a small impact on the nightly-marked Reach.Reach test, but it seems negligible (in this particular run).
Of the above times, the first few go up, the last one goes down drastically, by more than two hours. And indeed the overall nightly run went from about 4 hours to about 2 hours overall. It doesn't seem to be a fluke, since there is a pattern in the nightly runs before that day already. The overall timing went from under 2 hours to about 4 hours when 2c88b54 was merged and stayed there until 7489112 was merged. In fact, the short-circuiting
|
if requiredFusableTransitionsConsuming == 0 && requiredFusableTransitionsProducing == 0 |
|
then return ([], BM.empty, BM.empty) |
there was introduced precisely because I wanted to avoid some unnecessary overhead in
Reach.Reach tasks and in
Reach.Deadlock tasks with
fusableTransitionsConsumingAreExactly and
fusableTransitionsProducingAreExactly each being
Nothing or
Just 0.
But I hadn't expected it to have that much of an impact, really, because ultimately all that is saved seems to boil down to these two shuffleM calls:
|
shuffledTransitions <- shuffleM allTransitions |
|
shuffledPlaces <- shuffleM allPlaces |
That begs the question for further analysis whether the effect on runtime is reproducible.
Moreover, it calls into question the liberal use of shuffleM throughout the code base. In particular when it is used "just" to get a few random elements from a list (as is the case above) instead of really wanting to preserve the whole permuted list. Optimization for that sampling case could improve runtime not only for the special cases above but more generally (also when fusableTransitionsConsumingAreExactly and fusableTransitionsProducingAreExactly are set to positive numbers, and also in other code places).
That might involve switching (in certain places) to another algorithm, e.g., using sample_ from list-shuffle instead of shuffleM from random-shuffle, and also having to use MonadSplit in order to have a generator at hand to pass to sample_.
In the nightly run before and after 7489112 there are wildly varying runtimes for some tests (of course, there will always be variation, but here an order of magnitude is involved).
On the four
nightly-marked tests forReach.Deadlocktasks:There is also a small impact on the
nightly-markedReach.Reachtest, but it seems negligible (in this particular run).Of the above times, the first few go up, the last one goes down drastically, by more than two hours. And indeed the overall nightly run went from about 4 hours to about 2 hours overall. It doesn't seem to be a fluke, since there is a pattern in the nightly runs before that day already. The overall timing went from under 2 hours to about 4 hours when 2c88b54 was merged and stayed there until 7489112 was merged. In fact, the short-circuiting
modelling-tasks/src/Modelling/PetriNet/Reach/Roll.hs
Lines 201 to 202 in 7489112
Reach.Reachtasks and inReach.Deadlocktasks withfusableTransitionsConsumingAreExactlyandfusableTransitionsProducingAreExactlyeach beingNothingorJust 0.But I hadn't expected it to have that much of an impact, really, because ultimately all that is saved seems to boil down to these two
shuffleMcalls:modelling-tasks/src/Modelling/PetriNet/Reach/Roll.hs
Lines 154 to 155 in 7489112
That begs the question for further analysis whether the effect on runtime is reproducible.
Moreover, it calls into question the liberal use of
shuffleMthroughout the code base. In particular when it is used "just" to get a few random elements from a list (as is the case above) instead of really wanting to preserve the whole permuted list. Optimization for that sampling case could improve runtime not only for the special cases above but more generally (also whenfusableTransitionsConsumingAreExactlyandfusableTransitionsProducingAreExactlyare set to positive numbers, and also in other code places).That might involve switching (in certain places) to another algorithm, e.g., using
sample_fromlist-shuffleinstead ofshuffleMfromrandom-shuffle, and also having to useMonadSplitin order to have a generator at hand to pass tosample_.