Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #19037 > unrolled thread

Odd benchmark behavior

Back to article view | Back to comp.lang.c

Contents

  Odd benchmark behavior Nils M Holm <news2009@t3x.org> - 2012-03-26 07:51 +0000
    Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-03-26 11:26 +0200
      Re: Odd benchmark behavior "BartC" <bc@freeuk.com> - 2012-03-26 10:40 +0100
        Re: Odd benchmark behavior gwowen <gwowen@gmail.com> - 2012-03-26 03:37 -0700
        Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-03-26 14:13 +0200
      Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-03-26 11:55 +0200
        Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-03-27 09:17 +0200
          Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-03-27 09:20 +0200
            Re: Odd benchmark behavior "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2012-03-27 13:39 -0400
            Re: Odd benchmark behavior pete <pfiland@mindspring.com> - 2012-03-27 21:49 -0500
              Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-04-05 12:18 +0200
                Re: Odd benchmark behavior pete <pfiland@mindspring.com> - 2012-04-05 06:48 -0400
                  Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-04-05 14:12 +0200
                    Re: Odd benchmark behavior pete <pfiland@mindspring.com> - 2012-04-05 09:03 -0400
                      Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-04-05 16:18 +0200
                        Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-04-07 13:26 +0200
                      Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-04-06 09:31 +0200
          Re: Odd benchmark behavior "io_x" <a@b.c.invalid> - 2012-03-27 19:01 +0200
    Re: Odd benchmark behavior "BartC" <bc@freeuk.com> - 2012-03-26 10:36 +0100
      Re: Odd benchmark behavior Nils M Holm <news2009@t3x.org> - 2012-03-26 10:02 +0000
    Re: Odd benchmark behavior Ian Collins <ian-news@hotmail.com> - 2012-03-26 22:58 +1300
    Re: Odd benchmark behavior "BartC" <bc@freeuk.com> - 2012-03-26 15:16 +0100
      Re: Odd benchmark behavior Nils M Holm <news2009@t3x.org> - 2012-03-27 06:20 +0000
        Re: Odd benchmark behavior "BartC" <bc@freeuk.com> - 2012-03-27 10:13 +0100
          Re: Odd benchmark behavior Nils M Holm <news2009@t3x.org> - 2012-03-27 11:59 +0000

Page 2 of 2 — ← Prev page 1 [2]

#19044

On 03/26/12 08:51 PM, Nils M Holm wrote:
> I ran across some odd (as far as I can tell) behavior recently, when
> performing some fun benchmarks. (Yeah, but please bear with me!)
>
> The goal was to find out how bad exactly the code generated by my
> toy compiler is, so I passed the following program to GNU C (GCC),
> Portable C (PCC), and my toy compiler (let's call it SCC):
>
> -----[ p.c ] ---------------------------------------------------
> #include<stdio.h>
>
> #define	MAX 20000
>
> main() {
>          int     i, j, p[MAX], k;
>
>          for (k=0, i=3; k<MAX; i+=2) {
>                  for (j=0; j<k; j++)
>                          if (i % p[j] == 0)
>                                  break;
>                  if (j<  k) continue;
>                  p[k++] = i;
>          }
>          printf("%d\n", p[k-1]);
> }
> ----------------------------------------------------------------
>
> Just a sieve algorithm to calculate the 20,000'th prime number,
> nothing fancy, just some tight loops. Please note that I do NOT
> intend to boast the code quality of SCC here. The code emitted by
> it is in fact abysmally bad. So I was quite surprised to get the
> following run times of the generated programs (median of three
> runs, almost no deviation):
>
> gcc -O2 p.c:	12.39s
> pcc -O p.c:	12.42s
> scc p.c:	12.27s
>
> I can explain the difference between GCC/PCC and SCC by lower
> startup overhead, but shouldn't the better code quality of PCC
> and GCC compensate for this over a run time of 12 seconds?
>
> I am rather puzzled now. Any ideas?

The probably isn't a great deal an optimiser can do with your code.  I 
tried your code (doubling to 40000 to get a meaningful time) and got a 
run time between 3.3 and 3.4 seconds with everything from -g to -O3 
(-fast with Sun cc),

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#19053

"Nils M Holm" <news2009@t3x.org> wrote in message 
news:9talg3F84gU1@mid.individual.net...

>                        if (i % p[j] == 0)

> it is in fact abysmally bad. So I was quite surprised to get the
> following run times of the generated programs (median of three
> runs, almost no deviation):
>
> gcc -O2 p.c: 12.39s
> pcc -O p.c: 12.42s
> scc p.c: 12.27s

> I am rather puzzled now. Any ideas?

> idivl %ecx

I suspect the % operation (which needs a divide) dominates the proceedings. 
I put in an extra dummy % op, and it nearly doubled the runtime (3.5 to 6.6 
seconds).

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#19064

BartC <bc@freeuk.com> wrote:
> I suspect the % operation (which needs a divide) dominates the proceedings. 
> I put in an extra dummy % op, and it nearly doubled the runtime (3.5 to 6.6 
> seconds).

Yes, division is certainly an expensive operation, but I like your
initial guess better (memory access dominates the results). So I
rewrote the program slightly to give the optimizer a chance to do
better register allocation and voila:

scc p2.c:	30s
gcc -O2 p2.c:	15s

Here is the new program (using an even more brute-force algorithm):

----------------------------------------------------------------
#include <stdio.h>

#define	MAX 10000

main() {
	int	i, j, k, n;

	for (k=0, i=3; k<MAX; i+=2) {
		for (j=2; j<i/2; j++)
			if (i % j == 0)
				break;
		if (j < k) continue;
		n = i;
		k++;
	}
	printf("%d\n", n);
}
----------------------------------------------------------------

I also tried a dummy remainder and it indeed doubled the run time
of the SCC-generated executable while the GCC-generated executable
was not affected. I guess that GCC simply removes the dead code.

-- 
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

[toc] | [prev] | [next] | [standalone]

#19068

"Nils M Holm" <news2009@t3x.org> wrote in message 
news:9td4i1FvsgU1@mid.individual.net...
> BartC <bc@freeuk.com> wrote:
>> I suspect the % operation (which needs a divide) dominates the 
>> proceedings.
>> I put in an extra dummy % op, and it nearly doubled the runtime (3.5 to 
>> 6.6
>> seconds).
>
> Yes, division is certainly an expensive operation, but I like your
> initial guess better (memory access dominates the results).

I don't think your program actually used that much memory (only 80KB or so). 
Have a look at the NSIEVE benchmark:

http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsieve&lang=gcc

which allocates memory for some 5 million integers. (The overheads of memory 
accesses were such that I was able to get to a factor of 2.5:1 of gcc -O3, 
using interpreted bytecode! Compared with 6:1 when only a few thousand 
integers.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#19070

BartC <bc@freeuk.com> wrote:
> I don't think your program actually used that much memory (only 80KB or so). 
> Have a look at the NSIEVE benchmark:
> 
> http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsieve&lang=gcc

I think it is not a matter of the amount of memory being allocated,
but a matter of the amount of memory actually being accessed. The
algorithm used in the shootout accesses memory N+p(N) times, where
N is the upper limit of the range to check and N is the number of
primes in that range. My algorithm accesses memory at least N^2/2
times, so the difference is about the same as O(n) vs O(n^2), i.e.
my program does a lot more memory access in the same amount of
memory.

-- 
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web