Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!news1.tnib.de!feed.news.tnib.de!news.tnib.de!newsfeed.freenet.ag!news2.euro.net!postnews2.euro.net!news.wanadoo.nl!not-for-mail
From: mhx@iae.nl (Marcel Hendrix)
Subject: Re: ANN: All FIPS 180-4 Secure Hash Algorithms in ANS Forth
Newsgroups: comp.lang.forth
Message-ID: <95101915028434@frunobulax.edu>
Date: Sun, 20 Jan 2013 16:25:08 +0200
References: <9992845.Pkt4JWEiZa@sunwukong.fritz.box>
X-Newsreader: iForth 2.0 console (October 21, 2006)
Lines: 200
Organization: Wanadoo
NNTP-Posting-Date: 20 Jan 2013 15:24:31 GMT
NNTP-Posting-Host: s529d937f.adsl.online.nl
X-Trace: 1358695471 dr6.euro.net 226 82.157.147.127:60554
X-Complaints-To: abuse@wanadoo.nl
Xref: csiph.com comp.lang.forth:18937

Bernd Paysan <bernd.paysan@gmx.de> writes Re: ANN: All FIPS 180-4 Secure Hash Algorithms in ANS Forth

> Marcel Hendrix wrote:
>> To make this more concrete, I wrote a small program and ran the tests:
>> 

> You just can execute 3 nops in parallel on the Core i7, while all the 
> other methods have sequential dependencies, which prevents parallel 
> execution.

OK, seems to be consistent.

>             I'm a bit confused, because somehow I remember that Intel 
> said, their current microarchitecture has ways to fuse pushs, so that 
> you can do more than one push per cycle; but apparently, that's not the 
> case.  Apparently doing something like
>
> movq %rax,-8(%esp)
> movq %rbx,-16(%esp)
> movq %rcx,-24(%esp)
> movq %rdx,-32(%esp)
> leaq %esp,-32(%esp)
>
> should be twice as fast as four pushs.

That doesn't seem to work.

>>   5) A simple xchg of two registers (in 64 bit mode) is very slow.
>
> Indeed.  It's a bit confusing that it's 2.5 times slower than other 
> operations, but apparently the way it is broken up in microops allows it 
> to be slightly faster.  I think translating
>
> xchgq %r8, %r9
>
> to
>
> movq %r8, %eax
> movq %r9, %r8
> movq %eax, %r9
>
> should increase the speed.

Should, but doesn't.

>                             Let's schedule two of them:
>
> movq %r8, %eax || movq %r9, %r8
> movq %eax, %r9 || movq %r8, %eax
> movq %r9, %r8  || movq %eax, %r9
>
> I.e. you should have 1.5 cycles per exchange, not 2.5.

Maybe :-)

Here are my results.

FORTH> bench
direct  : 1.855 seconds elapsed.
null    : 0.613 seconds elapsed.
inc     : 1.791 seconds elapsed.
xchg    : 4.681 seconds elapsed.
xchg2   : 5.423 seconds elapsed.
xchg3   : 4.213 seconds elapsed.
xchg4   : 4.485 seconds elapsed.
rsp     : 1.843 seconds elapsed.
par|rsp : 1.832 seconds elapsed.
rbp     : 1.849 seconds elapsed.
par|rbp : 1.843 seconds elapsed. ok

No happiness. 
I redraw the remark that xchg is slow; I can not find
a simple sequence which is faster. The famous XOR does not work,
and using a scratch register gives no speedup.

No way to accelerate parallel pushes yet.

-marcel

-- ----------------

NEEDS -assemble

ANEW -testreg

#512 =: /ss
CREATE stack /ss CELLS ALLOT stack /ss CELLS ERASE
stack /ss CELLS + =: start

ALSO ASSEMBLER
: many_nop,  ( -- ) /ss 0 ?DO   nop,             LOOP ;
: many_inc,  ( -- ) /ss 0 ?DO   rax inc,         LOOP ;
: many_ex,   ( -- ) /ss 0 ?DO   rax -> rax xchg, LOOP ;
: many_ex2,  ( -- ) /ss 0 ?DO   rax -> rcx xor,  rcx -> rax xor,  rax -> rcx xor,  LOOP ;
: many_ex3,  ( -- ) /ss 0 ?DO   rax -> rdx mov,  rcx -> rax mov,  rdx -> rcx xor,  LOOP ;
: rax_push0, ( -- ) /ss 0 ?DO   [rcx   I 1+ cells +] qword -> rax mov,  rax -> [rcx I CELLS +] qword mov,  LOOP ;
: rax_push1, ( -- ) /ss 0 ?DO   rax -> push,  LOOP ;
: rax_push*, ( -- ) /ss 4 / 0 ?DO   rax -> push, rbx -> push, rcx -> push, rdx -> push,  LOOP ;
: rax_push2, ( -- ) /ss 0 ?DO   rax -> [rbp] mov,   [rbp -1 cells +] -> rbp lea,  LOOP ;

: many_ex4,  ( -- ) /ss 2/  0 ?DO   rax -> rcx xor,  r8  -> r9  xor,
				    rcx -> rax xor,  r9  -> r8  xor, 
				    rax -> rcx xor,  r8  -> r9  xor,  	
			     LOOP ;

: fuse_push, ( -- ) /ss 4 / 0 ?DO   [rbp -4 cells +] -> rbp lea,  
				    rax -> [rbp 4 cells +] mov,  rbx -> [rbp 3 cells +] mov,
				    rcx -> [rbp 2 cells +] mov,  rdx -> [rbp 1 cells +] mov,
			     LOOP ;
PREVIOUS

CODE test_direct ( a -- )
	stack q# -> rcx mov,
	  rax_push0, 
	rax pop, rax -> [rcx /ss 1- cells +] qword mov,
	rbx jmp,
END-CODE

CODE test_null ( a -- )
	rax pop,
	  many_nop, 
	rbx jmp,
END-CODE

CODE test_ex ( a -- )
	rax pop,
	  many_ex, 
	rbx jmp,
END-CODE

CODE test_ex2 ( a -- )
	rax pop,
	  many_ex2, 
	rbx jmp,
END-CODE

CODE test_ex3 ( a -- )
	rax pop,
	  many_ex3, 
	rbx jmp,
END-CODE

CODE test_ex4 ( a -- )
	rax pop,
	  many_ex4, 
	rbx jmp,
END-CODE

CODE test_inc ( a -- )
	rax pop,
	  many_inc, 
	rbx jmp,
END-CODE

CODE test_rsp ( a -- )
	rax pop,
	rsp -> rcx mov, start q# -> rsp mov,
	  rax_push1, 
	rcx -> rsp mov,
	rbx jmp,
END-CODE

CODE test_rsp* ( a -- )
	rax pop,
	rsp -> rcx mov, start q# -> rsp mov,
	  rax_push*, 
	rcx -> rsp mov,
	rbx jmp,
END-CODE

CODE test_rbp ( a -- )
	rax pop,
	rbp -> rcx mov, start q# -> rbp mov,
	  rax_push2,
	rcx -> rbp mov,
	rbx jmp,
END-CODE

CODE test_rbp* ( a -- )
	rax pop,
	rbp -> rcx mov, start q# -> rbp mov,
	  fuse_push,
	rcx -> rbp mov,
	rbx jmp,
END-CODE

#10000000 VALUE #times
: bench	CR ." direct  : " TIMER-RESET #times 0 DO  I test_direct     LOOP .ELAPSED 
	CR ." null    : " TIMER-RESET #times 0 DO  I test_null       LOOP .ELAPSED 
	CR ." inc     : " TIMER-RESET #times 0 DO  I test_inc        LOOP .ELAPSED 
	CR ." xchg    : " TIMER-RESET #times 0 DO  I test_ex         LOOP .ELAPSED 
	CR ." xchg2   : " TIMER-RESET #times 0 DO  I test_ex2        LOOP .ELAPSED 
	CR ." xchg3   : " TIMER-RESET #times 0 DO  I test_ex3        LOOP .ELAPSED 
	CR ." xchg4   : " TIMER-RESET #times 0 DO  I test_ex4        LOOP .ELAPSED 
	CR ." rsp     : " TIMER-RESET #times 0 DO  I test_rsp        LOOP .ELAPSED 
	CR ." par|rsp : " TIMER-RESET #times 0 DO  I test_rsp*       LOOP .ELAPSED 
	CR ." rbp     : " TIMER-RESET #times 0 DO  I test_rbp        LOOP .ELAPSED 
	CR ." par|rbp : " TIMER-RESET #times 0 DO  I test_rbp*       LOOP .ELAPSED ;