Re: Benchmark suite...

[Scott A Crosby <crosby at qwes dot math dot cmu dot edu>]

On Tue, 20 Oct 1998, Jan Hubicka wrote:

> After a week spent by tunning my patch I decided that I really need some testsuite.
> It is quite time consuming to test changes at real programs, since lots of thinks
> needs to be compiled. I would like to have some testsuite to verify my changes.
> So I've put together few programs and made a script to compile/test them.

There are two types of benchmarks we can run on the compiler on.. 

First, the benchmarkes used to study generated code. These benchmarks
should be small and simple. They are intended to find places where the
compiler is creating ineffecient code.

Second, the benchmarks used to study a whole system. These need to be big
and complicated, to emulate real-life applications. Finding out why they
slow down between two compilers is very difficult because of the huge
size. We might want a few of these for completeness, but they aren't all
that useful for measuring compilers generated-code performance. 


I believe that we want to use only the latter types of benchmark programs,
simple benchmarks, which test function-calling, CSE, eliminating unused
code, branch-prediction, deducing the range of a variable to eliminate
superflouis comparisons....  In many ways, we want this to be the
equivalent of the test suite, a lot of short programs which don't break
the compiler, but do aid in measuring the resultant code. So, any given
optimization can be judged based on how it affects the micro-benchmarks in
the suite.... Ideally, each one should be a single function, and only a
few dozen lines of code.

Some of the tests have to be lengthy and complicated, to help gauge
things like register-spilling, and other similar optimizations that are
only used in complicated code..


Thus, some of the LISP suites might be fairly good.. (TAK would be ideal
for measuring function-call overhead.) I would suggest using the Gabriel
benchmarks
(http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/bench/gabriel/0.html)

> My goal is not to make comparsion benchmark for various compilers, so I am not doing any overall
> results. It is targeted only for developpers who want to see behaviour of their changes.
> Thats why I want to make it consisting mainly of simple tests, where you may browse the assembly
> result and see whats is going wrong and so on.
> 
> So far I've implemented just very few tests mostly grabbed from my programs - Mset calcualtion
> loop, quicksort and recursive hanoi. Jeffrey pointed out that complex tests are also neccesary
> so I've added also mathing algorithm from XaoS and palette approximation from Allegro.
> I would love to have more tests. Both simple loops wich needs some tricks to optimize
> and complex code (like complression algorithm or whatever else)

I think that this is absolutely the wrong idea. We want to have a test
suite that, instead of detecting bugs, tests how well the optimizer is
doing.

How does quicksort help with that? What is it supposed to test?
(function-invocation speed? If so, TAK would be better, it is simpler and
all function invocation.)

Here is my contribution of a couple benchmarks in this philosphy:

-------------------------------------------------------------------

// Give it an array of 16 integers
// It performs 16 shuffles (copies from one array index to another) and exits. 

shuffle16(int *a) {
	a[10] = a[8];
	a[4]  = a[10];
..
..  more lines ..
..
        a[12] = a[4]
}


Similarily, make a shuffle32(), shuffle64(), shuffle128(), ...

Now, each of these functions should be optimized down to (at most) 16
loads and 16 stores, because the compiler should track the loads&stores
throughout the function, and output equivalent code.. Incidently, as a
regression test, if an array of volatiles were passed, it shouldn't
optimize the operations down this way.


Another micro-benchmark to measure how well the compiler performs register
assignment:

// Test register assignment, passing reg_assignXX an array of XX values.
reg_assign1_8(int *a, int *b)
	b[0] = 1*a[1] + 2*a[2] + 3*a[3] +  4*a[4] .... 7*a[7];
	b[1] = 0*a[0] + 1*a[2] + 2*a[3] .... 6*a[7];
..
..
        b[7] =  0*a[0] + ... + 1*a[7];
}

Here, the constants in the right hand sides were chosen so that a simple
CSE would not work well on them, so this would test how well the compiler
performs register assignment.. (It could also test a much more advanced
CSE that could simplify this.) Again, a list of functons reg_assign1_16(),
reg_assign1_32(), are created...

In a similar vein, create several series of the above functions
reg_assign_Y_XX where (for each Y) the constants are chosen differently to
make even a subtle CSE have difficulty in performing the optimization.
(and spreading the zero's around differently.)


Finally, here is the tak benchmark ported to C

int tak_ (int x, int y, int z)
 {
   if (y >= z)
	return z;
   else
      return tak(
		tak(x-1,y,z),
		tak(y-1,z,x),
		tak(z-1,x,y));
}

void tak() {
	return tak(18,12,6);
}
  

Scott Crosby