future(s) patmat analysis performance

[Adriaan Moors]

Last night I tried to reduce the time it takes to analyze matches for exhaustiveness and reachability using futures.

I'm using one future for each analysis of each match (thus, two futures per match),

and only for the part that doesn't interact with the rest of the compiler

(but -Ystatistics indicate that's a significant part of the time spent).

https://github.com/adriaanm/scala/commit/84e8382d?w=1

Unfortunately, compile times did not change ("significantly") on a 4-core i7. 

It's hard to know for sure, of course, since benchmarking this properly is too time consuming,

so I was wondering whether I am using Future wrong.

thanks!

adriaan

[Aleksandar Prokopec]

Hi,

Blocking until the future value becomes available makes sense if the amount of work you do with the future is relatively high.

How long does an asynchronous computation started by `future` last? Each of these futures seems to call DPLL, does that mean that these computations should last relatively long, but could you measure this?

If for some reachability inspections in turns out that they're relatively short, maybe you could heuristically spawn of a future, depending on the length of the formula.

Alex

[Aleksandar Prokopec]

Another option that I see is batching several formulas together and then running DPLL within a future for them together.

[Adriaan Moors]

I see, good point! That sounds feasible, but I think it would require too much of a rewrite to do right now.

[Miguel Garcia]

I was forgetting to mention in my previous reply [1], when to populate the job queue in (b). As with the pool of worker threads, it's best to set them up once (a sequential part that shouldn't take long) instead of tearing them down repeatedly. Once the queue is full, let the workers remove jobs.

For parallel DCE, all compilation units are traversed during which the job queue is populated. After that, the rest of the phase is just the workers' show. Source code in DeadCodeElimination.scala [2].


[1] https://groups.google.com/d/msg/scala-internals/tQt01aCMMD4/2-tJzE67KhMJ

[2] https://github.com/magarciaEPFL/scala/blob/parallelDCE/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/