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

Groups > comp.lang.forth > #29575 > unrolled thread

Forth vs Java in calculating partial sum ;)

Started byMelzzzzz <mel@zzzzz.com>
First post2014-04-12 19:11 +0200
Last post2014-12-10 18:29 +0000
Articles 11 on this page of 31 — 10 participants

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

Contents

  Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.com> - 2014-04-12 19:11 +0200
    Re: Forth vs Java in calculating partial sum ;) Paul Rubin <no.email@nospam.invalid> - 2014-04-12 10:15 -0700
      Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.com> - 2014-04-14 22:15 +0200
        Re: Forth vs Java in calculating partial sum ;) stephenXXX@mpeforth.com (Stephen Pelc) - 2014-04-14 23:20 +0000
          Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.invalid> - 2014-04-15 04:18 +0200
            Re: Forth vs Java in calculating partial sum ;) m.a.m.hendrix@tue.nl - 2014-04-15 00:32 -0700
              Re: Forth vs Java in calculating partial sum ;) stephenXXX@mpeforth.com (Stephen Pelc) - 2014-04-15 11:33 +0000
              Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.com> - 2014-04-15 15:55 +0200
            Re: Forth vs Java in calculating partial sum ;) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-04-15 14:44 +0000
              Re: Forth vs Java in calculating partial sum ;) Paul Rubin <no.email@nospam.invalid> - 2014-04-15 09:00 -0700
                Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.invalid> - 2014-04-15 19:38 +0200
              Re: Forth vs Java in calculating partial sum ;) mhx@iae.nl - 2014-04-15 11:41 -0700
              Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.com> - 2014-04-16 07:10 +0200
              Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.com> - 2014-04-16 07:24 +0200
                Re: Forth vs Java in calculating partial sum ;) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-04-16 10:24 +0000
    Re: Forth vs Java in calculating partial sum ;) mhx@iae.nl - 2014-04-12 13:01 -0700
      Re: Forth vs Java in calculating partial sum ;) mhx@iae.nl - 2014-04-12 13:06 -0700
      Re: Forth vs Java in calculating partial sum ;) Paul Rubin <no.email@nospam.invalid> - 2014-04-12 15:49 -0700
        Re: Forth vs Java in calculating partial sum ;) mhx@iae.nl - 2014-04-12 23:00 -0700
          Re: Forth vs Java in calculating partial sum ;) Paul Rubin <no.email@nospam.invalid> - 2014-04-13 00:14 -0700
            Re: Forth vs Java in calculating partial sum ;) mhx@iae.nl - 2014-04-13 02:03 -0700
          Re: Forth vs Java in calculating partial sum ;) Bernd Paysan <bernd.paysan@gmx.de> - 2014-04-13 14:52 +0200
      Re: Forth vs Java in calculating partial sum ;) "WJ" <w_a_x_man@yahoo.com> - 2014-12-12 23:45 +0000
    Re: Forth vs Java in calculating partial sum ;) mhx@iae.nl - 2014-04-12 13:33 -0700
      Re: Forth vs Java in calculating partial sum ;) Bernd Paysan <bernd.paysan@gmx.de> - 2014-04-12 22:50 +0200
        Re: Forth vs Java in calculating partial sum ;) Melzzzzz <mel@zzzzz.invalid> - 2014-04-13 03:30 +0200
        Re: Forth vs Java in calculating partial sum ;) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-04-13 13:43 +0000
    Re: Forth vs Java in calculating partial sum ;) Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-04-15 10:05 -0500
    Re: Forth vs Java in calculating partial sum ;) "WJ" <w_a_x_man@yahoo.com> - 2014-12-05 05:46 +0000
    Re: Forth vs Java in calculating partial sum ;) "WJ" <w_a_x_man@yahoo.com> - 2014-12-10 09:50 +0000
      Re: Forth vs Java in calculating partial sum ;) "WJ" <w_a_x_man@yahoo.com> - 2014-12-10 18:29 +0000

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

#29605

Frommhx@iae.nl
Date2014-04-13 02:03 -0700
Message-ID<3ad2f8c2-4e51-428d-821a-db4884bf61d0@googlegroups.com>
In reply to#29603
On Sunday, April 13, 2014 9:14:23 AM UTC+2, Paul Rubin wrote:
> Sorry, meant 0.0005 us (0.5 ns or 2 ghz).  But I think the speed is
> 
> limited by memory, so stuff like loop unrolling is unlikely to help.

This is as fast as I can get it to go (not using SSE etc.)
I don't think it is memory limited yet (smaller array doesn't
speed it up more than by about 10%).

-marcel
---
ANEW -cumul

#50000000 =: N  ( only works when N mod 16 =0, N mod 32 = 0 )
0 VALUE addr

DOC
(*
  t0 =  i   /3 + i
  ..
  t3 = (i+3)/3 + i+3 = i/3+i +  1  + 3
*)
ENDDOC

: init_cumul ( -- ) 
	addr 4 0 ?DO   I 3 / I +  SWAP !+  LOOP ( addr)
	     N 4 ?DO   
	     	       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
	     	       
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  

	     	       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
	     	       
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
		       DUP -3 CELL[] @ 4 + SWAP !+  
	   #16 +LOOP   DROP ; 

: cumul ( -- )	
	addr @+  
	N 1 ?DO  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  

		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
		OVER @ + DUP  ROT !+ SWAP  
      #32 +LOOP 2DROP ; 

: bench ( xt -- ) 
	N CELLS ALLOCATE ?ALLOCATE TO addr 
	TIMER-RESET 
	  init_cumul
	  N S>F  MS? S>F 1e+3 F*   F/ F>S CR 0DEC.R ."  million integers/sec, " 
	.ELAPSED  
	TIMER-RESET 
	  cumul
	  N S>F  MS? S>F 1e+3 F*   F/ F>S CR 0DEC.R ."  million integers/sec, " 
	.ELAPSED 
	CR addr N 1- CELL[] @ . 
	addr FREE ?ALLOCATE ;

bench

\ model name : Intel(R) Core(TM) i7 920 CPU @ 2.66GHz
\ 980 million integers/sec, 0.053 seconds elapsed.
\ 1000 million integers/sec, 0.052 seconds elapsed.
\ 1666666616666667  ok

\ FORTH> bench 
\ vendor_id  : GenuineIntel
\ model name : Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
\ 1282 million integers/sec, 0.039 seconds elapsed.
\ 1315 million integers/sec, 0.038 seconds elapsed.
\ 1666666616666667  ok

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

#29608

FromBernd Paysan <bernd.paysan@gmx.de>
Date2014-04-13 14:52 +0200
Message-ID<lie1a3$rt1$1@online.de>
In reply to#29601
mhx@iae.nl wrote:
> : init_cumul ( -- )
> addr  N 0 ?DO
> I       3 / I       +   SWAP !+
> I   1 + 3 / I   1 + +   SWAP !+
> I   2 + 3 / I   2 + +   SWAP !+
> I   3 + 3 / I   3 + +   SWAP !+
> 
> I   4 + 3 / I   4 + +   SWAP !+
> I   5 + 3 / I   5 + +   SWAP !+
> I   6 + 3 / I   6 + +   SWAP !+
> I   7 + 3 / I   7 + +   SWAP !+
> 8 +LOOP
> DROP ;

Outch, if you unroll ini_cumul, please unroll it by 3 times (or a multiple 
of 3), and get rid of the 3/ completely!

: init_cumul ( -- )
  addr 0 N 0 ?do
  tuck I     + swap !+
  over I 1 + + swap !+
  over I 2 + + swap !+ swap 1 +
  3 +LOOP  2drop ;

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#34888

From"WJ" <w_a_x_man@yahoo.com>
Date2014-12-12 23:45 +0000
Message-ID<m6fumq$q4u$1@dont-email.me>
In reply to#29590
mhx@iae.nl wrote:

> On Saturday, April 12, 2014 7:11:11 PM UTC+2, Melzzzzz wrote:
> > Seems that Java bits Forth in optimizing tight loops. Eg division by
> > constant optimization is performed automatically.
> [..]
> 
> Paraphrased:
> 
> ANEW -cumul
> 
> #50000000 =: N 
> N CELLS ALLOCATE ?ALLOCATE =: addr
> 
> : init_cumul ( -- ) addr  N 0 ?DO  I 3 / I +   SWAP !+   LOOP DROP ; 
>          
> : cumul ( -- )
> 	addr @+ ( [a] a -- )
> 	N 1 ?DO 
> 		OVER @ + DUP ( a [a]+x [a]+x -- )
> 		ROT !+ ( [a]+x a2 -- )	SWAP
> 	   LOOP 2DROP ; 
> 
> : bench ( xt -- ) 
> 	TIMER-RESET 
> 	EXECUTE   
> 	MS? S>F  N S>F  F/  CR F.N1 ." s/op, "  .ELAPSED ; 
> 
>   ' init_cumul bench 
>   ' cumul      bench 
> CR addr N 1- CELL[] @ .  
>    addr FREE ?ALLOCATE
> 
> \ 3.68 us/op, 0.186 seconds elapsed.
> \ 2.16 us/op, 0.109 seconds elapsed.
> \ 1666666616666667  ok
> 
> I guess Java programmers are paid per LOC.

SP-Forth:

REQUIRE TIME&DATE lib/include/facil.f
REQUIRE F. lib/include/float2.f
16 SET-PRECISION

50000000 CONSTANT n

: run ( -- )
  ms@
  0.0e
  n 1 DO  I 3 / I + DS>F  F+  LOOP
  F.  ms@ SWAP - . ." milliseconds"  ;

run

1666666616666667. 360 milliseconds Ok

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

#29592

Frommhx@iae.nl
Date2014-04-12 13:33 -0700
Message-ID<ca9e51d1-059e-4116-8f7c-024b903395e2@googlegroups.com>
In reply to#29575
On Saturday, April 12, 2014 7:11:11 PM UTC+2, Melzzzzz wrote: 
> Seems that Java bits Forth in optimizing tight loops. Eg division by 
> constant optimization is performed automatically. 

[..] 

Paraphrased: 

ANEW -cumul 

#50000000 =: N 
N CELLS ALLOCATE ?ALLOCATE =: addr 

: init_cumul ( -- ) addr  N 0 ?DO  I 3 / I +   SWAP !+   LOOP DROP ; 
          
: cumul ( -- ) 
        addr @+ ( [a] a -- ) 
        N 1 ?DO 
                OVER @ + DUP ( a [a]+x [a]+x -- ) 
                ROT !+ ( [a]+x a2 -- )        SWAP 
           LOOP 2DROP ; 

: bench ( xt -- ) 
        TIMER-RESET 
        EXECUTE   
        MS? S>F 1e-3 F* N S>F  F/  CR F.N1 ." s/op, "  .ELAPSED ; 

  ' init_cumul bench 
  ' cumul      bench 
CR addr N 1- CELL[] @ .   
   addr FREE ?ALLOCATE 

\ 3.68 ns/op, 0.186 seconds elapsed. 
\ 2.16 ns/op, 0.109 seconds elapsed. 
\ 1666666616666667  ok 

I guess Java programmers are paid per LOC. 

-marcel

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

#29593

FromBernd Paysan <bernd.paysan@gmx.de>
Date2014-04-12 22:50 +0200
Message-ID<lic8vb$dv4$1@online.de>
In reply to#29592
mhx@iae.nl wrote:

> On Saturday, April 12, 2014 7:11:11 PM UTC+2, Melzzzzz wrote:
>> Seems that Java bits Forth in optimizing tight loops. Eg division by
>> constant optimization is performed automatically.
> 
> [..]
> 
> Paraphrased:
> 
> ANEW -cumul
> 
> #50000000 =: N
> N CELLS ALLOCATE ?ALLOCATE =: addr
> 
> : init_cumul ( -- ) addr  N 0 ?DO  I 3 / I +   SWAP !+   LOOP DROP ;
>           
> : cumul ( -- )
>         addr @+ ( [a] a -- )
>         N 1 ?DO
>                 OVER @ + DUP ( a [a]+x [a]+x -- )
>                 ROT !+ ( [a]+x a2 -- )        SWAP
>            LOOP 2DROP ;
> 
> : bench ( xt -- )
>         TIMER-RESET
>         EXECUTE
>         MS? S>F 1e-3 F* N S>F  F/  CR F.N1 ." s/op, "  .ELAPSED ;
> 
>   ' init_cumul bench
>   ' cumul      bench
> CR addr N 1- CELL[] @ .
>    addr FREE ?ALLOCATE
> 
> \ 3.68 ns/op, 0.186 seconds elapsed.
> \ 2.16 ns/op, 0.109 seconds elapsed.
> \ 1666666616666667  ok
> 
> I guess Java programmers are paid per LOC.

That's how I would write cumul (with the original stack effeckt, which 
Melzzzzz forgot to write):

: cumul ( addr -- addr )
    dup N 1- cells bounds ?do
	i @ i cell+ +!
    cell +loop ;

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#29598

FromMelzzzzz <mel@zzzzz.invalid>
Date2014-04-13 03:30 +0200
Message-ID<licpbs$3kj$3@solani.org>
In reply to#29593
On Sat, 12 Apr 2014 22:50:50 +0200
Bernd Paysan <bernd.paysan@gmx.de> wrote:

> 
> That's how I would write cumul (with the original stack effeckt,
> which Melzzzzz forgot to write):
> 
> : cumul ( addr -- addr )
>     dup N 1- cells bounds ?do
> 	i @ i cell+ +!
>     cell +loop ;
> 

This one is even faster on gforth :

: cumul ( addr -- addr )
        dup @
        over dup N cells + swap cell + ?do   
        i +! i @
        cell +loop     
        drop ;



-- 
Click OK to continue...

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

#29610

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2014-04-13 13:43 +0000
Message-ID<2014Apr13.154333@mips.complang.tuwien.ac.at>
In reply to#29593
Bernd Paysan <bernd.paysan@gmx.de> writes:
>That's how I would write cumul (with the original stack effeckt, which 
>Melzzzzz forgot to write):
>
>: cumul ( addr -- addr )
>    dup N 1- cells bounds ?do
>	i @ i cell+ +!
>    cell +loop ;

Disadvantage: fetches every cell twice, and you have a recurrence
through memory, which may be quite expensive, maybe not on current
Intel processors, but on older Intel ones, and probably on many other
machines.  So for performance I would write this as

: cumul ( addr -- addr )
  0 over N 1- cells bounds ?do
    i @ + dup i !
  cell +loop 
  drop ;

(untested).  And the loop body is even one char shorter:-).

Here are the loop bodies on VFX:

Melzzzzz            Paysan              Ertl            
MOV EDX, [ESP]      MOV EDX, [ESP]      MOV EDX, [ESP]  
SHL EDX, 02         MOV ECX, [ESP]      ADD EBX, 0 [EDX]
ADD EDX, [EBP]      MOV EAX, 0 [EDX]    MOV EDX, [ESP]  
ADD EBX, 0 [EDX]    ADD [ECX+04], EAX   MOV 0 [EDX], EBX
MOV EDX, [ESP]      ADD [ESP], 04       ADD [ESP], 04   
SHL EDX, 02         ADD [ESP+04], 04    ADD [ESP+04], 04
ADD EDX, [EBP]      JNO 080BF3B0        JNO 080BF428    
MOV 0 [EDX], EBX
ADD [ESP], 01
ADD [ESP+04], 01
JNO 080BF338

Allocating I (and the conditioned loop bound) into a register might
pay off for this kind of code.

As for the benchmark: Sure, when you do a tiny benchmark that uses int
instead of Integer, and uses arrays instead of something from the Java
Collection classes, like ArrayList, then the Java JIT can shine.  And
to make sure of that, the original benchmark used a size (50*1000*1000
ints, i.e., 200MB) that far exceeds cache sizes, so any remaining
inefficiencies get swamped in the cache misses.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

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

#29668

FromAndrew Haley <andrew29@littlepinkcloud.invalid>
Date2014-04-15 10:05 -0500
Message-ID<F6qdnU9NjLgk19DOnZ2dnUVZ_sSdnZ2d@supernews.com>
In reply to#29575
Melzzzzz <mel@zzzzz.com> wrote:
> Seems that Java bits Forth in optimizing tight loops. Eg division by
> constant optimization is performed automatically.

It's not only that, it's a space versus speed trade-off.  The inner
loop of the Java code looks like this:
 
0e0   B10: #    B10 B11 <- B9 B10       Loop: B10-B10 inner main of N98 Freq: 999993
0e0     movslq  RDX, R13        # i2l
0e3     movl    R11, R13        # spill
0e6     sarl    R11, #31
0ea     imulq   R9, RDX, #1431655766    # long
0f1     movl    RCX, R13        # spill
0f4     addl    RCX, #3 # int
0f7     sarq    R9, #32
0fb     movslq  RDI, RCX        # i2l
0fe     movl    R9, R9  # l2i
101     subl    R9, R11 # int
104     addl    R9, R13 # int
107     imulq   R11, RDI, #1431655766   # long
10e     movslq  R9, R9  # i2l
111     movq    [RBX + #16 + R13 << #3], R9     # long
116     sarq    R11, #32
11a     movl    RDI, RCX        # spill
11c     sarl    RDI, #31
11f     movl    R9, R11 # l2i
122     subl    R9, RDI # int
125     addl    R9, RCX # int
128     movl    RCX, R13        # spill
12b     addl    RCX, #2 # int
12e     movslq  RAX, R9 # i2l
131     movslq  R11, RCX        # i2l
134     movl    RDI, RCX        # spill
136     sarl    RDI, #31
139     imulq   R11, R11, #1431655766   # long
140     movl    RSI, R13        # spill
143     incl    RSI     # int
145     sarq    R11, #32
149     movslq  R9, RSI # i2l
14c     movl    R11, R11        # l2i
14f     subl    R11, RDI        # int
152     addl    R11, RCX        # int
155     imulq   R9, R9, #1431655766     # long
15c     movslq  R11, R11        # i2l
15f     sarq    R9, #32
163     sarl    RSI, #31
166     movl    R9, R9  # l2i
169     subl    R9, RSI # int
16c     addl    R9, R13 # int
16f     incl    R9      # int
172     movslq  R9, R9  # i2l
175     movq    [RBX + #24 + RDX << #3], R9     # long
:
17a     movq    [RBX + #32 + RDX << #3], R11    # long
17f     movq    [RBX + #40 + RDX << #3], RAX    # long
184     addl    R13, #4 # int
188     cmpl    R13, R8
18b     jl     B10      # loop end  P=1.000000 C=48457.000000

... so not only is the division optimized, the loop is 4-way unrolled
and pipelined.  The question is whether this kind of heavyeweight
optimization is really appropriate for a Forth system,

Andrew.

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

#34783

From"WJ" <w_a_x_man@yahoo.com>
Date2014-12-05 05:46 +0000
Message-ID<m5rgrj$7gt$1@dont-email.me>
In reply to#29575
Melzzzzz wrote:

> bmaxa@maxa:~/examples/forth$ cat Cumul.java
> public class Cumul {
> 
> 	public static void sum(long[] data) {
> 		if(data.length == 0) return;
> 		for( int i = 1; i !=  data.length; ++i)
> 		  data[i] += data[i-1];
> 	}
> 
> 
> 
>     public static long[]  givemeanarray(int N) {
>     	long[] bigarray = new long[N];
>         for(int k = 0; k<N; ++k)
>           bigarray[k] = k+k/3;
>         return bigarray;
>      }
>      
>      public static void test(int N) {
>       long bef = System.currentTimeMillis();
>       long[] data = givemeanarray(N);
>       long aft = System.currentTimeMillis();
>       System.out.println(N/(1000.0 * (aft-bef)));
>       bef = System.currentTimeMillis();
>       sum(data);
>       aft = System.currentTimeMillis();
>       System.out.println(N/(1000.0 * (aft-bef)));
>       System.out.println(data[N-1]);
>      }
>      
>      public static void main(String[] args) {
>      	test( 50 * 1000 * 1000 );
>      }
> 
> 
> }

Free Pascal:

type v64 = array of int64;

function give_an_array( n:longint ): v64;
var v : v64;
    i : longint;
begin
  setLength(v,n);
  for i := 0 to n-1 do   v[i] := i + i div 3;
  exit(v)
end;

procedure sum( data : v64);
var i : longint;
begin
  for i := 1 to length(data)-1 do   data[i] += data[i-1]
end;

const n = 50*1000*1000;
var vec : v64;
begin
  vec := give_an_array( n );
  sum( vec );
  writeln( vec[n-1] )
end.

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

#34858

From"WJ" <w_a_x_man@yahoo.com>
Date2014-12-10 09:50 +0000
Message-ID<m6951l$tva$1@dont-email.me>
In reply to#29575
Melzzzzz wrote:

> Seems that Java bits Forth in optimizing tight loops. Eg division by
> constant optimization is performed automatically.
> 
> Idea for bench is from:
> http://lemire.me/blog/archives/2012/07/23/is-cc-worth-it/
> 
> bmaxa@maxa:~/examples/forth$ time gforth-fast -m 400M cumul.fs -e bye
> 62.1816300541229 
> 116.054248397871 
> 1666666616666667 
> 
> real	0m1.249s
> user	0m1.225s
> sys	0m0.023s
> 
> bmaxa@maxa:~/examples/forth$ time java Cumul
> 378.7878787878788
> 1190.4761904761904
> 1666666616666667
> 
> real	0m0.247s
> user	0m0.215s
> sys	0m0.042s
> 
> bmaxa@maxa:~/examples/forth$ cat cumul.fs
> : N 50000000 ;
> 
> : init_cumul
> 	N 0 ?do
> 	i 3 / i +
> 	over i cells + !
> 	loop ;
> 	
> : cumul 
> 	dup @ 
> 	N 1 ?do
> 	over i cells + @
> 	+ 2dup
> 	swap i cells + !
> 	loop 
> 	drop ;
> : bench 2dup utime 2over execute drop utime 
> 	2swap d- d>f N s>f fswap f/ f. cr 2drop drop ;
> 
> N cells allocate throw
> ' init_cumul bench
> ' cumul bench
> dup N 1 - cells + @ . cr
> free throw
> 
> 
> bmaxa@maxa:~/examples/forth$ cat Cumul.java
> public class Cumul {
> 
> 	public static void sum(long[] data) {
> 		if(data.length == 0) return;
> 		for( int i = 1; i !=  data.length; ++i)
> 		  data[i] += data[i-1];
> 	}
> 
> 
> 
>     public static long[]  givemeanarray(int N) {
>     	long[] bigarray = new long[N];
>         for(int k = 0; k<N; ++k)
>           bigarray[k] = k+k/3;
>         return bigarray;
>      }
>      
>      public static void test(int N) {
>       long bef = System.currentTimeMillis();
>       long[] data = givemeanarray(N);
>       long aft = System.currentTimeMillis();
>       System.out.println(N/(1000.0 * (aft-bef)));
>       bef = System.currentTimeMillis();
>       sum(data);
>       aft = System.currentTimeMillis();
>       System.out.println(N/(1000.0 * (aft-bef)));
>       System.out.println(data[N-1]);
>      }
>      
>      public static void main(String[] args) {
>      	test( 50 * 1000 * 1000 );
>      }
> 
> 
> }

OCaml:

(*
  Compile with
  ocamlopt -unsafe bigarray.cmxa partial_sum.ml -o partial_sum.exe
*)


open Bigarray

let t = Sys.time ()

let n = 50_000_000
let v = Array1.create float64 c_layout n ;;
for i = 0 to n-1 do
  Array1.set v i (float_of_int (i + i/3))
done ;;
for i = 1 to n-1 do
  v.{i} <- v.{i} +. v.{i-1}
done ;;
Printf.printf "%.3f  %.0f\n" (Sys.time() -. t) v.{n-1}

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

#34863

From"WJ" <w_a_x_man@yahoo.com>
Date2014-12-10 18:29 +0000
Message-ID<m6a3ec$nqc$1@dont-email.me>
In reply to#34858
WJ wrote:

> Melzzzzz wrote:
> 
> > Seems that Java bits Forth in optimizing tight loops. Eg division by
> > constant optimization is performed automatically.
> > 
> > Idea for bench is from:
> > http://lemire.me/blog/archives/2012/07/23/is-cc-worth-it/
> > 
> > bmaxa@maxa:~/examples/forth$ time gforth-fast -m 400M cumul.fs -e bye
> > 62.1816300541229 
> > 116.054248397871 
> > 1666666616666667 
> > 
> > real	0m1.249s
> > user	0m1.225s
> > sys	0m0.023s
> > 
> > bmaxa@maxa:~/examples/forth$ time java Cumul
> > 378.7878787878788
> > 1190.4761904761904
> > 1666666616666667
> > 
> > real	0m0.247s
> > user	0m0.215s
> > sys	0m0.042s
> > 
> > bmaxa@maxa:~/examples/forth$ cat cumul.fs
> > : N 50000000 ;
> > 
> > : init_cumul
> > 	N 0 ?do
> > 	i 3 / i +
> > 	over i cells + !
> > 	loop ;
> > 	
> > : cumul 
> > 	dup @ 
> > 	N 1 ?do
> > 	over i cells + @
> > 	+ 2dup
> > 	swap i cells + !
> > 	loop 
> > 	drop ;
> > : bench 2dup utime 2over execute drop utime 
> > 	2swap d- d>f N s>f fswap f/ f. cr 2drop drop ;
> > 
> > N cells allocate throw
> > ' init_cumul bench
> > ' cumul bench
> > dup N 1 - cells + @ . cr
> > free throw
> > 
> > 
> > bmaxa@maxa:~/examples/forth$ cat Cumul.java
> > public class Cumul {
> > 
> > 	public static void sum(long[] data) {
> > 		if(data.length == 0) return;
> > 		for( int i = 1; i !=  data.length; ++i)
> > 		  data[i] += data[i-1];
> > 	}
> > 
> > 
> > 
> >     public static long[]  givemeanarray(int N) {
> >     	long[] bigarray = new long[N];
> >         for(int k = 0; k<N; ++k)
> >           bigarray[k] = k+k/3;
> >         return bigarray;
> >      }
> >      
> >      public static void test(int N) {
> >       long bef = System.currentTimeMillis();
> >       long[] data = givemeanarray(N);
> >       long aft = System.currentTimeMillis();
> >       System.out.println(N/(1000.0 * (aft-bef)));
> >       bef = System.currentTimeMillis();
> >       sum(data);
> >       aft = System.currentTimeMillis();
> >       System.out.println(N/(1000.0 * (aft-bef)));
> >       System.out.println(data[N-1]);
> >      }
> >      
> >      public static void main(String[] args) {
> >      	test( 50 * 1000 * 1000 );
> >      }
> > 
> > 
> > }
> 
> OCaml:
> 
> (*
>   Compile with
>   ocamlopt -unsafe bigarray.cmxa partial_sum.ml -o partial_sum.exe
> *)
> 
> 
> open Bigarray
> 
> let t = Sys.time ()
> 
> let n = 50_000_000
> let v = Array1.create float64 c_layout n ;;
> for i = 0 to n-1 do
>   Array1.set v i (float_of_int (i + i/3))
> done ;;
> for i = 1 to n-1 do
>   v.{i} <- v.{i} +. v.{i-1}
> done ;;
> Printf.printf "%.3f  %.0f\n" (Sys.time() -. t) v.{n-1}

Of course, the same result can be produced with no array.

let t = Sys.time ()
let n = 50_000_000 ;;

let rec run sum i =
  if i < n then
    run (float (i + i/3) +. sum) (succ i)
  else
    (Printf.printf "%.0f  %f\n" sum (Sys.time() -. t))
in run 0. 1 ;;

[toc] | [prev] | [standalone]

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

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

csiph-web