From being greedy to being smart: How Tomato got faster and leaner on large models

By Patryk Chamuczyński, Testify

Tomato is Testify’s open-source test generator. You describe what you want to test as a model, with its parameters, their choices and the constraints between them, and Tomato generates the test cases and test data from it, at the volume and coverage you ask for.

This post is about the part of Tomato that does the generating. The default algorithm has changed from a greedy one to IPOG (In-Parameter-Order-General). Below we explain why the old algorithm was no longer enough, how the two work, how they compare on large models, and when the greedy algorithm is still the better choice.

Why greedy was no longer enough

Tomato builds an n-wise test suite from a model: a small set of tests that still covers the combinations that matter. The web app is backed by a free Python command-line client, the testomaton package (pip3 install testomaton). For a long time test suite was produced by a greedy algorithm, one test at a time. We wanted each finished test to go straight to the output, so a test runner could already be executing the first lines while the rest of the suite was still being generated.

For the models we started with, that was enough. A handful of parameters, a few choices each, and the suite came out quickly.

It stopped being enough when a model had to be large. A Norwegian taxpayer is a good example. A realistic model needs dozens of parameters: type of income, municipality, tax class, marital status, children, property, employment, and the deductions that apply. Each of them has several choices. At some point pairwise coverage is not enough either. Some faults only show up when three or more values line up, so we had to generate at a higher strength. Generating a suite at that strength, from a model this large, became time-consuming and resource-hungry. At some point, «good enough» stopped being good enough, and we had to move forward.

IPOG (In-Parameter-Order-General) was a natural candidate to try. Tomato already had the basic framework the algorithm needs, so adapting it was quite straightforward. Generation is faster, it uses much less memory, and the suite is usually smaller. There are still cases where the greedy algorithm is preferable, so we kept it. For most realistic models IPOG simply wins, and it is now the default.

Greedy algorithm

The greedy algorithm starts from the full list of combinations it has to cover: every valid group of n parameter values. A combination that breaks a constraint never enters the list.

It then builds one test at a time. One uncovered combination is taken as the seed of the next line, and the parameters it left empty are filled in, starting with the ones that have the most choices. For each of them the algorithm tries the possible values and keeps the one that covers the most combinations still on the list and that the constraints allow. The finished line is written out, everything it covered is removed from the list, and the next line starts from what remains. This continues until the coverage you asked for is reached.

Two properties follow from building the suite this way. Tests come out one by one, so a runner can execute the first lines while later ones are still being generated. And the early lines are the dense ones. Each line is chosen to cover as much of what is left as it can, so stopping at 80% or 50% drops the lines that would only have covered the last, sparse combinations. The suite stays close to the coverage you asked for, which is the case where this algorithm still tends to produce fewer tests than IPOG.

The algorithm is still in the tool. It is used by default if the requested coverage is not 100%. In other cases, pass --greedy to use it:

tomato model.yaml --greedy

--demo-level shows it working. Under the tests already written out, you see the line currently being filled in and how many combinations are still uncovered.

IPOG algorithm

IPOG builds the suite one parameter at a time, starting with the parameters that have the most choices. The first parameters form the initial tests. Each later parameter is then added to the tests that already exist.

Adding a parameter has two steps. In the horizontal growth, every existing test is extended with the value that covers the most combinations still uncovered, provided the constraints allow it. A value that covers nothing is left empty, so a later step can use that position. In the vertical growth, each combination that is still open is placed into an existing test that has room for it, or a new test is added. When every parameter is in place, the empty positions are filled with any value the constraints allow.

Only the combinations that involve the parameter being added are kept in memory. The full list never has to exist at once, which is why a large model, and a strength above pairwise, stays within reach. Generation is faster, and at full coverage the suite is usually smaller.

IPOG is used by default when the requested coverage is 100%. In other cases, pass --ipog to use it:

tomato model.yaml --coverage 80 --ipog

--demo-level shows the whole suite, because a test can still change until the last parameter is added.

Comparison

We ran both algorithms at full coverage, at strength 2, 3 and 4, on models from a handful of parameters up to a hundred. Each figure is one run. A run still going after 10 minutes was stopped, and so was a run that passed 6 GB. On a small model both finish in well under a second. The table is the point where they separate.

The model is written in pairwise notation. The base is the number of choices and the exponent is the number of parameters, so 2¹⁰×3⁸ is 10 parameters with 2 choices and 8 parameters with 3 choices.

Model	Strength	Greedy	IPOG	Benefit of IPOG
2¹⁰⁰	3	71 s, 1.2 GB, 55 tests	59 s, 69 MB, 48 tests	about 17 times less memory
5⁵⁰	3	5.2 min, 1.3 GB, 684 tests	2.5 min, 104 MB, 627 tests	about twice as fast, about 12 times less memory
5²⁰	4	6.2 min, 890 MB, 3168 tests	2.7 min, 185 MB, 3022 tests	less than half the time, about 5 times less memory
10²⁰	3	173 s, 352 MB, 3544 tests	91 s, 83 MB, 3463 tests	about half the time, about 4 times less memory
4¹⁵×3¹⁷×2²⁹	3	44 s, 487 MB, 224 tests	31 s, 46 MB, 199 tests	about 10 times less memory
4¹×3³⁹×2³⁵	3	69 s, 820 MB, 145 tests	54 s, 55 MB, 129 tests	about 15 times less memory
10²⁰	4	stopped, over 6 GB	still running, 136 MB	stays within memory
2¹⁰⁰	4	stopped, over 6 GB	still running, 670 MB	stays within memory

IPOG keeps only the combinations of the parameter it is adding, so a large model stays in the hundreds of megabytes where the greedy algorithm climbs into gigabytes. Where both finish, IPOG also produces a slightly smaller suite, in every row above: 48 tests against 55 for 2¹⁰⁰ at strength 3, 3463 against 3544 for 10²⁰ at strength 3, 3022 against 3168 for 5²⁰ at strength 4. At strength 4 on the largest models the greedy algorithm runs out of memory, and IPOG is still going.

Conclusion

Tomato got better, and nothing was given up to get there. Full coverage is faster, it uses much less memory, and the result suite is smaller. The greedy algorithm is still there for the cases where it remains the better choice.

The online version limits how long a generation may run and how much memory it may use. The biggest models are still too hard at a higher strength, and they run into that limit. The command-line client can still take them on, if you give it enough time and resources.