[m-rev.] for review: faster merging of varsets

[Zoltan Somogyi]

On Sun, 27 Jan 2019 12:14:28 +0000 (UTC), Julien Fischer <jfischer at opturion.com> wrote:
> Here's an initial set of benchmarks on my machine; I've repeated each
> benchmark 200 times.  The numbers in parenthesis give the numbers in
> the heuristic in varset.use_simple_loop

Thank you for that. That is a lot of data points; I hope you got them using
a script, rather than manual editing :-)

Did you modify my benchmark module to include small varsets? If not, then
I don't think most of those data points are meaningfully different from each other.
Since my original benchmark module had no varsets whose size was between 0 and 100
elements, the test NumAllocatedB < 5 would succeed for exactly the same merges
as NumAllocated < 20.

> rotd-2019-01-21: 1132.65
> no-simple-loop: 134.50

It seems the speedup on your machine was even bigger than on mine.
It also seems that all of the tested heuristics for falling back to the old
simple loop improve things still further, though (for the reason given above)
I don't this tells us the optimal values of the heuristic parameters.
However, it does seem that the values I guessed (5,16) are pretty good.

Zoltan.