Feature proposal: Order test bundles based on estimated execution times

[ravimandala]

Issue: The execution of test bundles by the simulators is observed to be inefficient more often than not. Towards the end of test execution, one or more simulators may be busy while the rest of them are idle with no more test bundles to execute. This issue is very similar to page fragmentation in memory allocation and multi-processor job scheduling inefficiencies.

Proposal: If a statistical model to estimate the execution times of the bundles is at Bluepill's disposal, it should be able to avoid such fragmentation by employing heuristic approaches.

Typical solution: Bluepill should support a config named input-dir where it looks for a specific file name (Eg. TEST-TimeEstimates.json) or should support a config like input-file-path. The file can have the best-estimated execution times at target/test case level which could be derived from a statistical model based on past execution times or some other means (Eg. an API service) a Bluepill customer might see fit. Those time estimates can then be used to split (as and when needed and appropriate) and/or order the test bundles in non-decreasing order which is a decent heuristic to avoid this fragmentation and reduce the long pole.

\cc @ob

[ob]

I like this idea. We already have the test timings when we generate the tracing-profile.json file. How about we add a new flag called --test-time-estimates=<json_file> that can take a JSON formatted file with the test estimates. Bluepill would then use these timings for packing the tests and at the end of the test run generate an updated file with the same name that can be fed to the next run.

An open question would be how to update the estimated timings with the actual timings... and I think that would determine what information besides the timings we need to keep in those files. Any ideas what statistic to use?

[ravimandala]

If we go by a simple average, then the additional info we need along with the current average is how many instances produced that average. If it is from n instances, then with new execution time the new average would be (current_average * n + new_execution_time)/(n+1).

Alternatively, if we want to go by percentiles (50th or 90th %ile) moving percentile algorithms like this one can be used.

[oliverhu]

+1 to the idea & proposal from Oscar.

I am not sure what your question is about tho @ob , are you talking about handling the update process in bluepill or in the build process.
I feel it would be like after each run Bluepill will generate a timing file (either reuse tracing-profile.json or a new one) local, the application build process would pick that up and commit to its git (like a cron job that kicks in every day to update the timing info).

[ob]

Ah, good point... I was thinking about having Bluepill keep the statistics but it doesn't need to. All it needs to do is use the input timings for packing and generate the actual timings. Then let the CI do with it whatever it wants.

[ob]

Fixed in #342

[ravimandala]

It's a good idea that Bluepill should generate the output file that it can use for estimates in the next run. I opened this issue #351 to discuss different ways to do that and come up with the best option.