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

Ruby/Forth challenge for WJ

Started by	Chris Curl <ccurl609@gmail.com>
First post	2016-01-12 07:47 -0800
Last post	2016-02-11 07:39 -0800
Articles	20 on this page of 127 — 28 participants

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

  Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 07:47 -0800
    Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-12 16:25 +0000
      Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-12 10:45 -0600
      Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 08:46 -0800
        Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-12 11:57 -0500
          Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 09:22 -0800
            Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-12 21:04 -0800
              Re: Ruby/Forth challenge for WJ Ron Aaron <rambamist@gmail.com> - 2016-01-13 07:59 +0200
        Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-12 19:42 +0000
          Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 12:53 -0800
      Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-13 15:45 +0000
        Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-13 13:44 -0500
          Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 11:39 -0800
            Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-14 05:01 +0100
            Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-14 12:28 +0000
    Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 09:50 -0800
    Re: Ruby/Forth challenge for WJ Pablo Hugo Reda <pabloreda@gmail.com> - 2016-01-12 11:50 -0800
    Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 12:30 -0800
    Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 12:43 -0800
      Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-12 21:01 +0000
      Re: Ruby/Forth challenge for WJ peter.m.falth@gmail.com - 2016-01-12 15:00 -0800
        Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 16:13 -0800
          Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-12 16:22 -0800
          Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 16:24 -0800
            Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-12 17:46 -0800
              Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 18:39 -0800
                Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-13 13:05 -0800
                  Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-14 04:33 +0100
                    Re: Ruby/Forth challenge for WJ m.a.m.hendrix@tue.nl - 2016-01-14 03:27 -0800
                      Re: Ruby/Forth challenge for WJ peter.m.falth@gmail.com - 2016-01-14 04:42 -0800
                      Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-14 13:03 +0000
                  Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 21:17 -0800
                    Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-13 21:44 -0800
                  Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-14 10:57 +0000
                    Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-14 12:20 -0800
                      Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-14 13:57 -0800
                        Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-14 14:22 -0800
                          Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-14 16:14 -0800
                          Re: Ruby/Forth challenge for WJ Melzzzzz <mel@zzzzz.com> - 2016-01-15 03:05 +0100
                        Re: Ruby/Forth challenge for WJ Waldek Hebisch <hebisch@antispam.uni.wroc.pl> - 2016-01-15 00:41 +0000
                      Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-15 16:22 +0000
                        Re: Ruby/Forth challenge for WJ mhx@iae.nl (Marcel Hendrix) - 2016-01-16 11:44 +0200
                          Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-16 04:49 -0800
                            Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-16 15:05 +0000
                              Re: Ruby/Forth challenge for WJ m.a.m.hendrix@tue.nl - 2016-01-18 03:26 -0800
                                Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-18 12:48 +0000
                                  Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-19 22:26 +0100
                                    Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-20 03:05 -0800
                                      Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-20 21:00 +0100
                                        Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-20 15:57 -0800
                                          Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-21 23:02 +0100
                                            Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-22 01:25 +0000
                                              Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-21 18:05 -0800
                                              Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-21 22:03 -0800
                                    Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-20 13:40 +0000
                              Re: Ruby/Forth challenge for WJ m.a.m.hendrix@tue.nl - 2016-01-18 03:55 -0800
                            Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-23 15:13 -0600
                              Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-24 00:55 -0800
                                Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 04:48 -0600
                                  Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-25 12:39 +0000
                                    Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 08:05 -0600
                                      Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-25 16:40 +0000
                                  Re: Ruby/Forth challenge for WJ Mark Wills <markwills1970@gmail.com> - 2016-01-25 04:44 -0800
                                  Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-25 14:01 +0000
                                    Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 08:08 -0600
                                      Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 11:56 -0600
                                        Re: Ruby/Forth challenge for WJ "Elizabeth D. Rather" <erather@forth.com> - 2016-01-25 11:12 -1000
                                          Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-26 03:33 -0600
                                          Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-26 11:09 +0000
                                        Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-26 11:06 +0000
                                          Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-26 07:45 -0600
                                            Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-26 16:46 +0000
                                              Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-26 11:16 -0600
                                                Object-oriented Forth (was: Ruby/Forth challenge for WJ) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-27 14:13 +0000
                                                  Re: Object-oriented Forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-27 10:33 -0600
                                                    Re: Object-oriented Forth hughaguilar96@gmail.com - 2016-01-27 08:45 -0800
                                                      Re: Object-oriented Forth Chris Curl <ccurl609@gmail.com> - 2016-01-27 09:14 -0800
                                                        Re: Object-oriented Forth hughaguilar96@gmail.com - 2016-01-29 21:57 -0800
                                                          Re: Object-oriented Forth Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-30 10:58 +0000
                                                          Re: Object-oriented Forth Chris Curl <ccurl609@gmail.com> - 2016-01-30 09:38 -0800
                                                            Re: Object-oriented Forth Coos Haak <chforth@hccnet.nl> - 2016-01-30 20:39 +0100
                                          Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-26 15:56 +0100
                                            Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-26 20:46 +0000
                                    Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-25 22:27 +0100
                                      Re: Ruby/Forth challenge for WJ Roelf Toxopeus <rt4all@notthis.hetnet.nl> - 2016-01-28 14:20 +0100
                                      Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-28 08:06 -0600
                                        Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-28 16:14 +0100
                                          Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-28 10:32 -0600
                                            Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-28 17:26 +0000
                                              Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-28 12:13 -0600
                                          Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-29 11:07 +0000
                                            Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-29 21:18 +0100
                          Re: Ruby/Forth challenge for WJ Tessa Bonting <tessa.bonting@gmail.com> - 2016-01-16 06:24 -0800
            Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-13 05:21 -0500
              Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-13 05:36 -0500
              Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 10:33 -0800
                Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-14 01:37 -0500
    Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 13:45 -0800
    Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 13:55 -0800
      Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 14:34 -0800
      Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-12 19:00 -0500
        Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 16:49 -0800
          Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-12 22:18 -0500
    Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-12 14:31 -0800
      Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 16:05 -0800
    Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-01-13 07:58 +0000
      Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-13 05:17 -0500
        Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 12:36 -0800
          Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-13 12:53 -0800
          Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-14 06:50 -0600
      Re: Ruby/Forth challenge for WJ Julian Fondren <julian.fondren@gmail.com> - 2016-01-13 05:36 -0800
      Re: Ruby/Forth challenge for WJ lehs <skydda.barnen@gmail.com> - 2016-01-13 11:59 -0800
      Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-21 21:08 -0800
      Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 13:36 +0000
      Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 13:48 +0000
        Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-02-09 12:02 -0800
      Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 13:58 +0000
      Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 14:30 +0000
      Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-14 15:35 +0000
        Re: Ruby/Forth challenge for WJ franck.bensusan@gmail.com - 2016-02-14 08:50 -0800
          Re: Ruby/Forth challenge for WJ Julian Fondren <julian.fondren@gmail.com> - 2016-02-14 20:09 -0800
            Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-02-15 08:52 -0800
      Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-14 21:31 +0000
    Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-01-14 22:49 +0000
      Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-14 15:31 -0800
        Re: Ruby/Forth challenge for WJ Melzzzzz <mel@zzzzz.com> - 2016-01-15 06:55 +0100
    Re: Ruby/Forth challenge for WJ djc <ciesinger@gmx.net> - 2016-02-11 07:39 -0800

Page 3 of 7 — ← Prev page 1 2 [3] 4 5 6 7 Next page →

#44893

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-01-15 16:22 +0000
Message-ID	<2016Jan15.172237@mips.complang.tuwien.ac.at>
In reply to	#44878

mhx@iae.nl writes:
>$01224600  : do-test
>$0122460A  mov           rcx, $1B350050 d#
>$01224611  mov           rbx, $0FFFFFFF d#
>$01224618  call          (FOR) offset NEAR
>$01224622  nop
>$01224623  nop
>$01224624  mov           rcx, [rbp 0 +] qword
>$01224628  movzx         rdi, [rbx] byte
>$0122462C  add           [rdi*8 $01220F30 +] qword, 1 b#
>$01224635  lea           rbx, [rbx 1 +] qword
>$01224639  sub           rcx, 1 b#
>$0122463D  nop
>$0122463E  jae           $01224628 offset NEAR
>$01224644  add           rbp, #24 b#
>$01224648  ;
>
>Both do-tests need the same amount of time,
>although the "sub [rbp 0 +] qword, 1 b#" instruction is
>avoided. (I should've stuck to the tight loop, for 
>comparison, sorry about that).
>
>I tried pre-filling "memory" with '1': no change.
>I allotted 256MB at HERE instead of ALLOCATE: no change.

If you fill everything with the same byte, you have the same kind of
recurrence in the instruction at $0122462C, and of course you get the
same result.

Here I have a version that initializes the array in a way that should
reduce this effect:

create counts 256 cells allot
256 1024 * 1024 * constant a-size
a-size allocate throw constant a
: init-a ( -- )
  a a-size bounds ?do
    $00204060 i ! $80a0c0e0 i cell+ !
  2 cells +loop ;
: do-test 
  a a-size bounds ?do
    1 counts i c@ cells + +!
  loop ;
init-a
do-test

I tried it on vfxlin-4.71, but, alas, it has the same loop variable
recurrence as iForth.  Here's the inner loop:

( 080C0E10    8B1424 )                MOV       EDX, [ESP]
( 080C0E13    0FB612 )                MOVZX     EDX, Byte Ptr 0 [EDX]
( 080C0E16    830495F0080C0801 )      ADD       [080C08F0+EDX*4], 01
( 080C0E1E    83042401 )              ADD       [ESP], 01
( 080C0E22    8344240401 )            ADD       [ESP+04], 01
( 080C0E27    71E7 )                  JNO       080C0E10

Note that you should vary the code above for 64-bit systems, e.g.:

: init-a ( -- )
  a a-size bounds ?do
    $0020406080a0c0e0 i ! $1030507090b0d0f0 i cell+ !
  2 cells +loop ;

With random data, do-test performance should be close to the
performance of using this initialization; but better measure this:
AFAIK there a hardware predictor that predicts whether a load is
independent of a previous store, and this might be a case where its
performance and the performance of the fallback (what is done when it
predicts independence, but there actually is a dependence) may be
relevant.

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

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

#44905

From	mhx@iae.nl (Marcel Hendrix)
Date	2016-01-16 11:44 +0200
Message-ID	<78599219028399@frunobulax.edu>
In reply to	#44893

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge 
>mhx@iae.nl writes:
[..]
>>I tried pre-filling "memory" with '1': no change.
>>I allotted 256MB at HERE instead of ALLOCATE: no change.
> If you fill everything with the same byte, you have the same kind of
> recurrence in the instruction at $0122462C, and of course you get the
> same result.

> Here I have a version that initializes the array in a way that should
> reduce this effect:

> create counts 256 cells allot
> 256 1024 * 1024 * constant a-size
> a-size allocate throw constant a
> : init-a ( -- )
>  a a-size bounds ?do
>    $00204060 i ! $80a0c0e0 i cell+ !
>  2 cells +loop ;
> : do-test 
>   a a-size bounds ?do
>    1 counts i c@ cells + +!
>  loop ;
> init-a
> do-test

[..]

> With random data, do-test performance should be close to the
> performance of using this initialization; but better measure this:
> AFAIK there a hardware predictor that predicts whether a load is
> independent of a previous store, and this might be a case where its
> performance and the performance of the fallback (what is done when it
> predicts independence, but there actually is a dependence) may be
> relevant.

The result of pattern pre-filling is as follows:

: do-test 
  CR TIMER-RESET
    a a-size bounds ?do
      1 counts i c@ cells + +!
    loop 
  ." \ 0: " .ELAPSED ; do-test
\ 0: 0.459 seconds elapsed. ok

As expected, in high-level it makes no difference.

I dropped to Forth assembler as the problem became
too tedious otherways. The following does in 
assembly language what I tried to express in Forth:

CODE (do-test1) ( -- )
	a-size d# -> rcx mov,
	a d# -> rax mov, 
	BEGIN,
	  [rax] byte -> rdx movzx, 
	  rax inc, 
	  1 b# -> [_ +rdx *8 counts +] qword add,
	  1 b# -> rcx sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  

: do-test 
  CR TIMER-RESET
    (do-test1)
  ." \ 3: " .ELAPSED ; 
\ 3: 0.142 seconds elapsed.

... and this shows that your analysis is fully correct,
we get a run-time as fast as gcc accomplished.

I tried unrolling the loop -- it made no difference.
I removed your initialization -- the run-time dropped
back to 415 ms, as expected.

This means that we should try to minimize certain types
of memory access. The high-level Forth has the same
machine code as shown above, but it additionally 
decrements a stack variable, increasing the run-time 
by a factor of 3. Very annoying in the context of 
Forth. 

It is interesting that the effects of a) not 
initializing and b) having a stack variable do 
not add up. Either one causes the 3 times 
slowdown, having both does not give a 6 times 
slow-down.
I did some more experiments that simply
increment a variable in different locations.

First the straightforward one: keep it in a 
register. As expected this is fast (but
not unbeatable, see (do-count10)).

CODE (do-count1) ( -- ) \ fast!
	a-size d# -> rcx mov,
	BEGIN,
	  1 b# -> rcx sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  
\ count1  : 0.069 seconds elapsed.


The next one is very strange. The
variable is kept in the counts array. After the
memory decrement a variable amount of NOPs
is added and the run-speed is measured. 
At 10 NOPs there is a sweet point: 280 ms. 
It's too slow to be of real interest.
Maybe this indicates problems with jump 
prediction.

: NOPS, ( u -- ) 0 ?DO $90 C, LOOP ;

CODE (do-count2) ( -- ) \ slow
    counts d# -> rax  mov,
    a-size d# -> [rax] mov,
    BEGIN,
	1 b# -> [rax] sub,
	#10 NOPS,
\		\ no nops: 519 ms
\	nop, 	\ 517 ms
\	nop, 	\ 464 ms
\	nop, 	\ 517 ms
\	nop, 	\ 492 ms
\	nop, 	\ 418 ms
\	nop, 	\ 417 ms
\	nop, 	\ 415 ms
\ 	nop, 	\ 452 ms
\ 	nop, 	\ 439 ms
\	nop, 	\ 280 ms
\	nop, 	\ 284 ms
\	nop,  	\ 295 ms
\ 	nop, 	\ 299 ms
\	nop, 	\ 415 ms
\	nop, 	\ 394 ms
\	nop,  	\ 346 ms
\ 	nop, 	\ 358 ms
\	nop, 	\ 422 ms
\	nop, 	\ 420 ms
\	nop,  	\ 415 ms
\ 	nop, 	\ 419 ms
\	nop, 	\ 483 ms
\	nop, 	\ 486 ms
\	nop,  	\ 486 ms
\ 	nop, 	\ 490 ms
\	nop, 	\ 555 ms
\	nop, 	\ 555 ms
\	nop,  	\ 567 ms
\	32 nops 0.696 s
\ 	64 nops 1.256 s
	0=, 
    UNTIL,
    rbx jmp,
END-CODE  
\ count2  : 0.280 seconds elapsed.

Next I put the variable in the Forth return stack.
I was relieved to see that this is not very much 
worse than other locations (read on). My fear
that executable stack memory pages are worse than
R/W ones appears not be true.

CODE (do-count3) ( -- ) \ slow
	a-size d# -> [rbp -8 +] mov,
	BEGIN,
	  1 b# -> [rbp -8 +] sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  
\ count3  : 0.516 seconds elapsed.


This one just tries a different sequence 
(than do-count3) to update the stack variable. 
It is all the same to the CPU.

CODE (do-count4) ( -- )
	a-size d# -> [rbp -8 +] mov,
    	BEGIN,
          [rbp -8 +] -> rax mov,
	  1 b# -> rax sub,
	  rax -> [rbp -8 +] mov, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  
\ count4  : 0.511 seconds elapsed.

This shows yet another sequence. Don't
bother, the CPU couldn't care less.

CODE (do-count5) ( -- )
	[rbp -8 +] -> rcx  lea,
	a-size d# -> [rcx] mov,
    	BEGIN,
          [rcx] -> rax mov,
	  1 b#  -> rax sub,
	  rax   -> [rcx] mov,  0=, 
	UNTIL,
	rbx jmp,
END-CODE  
\ count5  : 0.510 seconds elapsed.

SIB addressing: it is as fast as the 
old stuff, the CPU doesn't mind (any more).

CODE (do-count6) ( -- )
	a-size d# -> [_ counts +] mov,
    BEGIN,
        1 b# -> [_ counts +] sub,
0=, UNTIL,
	rbx jmp,
END-CODE  
\ count5  : 0.510 seconds elapsed.

Very conventional: no change.

CODE (do-count7) ( -- )
	a-size d# -> counts offset mov,
    	BEGIN,
          1 b# -> counts offset sub, 0=, 
        UNTIL,
	rbx jmp,
END-CODE  
\ count5  : 0.524 seconds elapsed.

This is a variant of (do-count2). It is
a bit faster although it has two jumps.
Being faster might also be because it is
assembled at a different memory address.

CODE (do-count8a) ( -- ) \ has 2 jumps
	a      d# ->  rax  mov,
	a-size d# -> [rax] mov,
	BEGIN,
	  1 b# -> [rax] sub,  0<>,
	WHILE,	
	REPEAT,
	rbx jmp,
END-CODE  
\ count8a : 0.425 seconds elapsed.


Spreading out the code, worse.

CODE (do-count8b) ( -- ) \ has 2 jumps and extra fetch
	a      d# ->  rax  mov,
	a-size d# -> [rax] mov,
	BEGIN,
	  0 b# -> [rax] cmp, 0<>,
	WHILE,	
	  1 b# -> [rax] sub, 
	REPEAT,
	rbx jmp,
END-CODE  
\ count8b : 0.475 seconds elapsed.

Deliberately bad code. The CPU couldn't care less.

CODE (do-count8c) ( -- ) \ has 2 jumps and 2 extra fetches
	a      d# ->  rax  mov,
	a-size d# -> [rax] mov,
	BEGIN,
	  [rax] -> rcx mov, 
	  0 b# -> [rax] cmp, 0<>,
	WHILE,	
	  1 b# -> [rax] sub, 
	REPEAT,
	rbx jmp,
END-CODE  
\ count8c : 0.500 seconds elapsed.

The fact that the variable is in a 
register does not mean that jumps 
are free (see (do-count1) which only has
a single jump and is twice faster).

CODE (do-count8d) ( -- ) \ fast!
	a-size d# -> rax mov,
	BEGIN,
	  rax -> rax or, 0<>,
	WHILE,	
	  [rax -1 +] -> rax lea, 
	REPEAT,
	rbx jmp,
END-CODE  
\ count8d : 0.138 seconds elapsed.

This shows that loop unrolling is effective, 
so even the single jump is costly.
Note that we try to prevent hitting the
same memory location here.

CODE (do-count9) ( -- ) 
	counts d#     -> rax mov,
	a-size 8 / d# -> rcx mov,
	rcx  -> [rax   0 +] mov,
	rcx  -> [rax   8 +] mov,
	rcx  -> [rax #16 +] mov,
	rcx  -> [rax #24 +] mov,
	rcx  -> [rax #32 +] mov,
	rcx  -> [rax #40 +] mov,
	rcx  -> [rax #48 +] mov,
	rcx  -> [rax #56 +] mov,
	BEGIN,
	  1 b# -> [rax   0 +] sub,
	  1 b# -> [rax   8 +] sub,
	  1 b# -> [rax #16 +] sub,
	  1 b# -> [rax #24 +] sub,
	  1 b# -> [rax #32 +] sub,
	  1 b# -> [rax #40 +] sub,
	  1 b# -> [rax #48 +] sub,
	  1 b# -> [rax #56 +] sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  
\ count9  : 0.069 seconds elapsed.

Hitting the same memory location is
not the problem ((do-count9)), it appears 
that the jump is eating the time. This
variant is faster than count9 because it
only has one jump.

CODE (do-count10) ( -- ) 
	counts d# -> rax mov,
	a-size 8 / d# -> rcx mov,
	rcx -> [rax 0 +] mov,
    BEGIN,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
0=, UNTIL,
	rbx jmp,
END-CODE  
\ count10 : 0.054 seconds elapsed.


I think that this exercise proves that

1) The stack is not different from the
dictionary or allocated memory (for variable
storage).

2) Hitting the same memory location all of the
time is not a problem (it happens a lot in
many programs so it may have received close
engineering attention). What hurts is tight
loops. Tight loops must be unrolled not because
it makes code faster, but because not
unrolling makes the code slower :-)

3) R-M-W code sequences should get special
attention, as Anton's analysis (verified by 
experiment) shows. The solution is not 
necessarily to keep everything in registers
all of the time, as the do-count exercise
shows. 

Comments invited.

-marcel

-- full source code, needs hand editing ----------

ANEW -strangefruit

NEEDS -assemble

HERE #256 cells allot =: counts
#256 #1024 * #1024 * constant a-size
a-size allocate ?allocate =: a

: init-a ( -- )
  a a-size bounds ?do
    $0020406080a0c0e0 i ! $1030507090b0d0f0 i cell+ !
  2 cells +loop ;

init-a FORGET init-a



0 [IF]

: do-test 
  CR TIMER-RESET
    a a-size bounds ?do
      1 counts i c@ cells + +!
    loop 
  ." \ 0: " .ELAPSED ; do-test

[THEN]

0 [IF]

: do-test 
  CR TIMER-RESET
    a  a-size 1- FOR  C@+  counts []CELL  1 swap +!  NEXT  DROP  
  ." \ 1: " .ELAPSED ; do-test

[THEN]

0 [IF]

: do-test 
  CR TIMER-RESET
    a a-size
    BEGIN  DUP 1- SWAP
    WHILE  SWAP  C@+  counts []CELL  1 swap +!  SWAP 
    REPEAT
    2DROP
  ." \ 2: " .ELAPSED ; do-test

[THEN]

1 [IF]

CODE (do-count1) ( -- ) \ fast!
	a-size d# -> rcx mov,
	BEGIN,
	  1 b# -> rcx sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  

: NOPS, ( u -- ) 0 ?DO $90 C, LOOP ;

CODE (do-count2) ( -- ) \ slow
    counts d# -> rax  mov,
    a-size d# -> [rax] mov,
    BEGIN,
	1 b# -> [rax] sub,
	1 NOPS,
\		\ no nops: 519 ms
\	nop, 	\ 517 ms
\	nop, 	\ 464 ms
\	nop, 	\ 517 ms
\	nop, 	\ 492 ms
\	nop, 	\ 418 ms
\	nop, 	\ 417 ms
\	nop, 	\ 415 ms
\ 	nop, 	\ 452 ms
\ 	nop, 	\ 439 ms
\	nop, 	\ 280 ms
\	nop, 	\ 284 ms
\	nop,  	\ 295 ms
\ 	nop, 	\ 299 ms
\	nop, 	\ 415 ms
\	nop, 	\ 394 ms
\	nop,  	\ 346 ms
\ 	nop, 	\ 358 ms
\	nop, 	\ 422 ms
\	nop, 	\ 420 ms
\	nop,  	\ 415 ms
\ 	nop, 	\ 419 ms
\	nop, 	\ 483 ms
\	nop, 	\ 486 ms
\	nop,  	\ 486 ms
\ 	nop, 	\ 490 ms
\	nop, 	\ 555 ms
\	nop, 	\ 555 ms
\	nop,  	\ 567 ms
\	32 nops 0.696 s
\ 	64 nops 1.256 s
	0=, 
    UNTIL,
    rbx jmp,
END-CODE  

CODE (do-count3) ( -- ) \ slow
	a-size d# -> [rbp -8 +] mov,
	BEGIN,
	  1 b# -> [rbp -8 +] sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  

CODE (do-count4) ( -- )
	a-size d# -> [rbp -8 +] mov,
    	BEGIN,
          [rbp -8 +] -> rax mov,
	  1 b# -> rax sub,
	  rax -> [rbp -8 +] mov, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  

CODE (do-count5) ( -- )
	[rbp -8 +] -> rcx  lea,
	a-size d# -> [rcx] mov,
    	BEGIN,
          [rcx] -> rax mov,
	  1 b#  -> rax sub,
	  rax   -> [rcx] mov,  0=, 
	UNTIL,
	rbx jmp,
END-CODE  

CODE (do-count6) ( -- )
	a-size d# -> [_ counts +] mov,
    BEGIN,
        1 b# -> [_ counts +] sub,
0=, UNTIL,
	rbx jmp,
END-CODE  

CODE (do-count7) ( -- )
	a-size d# -> counts offset mov,
    	BEGIN,
          1 b# -> counts offset sub, 0=, 
        UNTIL,
	rbx jmp,
END-CODE  

CODE (do-count8a) ( -- ) \ has 2 jumps, slow but not slower
	a      d# ->  rax  mov,
	a-size d# -> [rax] mov,
	BEGIN,
	  1 b# -> [rax] sub,  0<>,
	WHILE,	
	REPEAT,
	rbx jmp,
END-CODE  

CODE (do-count8b) ( -- ) \ has 2 jumps and extra fetch, slow but not slower
	a      d# ->  rax  mov,
	a-size d# -> [rax] mov,
	BEGIN,
	  0 b# -> [rax] cmp, 0<>,
	WHILE,	
	  1 b# -> [rax] sub, 
	REPEAT,
	rbx jmp,
END-CODE  

CODE (do-count8c) ( -- ) \ has 2 jumps and 2 extra fetches, bit slower 
	a      d# ->  rax  mov,
	a-size d# -> [rax] mov,
	BEGIN,
	  [rax] -> rcx mov, 
	  0 b# -> [rax] cmp, 0<>,
	WHILE,	
	  1 b# -> [rax] sub, 
	REPEAT,
	rbx jmp,
END-CODE  

CODE (do-count8d) ( -- ) \ has 2 jumps, bit slower 
	a-size d# -> rax mov,
	BEGIN,
	  rax -> rax or, 0<>,
	WHILE,	
	  [rax -1 +] -> rax lea, 
	REPEAT,
	rbx jmp,
END-CODE  

CODE (do-count9) ( -- ) 
	counts d#     -> rax mov,
	a-size 8 / d# -> rcx mov,
	rcx  -> [rax   0 +] mov,
	rcx  -> [rax   8 +] mov,
	rcx  -> [rax #16 +] mov,
	rcx  -> [rax #24 +] mov,
	rcx  -> [rax #32 +] mov,
	rcx  -> [rax #40 +] mov,
	rcx  -> [rax #48 +] mov,
	rcx  -> [rax #56 +] mov,
    BEGIN,
	1 b# -> [rax   0 +] sub,
	1 b# -> [rax   8 +] sub,
	1 b# -> [rax #16 +] sub,
	1 b# -> [rax #24 +] sub,
	1 b# -> [rax #32 +] sub,
	1 b# -> [rax #40 +] sub,
	1 b# -> [rax #48 +] sub,
	1 b# -> [rax #56 +] sub,
0=, UNTIL,
	rbx jmp,
END-CODE  

CODE (do-count10) ( -- ) 
	counts d# -> rax mov,
	a-size 8 / d# -> rcx mov,
	rcx -> [rax 0 +] mov,
    BEGIN,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
	1 b# -> [rax] sub,
0=, UNTIL,
	rbx jmp,
END-CODE  

CODE (do-test1) ( -- )
	a-size d# -> rcx mov,
	a d# -> rax mov, 
	BEGIN,
	  [rax] byte -> rdx movzx, rax inc, 1 b# -> [_ +rdx *8 counts +] qword add,
	  1 b# -> rcx sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  

CODE (do-test2) ( -- )
	a-size d# -> rcx mov,
	a d# -> rax mov, 
	BEGIN,
	  [rax] byte -> rdx movzx, rax inc,
	  1 b# -> [_ +rdx *8 counts +] qword add,
  	  [rax] byte -> rdx movzx, rax inc, 
  	  1 b# -> [_ +rdx *8 counts +] qword add,
	  2 b# -> rcx sub, 0=, 
	UNTIL,
	rbx jmp,
END-CODE  


: do-test1 
  CR TIMER-RESET
    (do-test1)
  ." \ 3: " .ELAPSED ; do-test1

: do-test2 
  CR TIMER-RESET
    (do-test2)
  ." \ 4: " .ELAPSED ; do-test2

: DO-TESTS
  CR ." \ count1  : " TIMER-RESET  (do-count1)  .ELAPSED	
  CR ." \ count2  : " TIMER-RESET  (do-count2)  .ELAPSED	
  CR ." \ count3  : " TIMER-RESET  (do-count3)  .ELAPSED 
  CR ." \ count4  : " TIMER-RESET  (do-count4)  .ELAPSED 
  CR ." \ count5  : " TIMER-RESET  (do-count5)  .ELAPSED 
  CR ." \ count6  : " TIMER-RESET  (do-count6)  .ELAPSED 
  CR ." \ count7  : " TIMER-RESET  (do-count7)  .ELAPSED 
  CR ." \ count8a : " TIMER-RESET  (do-count8a) .ELAPSED
  CR ." \ count8b : " TIMER-RESET  (do-count8b) .ELAPSED
  CR ." \ count8c : " TIMER-RESET  (do-count8c) .ELAPSED
  CR ." \ count8d : " TIMER-RESET  (do-count8d) .ELAPSED
  CR ." \ count9  : " TIMER-RESET  (do-count9)  .ELAPSED 
  CR ." \ count10 : " TIMER-RESET  (do-count10) .ELAPSED ;

[THEN]

\ 0: 0.459 seconds elapsed.
\ 1: 0.456 seconds elapsed.
\ 2: 0.826 seconds elapsed.
\ 3: 0.142 seconds elapsed.
\ 4: 0.142 seconds elapsed.

\ FORTH> do-tests
\ count1  : 0.072 seconds elapsed.
\ count2  : 0.280 seconds elapsed.
\ count3  : 0.521 seconds elapsed.
\ count4  : 0.486 seconds elapsed.
\ count5  : 0.494 seconds elapsed.
\ count6  : 0.497 seconds elapsed.
\ count7  : 0.523 seconds elapsed.
\ count8a : 0.421 seconds elapsed.
\ count8b : 0.484 seconds elapsed.
\ count8c : 0.494 seconds elapsed.
\ count8d : 0.139 seconds elapsed.
\ count9  : 0.070 seconds elapsed.
\ count10 : 0.056 seconds elapsed.

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

#44907

From	mhx@iae.nl
Date	2016-01-16 04:49 -0800
Message-ID	<3f866042-67c5-419c-b921-963493c5ecf5@googlegroups.com>
In reply to	#44905

On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote:
> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge 
> >mhx@iae.nl writes:

When using iForth's parallel extensions there is the memory
dependence of threads access to take care of. It is not
pretty, but 4 times faster than C with openMP (48ms vs 190ms).

ANEW -strangefruit

NEEDS -threads

HERE #256 cells allot =: counts0
HERE #256 cells allot =: counts1
HERE #256 cells allot =: counts2
HERE #256 cells allot =: counts3

#256 #1024 * #1024 * constant a-size
a-size allocate ?allocate =: a

: init-a ( -- )
  a a-size bounds ?do
    $0020406080a0c0e0 i ! $1030507090b0d0f0 i cell+ !
  2 cells +loop ;

init-a FORGET init-a

: do-80 ( a1 -- a2 8 ) 
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!   
	C@+ counts0 []CELL  1 swap +!  
	8 ;

: do-81 ( a1 -- a2 8 ) 
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!   
	C@+ counts1 []CELL  1 swap +!  
	8 ;

: do-82 ( a1 -- a2 8 ) 
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!   
	C@+ counts2 []CELL  1 swap +!  
	8 ;
: do-83 ( a1 -- a2 8 ) 
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!   
	C@+ counts3 []CELL  1 swap +!  
	8 ;

: TH-RANGE ( a u n -- a2 hi lo ) ROT >R  TH-PART DUP R> +  -ROT ;

: do-test ( -- )
  CR TIMER-RESET
    PAR
      STARTP  a a-size 0 TH-RANGE ?do  do-80  +loop DROP  ENDP
      STARTP  a a-size 1 TH-RANGE ?do  do-81  +loop DROP  ENDP
      STARTP  a a-size 2 TH-RANGE ?do  do-82  +loop DROP  ENDP
      STARTP  a a-size 3 TH-RANGE ?do  do-83  +loop DROP  ENDP
    ENDPAR
    #256 0 DO  	
    		counts0 I CELL[] @  
    		counts1 I CELL[] @ + 
    		counts2 I CELL[] @ +  
    		counts3 I CELL[] @ +  
    		counts0 I CELL[] !
         LOOP
  ." \ 6: " .ELAPSED ; do-test

\ 0: 0.459 seconds elapsed.
\ 1: 0.456 seconds elapsed.
\ 2: 0.826 seconds elapsed.
\ 3: 0.142 seconds elapsed.
\ 4: 0.142 seconds elapsed.
\ 5: 0.184 seconds elapsed.
\ 6: 0.048 seconds elapsed.

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

#44910

From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Date	2016-01-16 15:05 +0000
Message-ID	<569a5c2e$0$23750$e4fe514c@news.xs4all.nl>
In reply to	#44907

mhx@iae.nl writes:

>On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote:
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge
>> >mhx@iae.nl writes:

>When using iForth's parallel extensions there is the memory
>dependence of threads access to take care of. It is not
>pretty, but 4 times faster than C with openMP (48ms vs 190ms).

>ANEW -strangefruit


>NEEDS -threads
<SNIP>
>\ 0: 0.459 seconds elapsed.
>\ 1: 0.456 seconds elapsed.
>\ 2: 0.826 seconds elapsed.
>\ 3: 0.142 seconds elapsed.
>\ 4: 0.142 seconds elapsed.
>\ 5: 0.184 seconds elapsed.
>\ 6: 0.048 seconds elapsed.

You do realize that all those benchmarks are pretty worthless without
mentioning the exact processor they are running on, don't you?
In this thread there were sufficient examples of unexpected results,
that were obtained by different processors.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#44941

From	m.a.m.hendrix@tue.nl
Date	2016-01-18 03:26 -0800
Message-ID	<f5f6d3e8-3c6b-4ccd-92a8-fe1e87ca5d01@googlegroups.com>
In reply to	#44910

On Saturday, January 16, 2016 at 4:05:20 PM UTC+1, Albert van der Horst wrote:
> mhx@iae.nl writes:
> 
> >On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote:
> >> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge
[..] 
> You do realize that all those benchmarks are pretty worthless without
> mentioning the exact processor they are running on, don't you?
> In this thread there were sufficient examples of unexpected results,
> that were obtained by different processors.

Benchmarks? Processors? You mean experiments and Forth 
implementations?

Only users of Forths with optimizing compilers will notice 
the effects uncovered in this thread. In a `standard' Forth
threaded-code implementation loops can not be so tight that
they can cause problems.

For readers with such Forths, it suffices to see the 
differences caused by high-level source code changes.
(I used the Forth assembler only to prevent having to 
guess what machine instructions are behind the high-level 
words.) For this purpose it suffices to know that I use
current hardware. Actually, the target CPU is mentioned
in the thread, but not for each and every re-run.

Of course, nowadays processing computers are more than 
fast enough and we don't need to worry about these silly 
details anymore. It must be true, because I have heard
people say it ever since I got my first desktop computer 
(a dual-drive P2000 from Philips).

-marcel

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

#44944

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-01-18 12:48 +0000
Message-ID	<2016Jan18.134817@mips.complang.tuwien.ac.at>
In reply to	#44941

m.a.m.hendrix@tue.nl writes:
>Only users of Forths with optimizing compilers will notice
>the effects uncovered in this thread. In a `standard' Forth
>threaded-code implementation loops can not be so tight that
>they can cause problems.

They can. A Haswell takes 2.3 cycles per NEXT on my threaded-code
microbenchmark <http://www.complang.tuwien.ac.at/forth/threading/>,
which is probably 2 cycles for the NEXT without payload, and 5 cycles
for the (LOOP)-like part of the microbenchmark (for a total of
9*2+1*5=23 cycles per iteration). With 2 cycles per NEXT, a 6 cycle
latency for the loop-counter recurrence can become critical (as in
"critical path").

From theory to practice:
perf stat -x " " -e cycles gforth-fast -e ": foo 1000000000 0 do loop ; foo bye"
6033467997 cycles
perf stat -x " " -e cycles vfxlin ": foo 1000000000 0 do loop ; foo bye"
6025464845 cycles
perf stat -x " " -e cycles gforth-fast --no-dynamic -e ": foo 1000000000 0 do loop ; foo bye"
6029161316 cycles

(on a Core i3-3227U (Ivy Bridge))

So, for the empty DO LOOP, using the recurrence through memory makes
vfxlin as slow as gforth-fast and gforth-fast --no-dynamic (the latter
being plain direct-threaded code).

I also noticed such effects when I microbenchmarked various locals and
DOES> implementations on Gforth for the last EuroForth paper. Many
differences had no effect on the performance of a Haswell, despite
significant differences in instruction count.

So I looked closer at the machine code that is executed, and found
that for these microbenchmarks, the critical path is often a
recurrence involving the virtual machine instruction pointer. The
microbenchmark involved a call in a loop, so the recurrence across the
whole loop pushed the IP to the return stack, loaded it back from the
return stack, loaded the start of the next loop iteration depending on
that, and performed a few IP increments in between. The one
microbenchmark that did not perform the call was a lot faster, almost
as fast as the empty loop (probably the performance was determined by
the recurrence of several IP increments (not present in the empty
loop) followed by loading the start of the next loop iteration (also
present in the empty loop).

All the other stuff the microbenchmarks did was performed by the
Haswell in parallel with this recurrence. I think that one reason why
the other stuff did not lead to longer recurrences is that these
benchmarks dropped anything computed on the data stack, so all the
data stack stuff became independent dependency chains (that can be
performed in parallel) rather than recurrences.

30 years ago, compilers ruined the Dhrystone 1.1 benchmark by noticing
that the results were not used and optimizing much of the computation
away. These days, we see similar effects from the hardware. The
computation is performed, but if the result is not used, it can
perform much more computation in parallel than you normally see in
useful applications.

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

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

#44952

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-01-19 22:26 +0100
Message-ID	<n7m9hc$e64$1@dont-email.me>
In reply to	#44944

Anton Ertl wrote:

> So, for the empty DO LOOP, using the recurrence through memory makes
> vfxlin as slow as gforth-fast and gforth-fast --no-dynamic (the latter
> being plain direct-threaded code).

Hm, we could use registers for the loop counters in Gforth on all non-
register-starved architectures, and use the new gcc5 arithmetic overflow 
intrinsics to produce the jump on overflow code, and then beat VFX ;-).  On 
the empty loop benchmark, at least.

BTW, bigForth uses registers and jump on overflow, so it's 6 times faster on 
Core i7-3517U:

% perf stat -x " " -e cycles bigforth -e ": foo 1000000000 0 do loop ; foo 
bye"
1031068581  cycles

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#44958

From	mhx@iae.nl
Date	2016-01-20 03:05 -0800
Message-ID	<f01d2696-1d84-4530-9ea1-3b821833dc3f@googlegroups.com>
In reply to	#44952

On Tuesday, January 19, 2016 at 10:26:43 PM UTC+1, Bernd Paysan wrote:
> Anton Ertl wrote:
> 
> > So, for the empty DO LOOP, using the recurrence through memory makes
> > vfxlin as slow as gforth-fast and gforth-fast --no-dynamic (the latter
> > being plain direct-threaded code).
> 
> Hm, we could use registers for the loop counters in Gforth on all non-
> register-starved architectures, and use the new gcc5 arithmetic overflow 
> intrinsics to produce the jump on overflow code, and then beat VFX ;-).  On 
> the empty loop benchmark, at least.
> 
> BTW, bigForth uses registers and jump on overflow, so it's 6 times faster on 
> Core i7-3517U:
> 
> % perf stat -x " " -e cycles bigforth -e ": foo 1000000000 0 do loop ; foo 
> bye"
> 1031068581  cycles
> 
> -- 
> Bernd Paysan
> "If you want it done right, you have to do it yourself"
> net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
> http://bernd-paysan.de/

Thanks for independently verifying the basic principle.

Could you also share what happens when there's more work in
that loop? You could use the byte counter with initialized 
main array further up in this thread, and unroll the loop a 
various number of times to see what happens.

-marcel

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

#44969

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-01-20 21:00 +0100
Message-ID	<n7oorm$po0$1@dont-email.me>
In reply to	#44958

mhx@iae.nl wrote:
> Thanks for independently verifying the basic principle.
> 
> Could you also share what happens when there's more work in
> that loop? You could use the byte counter with initialized
> main array further up in this thread, and unroll the loop a
> various number of times to see what happens.

Ok, based on this:

\ benchmark
[defined] buffer: 0= [IF]
    : buffer: create here swap dup allot erase ;
[THEN]
1000000000 Constant size#
256 cells buffer: cbuf
: foo1 size# bounds do
	1 I c@ cells cbuf + +!
    loop ;
: foo2 size# bounds do
	1 I c@ cells cbuf + +!
	1 I 1+ c@ cells cbuf + +!
    2 +loop ;
: foo4 size# bounds do
	1 I c@ cells cbuf + +!
	1 I 1+ c@ cells cbuf + +!
	1 I 2 + c@ cells cbuf + +!
	1 I 3 + c@ cells cbuf + +!
    4 +loop ;
size# allocate throw Constant mem
[defined] >rng$ [IF]
    mem size# >rng$
[ELSE]
    mem size# 3 fill
[THEN]
: .cbuf ( -- ) $100 0 DO cr cbuf I cells + @ . LOOP ;

Other variants like using count instead of I produced the same number of 
cycles, so I stick with that version.  Unrolling helps only very little with 
bigForth:

foo1: 7179648133
foo2: 7141923519
foo4: 7203558307

FOO4 is slower, since 3 + in bigForth does not work as well as 1+ or 2+ (for 
Gforth, use 2 + instead of 2+).

That's with uninitialized memory. Initializing it with a constant number 
(mem 1000000000 3 fill) gives

bigforth foo1: 7575601510
bigforth foo2: 7554567180
bigforth foo4: 7588444217

Gforth benefits most from unrolling, due to the high loop overhead

gforth-fast foo1: 13716218472
gforth-fast foo2: 12308216559
gforth-fast foo4: 10828943847

VFX benefits a bit from the 2 times unrolling, but not for the four times:

vfxlin foo1: 7584505558
vfxlin foo2: 7051855824
vfxlin foo4: 7436633963

And actually using a cryptographic hard random number genrator (Keccak-
based, using net2o's framework):

gforth-fast foo1: 25352164468
gforth-fast foo4: 23543813582

Output of these 1 billion pseudo-random bytes:

3905165 
3904865 
3906918 
3908466 
3904234 
3908752 
3905345 
3907909 
3905398 
3903024 
3907530 
3910724 
3905809 
3905394 
3904374 
3904834 
3906032 
3900550 
3905507 
3904065 
3904039 
3908412 
3909854 
3907097 
3902369 
3909287 
3906150 
3909990 
3904391 
3906278 
3903488 
3901682 
3904361 
3906854 
3904717 
3907915 
3905285 
3904708 
3905333 
3907791 
3906312 
3907439 
3904901 
3902937 
3910548 
3906823 
3906697 
3903976 
3906602 
3906875 
3903598 
3906926 
3908504 
3907320 
3904747 
3904304 
3907230 
3907863 
3906191 
3904602 
3903723 
3908629 
3906795 
3905477 
3907267 
3905998 
3910207 
3904676 
3907314 
3904488 
3904025 
3909867 
3905565 
3901720 
3904448 
3903353 
3908202 
3905578 
3904127 
3904933 
3908339 
3908128 
3906704 
3906135 
3909358 
3905612 
3905318 
3905675 
3906190 
3906521 
3904373 
3910256 
3905023 
3905726 
3908079 
3907210 
3907555 
3904585 
3907454 
3903768 
3911082 
3905707 
3907181 
3904799 
3903506 
3906354 
3906775 
3906786 
3905263 
3901839 
3908258 
3905968 
3905384 
3904685 
3908286 
3905696 
3906063 
3903184 
3907495 
3906375 
3905776 
3905640 
3903414 
3908899 
3908198 
3906120 
3905625 
3905386 
3905227 
3904634 
3903545 
3906656 
3903119 
3907723 
3908005 
3906038 
3905797 
3908381 
3907061 
3906883 
3908926 
3906840 
3906954 
3905509 
3907072 
3907340 
3904297 
3906076 
3909036 
3905862 
3907911 
3907178 
3906691 
3907284 
3902010 
3908073 
3907535 
3908574 
3906955 
3910537 
3906444 
3906922 
3909848 
3907480 
3905920 
3902299 
3906747 
3906634 
3907099 
3905613 
3908810 
3909173 
3900360 
3907015 
3910634 
3901799 
3905659 
3908864 
3905391 
3907218 
3907228 
3903872 
3905647 
3902822 
3911059 
3904582 
3905508 
3909457 
3908722 
3907791 
3906240 
3906059 
3908140 
3908294 
3907865 
3907043 
3906251 
3906787 
3904215 
3906409 
3906242 
3904052 
3909706 
3903932 
3907125 
3903344 
3906138 
3903919 
3906977 
3903751 
3904239 
3906469 
3903635 
3904339 
3904647 
3907139 
3904553 
3907260 
3903437 
3907722 
3907139 
3907619 
3906628 
3907709 
3904318 
3904275 
3905791 
3908354 
3907609 
3903843 
3906220 
3906824 
3903789 
3905204 
3906811 
3908850 
3902650 
3902528 
3907953 
3904831 
3906327 
3910769 
3906732 
3908593 
3907378 
3909317 
3904161 
3905861 
3905033 
3908980 
3907809 
3905331 
3907647 
3905932 
3908729 
3908745 

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#44977

From	mhx@iae.nl
Date	2016-01-20 15:57 -0800
Message-ID	<cf5003f0-afd2-4358-b0c0-b5aa8d1225af@googlegroups.com>
In reply to	#44969

On Wednesday, January 20, 2016 at 9:00:29 PM UTC+1, Bernd Paysan wrote:
> mhx@iae.nl wrote:
> > Thanks for independently verifying the basic principle.
> > 
> > Could you also share what happens when there's more work in
> > that loop? You could use the byte counter with initialized
> > main array further up in this thread, and unroll the loop a
> > various number of times to see what happens.
> 
> Ok, based on this:
> 
> \ benchmark
> [defined] buffer: 0= [IF]
>     : buffer: create here swap dup allot erase ;
> [THEN]
> 1000000000 Constant size#
> 256 cells buffer: cbuf
> : foo1 size# bounds do
> 	1 I c@ cells cbuf + +!
>     loop ;
> : foo2 size# bounds do
> 	1 I c@ cells cbuf + +!
> 	1 I 1+ c@ cells cbuf + +!
>     2 +loop ;
> : foo4 size# bounds do
> 	1 I c@ cells cbuf + +!
> 	1 I 1+ c@ cells cbuf + +!
> 	1 I 2 + c@ cells cbuf + +!
> 	1 I 3 + c@ cells cbuf + +!
>     4 +loop ;
> size# allocate throw Constant mem
> [defined] >rng$ [IF]
>     mem size# >rng$
> [ELSE]
>     mem size# 3 fill
> [THEN]
> : .cbuf ( -- ) $100 0 DO cr cbuf I cells + @ . LOOP ;
> 
> Other variants like using count instead of I produced the same number of 
> cycles, so I stick with that version.  Unrolling helps only very little with 
> bigForth:

The unrolling is not to speed up the code, but 
because it may prevent it from slowing down (see above). 

The most interesting result is what happens  
when 1) the loop counter is in a register (taking away 
one of the two identified dependencies), *and* 2) 
with randomly initialized memory (taking away the 
other dependency). When 1 & 2, the expected 
result is that your code proves to be at least as fast 
or faster than we have seen for the C code, without 
further tricks. This is assuming that bigForth 
reduces "1 I c@ cells cbuf + +!" to two or so
cycles worth of work. 

I can speculate what should the timings in your
case, but it is much more effective if you can post the
bigForth timings with pre-initialized memory. The time
taken for the rng is *not* interesting here and
should not be included (7 GigaTicks is about 2 seconds
on a 3.4GHz CPU, much higher than expected for bare 
counting, so I guess you posted the total elapsed time).

-marcel

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

#44999

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-01-21 23:02 +0100
Message-ID	<n7rkcu$qln$1@dont-email.me>
In reply to	#44977

mhx@iae.nl wrote:

> I can speculate what should the timings in your
> case, but it is much more effective if you can post the
> bigForth timings with pre-initialized memory. The time
> taken for the rng is *not* interesting here and
> should not be included (7 GigaTicks is about 2 seconds
> on a 3.4GHz CPU, much higher than expected for bare
> counting, so I guess you posted the total elapsed time).

The 7 Gigaticks are for counting 1 Gigabyte of memory. 7 ticks for a

1 I c@ cells cbuf + +!

without sophisticated optimization.  Replacing that with three assembler 
instructions gives 6034861067 cycles for counting non-random stuff (only one 
cycle better), which means it's incrementing always the same cell (bad for 
Core i7).

Let's take a simpler random number generator (not Keccak):

bigforth high-level: 5156613792
bigforth 2* unroll:  4276095541
bigforth 4* unroll:  4431504851

Using count+ in assembler (that's what I expect iForth to generate as code 
;-):

    Code count+ ( addr -- addr+1 )
	.b AX ) DX movzx
	cbuf DX *4 I#) inc
          AX inc
	Next end-code macro

bigforth low-level:  3038909603
bigforth ll 2* ur:   1976264691
bigforth ll 4* ur:   1879955686

The low-level uses its own pointer, not I. Funny enough, using I actually 
gives a gain for the non-unroled version:

bigforth ll using I: 2355539066

and a slowdown for the 2* unroll.  This is a bit odd... but probably there 
are not enough resources for complex address calculations available.

That's showing a significant gain, and the assembler version is really two 
times faster.

In Gforth, random and non-random have the reverse effect:

gforth-fast non-random: 12688324960
gforth-fast random: 13742084088

Each measured with first measuring only the fill-up, and then the total 
number of cycles, subtracting the fill-up cycles.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#45004

From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Date	2016-01-22 01:25 +0000
Message-ID	<56a18509$0$23726$e4fe514c@news.xs4all.nl>
In reply to	#44999

Bernd Paysan <bernd.paysan@gmx.de> writes:

>mhx@iae.nl wrote:

>> I can speculate what should the timings in your
>> case, but it is much more effective if you can post the
>> bigForth timings with pre-initialized memory. The time
>> taken for the rng is *not* interesting here and
>> should not be included (7 GigaTicks is about 2 seconds
>> on a 3.4GHz CPU, much higher than expected for bare
>> counting, so I guess you posted the total elapsed time).

>The 7 Gigaticks are for counting 1 Gigabyte of memory. 7 ticks for a

>1 I c@ cells cbuf + +!

>without sophisticated optimization.  Replacing that with three assembler
>instructions gives 6034861067 cycles for counting non-random stuff (only one
>cycle better), which means it's incrementing always the same cell (bad for
>Core i7).

>Let's take a simpler random number generator (not Keccak):

>bigforth high-level: 5156613792
>bigforth 2* unroll:  4276095541
>bigforth 4* unroll:  4431504851

>Using count+ in assembler (that's what I expect iForth to generate as code
>;-):

>    Code count+ ( addr -- addr+1 )
>       .b AX ) DX movzx
>       cbuf DX *4 I#) inc
>          AX inc
>       Next end-code macro

>bigforth low-level:  3038909603
>bigforth ll 2* ur:   1976264691
>bigforth ll 4* ur:   1879955686

>The low-level uses its own pointer, not I. Funny enough, using I actually
>gives a gain for the non-unroled version:

>bigforth ll using I: 2355539066

>and a slowdown for the 2* unroll.  This is a bit odd... but probably there
>are not enough resources for complex address calculations available.

>That's showing a significant gain, and the assembler version is really two
>times faster.

>In Gforth, random and non-random have the reverse effect:

>gforth-fast non-random: 12688324960
>gforth-fast random: 13742084088

>Each measured with first measuring only the fill-up, and then the total
>number of cycles, subtracting the fill-up cycles.

Can't we run a nicer benchmark, that actually does something and can't
be optimised?

 \ For N and HINT return FACTOR >= hint, maybe n.
: FACTOR   BEGIN   2DUP /MOD SWAP
     0= IF DROP SWAP DROP EXIT THEN
     OVER < IF DROP EXIT THEN
     1+ 1 OR AGAIN ;
\ Find largest factor of the 61 mersenne number
\ It is prime, so the numbers printed should be the same
MARK-TIME 1 61 LSHIFT 1-  DUP . 2 FACTOR . ELAPSED .mS

2305843009213693951 2305843009213693951  38477.666mS  OK
AMD FX8370 4 Ghz     lina64  5.2.1

Groetjes Albert

>--
>Bernd Paysan
>"If you want it done right, you have to do it yourself"
>net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
>http://bernd-paysan.de/
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#45006

From	hughaguilar96@gmail.com
Date	2016-01-21 18:05 -0800
Message-ID	<ade37731-f523-4918-984a-365384746c25@googlegroups.com>
In reply to	#45004

On Thursday, January 21, 2016 at 6:25:31 PM UTC-7, Albert van der Horst wrote:
> Can't we run a nicer benchmark, that actually does something and can't
> be optimised?

Well, that is why I suggested my LowDraw poker probability calculation program. 

These tiny benchmarks with a single loop and some pointless calculation in the loop are pretty meaningless.

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

#45014

From	mhx@iae.nl
Date	2016-01-21 22:03 -0800
Message-ID	<0aaf4bb8-07f5-47c4-bd61-00624e401a96@googlegroups.com>
In reply to	#45004

On Friday, January 22, 2016 at 2:25:31 AM UTC+1, Albert van der Horst wrote:
> 
> Can't we run a nicer benchmark, that actually does something and can't
> be optimised?

This leaf of the thread is not about benchmarking, but about 
certain hardware characteristics that are influencing the way
analytic Forth compilers generate code for their targets.
Before investing time in modifying these compilers, it would be
nice to be able to predict what the effects will be in practice.
These postings help in doing that.

-marcel

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

#44961

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-01-20 13:40 +0000
Message-ID	<2016Jan20.144001@mips.complang.tuwien.ac.at>
In reply to	#44952

Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>
>> So, for the empty DO LOOP, using the recurrence through memory makes
>> vfxlin as slow as gforth-fast and gforth-fast --no-dynamic (the latter
>> being plain direct-threaded code).
>
>Hm, we could use registers for the loop counters in Gforth on all non-
>register-starved architectures

I.e., on PowerPC (maybe also SPARC).  All other architectures are
register-starved when you use gcc, as I learned in my experiments with
stack caching.  I could not even use two registers for the stack cache
on Alpha or AMD64 (or any other architecture I tried except PowerPC)
without spilling some important virtual machine register.

>and use the new gcc5 arithmetic overflow 
>intrinsics to produce the jump on overflow code, and then beat VFX ;-).  On 
>the empty loop benchmark, at least.

I think it's more cost-effective if we invest that effort into the
native-code compiler.

>BTW, bigForth uses registers and jump on overflow, so it's 6 times faster on 
>Core i7-3517U:
>
>% perf stat -x " " -e cycles bigforth -e ": foo 1000000000 0 do loop ; foo 
>bye"
>1031068581  cycles

Cool.  Now for the benchmark from
<2016Jan15.172237@mips.complang.tuwien.ac.at>:

create counts 256 cells allot
256 1024 * 1024 * constant a-size
a-size allocate throw constant a
: init-a ( -- )
  a a-size bounds ?do
    $00204060 i ! $80a0c0e0 i cell+ !
  2 cells +loop ;
: do-test 
  a a-size bounds ?do
    1 counts i c@ cells + +!
  loop ;
init-a
do-test

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

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

#44943

From	m.a.m.hendrix@tue.nl
Date	2016-01-18 03:55 -0800
Message-ID	<b41921b8-1a9e-4e9d-a88d-bde8930d1d80@googlegroups.com>
In reply to	#44910

On Saturday, January 16, 2016 at 4:05:20 PM UTC+1, Albert van der Horst wrote: 

> mhx@iae.nl writes: 
> 
> >On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote: 

> >> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge 
[..] 

> You do realize that all those benchmarks are pretty worthless without 
> mentioning the exact processor they are running on, don't you? 
> In this thread there were sufficient examples of unexpected results, 
> that were obtained by different processors. 

Benchmarks? Processors? You mean experiments and Forth 
implementations? 

Only users of Forths with optimizing compilers will notice 
the effects uncovered in this thread. In a `standard' Forth 
threaded-code implementation loops are not so tight that 
they cause problems. 

For readers with such Forths, it suffices to see the 
differences caused by high-level source code changes. 
(I used the Forth assembler only to prevent having to 
guess what machine instructions are behind the high-level 
words.) For this purpose it suffices to know that I use 
current hardware. Actually, the target CPU is mentioned 
in the thread, but not for each and every re-run. 

Of course, nowadays computers are more than fast enough
and we don't need to worry about these silly details
anymore. It must be true, because I have heard
people say it ever since I got my first desktop
computer 35 years ago (a dual-drive P2000 from 
Philips).

-marcel

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

#45048

From	Andrew Haley <andrew29@littlepinkcloud.invalid>
Date	2016-01-23 15:13 -0600
Message-ID	<gNOdnR-Lm7mccD7LnZ2dnUU78V2dnZ2d@supernews.com>
In reply to	#44907

mhx@iae.nl wrote:
> On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote:
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge 
>> >mhx@iae.nl writes:
> 
> When using iForth's parallel extensions there is the memory
> dependence of threads access to take care of. It is not
> pretty, but 4 times faster than C with openMP (48ms vs 190ms).

Mmm, but your C version used a single array for summation rather than
four arrays as here, did it not?  That means that every core would be
sharing the same cache lines for the totals: not good.

I got curious about just how fast it would be possible to do this on
the systems I have.  I tried it with Java using Fork/Join to spread
the work over the available cores and it bottomed out at about 28ms on
both a system with many smallish cores and a high-end Intel desktop
machine.  I imagine that Cilk Plus would give similar results, but I
haven't tried.

Andrew.

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

#45057

From	mhx@iae.nl
Date	2016-01-24 00:55 -0800
Message-ID	<1ebdab9b-4700-48f1-a070-cfd1d67f91f0@googlegroups.com>
In reply to	#45048

On Saturday, January 23, 2016 at 10:13:38 PM UTC+1, Andrew Haley wrote:
> mhx@iae.nl wrote:
> > On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote:
> >> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge 
> >> >mhx@iae.nl writes:
> > 
> > When using iForth's parallel extensions there is the memory
> > dependence of threads access to take care of. It is not
> > pretty, but 4 times faster than C with openMP (48ms vs 190ms).
> 
> Mmm, but your C version used a single array for summation rather than
> four arrays as here, did it not?  That means that every core would be
> sharing the same cache lines for the totals: not good.

I assumed openMP would take care of it, as it is a natural
problem for for-loops (maybe not).

> I got curious about just how fast it would be possible to do this on
> the systems I have.  I tried it with Java using Fork/Join to spread
> the work over the available cores and it bottomed out at about 28ms on
> both a system with many smallish cores and a high-end Intel desktop
> machine.  
[..]

I hadn't looked for the minimum yet, but with 12 threads iForth
bottoms out at 31 ms. The variability over different runs is almost
0, so I don't trust it too much. With 8 threads I occasionally 
saw 31 ms also. The CPU has 6 real cores.

-marcel

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

#45063

From	Andrew Haley <andrew29@littlepinkcloud.invalid>
Date	2016-01-25 04:48 -0600
Message-ID	<_vSdnceejs3xYDjLnZ2dnUU78UudnZ2d@supernews.com>
In reply to	#45057

mhx@iae.nl wrote:
> On Saturday, January 23, 2016 at 10:13:38 PM UTC+1, Andrew Haley wrote:
>> mhx@iae.nl wrote:
>> > On Saturday, January 16, 2016 at 11:45:00 AM UTC+1, Marcel Hendrix wrote:
>> >> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ruby/Forth challenge 
>> >> >mhx@iae.nl writes:
>> > 
>> > When using iForth's parallel extensions there is the memory
>> > dependence of threads access to take care of. It is not
>> > pretty, but 4 times faster than C with openMP (48ms vs 190ms).
>> 
>> Mmm, but your C version used a single array for summation rather than
>> four arrays as here, did it not?  That means that every core would be
>> sharing the same cache lines for the totals: not good.
> 
> I assumed openMP would take care of it, as it is a natural
> problem for for-loops (maybe not).

I don't think it does.  It would have to clone the summation array
into several arrays, and then add them later.  It's not that smart.

>> I got curious about just how fast it would be possible to do this on
>> the systems I have.  I tried it with Java using Fork/Join to spread
>> the work over the available cores and it bottomed out at about 28ms on
>> both a system with many smallish cores and a high-end Intel desktop
>> machine.  
> [..]
> 
> I hadn't looked for the minimum yet, but with 12 threads iForth
> bottoms out at 31 ms. The variability over different runs is almost
> 0, so I don't trust it too much. With 8 threads I occasionally 
> saw 31 ms also. The CPU has 6 real cores.

Right, so perhaps similar to what I have, which is a i7-3930K @3.5GHz.
I tried Cilk Plus (which is part of GCC these days) and improved my
Java code, and my final results are

Java: 25.4ms
C (Cilk Plus): 23.4ms

An interesting lesson about this is that we have all these cores, and
it's sometimes far more effective to use them all than to worry about
micro-optimizing a single core.  And that as long as you have a
good-enough compiler, programming language doesn't seem to matter
much.

And a final conclusion: we still don't have any kind of standard
concurrency mechanisms in Forth.  Sigh.  Some kind of load-balancing
system like Cilk Plus would be a nice thing to have, and wouldn't be
all that hard to use.

I realize that I may be about to get into some trouble by posting C
code here, but it's with a mind to create something similar for Forth.
The Cilk Plus code to spread the work across multiple cores looks like
this:

void compute(int result[restrict], unsigned char bytes[restrict],
             int begin, int end) {
  int length = end - begin;
  if (length < 256*1024) {
    return computeDirectly(result, bytes, begin, end);
  }
  int a1[256], a2[256];
  clear(a1); clear(a2);
  cilk_spawn compute(a1, bytes, begin, begin + length / 2);
  compute(a2, bytes, begin + length / 2, end);
  cilk_sync;
  add(result, a1, a2, 256);
}

So, we split the source byte array into two and spawn a task to handle
one half, handle and we the other half ourselves, recursively.  If the
source array is "small enough" we just do the summation directly.  The
exact value of "small enough" parameter doesn't seem to matter much.
The only unusual code here is cilk_spawn and cilk_sync, but (of
course) this hides a lot of machinery.  SPAWN and SYNC would be nice
to have in Forth.

OK, I'll stop now: I shouldn't get so OCD about things.  :-)

Andrew.

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

#45064

From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Date	2016-01-25 12:39 +0000
Message-ID	<56a61765$0$23781$e4fe514c@news.xs4all.nl>
In reply to	#45063

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:

>An interesting lesson about this is that we have all these cores, and
>it's sometimes far more effective to use them all than to worry about
>micro-optimizing a single core.  And that as long as you have a
>good-enough compiler, programming language doesn't seem to matter
>much.

>And a final conclusion: we still don't have any kind of standard
>concurrency mechanisms in Forth.  Sigh.  Some kind of load-balancing
>system like Cilk Plus would be a nice thing to have, and wouldn't be
>all that hard to use.

Al the more strange because the stack diagram is compelling.

First, it doesn't make sense to split of task that are too small.
So don't mind to clone the stacks.
Next we need an environment to run things in. That is just a Forth.
So there you go:

THREAD-PET "name"
make a data structure to run a process in. (With its own stack user area
and maybe other buffers.) If you want to add definitions in the
process, you may pass a parameter, the size of the dictionary
to be reserved.

Usages is:
THREAD-PET APE
' calc APE

Run the calculation `` calc '' in the environment APE until completion.

The transputer has learned us that communication between parallel
task must use channels. Furthermore all global data plus
user variables are available.

>I realize that I may be about to get into some trouble by posting C
>code here, but it's with a mind to create something similar for Forth.
>The Cilk Plus code to spread the work across multiple cores looks like
>this:

>void compute(int result[restrict], unsigned char bytes[restrict],
>             int begin, int end) {
>  int length = end - begin;
>  if (length < 256*1024) {
>    return computeDirectly(result, bytes, begin, end);
>  }
>  int a1[256], a2[256];
>  clear(a1); clear(a2);
>  cilk_spawn compute(a1, bytes, begin, begin + length / 2);
>  compute(a2, bytes, begin + length / 2, end);
>  cilk_sync;
>  add(result, a1, a2, 256);
>}

Passing parameters must not be confounded with the parallel processing
per se.

>So, we split the source byte array into two and spawn a task to handle
>one half, handle and we the other half ourselves, recursively.  If the
>source array is "small enough" we just do the summation directly.  The
>exact value of "small enough" parameter doesn't seem to matter much.
>The only unusual code here is cilk_spawn and cilk_sync, but (of
>course) this hides a lot of machinery.  SPAWN and SYNC would be nice
>to have in Forth.

>OK, I'll stop now: I shouldn't get so OCD about things.  :-)

What's OCD?

By the by. The THREAD-PET is present in ciforth. Another of those
one-screeners.

However it didn't work in 64 bits. The solution is interesting.
The Linux syscall supposedly leaves the base pointer BP (ciforth's
return stack) alone, so I saved the High Level Interpreter pointer (SI)
on the return stack. This has worked for ages, and still works on 32 bits.
But it doesn't work for the __NR_clone system call on 64 bits,
as I get a memory fault on my first next.

Now I save RSI into the R15 register, (that reportedly is not
touched by kernel calls) and all works out. This took me a week of
debugging, if not more.

>Andrew.
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

Page 3 of 7 — ← Prev page 1 2 [3] 4 5 6 7 Next page →

csiph-web

Ruby/Forth challenge for WJ

Contents

#44893

#44905

#44907

#44910

#44941

#44944

#44952

#44958

#44969

#44977

#44999

#45004

#45006

#45014

#44961

#44943

#45048

#45057

#45063

#45064