Improving smoke coverage with graco latin squares

You've probably noticed, if you watch the smoke matrices, that they are
often repetitions and patterns in them, because a failure is often
triggerred by one configuration option.

I've got an idea to improve smoke coverage, using a technique from
statisticians.

A latin square is a N x N square filled with N symbols, so that
a given symbol occurs only once in row or in a column. Example :

1 2 3
2 3 1
3 1 2

A graeco-latin square is the superposition of two orthogonal latin
squares, i.e. where all couples of symbols are distinct. Example :

11 23 32
22 31 13 
33 12 21

The interesting property of graeco-latin squares is that, if you label
rows and columns with symbols as well, every couple of symbols occurs at
most once. Moreover, each symbol is paired exactly once with each symbol
from the other 3 groups of N symbols.

      a    b    c
      |    |    |
      v    v    v
d -> adgj bdhl cdik 
e -> aehk beij cegl 
f -> afil bfgk cfhj 

Let a..l be 12 build options or runtime configuration options (e.g.
-Dusethreads or PERLIO=perlio). By compiling and testing only 9 perl
configurations, you get a pretty good coverage of those 12 options.
For example, if option (a) induces a failure, the smoke matrix will be
    FOO
    FOO
    FOO
if option (h) induces a failure, you'll get
    OFO
    FOO
    OOF
etc.
If only (a+h) induces a failure, you'll get only one 'F'.
The only combinations that aren't tested are ab, ac, bc and the like
(combinations of symbols in the same group.) This doesn't matter
if we choose carefully options (example :
    a -> <nothing>
    b -> -Duse64bitint
    c -> -Duse64bitall )

With a 4x4 square, one could test 16 options in 16 builds.
With a 5x5 square, one could test 20 options in 25 builds.
Smaller build times, more options. Could be a great complement to the
usual smoking matrix.

-- 
http://www.ams.org/new-in-math/cover/latinI1.html
http://www.ams.org/new-in-math/cover/latinII1.html

• Improving smoke coverage with graco latin squares by Rafael Garcia-Suarez
• Re: Improving smoke coverage with graco latin squares by Nicholas Clark