Benchmark suite...

Benchmark suite...

[Jan Hubicka]

Hi
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.

Because others seemsed to like benchmark suite idea too, I've decided to make something
more definitive, wich should possibly become part of egcs, if it turns out to be usefull.
I've made benchmarking library that uses interupt to stop test, so you might change time
of test as you wish and benchmarking is quite accurate since speed of system calls is not
significant. Also I've made script able to automatically run tests at various data types
(long long, long, short and char), display results and compare them immediately with
saved files. So you might see the changes before test is finished. It is also able to
run specified tests, so when you see some problem in one test, you don't need to run whole
suite etc...

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)

Current version is avalable at my ftp site ftp://ftp.ta.jcu.cz/pub/linux/hubicka/experimental/egcs-bench.tgz

I have only gcc2.7.2.3 and egcc here, but results seems to be very interesting. I will
send comparsions of current snapshot tommorow.

So here is place for yours ideas :) I am open to all suggestions....


PS: here is comparsion of gcc2.7.2 and egcs1.0 at Pentium/120. For every test
the number of loops per socond is printed and comparsion to gcc (100%=no change,
50% = twice as slow, 200% = twice as fast).
First line is signed types, second unsigned. The types are sorted by size, so
for integer test it is:
long long, long, short, char
and for fp it is long double,double,char.

Benchmarks Tue Oct 20 14:36:33 MET DST 1998
egcc -O2 -pipe

Integer tests
Hanoi (tests/hanoi.c)
      836.6337 101%     1270.2970  96%      854.0000 107%     1036.0000 106%
      827.0000 100%     1265.0000  96%      905.0000 110%     1204.9020 116%
Mandelbrot set calculation loop (tests/mset.c)
   764000.0000  92%  2093137.2549  90%  1726732.6733 111%  1666000.0000  99%
   767647.0588  92%  2100990.0990  91%  1826732.6733 116%  1902970.2970 113%
Unrolled mandelbrot set calculation loop (tests/umset.c)
   864000.0000  95%  2406930.6931  91%  2190099.0099 116%  2080198.0198 102%
   856435.6436  96%  2428431.3725  91%  2244554.4554 119%  2310891.0891 113%
Quicksort (tests/qsort.c)
       37.8641  84%       96.0396 128%       67.3267  89%      109.9010 102%
       38.2353  84%       95.0495 125%       67.3267  89%      110.8911  99%
Bressemham line drawing algorithm (tests/bressemham.c)
  6554613.8614 100%  8417720.0000 103%  7112316.8317 101%  8328500.0000  99%
  6642680.0000 102%  8444198.0198 103%  7191702.9703 103%  8421333.3333 100%
Palette approximation (tests/pal.c)
  -------.---- ---%        7.2072 112%  -------.---- ---%  -------.---- ---%
  -------.---- ---%  -------.---- ---%  -------.---- ---%  -------.---- ---%
XaoS internal loop (tests/xaos.c)
  -------.---- ---%      449.0196  91%  -------.---- ---%  -------.---- ---%
  -------.---- ---%  -------.---- ---%  -------.---- ---%  -------.---- ---%

Floating point tests
Mandelbrot set calculation loop (tests/mset.c)
  2853465.3465 107%  2888118.8119 109%  2903960.3960 109%
Unrolled mandelbrot set calculation loop (tests/umset.c)
  6158415.8416 136%  6052475.2475 134%  5890196.0784 131%
Quicksort (tests/qsort.c)
       38.6139  77%       32.6733  66%       28.1553  78%

Complex type tests
Mandelbrot set calculation loop using complex numbers (tests/cmset.c)
  2947000.0000  88%  3051485.1485  92%  2975247.5248  89%
Unrolled mandelbrot set calculation loop using complex numbers (tests/cumset.c)
  5826732.6733  97%  5884158.4158  99%  5399009.9010  91%


Honza

Re: Benchmark suite...

[Jan Hubicka]

> 
> What do you think about the idea of adding gzip/bzip2 to the test suite?
It is one thinks I want to do today. Problem is that gzip itself
is long. I will have to dig out deflate code and make suitable test.
(using whole gzip or whole crafty is IMO bad, because compilation time
would increase significantly)
> It might also be useful to add code that currently isn't optimized as wel
> as it could be by the compiler: e.g. tail-recursive functions.  That could
> provide some incentive to implement better mechanisms in the compiler.
I've done naive implementations of recursive hanoi solver and quicksort,
wich is first of these. Especially quicksort shows VERY interesting behaviour.
Of course I will welcome other code too.
I also want to use dryrstoe benchmark and dig out suitable tests from byte
benchmarks.

Honza
> 
> Bernd

-- 
                       OK. Lets make a signature file.
+-------------------------------------------------------------------------+
|        Jan Hubicka (Jan Hubi\v{c}ka in TeX) hubicka@freesoft.cz         |
|         Czech free software foundation: http://www.freesoft.cz          |
|AA project - the new way for computer graphics - http://www.ta.jcu.cz/aa |
|  homepage: http://www.paru.cas.cz/~hubicka/ , games koules, Xonix, fast  |
|  fractal zoomer XaoS, index of Czech GNU/Linux/UN*X documentation etc.  | 
+-------------------------------------------------------------------------+

Re: Benchmark suite...

[Michael Meissner]

On Wed, Oct 21, 1998 at 01:28:22PM +0200, Jan Hubicka wrote:
> > 
> > What do you think about the idea of adding gzip/bzip2 to the test suite?
> It is one thinks I want to do today. Problem is that gzip itself
> is long. I will have to dig out deflate code and make suitable test.
> (using whole gzip or whole crafty is IMO bad, because compilation time
> would increase significantly)
> > It might also be useful to add code that currently isn't optimized as wel
> > as it could be by the compiler: e.g. tail-recursive functions.  That could
> > provide some incentive to implement better mechanisms in the compiler.
> I've done naive implementations of recursive hanoi solver and quicksort,
> wich is first of these. Especially quicksort shows VERY interesting behaviour.
> Of course I will welcome other code too.
> I also want to use dryrstoe benchmark and dig out suitable tests from byte
> benchmarks.

This will break embedded environments which don't have filesystems or I/O in
the general sense.  If this goes in, please put it under something like make
benchmark, and NOT under make check.

As a side note, hanoi, etc. are part of the Stanford benchmark suite.  It is
generally felt these are useless for today's apps.  In particular, they all fit
in the L1 cache of today's modern chips (hell, spec 92 nearly fits in the L2
cache nowadays).  Also when I was using the benchmark suite 9+ years ago to
tune the 88k compiler, I found that the system clock (which for the 88k was 100
times a second) was too coarse grained to be of any use -- one clock tick
more/less would seriously upset the timing.

-- 
Michael Meissner, Cygnus Solutions (Massachusetts office)
4th floor, 955 Massachusetts Avenue, Cambridge, MA 02139, USA
meissner@cygnus.com,	617-354-5416 (office),	617-354-7161 (fax)

Re: Benchmark suite...

[joel]

On Wed, 21 Oct 1998, Michael Meissner wrote:

> On Wed, Oct 21, 1998 at 01:28:22PM +0200, Jan Hubicka wrote:
> > > 
> > > What do you think about the idea of adding gzip/bzip2 to the test suite?
> > It is one thinks I want to do today. Problem is that gzip itself
> > is long. I will have to dig out deflate code and make suitable test.
> > (using whole gzip or whole crafty is IMO bad, because compilation time
> > would increase significantly)
> > > It might also be useful to add code that currently isn't optimized as wel
> > > as it could be by the compiler: e.g. tail-recursive functions.  That could
> > > provide some incentive to implement better mechanisms in the compiler.
> > I've done naive implementations of recursive hanoi solver and quicksort,
> > wich is first of these. Especially quicksort shows VERY interesting behaviour.
> > Of course I will welcome other code too.
> > I also want to use dryrstoe benchmark and dig out suitable tests from byte
> > benchmarks.
> 
> This will break embedded environments which don't have filesystems or I/O in
> the general sense.  If this goes in, please put it under something like make
> benchmark, and NOT under make check.

Please don't forget that embedded systems generally have a small stack in
comparison to UNIX systems.  On UNIX systems, the stack can grow in
virtual memory.  This doesn't happen on embedded systems. 

I mention this because a heavily recursive benchmark is almost certainly
going to use a lot of stack space and not run on most embedded targets
even if it avoids file IO.

> As a side note, hanoi, etc. are part of the Stanford benchmark suite.  It is
> generally felt these are useless for today's apps.  In particular, they all fit
> in the L1 cache of today's modern chips (hell, spec 92 nearly fits in the L2
> cache nowadays).  Also when I was using the benchmark suite 9+ years ago to
> tune the 88k compiler, I found that the system clock (which for the 88k was 100
> times a second) was too coarse grained to be of any use -- one clock tick
> more/less would seriously upset the timing.

Another technique is to measure how many iterations of something you can
do in a specific period of time (usually at least a second).  This does
not solve the cache issue but does help on the timing issue.

--jel

Re: Benchmark suite...

[Jan Hubicka]

> 
> This will break embedded environments which don't have filesystems or I/O in
> the general sense.  If this goes in, please put it under something like make
> benchmark, and NOT under make check.

I personally also don't think that running benchmarks under make check is
good idea....
In future it should take quite large about of time...
Embedded environments should be problem for benchmarking. I am not very
experienced in this topic but I believe tests should easily get out of
memory or stack space.
Note that I've added bzip into benchmarks, but it generates random file
in memory and then compress it to memory, so it don't do any IO. Measures
just the sorting loops..
> 
> As a side note, hanoi, etc. are part of the Stanford benchmark suite.  It is

I've picked hanoi just because I've played a bit with scheduling of prologues
of functions at i386 so I needed some test that depends heavily at function
calls...
Once I will have enought tests, I will probably remove these that are not
usefull.

> generally felt these are useless for today's apps.  In particular, they all fit
> in the L1 cache of today's modern chips (hell, spec 92 nearly fits in the L2
> cache nowadays).  Also when I was using the benchmark suite 9+ years ago to
> tune the 88k compiler, I found that the system clock (which for the 88k was 100
> times a second) was too coarse grained to be of any use -- one clock tick
> more/less would seriously upset the timing.
When I run tests more times, there is usually not higher differences that 1%,
wich should be OK IMO.

Honza
> 
> -- 
> Michael Meissner, Cygnus Solutions (Massachusetts office)
> 4th floor, 955 Massachusetts Avenue, Cambridge, MA 02139, USA
> meissner@cygnus.com,	617-354-5416 (office),	617-354-7161 (fax)

-- 
                       OK. Lets make a signature file.
+-------------------------------------------------------------------------+
|        Jan Hubicka (Jan Hubi\v{c}ka in TeX) hubicka@freesoft.cz         |
|         Czech free software foundation: http://www.freesoft.cz          |
|AA project - the new way for computer graphics - http://www.ta.jcu.cz/aa |
|  homepage: http://www.paru.cas.cz/~hubicka/ , games koules, Xonix, fast  |
|  fractal zoomer XaoS, index of Czech GNU/Linux/UN*X documentation etc.  | 
+-------------------------------------------------------------------------+

Re: Benchmark suite...

[Scott A Crosby]

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

Re: Benchmark suite...

[Jeroen Dobbelaere]

Hi,

Michael Meissner wrote:
> 
[..]
> cache nowadays).  Also when I was using the benchmark suite 9+ years ago to
> tune the 88k compiler, I found that the system clock (which for the 88k was 100
> times a second) was too coarse grained to be of any use -- one clock tick
> more/less would seriously upset the timing.

Have a look at bench++ (like Klaus-Georg Adams suggested) :
(< http://www.research.att.com/~orost/bench_plus_plus.html >)

it contains timing code to adapt automagically to the speed of your system.

A test in this benchmark consists normally of a
function containing the code to be optimized, and a function
containing 'hand optimized code' to check how effective the optimizer has been.

If you keep the 'hand optimized code' empty, you will measure how many times/second
you can execute your test without the calling overhead.
The test engine adapts itself to the timing granularity of your system
and runs until a certain accuracy has been reached.

Hope this helps,

Greetings,

Jeroen Dobbelaere

Re: Benchmark suite...

[Jan Hubicka]

> 
> 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.

Thats exactly what I am shooting for. I want to create suite where you can
see how for example using leas at inc place behaves and where it is hit
and where miss.
> 
> 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

Thats not my goal. Only purpose for adding more complex ones (like XaoS loop
an so on is that Jeff pointed, that some optimizations (like register allocatin
or gcse possible) don't show itself a much at simple code.
They are in separate file, not targeted for main tunning. Idea was that you
might tune the simple cases and then look if it works well for complex ones
too.
> 
> 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 )

Good idea, I will look at them.

> 
> 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.

The purpose for more complex tests was to stress optimizer. Many optimizations
seems to be good in simple benchmarks (for example like enabling -fschedule-insns
at i386, but loose in more complex tests. I have this complex tests separated
out into "unsorted" category and their only purpose is to show this case.
Because it is hard to write such complex benchmark, complex internal loops 
of some real programs should be good IMO. I am not planning to add more 
of them in near future.
> 
> 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
For function invocatiuon I have recusive hanoi, wich does manly just this
operations...
> all function invocation.)
Quicksort test is just few of lines (not more than page) and it tests mainly
inrenal loop comparing numbers. But agreed, we should have two tests, first
clearing array and second doing the recursion. I will change that.
Interesting is that exactly this benchmark shows quite strange behaviour :)

I've added some other simple loops. Of course I will look closely to tests
and probably remove those which are useless and redundant.
I needed to make enought tests to make it a bit usefull, thats why I am
added more tests that I probably want to include. 
> 
> Here is my contribution of a couple benchmarks in this philosphy:
Thank you very much!
They are very interesting.

Honza

Re: Benchmark suite...

[Joern Rennecke]

> 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...

This does not work.  a and b can be aliased.

Re: Benchmark suite...

[Scott A Crosby]

On Thu, 5 Nov 1998, Joern Rennecke wrote:

> > 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...
> 
> This does not work.  a and b can be aliased.
> 

Whoops.. :-) 

How about:

// Test register assignment, passing reg_assignXX an array of XX values.
reg_assign1_8(int *a) {
	b = a;
	a = a+10;
     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];
}

Re: Benchmark suite...

[Klaus-Georg Adams]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 488 bytes --]

Hi Jan,
have a look at the Bench++ suite at
http://www.research.att.com/~orost/bench_plus_plus.html
It may give you some interesting ideas.

-- kga
-------------------------------------------------------------------------
Klaus-Georg Adams        Email: Klaus-Georg.Adams@chemie.uni-karlsruhe.de
Institut f. Anorg. Chemie, Lehrstuhl II            Tel: 49(0)721 608 3485
Universität Karlsruhe, D-76128 Karlsruhe
-------------------------------------------------------------------------