# Testing all combinations

I need to do some performance measurements inside my application. I want to measure, change some parameters, measure again. There are different algorithms I want to test, and there are various parameters which interact with each other in that the total performance depends on all of the parameters (but the parameters themselves don't influence each other. e.g. if I set x to 5, it will always stay 5 and changing some other parameter won't change x).

I think the total number of combinations is quite high, at least enough so that I don't want to manually change everything and test out each possibility by hand.

I'm looking for a piece of lightweight piece of software architecture (I dare say a design pattern) that basically enables me to define a set parameter types relevant to an algorithm, the possible values of those types, and that piece of code should then run through all combinations of those types and their values, for each one doing the required stuff (calling some functions to change values, etc.) and then executing the algorithm.

Example: An algorithm depends on values x, y and z. x can be either 0 or 1, y can be "hello" or "goodbye", and z can be in the range [0,100]. The solution I'm looking for starts with [0,"hello",0], calls some functions to set the values of those variables, lets the profiling run for some time, then changes to [0,"hello",1], repeat, [0,"hello",2]... etc.

This is probably something that people have needed to solve before. How do I solve this elegantly?

You can do this in (at least) two ways.

One is simply to have a vector with the cardinalities of your parameters. So since your parameter array is (slightly edited to get unique numbers):

``````[
[ 0, 1, -1 ],
[ 'hello', 'goodbye' ],
[ 0 .. 100 ],
]
``````

the cardinalities are [ 3, 2, 101 ]. This gives a Cartesian product of 3*2*101 = 606 combinations. Given any number from 0 to 605 inclusive, its remainder modulo 3 is the index of the parameter in the first option array, then modulo 2 again for the second, and modulo 101 for the third. E.g. 137:

137 modulo 3 is 2, so first parameter is -1. 137 integer-divided-by 3 is 45, 45 modulo 2 is 1, so second parameter is "goodbye". 45 i.d.b. 2 is 22, so third parameter is 22.

This allows for mapping the whole configuration to a single number and viceversa. Then you can have a function or method that will set the configuration from a number, given the arrays of possible values.

You can now just try all the values in sequence. This is just a brute force approach.

Another possibility is to assume that the performance function f(x, y, z) is reasonably continuous, i.e., the change in performances is proportional to the change of any given parameter from its i-th to i+j-th value; the more you change, the more performances will vary.

If this holds true, there are several options to find the performance maximum efficiently, without examining all the possible values. For example, you generate a number at random from 0 to (here) 605, thus obtaining an initial configuration (x, y, z). You can now increase or decrease any of the three parameters, which gives you at most twenty-seven sets of values to investigate (each parameter can increase by one, decrease by one or stay the same, which is three possibilities; and three are the parameters, so you raise the number of possibilities by the number of parameters and get 3^3 or 27). Run the performance test for each of these sets. The best combination will be your new starting point. Repeat (you will want to cache results for the last runs, since several sets would otherwise be examined repeatedly).

When you have many possible values for each parameter, this method allows for examining comparatively very few of them. If f() is "reasonably" well-behaved, this method will "walk" the parameter space following the line of steepest ascent, rapidly converging towards the best combination. You may want to use techniques such as annealing or restarting from a very different initial position to ensure that you do not get "stuck" in a local maximum.

• Oh, thanks, this answer hits the nail in the head perfectly. Quite a number light bulbs lit up in my brain. By the way, the method you describe in the second half is hill climbing, isn't it? edit: Second by the way, I'm not trying to find maximum performance, since it's mostly about tradeoffs between quality and tradeoffs, and I'd like to discover how a certain parameter changes the performance. But that advice is worth gold anyways, will certainly be useful to someone reading this answer. – heishe Feb 11 '14 at 1:25
• I think you dropped 1: `[ 3, 2, 101 ]. This gives 2*2*101 = 404` - that should be a 3, resulting in 606, should it not? – Izkata Feb 11 '14 at 4:51
• Yes, sorry. I had started with the same parameters as the OP, but that gave me multiplicities of 2 and 2, and I thought it to be confusing. So I added an extra parameter to get 3. And forgot to update the numbers. Fixed -- and thanks! – LSerni Feb 11 '14 at 10:20
• Nice solution, but won't handle more than 2 billion combinations. Try Chase's Twiddle algorithm for really large problems. – david.pfx Feb 11 '14 at 11:10

There is no need to reinvent the wheel - use the functionality of your favorite unit testing framework. For example, Nunit provides a "combinatorial" attribute (and some other helpful attributes like "sequential") which does exactly what you are looking for. For JUnit, you find add-ons like "jcombinatorial". I guess there are similar functionalities for other xUnit frameworks.

run through all combinations of those types and their values, for each one doing the required stuff (calling some functions to change values, etc.) and then executing the algorithm.

That sounds like Cartesian Product to me. Many languages have library to calculate the Cartesian Product of a list of lists, e.g python itertools.product().

@Iserni had a very good point, in most cases, the performance of algorithms aren't completely random. There are often ways to avoid doing exhaustive search, maybe at the cost of possibly not finding the most optimal solution (i.e. a heuristics).

This is probably something that people have needed to solve before.

Yes, indeed.

How do I solve this elegantly?

I would use Prolog, because it fits perfectly in this case. Prolog predicates are made of different clauses; let's define the `x/1` predicate (`x/1` means functor `x` with arity 1, a.k.a. the number of arguments) :

``````x(-1).
x(0).
x(1).
``````

We defined 3 alternative clauses for `x/1` (order of declaration matters). Then, any call to `x(V)` with `V` a free variable will leave "choice points" that are visited upon backtrack. Interactively:

``````[eclipse]: x(V).

V = -1
Yes (0.00s cpu, solution 1, maybe more) ? ;

V = 0
Yes (0.00s cpu, solution 2, maybe more) ? ;

V = 1
Yes (0.00s cpu, solution 3)
``````

We do not necessarily need to have two clauses, though:

``````y(Y) :- Y = "hello"; Y = "goodbye".
``````

Here, the `;` disjunction operator separates two alternative unifications of variable `V` with different strings*. Let's define also a `z/1` predicate, using the between/4 built-in auxiliary predicate :

``````z(Result) :- between(0,100,1,Result).
``````

Now, you will need to call a specific test function, which depends heavily on your exact requirements. But here is a sketch of how to call it:

``````run :-
x(X),
y(Y),
z(Z),
test(X,Y,Z),
% failing here will backtrack over other values of X, Y, Z.
fail.

% since the previous clause of the run predicate always fail, we
% add another one that will succeed. It will be tried after all values of
% X, Y and Z have been attempted. Since there is no need to have a body, we
% simply write "run."
run.
``````

The control flow of the program is lead by an implicit backtracking mechanism: basically, in order to see if `run/0` succeeds, we try both clauses, one after the other. In order for the the first clause to succeed, all the goals that are listed must succeed. Goals `x(X)`, `y(Y)` and `z(Z)` bind one of the possible values to free variables X, Y and Z. When we reach the `fail` predicate, which always fails, we must try alternative valuations of the free variables; first, all values for Z are tested, then another for Y and again, all values of Z, until we try all combinations of X, Y and Z. In fact, the first clause of `run/0` can never succeed (but we try anyway, and as a side-effect we call the test with all combination of values). Finally, we end-up trying the other clause of `run/0`, which trivially succeeds.

The `test/3` predicate is where you should define your test. You might want to concatenate all your terms and call an external shell, for example:

``````test(X,Y,Z) :-
join_string(["./test",X,Y,Z]," ",Cmd),
sh(Cmd).
``````

Alernatively, you can talk to another process with sockets or through a stream. This particular example does not handle possible spaces in arguments, so take care.

@Iserni pointed out that you might want to avoid doing an exhaustive search. If you think you need to cut down your search tree according to additional constraints, then you can encode your constraints and cost functions as predicates: this is exactly the kind of problems people solve daily with Prolog.

It isn't python or any other popular scripting language, but I think it is worth trying. After all, if it fails, you can just got back trying another option :-)

(*) Even though the resulting code is short, it could be shorter using only the `member/2` predicate for X and Y (`member(X,[-1,0,1])`, `member(Y,["hello","goodbye"])`).