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

Odd benchmark behavior

Started by	Nils M Holm <news2009@t3x.org>
First post	2012-03-26 07:51 +0000
Last post	2012-03-27 11:59 +0000
Articles	20 on this page of 25 — 7 participants

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

  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 1 of 2 [1] 2 Next page →

#19037 — Odd benchmark behavior

From	Nils M Holm <news2009@t3x.org>
Date	2012-03-26 07:51 +0000
Subject	Odd benchmark behavior
Message-ID	<9talg3F84gU1@mid.individual.net>

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 output of my toy compiler compiler is attached below. You can
download the complete compiler source code here in case you want
to do some own experiments.

http://www.t3x.org/subc/

Any explanations or additional data (run times) would be greatly
appreciated.

-----[ compiler output (SubC) ]---------------------------------
	.text
	.globl	Cmain
Cmain:	pushl	%ebp			# main() {
	movl	%esp,%ebp
	addl	$-80012,%esp		#   int i, j, p[MAX], k;
	movl	$0,%eax			#   for (k=0, i=3;
	movl	%eax,-80012(%ebp)
	movl	$3,%eax
	movl	%eax,-4(%ebp)
L2:	movl	-80012(%ebp),%eax	#        k<MAX;
	pushl	%eax
	movl	$20000,%eax
	xorl	%edx,%edx
	popl	%ecx
	cmpl	%eax,%ecx
	jge	L6
	incl	%edx
L6:	movl	%edx,%eax
	orl	%eax,%eax
	jnz	L7
	jmp	L4
L7:	jmp	L3
L5:	movl	$2,%eax			#        i+=2) {
	pushl	%eax
	movl	-4(%ebp),%eax
	popl	%ecx
	addl	%ecx,%eax
	movl	%eax,-4(%ebp)
	jmp	L2
L3:	movl	$0,%eax			#   for (j=0;
	movl	%eax,-8(%ebp)
L8:	movl	-8(%ebp),%eax		#        j<k;
	pushl	%eax
	movl	-80012(%ebp),%eax
	xorl	%edx,%edx
	popl	%ecx
	cmpl	%eax,%ecx
	jge	L12
	incl	%edx
L12:	movl	%edx,%eax
	orl	%eax,%eax
	jnz	L13
	jmp	L10
L13:	jmp	L9
L11:	movl	-8(%ebp),%eax		#        j++) {
	incl	-8(%ebp)
	jmp	L8
L9:	movl	-4(%ebp),%eax		#     if (i % p[j] == 0)
	pushl	%eax
	leal	-80008(%ebp),%eax
	pushl	%eax
	movl	-8(%ebp),%eax
	shll	$2,%eax
	popl	%ecx
	addl	%ecx,%eax
	movl	(%eax),%eax
	popl	%ecx
	xchgl	%eax,%ecx
	cdq
	idivl	%ecx
	movl	%edx,%eax
	pushl	%eax
	movl	$0,%eax
	xorl	%edx,%edx
	popl	%ecx
	cmpl	%eax,%ecx
	jne	L14
	incl	%edx
L14:	movl	%edx,%eax
	orl	%eax,%eax
	jnz	L16
	jmp	L15
L16:	jmp	L10			#       break;
L15:	jmp	L11
L10:	movl	-8(%ebp),%eax		#     if (j < k)
	pushl	%eax
	movl	-80012(%ebp),%eax
	xorl	%edx,%edx
	popl	%ecx
	cmpl	%eax,%ecx
	jge	L17
	incl	%edx
L17:	movl	%edx,%eax
	orl	%eax,%eax
	jnz	L19
	jmp	L18
L19:	jmp	L5			#       continue;
L18:	leal	-80008(%ebp),%eax	#     p[k++] = i;
	pushl	%eax
	movl	-80012(%ebp),%eax
	incl	-80012(%ebp)
	shll	$2,%eax
	popl	%ecx
	addl	%ecx,%eax
	pushl	%eax
	movl	-4(%ebp),%eax
	popl	%edx
	movl	%eax,(%edx)
	jmp	L5			#   }
L4:	.data
L20:	.byte	37
	.byte	'd'
	.byte	10
	.byte	0
	.text				#   printf("%d\n", p[k-1]);
	movl	$L20,%eax
	pushl	%eax
	leal	-80008(%ebp),%eax
	pushl	%eax
	movl	-80012(%ebp),%eax
	pushl	%eax
	movl	$1,%eax
	popl	%ecx
	xchgl	%eax,%ecx
	subl	%ecx,%eax
	shll	$2,%eax
	popl	%ecx
	addl	%ecx,%eax
	movl	(%eax),%eax
	pushl	%eax
	pushl	$2
	call	Cprintf
	addl	$12,%esp
L1:	addl	$80012,%esp		# }
	popl	%ebp
	ret
----------------------------------------------------------------

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

[toc] | [next] | [standalone]

#19040

From	"io_x" <a@b.c.invalid>
Date	2012-03-26 11:26 +0200
Message-ID	<4f70351c$0$1385$4fafbaef@reader2.news.tin.it>
In reply to	#19037

"Nils M Holm" <news2009@t3x.org> ha scritto nel messaggio
news:9talg3F84gU1@mid.individual.net...
>
> 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 not understand why you build one algo that take 12s if there is
one other can take 0s...

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

// macro for types
#define  u64  uint64_t
#define  u32  uint32_t
#define  u16  uint16_t
#define  u8    uint8_t
#define  i64   int64_t
#define  i32   int32_t
#define  i16   int16_t
#define  i8     int8_t

// macro for keywords
#define   R    return
#define   P    printf
#define   F    for
#define   G    goto

// for find pos prime
u32  FindNPrime(u32  pos)
{double            r;
 u32    i, p, cnt, v;
    if(pos>=0xFFFFFF00)  G  le;
    cnt=1; // 2 is prime, 1 not
    p  =2;
    if(pos==1)  G  ok;
    ++p;  // this loop find prime from 3
la: r=p; v=sqrt(r);
    F(i=3; i<=v; ++i)
         if(p%i==0) G  l0;
    ++cnt;
    if(cnt==pos) G  ok;
l0: p+=2;
    if(p<=0xFFFFFFF0) G  la;
le: R  -1;
ok: R   p;
}

int main(int c, char *v[])
{double       r;
 time_t  ti, tf;
 u32    pos, ru;
 int         ri;

 if(c<=1||v[1]==0)  R  0;
 ri=atoi(v[1]);
 // there is someone know if the line below conversion
 // are right? i think they are not...
 if(ri<=0 || (unsigned)ri >= 0xFFFFFFFF)
                    R  0;
 pos=(u32)ri;
 ti=time(0); ru=FindNPrime(pos); tf=time(0);
 r=difftime(tf, ti);
 if(ru==(u32)-1)
   P("Not Find %u prime\n", pos);
 else
   P("Find %u prime it is: %u \n", pos, ru);
 P("Difftime return %.2fs\n", r);
 R  0;
}

----------------
C:>prime 20000
Find 20000 prime it is: 224737
Difftime return 0.00s

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

#19042

From	"BartC" <bc@freeuk.com>
Date	2012-03-26 10:40 +0100
Message-ID	<jkpdj5$sbs$1@dont-email.me>
In reply to	#19040

"io_x" <a@b.c.invalid> wrote in message 
news:4f70351c$0$1385$4fafbaef@reader2.news.tin.it...
>
> "Nils M Holm" <news2009@t3x.org> ha scritto nel messaggio

>> gcc -O2 p.c: 12.39s
>> pcc -O p.c: 12.42s
>> scc p.c: 12.27s
>
> i not understand why you build one algo that take 12s if there is
> one other can take 0s...

Because we're investigating code generation not algorithms. A benchmark that 
runs in 0 seconds on any compiler is not very useful!

-- 
Bartc

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

#19047

From	gwowen <gwowen@gmail.com>
Date	2012-03-26 03:37 -0700
Message-ID	<e0ea4cf8-95c9-4fbf-ae26-5fd39c183129@l18g2000vbx.googlegroups.com>
In reply to	#19042

On Mar 26, 10:40 am, "BartC" <b...@freeuk.com> wrote:
> "io_x" <a...@b.c.invalid> wrote in message
>
> news:4f70351c$0$1385$4fafbaef@reader2.news.tin.it...
>
>
>
> > "Nils M Holm" <news2...@t3x.org> ha scritto nel messaggio
> >> gcc -O2 p.c: 12.39s
> >> pcc -O p.c: 12.42s
> >> scc p.c: 12.27s
>
> > i not understand why you build one algo that take 12s if there is
> > one other can take 0s...
>
> Because we're investigating code generation not algorithms. A benchmark that
> runs in 0 seconds on any compiler is not very useful!
>
> --
> Bartc

<CODE type="io_x" idiotic_obfuscation="off">

printf("224737\n");

</CODE>

I WIN!

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

#19051

From	"io_x" <a@b.c.invalid>
Date	2012-03-26 14:13 +0200
Message-ID	<4f705c50$0$1390$4fafbaef@reader1.news.tin.it>
In reply to	#19042

"BartC" <bc@freeuk.com> ha scritto nel messaggio
news:jkpdj5$sbs$1@dont-email.me...
> "io_x" <a@b.c.invalid> wrote in message
> news:4f70351c$0$1385$4fafbaef@reader2.news.tin.it...
>>
>> "Nils M Holm" <news2009@t3x.org> ha scritto nel messaggio
>
>>> gcc -O2 p.c: 12.39s
>>> pcc -O p.c: 12.42s
>>> scc p.c: 12.27s
>>
>> i not understand why you build one algo that take 12s if there is
>> one other can take 0s...
>
> Because we're investigating code generation not algorithms. A benchmark that
> runs in 0 seconds on any compiler is not very useful!

sorry i can not help you
i'm too lazy for understand code compiler get out for -Oxxx :)

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

#19043

From	"io_x" <a@b.c.invalid>
Date	2012-03-26 11:55 +0200
Message-ID	<4f703bfa$0$1386$4fafbaef@reader2.news.tin.it>
In reply to	#19040

"io_x" <a@b.c.invalid> ha scritto nel messaggio 
news:4f70351c$0$1385$4fafbaef@reader2.news.tin.it...
>
> // for find pos prime
> u32  FindNPrime(u32  pos)
> {double            r;
> u32    i, p, cnt, v;
>    if(pos>=0xFFFFFF00)  G  le;
>    cnt=1; // 2 is prime, 1 not
>    p  =2;
>    if(pos==1)  G  ok;
>    ++p;  // this loop find prime from 3
> la: r=p; v=sqrt(r);
>    F(i=3; i<=v; ++i)
>         if(p%i==0) G  l0;
>    ++cnt;
>    if(cnt==pos) G  ok;
> l0: p+=2;
>    if(p<=0xFFFFFFF0) G  la;
> le: R  -1;
> ok: R   p;
> }

the Borland C compiler return for above something as
 ;
 ; u32  FindNPrime(u32  pos)
 ;
 push      ebp
 mov       ebp,esp
 add       esp,-20
 push      ebx
 push      esi
 push      edi
 mov       edi,dword ptr [ebp+8]

@1:        cmp       edi,-256
 jb        short @2
 or        eax,-1
 jmp short @3
@2:        mov       dword ptr [ebp-12],1
 mov       ebx,2
 cmp       edi,1
 je        short @5
 inc       ebx

@6:        mov       dword ptr [ebp-20],ebx
 xor       eax,eax
 mov       dword ptr [ebp-16],eax
 fild      qword ptr [ebp-20]
 fstp      qword ptr [ebp-8]
 push      dword ptr [ebp-4]
 push      dword ptr [ebp-8]
 call      _sqrt
 add       esp,8
 call      __ftol
 mov       esi,eax
 mov       ecx,3
 cmp       esi,ecx
 jb        short @8
@7:        mov       eax,ebx
 xor       edx,edx
 div       ecx
 test      edx,edx
 je        short @10
 inc       ecx
 cmp       esi,ecx
 jae       short @7
@8:        inc       dword ptr [ebp-12]
 cmp       edi,dword ptr [ebp-12]
 je        short @5
@10:       add       ebx,2
 cmp       ebx,-16
 jbe       short @6

 or        eax,-1
 jmp short @3
@5:        mov       eax,ebx
@3:        pop       edi
 pop       esi
 pop       ebx
 mov       esp,ebp
 pop       ebp
 ret

do you know it is possible can result
(unsigned) sqrt(9.0)  is  2 and not 3

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

#19066

From	"io_x" <a@b.c.invalid>
Date	2012-03-27 09:17 +0200
Message-ID	<4f71688a$0$1383$4fafbaef@reader2.news.tin.it>
In reply to	#19043

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4f703bfa$0$1386$4fafbaef@reader2.news.tin.it...
>
> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> news:4f70351c$0$1385$4fafbaef@reader2.news.tin.it...
>>
>> // for find pos prime
>> u32  FindNPrime(u32  pos)
>> {double            r;
>> u32    i, p, cnt, v;
>>    if(pos>=0xFFFFFF00)  G  le;
>>    cnt=1; // 2 is prime, 1 not
>>    p  =2;
>>    if(pos==1)  G  ok;
>>    ++p;  // this loop find prime from 3
>> la: r=p; v=sqrt(r);
>>    F(i=3; i<=v; ++i)
>>         if(p%i==0) G  l0;
>>    ++cnt;
>>    if(cnt==pos) G  ok;
>> l0: p+=2;
>>    if(p<=0xFFFFFFF0) G  la;
>> le: R  -1;
>> ok: R   p;
>> }
>
> the Borland C compiler return for above something as
> ;
> ; u32  FindNPrime(u32  pos)
> ;
> push      ebp
> mov       ebp,esp
> add       esp,-20
> push      ebx
> push      esi
> push      edi
> mov       edi,dword ptr [ebp+8]
>
> @1:        cmp       edi,-256
> jb        short @2
> or        eax,-1
> jmp short @3
> @2:        mov       dword ptr [ebp-12],1
> mov       ebx,2
> cmp       edi,1
> je        short @5
> inc       ebx
>
> @6:        mov       dword ptr [ebp-20],ebx
> xor       eax,eax
> mov       dword ptr [ebp-16],eax
> fild      qword ptr [ebp-20]
> fstp      qword ptr [ebp-8]
> push      dword ptr [ebp-4]
> push      dword ptr [ebp-8]
> call      _sqrt
> add       esp,8
> call      __ftol
> mov       esi,eax
> mov       ecx,3
> cmp       esi,ecx
> jb        short @8
> @7:        mov       eax,ebx
> xor       edx,edx
> div       ecx
> test      edx,edx
> je        short @10
> inc       ecx
> cmp       esi,ecx
> jae       short @7
> @8:        inc       dword ptr [ebp-12]
> cmp       edi,dword ptr [ebp-12]
> je        short @5
> @10:       add       ebx,2
> cmp       ebx,-16
> jbe       short @6
>
> or        eax,-1
> jmp short @3
> @5:        mov       eax,ebx
> @3:        pop       edi
> pop       esi
> pop       ebx
> mov       esp,ebp
> pop       ebp
> ret
>
> do you know it is possible can result
> (unsigned) sqrt(9.0)  is  2 and not 3

my assembly try:

;0k,4j,8i,12b,16ra, 20P_pos + 64
;                   84
align  4
FindNPrime:
<b,i,j,k
s-=   64
    ;iint3
    k=^84|k>=0FFFFFF00h#.e
.0: c=1  |j=2|k==1#.a   ; c==conter  j==prime number
    ++j
.1:  *s=j|fild D*s|fsqrt|fistp D*s  ; *s==(u32)sqrt(i)
      i=3 |b=*s|#.3
.2:       a=j|r=0 |div i|r==0#.4|++i
.3:       i<=b#.2
      ++c |c==k#.a
.4:   j+=2|j<=0FFFFFFF0h#.1
.e: a=-1|stc|#.z
.a: a= j|clc
.z:
s=&*s+64
>b,i,j,k
ret  4


;0k,4j,8i,12b,16ra, 20P_pos + 64
;                   84
align 4
FindNPrime:
     push  ebx
     push   esi
     push   edi
     push   ebp
     sub   esp,  64
;iint3
     mov   ebp,   dword[esp+ 84]
     cmp   ebp,  0FFFFFF00h
     jae  .e
.0:  mov   ecx,  1
     mov   edi,  2
     cmp   ebp,  1
     je   .a ; c==conter  j==prime number
     inc   edi
.1:  mov   [esp],  edi
     fild dword[esp]
     fsqrt
     fistp dword[esp] ; *s==sqrt(i)
     mov   esi,  3
     mov   ebx,  [esp]
     jmp short .3
.2:  mov   eax,  edi
     mov   edx,  0
     div esi
     cmp   edx,  0
     je   .4
     inc   esi
.3:  cmp   esi,  ebx
     jbe  .2
     inc   ecx
     cmp   ecx,  ebp
     je   .a
.4:  add   edi,  2
     cmp   edi,  0FFFFFFF0h
     jbe  .1
.e:  mov   eax,  -1
     stc
     jmp short .z
.a:  mov   eax,  edi
     clc
.z:
     lea   esp,  [esp+64]
     pop    ebp
     pop    edi
     pop    esi
     pop   ebx
     ret 4

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

#19067

From	"io_x" <a@b.c.invalid>
Date	2012-03-27 09:20 +0200
Message-ID	<4f716921$0$1383$4fafbaef@reader2.news.tin.it>
In reply to	#19066

"io_x" <a@b.c.invalid> ha scritto nel messaggio 
news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...

there is someone that know if  (unsigned) sqrt(9.0) can be
follow the C standard the unsigned 2???
Thank you

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

#19081

From	"Scott Fluhrer" <sfluhrer@ix.netcom.com>
Date	2012-03-27 13:39 -0400
Message-ID	<1332869863.433565@rcdn-nntpcache-1>
In reply to	#19067

"io_x" <a@b.c.invalid> wrote in message 
news:4f716921$0$1383$4fafbaef@reader2.news.tin.it...
>
> "io_x" <a@b.c.invalid> ha scritto nel messaggio 
> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
>
> there is someone that know if  (unsigned) sqrt(9.0) can be
> follow the C standard the unsigned 2???

Well, yes, 2 is an allowed value for that expression.  Floating point 
functions such are sqrt, sin and log are not required to be exact; only 
close; it is quite acceptable if sqrt(9.0) evaluates to 2.999999999999; when 
you convert that to unsigned, it does a round down, giving you 2.

The inexactness of floating point is something the programmer needs to be 
aware of whenever they deal with floating point.

-- 
poncho

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

#19092

From	pete <pfiland@mindspring.com>
Date	2012-03-27 21:49 -0500
Message-ID	<4F727C20.5A49@mindspring.com>
In reply to	#19067

io_x wrote:
> 
> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
> 
> there is someone that know if  (unsigned) sqrt(9.0) can be
> follow the C standard the unsigned 2???
> Thank you

You could do it this way instead:

la:
    v = p;
    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
        v = i;
    }

-- 
pete

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

#19353

From	"io_x" <a@b.c.invalid>
Date	2012-04-05 12:18 +0200
Message-ID	<4f7d7076$0$1379$4fafbaef@reader2.news.tin.it>
In reply to	#19092

"pete" <pfiland@mindspring.com> ha scritto nel messaggio
news:4F727C20.5A49@mindspring.com...
> io_x wrote:
>>
>> "io_x" <a@b.c.invalid> ha scritto nel messaggio
>> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
>>
>> there is someone that know if  (unsigned) sqrt(9.0) can be
>> follow the C standard the unsigned 2???
>> Thank you
>
> You could do it this way instead:
>
> la:
>    v = p;
>    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
>        v = i;
>    }

the above is wrong, for example
if p==0 than v=0, i=0/2=0; 0>0 is false; so i=0/0 and here seg fault

if 0.0<p<1.0  i have some doubit too
for exampel v=p=0.1  sqrt(p)=0.316....
v_(n+1)=(p/v_n + v_n)
at the time of the ceck "v>i"
v=v_(n+1)  and i=v_n  and i know would be v_(n+1)>v_n
so at the time of check "v>i" would result v=v_(n+1)>v_n=i
ok this is ok

if p>1.0  => sqrt(p)<p
at the time of the check "v>i"
v=v_(n+1)  and i=v_n  and i know would be v_(n+1)<v_n
so at the time of check "v>i" would result v=v_(n+1)<v_n=i
this is not ok v<i at first iteration so the loop end
to the first iteration....

do you accurate rethink first of post something??
for what i mean...
for example what wrong if sqrt(9)=2.9999999999999999
and (unsigned)2.9999999999999999==2?
this could be wrong if the standard says
(unsigned) floatNumber == round(floatNumber, 0)
where round: Float x Unsigned -> Unsigned is the roung function
here happen to be so [round to the unsigned next up or down value..]

it depend how they round float number

> -- 
> pete

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

#19354

From	pete <pfiland@mindspring.com>
Date	2012-04-05 06:48 -0400
Message-ID	<4F7D788E.45B9@mindspring.com>
In reply to	#19353

io_x wrote:
> 
> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
> news:4F727C20.5A49@mindspring.com...
> > io_x wrote:
> >>
> >> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> >> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
> >>
> >> there is someone that know if  (unsigned) sqrt(9.0) can be
> >> follow the C standard the unsigned 2???
> >> Thank you
> >
> > You could do it this way instead:
> >
> > la:
> >    v = p;
> >    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
> >        v = i;
> >    }
> 
> the above is wrong, for example
> if p==0 than v=0, i=0/2=0; 0>0 is false;
> so i=0/0 and here seg fault

After 0>0 is false, the loop stops 
and then there is no i=0/0.


 
> if 0.0<p<1.0  i have some doubit too

> it depend how they round float number

This is the code that you wrote:

    #define  u32  uint32_t

    u32    i, p, cnt, v;

There are no float numbers in that code.


-- 
pete

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

#19358

From	"io_x" <a@b.c.invalid>
Date	2012-04-05 14:12 +0200
Message-ID	<4f7d8b0e$0$1385$4fafbaef@reader1.news.tin.it>
In reply to	#19354

"pete" <pfiland@mindspring.com> ha scritto nel messaggio
news:4F7D788E.45B9@mindspring.com...
> io_x wrote:
>>
>> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
>> news:4F727C20.5A49@mindspring.com...
>> > io_x wrote:
>> >>
>> >> "io_x" <a@b.c.invalid> ha scritto nel messaggio
>> >> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
>> >>
>> >> there is someone that know if  (unsigned) sqrt(9.0) can be
>> >> follow the C standard the unsigned 2???
>> >> Thank you
>> >
>> > You could do it this way instead:
>> >
>> > la:
>> >    v = p;
>> >    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
>> >        v = i;
>> >    }
>>
>> the above is wrong, for example
>> if p==0 than v=0, i=0/2=0; 0>0 is false;
>> so i=0/0 and here seg fault
>
> After 0>0 is false, the loop stops
> and then there is no i=0/0.
>
>
>
>> if 0.0<p<1.0  i have some doubit too
>
>> it depend how they round float number
>
> This is the code that you wrote:
>
>    #define  u32  uint32_t
>
>    u32    i, p, cnt, v;
>
> There are no float numbers in that code.

without use macro,

if that code is so ok, even if i can not uderstand enought for
explain right why it is wrong...

why this print the wrong result??

PeteSqrt(0.100000) = 1.025000
-------------------
#include <stdio.h>

double  peteSqrt(double   p)
{double  v, i;
 int        j;
 v=p;
 for(i=((1==v)+v)/2, j=0;  v>i && j<1000; i=(p/v+v)/2, ++j)
          v = i;
 return   i;
}

int  main(void)
{double   x, y;
 x=0.1;
 y=peteSqrt(x);
 printf("PeteSqrt(%f) = %f\n",  x, y);
 return 0;
}
----------------

ciao

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

#19359

From	pete <pfiland@mindspring.com>
Date	2012-04-05 09:03 -0400
Message-ID	<4F7D9807.1D82@mindspring.com>
In reply to	#19358

io_x wrote:
> 
> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
> news:4F7D788E.45B9@mindspring.com...
> > io_x wrote:
> >>
> >> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
> >> news:4F727C20.5A49@mindspring.com...
> >> > io_x wrote:
> >> >>
> >> >> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> >> >> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
> >> >>
> >> >> there is someone that know if  (unsigned) sqrt(9.0) can be
> >> >> follow the C standard the unsigned 2???
> >> >> Thank you
> >> >
> >> > You could do it this way instead:
> >> >
> >> > la:
> >> >    v = p;
> >> >    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
> >> >        v = i;
> >> >    }

> > This is the code that you wrote:
> >    #define  u32  uint32_t
> >    u32    i, p, cnt, v;
> > There are no float numbers in that code.

> why this print the wrong result??

> {double  v, i;

That print the wrong result 
because you changed the code to make it wrong.

You already defined (v), (p) and (i) to be all integes,
in your function 
u32  FindNPrime(u32  pos)

The code that I wote, is supposed to be used by you
to replace the line of code that you wrote
at the label la:

la: r=p; v=sqrt(r);

After the line with the lable la:
 What you want is for (v) to be equal to the greatest integer
 with a value less than or equal to the square root of (p).

My suggestion was for you to replace the floating point math
in your FindNPrime function with integer math.

-- 
pete

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

#19361

From	"io_x" <a@b.c.invalid>
Date	2012-04-05 16:18 +0200
Message-ID	<4f7da890$0$1381$4fafbaef@reader1.news.tin.it>
In reply to	#19359

"pete" <pfiland@mindspring.com> ha scritto nel messaggio 
news:4F7D9807.1D82@mindspring.com...
> io_x wrote:
>>
>> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
>> news:4F7D788E.45B9@mindspring.com...
>> > io_x wrote:
>> >>
>> >> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
>> >> news:4F727C20.5A49@mindspring.com...
>> >> > io_x wrote:
>> >> >>
>> >> >> "io_x" <a@b.c.invalid> ha scritto nel messaggio
>> >> >> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
>> >> >>
>> >> >> there is someone that know if  (unsigned) sqrt(9.0) can be
>> >> >> follow the C standard the unsigned 2???
>> >> >> Thank you
>> >> >
>> >> > You could do it this way instead:
>> >> >
>> >> > la:
>> >> >    v = p;
>> >> >    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
>> >> >        v = i;
>> >> >    }
>
>> > This is the code that you wrote:
>> >    #define  u32  uint32_t
>> >    u32    i, p, cnt, v;
>> > There are no float numbers in that code.
>
>> why this print the wrong result??
>
>> {double  v, i;
>
> That print the wrong result
> because you changed the code to make it wrong.
>
> You already defined (v), (p) and (i) to be all integes,
> in your function
> u32  FindNPrime(u32  pos)
>
> The code that I wote, is supposed to be used by you
> to replace the line of code that you wrote
> at the label la:
>
> la: r=p; v=sqrt(r);
>
> After the line with the lable la:
> What you want is for (v) to be equal to the greatest integer
> with a value less than or equal to the square root of (p).
>
> My suggestion was for you to replace the floating point math
> in your FindNPrime function with integer math.
>
> -- 
> pete

ma che cazzo dici
KF

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

#19423

From	"io_x" <a@b.c.invalid>
Date	2012-04-07 13:26 +0200
Message-ID	<4f802349$0$1383$4fafbaef@reader1.news.tin.it>
In reply to	#19361

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4f7da890$0$1381$4fafbaef@reader1.news.tin.it...
>
> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
> news:4F7D9807.1D82@mindspring.com...
>> -- 
>> pete
>
> ma che cazzo dici
> KF

temo di aver esagerato: scusa a Pete, scusa a tutti...
Buone Feste :)

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

#19396

From	"io_x" <a@b.c.invalid>
Date	2012-04-06 09:31 +0200
Message-ID	<4f7e9ac0$0$1374$4fafbaef@reader1.news.tin.it>
In reply to	#19359

"pete" <pfiland@mindspring.com> ha scritto nel messaggio
news:4F7D9807.1D82@mindspring.com...
> io_x wrote:
>>
>> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
>> news:4F7D788E.45B9@mindspring.com...
>> > io_x wrote:
>> >>
>> >> "pete" <pfiland@mindspring.com> ha scritto nel messaggio
>> >> news:4F727C20.5A49@mindspring.com...
>> >> > io_x wrote:
>> >> >>
>> >> >> "io_x" <a@b.c.invalid> ha scritto nel messaggio
>> >> >> news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
>> >> >>
>> >> >> there is someone that know if  (unsigned) sqrt(9.0) can be
>> >> >> follow the C standard the unsigned 2???
>> >> >> Thank you
>> >> >
>> >> > You could do it this way instead:
>> >> >
>> >> > la:
>> >> >    v = p;
>> >> >    for (i = ((1 == v) + v) / 2; v > i; i = (p / v + v) / 2) {
>> >> >        v = i;
>> >> >    }
>
>> > This is the code that you wrote:
>> >    #define  u32  uint32_t
>> >    u32    i, p, cnt, v;
>> > There are no float numbers in that code.
>
>> why this print the wrong result??
>
>> {double  v, i;
>
> That print the wrong result
> because you changed the code to make it wrong.
>
> You already defined (v), (p) and (i) to be all integes,
> in your function
> u32  FindNPrime(u32  pos)
>
> The code that I wote, is supposed to be used by you
> to replace the line of code that you wrote
> at the label la:
>
> la: r=p; v=sqrt(r);
>
> After the line with the lable la:
> What you want is for (v) to be equal to the greatest integer
> with a value less than or equal to the square root of (p).
>
> My suggestion was for you to replace the floating point math
> in your FindNPrime function with integer math.
>
> -- 
> pete

i think i not have understood that, i'm wrong you are right...

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

#19079

From	"io_x" <a@b.c.invalid>
Date	2012-03-27 19:01 +0200
Message-ID	<4f71f167$0$1386$4fafbaef@reader2.news.tin.it>
In reply to	#19066

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4f71688a$0$1383$4fafbaef@reader2.news.tin.it...
>
> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> news:4f703bfa$0$1386$4fafbaef@reader2.news.tin.it...
>>
>> "io_x" <a@b.c.invalid> ha scritto nel messaggio
>> news:4f70351c$0$1385$4fafbaef@reader2.news.tin.it...
>>>
>>> // for find pos prime
>>> u32  FindNPrime(u32  pos)
>>> {double            r;
>>> u32    i, p, cnt, v;
>>>    if(pos>=0xFFFFFF00)  G  le;
>>>    cnt=1; // 2 is prime, 1 not
>>>    p  =2;
>>>    if(pos==1)  G  ok;
>>>    ++p;  // this loop find prime from 3
>>> la: r=p; v=sqrt(r);

i change the line above in:
la: r=p+1; v=sqrt(r);

>>>    F(i=3; i<=v; ++i)
>>>         if(p%i==0) G  l0;
>>>    ++cnt;
>>>    if(cnt==pos) G  ok;
>>> l0: p+=2;
>>>    if(p<=0xFFFFFFF0) G  la;
>>> le: R  -1;
>>> ok: R   p;
>>> }

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

#19041

From	"BartC" <bc@freeuk.com>
Date	2012-03-26 10:36 +0100
Message-ID	<jkpdca$ra3$1@dont-email.me>
In reply to	#19037

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

> 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):

> #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]);
> }

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

I tried it with my compiler (not of C, but similar), which while not a toy,
does also generate some very bad code. And while it was slower than the Cs,
all the results were in quite a narrow range: 3.1 to 3.4 seconds for various
C compilers, and 3.5 seconds for my compiler (all x86-32).

The 3.1 seconds was for gcc -O3.

However, with the conventional sieve benchmark, gcc -O3 was over 3 times as
fast as my compiler. So perhaps there's something peculiar with your
benchmark.

(The ratio between gcc -O3 and gcc -O0 was 1.13:1 with your benchmark, but
4:1 with the regular sieve, however the latter does repeat the main loop
thousands of times, which I suspect -O3 takes advantage of. You need a
different benchmark which isn't repetitive, and doesn't use too much memory
either, otherwise the timings will be dominated by memory accesses.)

-- 
Bartc

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

#19046

From	Nils M Holm <news2009@t3x.org>
Date	2012-03-26 10:02 +0000
Message-ID	<9tat6cFucaU2@mid.individual.net>
In reply to	#19041

BartC <bc@freeuk.com> wrote:
> (The ratio between gcc -O3 and gcc -O0 was 1.13:1 with your benchmark, but
> 4:1 with the regular sieve, however the latter does repeat the main loop
> thousands of times, which I suspect -O3 takes advantage of. You need a
> different benchmark which isn't repetitive, and doesn't use too much memory
> either, otherwise the timings will be dominated by memory accesses.)

Very good point, did not think of that!  I already suspected that the
results were tightly knit to my benchmark program, because I did some
other tests where SCC performed as lousy as expected.

Alright, now going to implement the optimizer...

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

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

Page 1 of 2 [1] 2 Next page →

csiph-web

Odd benchmark behavior

Contents

#19037 — Odd benchmark behavior

#19040

#19042

#19047

#19051

#19043

#19066

#19067

#19081

#19092

#19353

#19354

#19358

#19359

#19361

#19423

#19396

#19079

#19041

#19046