On Wednesday, February 9, 2022 at 2:52:33 AM UTC-6, Marcel Hendrix wrote:
> On Wednesday, February 9, 2022 at 5:59:45 AM UTC+1, km361...@gmail.com wrote:
> > On Tuesday, February 8, 2022 at 9:06:03 PM UTC-6, Marcel Hendrix wrote:
> > > On Wednesday, February 9, 2022 at 3:23:05 AM UTC+1, Marcel Hendrix wrote:
> > > [..]
> > > > Maybe I'll try to optimize it some more. The above is for the do-loop version.
> > > FORTH> S" abc" SHA512_Data .SHA512
> > > DDAF35A1 93617ABA CC417349 AE204131 12E6FA4E 89A97EA2
> > > 0A9EEEE6 4B55D39A 2192992A 274FC1A8 36BA3C23 A3FEEBBD
> > > 454D4423 643CE80E 2A9AC94F A54CA49F ok
> > > FORTH> SHAspeed many
> > > Processing 40 Mbytes ... 0.149 seconds elapsed.
> > > Processing 40 Mbytes ... 0.149 seconds elapsed.
> > > Processing 40 Mbytes ... 0.149 seconds elapsed.
> > > Processing 40 Mbytes ... 0.149 seconds elapsed.
> > > Processing 40 Mbytes ... 0.149 seconds elapsed.
> > > Processing 40 Mbytes ... 0.149 seconds elapsed. ok
> > > FORTH> 1000 40 149 */ . 268 ok
> > >
> > > -marcel
> > The word SLIDE_WITH_ADD in the Loop version is actually a shift register
> > operation on a...h, with 'h' being shifted out on the right, and T1 + T2 being
> > shifted in on the left. Additonally, one of the elements, 'd', was summed
> > with T1 before being shifted to the position of 'e' during the shift operation.
> >
> > Your original unrolled code did not reproduce this type of operation. There
> > were additional bugs also.
> Sorry if I was unclear. I consulted your repository, specifically
> the earliest modification that produced correct results.
> That version had a DO-LOOP, (no SLIDE_WITH_ADD, though) and
> I wanted to see how that worked out, so kept it in place.
>
> The version that I originally posted did not have the line-by-line
> debugging code from the C version (too bulky for a post), but
> with that in place I quickly got it working (at least the examples).
>
> T1 and T2 are removed from the present code as they can be kept
> on the stack (that is actually the 35ms speed up in my last result).
> Given the unexpectedly high influence of T1 and T2, looking at
> the fetch and store patterns might be beneficial.
>
> -marcel

The SLIDE_WITH_ADD is just an inlining word for code in SHA_Transform
which was already present in SHA_Transform in the first working version.
SLIDE_WITH_ADD was used in subsequent versions to make the code
more readable, but did not change the efficiency of the computation.
In contrast, the inlining word COMPUTE_T1 was a slightly more efficient
version of the code than the earlier version.

Good idea to keep T1 and T2 on the stack. There might be a more efficient
way to implement the shift register. Congrats on your throughput. It will be
useful if we could benchmark iforth running the same code on the same
system along with the other Forth systems. From Anton's earlier post, it
seems like all that was needed to do that was a way to obtain a time
elapsed with millisecond or higher resolution.

--
Krishna

On Wednesday, February 9, 2022 at 1:23:50 PM UTC+1, km361...@gmail.com wrote:
[..]
> > > The word SLIDE_WITH_ADD in the Loop version is actually a shift register
[..]
> The SLIDE_WITH_ADD is just an inlining word for code in SHA_Transform
> which was already present in SHA_Transform in the first working version.

Sorry, I didn't see it there (I copied the full do-loop SHA_Transform).

> It will be
> useful if we could benchmark iforth running the same code on the same
> system along with the other Forth systems.

That can be done by reporting clock ticks instead of wall-clock ticks,
but then the question becomes AMD or Intel, let alone other architectures,
so I generally avoid that (plus that I am always converting these horribly
long numbers to seconds in my head anyway).

> From Anton's earlier post, it
> seems like all that was needed to do that was a way to obtain a time
> elapsed with millisecond or higher resolution.

This is fundamentally a non-portable word, so what is the correct
response?

FORTH> WORDS: MS
..MSECS TICKS>MS .MS MS?
MS ?MS ~MS ticks/ms
ok

And then LOCATE <word> or help <word>
FORTH> help MS?
MS? IFORTH
( -- u )
Fetches the elapsed time in milliseconds since the execution of TIMER-RESET
TIMER-PRESET and others. Updates diff0 .
See also: (.T0) .MS n.ELAPSED diff0
ok
FORTH> help ?MS
?MS IFORTH
( -- time )
time is a time in milliseconds derived from the value of the system
clock. The only property of time is the fact that it represents a time
in milliseconds, there is no 'starting point'. Note that when the system
clock is halted, which is only possible on some processor models, the
time returned by ?MS will not advance anymore. Note also that processes
are free to load the system timer with a new value.

?MS avoids the use of additional non-portable words.

I think I can now use the WSL to also get these fancy portable
1,161,347,179 cycles, 3,410,826,133 instructions # 2.94 insn per cycle
reports, let me try...

-marcel

On Wednesday, February 9, 2022 at 11:09:20 AM UTC-6, Marcel Hendrix wrote:
> On Wednesday, February 9, 2022 at 1:23:50 PM UTC+1, km361...@gmail.com wrote:
> [..]
> > > > The word SLIDE_WITH_ADD in the Loop version is actually a shift register
> [..]
> > The SLIDE_WITH_ADD is just an inlining word for code in SHA_Transform
> > which was already present in SHA_Transform in the first working version.
> Sorry, I didn't see it there (I copied the full do-loop SHA_Transform).
> > It will be
> > useful if we could benchmark iforth running the same code on the same
> > system along with the other Forth systems.
> That can be done by reporting clock ticks instead of wall-clock ticks,
> but then the question becomes AMD or Intel, let alone other architectures,
> so I generally avoid that (plus that I am always converting these horribly
> long numbers to seconds in my head anyway).
> > From Anton's earlier post, it
> > seems like all that was needed to do that was a way to obtain a time
> > elapsed with millisecond or higher resolution.
> This is fundamentally a non-portable word, so what is the correct
> response?
>
> FORTH> WORDS: MS
> .MSECS TICKS>MS .MS MS?
> MS ?MS ~MS ticks/ms
> ok
>
> And then LOCATE <word> or help <word>
> FORTH> help MS?
> MS? IFORTH
> ( -- u )
> Fetches the elapsed time in milliseconds since the execution of TIMER-RESET
> TIMER-PRESET and others. Updates diff0 .
> See also: (.T0) .MS n.ELAPSED diff0
> ok
> FORTH> help ?MS
> ?MS IFORTH
> ( -- time )
> time is a time in milliseconds derived from the value of the system
> clock. The only property of time is the fact that it represents a time
> in milliseconds, there is no 'starting point'. Note that when the system
> clock is halted, which is only possible on some processor models, the
> time returned by ?MS will not advance anymore. Note also that processes
> are free to load the system timer with a new value.
>
> ?MS avoids the use of additional non-portable words.
>
Sounds like ?MS will work as a drop-in replacement for MS@.

The time origin (starting point) is not relevant to the use of MS@ for timing
the execution of Forth code. It is important that the returned time has
a resolution of 1 ms, and that subsequent calls can be differenced to
give an elapsed time which is accurate to +/-1 ms. The accuracy may
depend on the length of the interval between successive calls,
particularly if the system is flooded with hardware interrupts and
interrupt handlers suppress the system clock interrupt. I have only
observed this under deliberate tests to flood a system. For millisecond
accuracy over timing tests of seconds to minutes, I have not found
a problem, at least when there is a stratum 2 time server maintaining
the system time.

--
Krishna

> I think I can now use the WSL to also get these fancy portable
> 1,161,347,179 cycles, 3,410,826,133 instructions # 2.94 insn per cycle
> reports, let me try...
>

On Wednesday, February 9, 2022 at 11:09:20 AM UTC-6, Marcel Hendrix wrote:
> On Wednesday, February 9, 2022 at 1:23:50 PM UTC+1, km361...@gmail.com wrote:
> [..]
> > > > The word SLIDE_WITH_ADD in the Loop version is actually a shift register
> [..]
> > The SLIDE_WITH_ADD is just an inlining word for code in SHA_Transform
> > which was already present in SHA_Transform in the first working version.
> Sorry, I didn't see it there (I copied the full do-loop SHA_Transform).
> > It will be
> > useful if we could benchmark iforth running the same code on the same
> > system along with the other Forth systems.
> That can be done by reporting clock ticks instead of wall-clock ticks,
> but then the question becomes AMD or Intel, let alone other architectures,
> so I generally avoid that (plus that I am always converting these horribly
> long numbers to seconds in my head anyway).
> > From Anton's earlier post, it
> > seems like all that was needed to do that was a way to obtain a time
> > elapsed with millisecond or higher resolution.
> This is fundamentally a non-portable word, so what is the correct
> response?
>
> FORTH> WORDS: MS
> .MSECS TICKS>MS .MS MS?
> MS ?MS ~MS ticks/ms
> ok
>
> And then LOCATE <word> or help <word>
> FORTH> help MS?
> MS? IFORTH
> ( -- u )
> Fetches the elapsed time in milliseconds since the execution of TIMER-RESET
> TIMER-PRESET and others. Updates diff0 .
> See also: (.T0) .MS n.ELAPSED diff0
> ok
> FORTH> help ?MS
> ?MS IFORTH
> ( -- time )
> time is a time in milliseconds derived from the value of the system
> clock. The only property of time is the fact that it represents a time
> in milliseconds, there is no 'starting point'. Note that when the system
> clock is halted, which is only possible on some processor models, the
> time returned by ?MS will not advance anymore. Note also that processes
> are free to load the system timer with a new value.
>
> ?MS avoids the use of additional non-portable words.
>
Sounds like ?MS will work as a drop-in replacement for MS@.

The time origin (starting point) is not relevant to the use of MS@ for timing
the execution of Forth code. It is important that the returned time has
a resolution of 1 ms, and that subsequent calls can be differenced to
give an elapsed time which is accurate to +/-1 ms. The accuracy may
depend on the length of the interval between successive calls,
particularly if the system is flooded with hardware interrupts and
interrupt handlers suppress the system clock interrupt. I have only
observed this under deliberate tests to flood a system. For millisecond
accuracy over timing tests of seconds to minutes, I have not found
a problem, at least when there is a stratum 2 time server maintaining
the system time.

--
Krishna

> I think I can now use the WSL to also get these fancy portable
> 1,161,347,179 cycles, 3,410,826,133 instructions # 2.94 insn per cycle
> reports, let me try...
>

On 2/9/22 06:23, Krishna Myneni wrote:
....
> The SLIDE_WITH_ADD is just an inlining word for code in SHA_Transform
> which was already present in SHA_Transform in the first working version.
> SLIDE_WITH_ADD was used in subsequent versions to make the code
> more readable, but did not change the efficiency of the computation.
> In contrast, the inlining word COMPUTE_T1 was a slightly more efficient
> version of the code than the earlier version.
>
> Good idea to keep T1 and T2 on the stack. There might be a more efficient
> way to implement the shift register. ...

I have implemented the shift register idea, now using a contiguous block
of 8 CELLS to hold the a--h values. Now a shift by 1 cell can be
implemented with a single MOVE instead of performing g TO h f TO g ... etc.

The new inline word replacing SLIDE_WITH_ADD is SHIFT_WITH_ADD. It gives
a significant speedup in kforth64 (see below). The version of sha512.4th
has been bumped up to 0.02.

--
Krishna

---
shaspeed

Processing 40 Mbytes ... 8625 ms elapsed
ok
40000000e 8.625e f/ f.
4.63768e+06 ok \ Hashing rate of 4.6 MB/s; previous was 4.1 MB/s
---

On 2/9/22 20:41, Krishna Myneni wrote:
> On 2/9/22 06:23, Krishna Myneni wrote:
> ...

>> Good idea to keep T1 and T2 on the stack. There might be a more efficient
>> way to implement the shift register. ...
>
> I have implemented the shift register idea, now using a contiguous block
> of 8 CELLS to hold the a--h values. Now a shift by 1 cell can be
> implemented with a single MOVE instead of performing g TO h  f TO g ...
> etc.
>
> The new inline word replacing SLIDE_WITH_ADD is SHIFT_WITH_ADD. It gives
> a significant speedup in kforth64 (see below). The version of sha512.4th
> has been bumped up to 0.02.
>
> --
> Krishna
>
>
> ---
> shaspeed
>
> Processing 40 Mbytes ...   8625 ms elapsed
>  ok
> 40000000e 8.625e f/ f.
> 4.63768e+06  ok  \ Hashing rate of 4.6 MB/s; previous was 4.1 MB/s
> ---
>
>

Also keep T1 and T2 on the stack.

---
shaspeed

Processing 40 Mbytes ... 8496 ms elapsed
ok
4e7 8.496e f/ f.
4.7081e+06 ok
---

KM

On 2/9/22 22:15, Krishna Myneni wrote:
> On 2/9/22 20:41, Krishna Myneni wrote:
>> On 2/9/22 06:23, Krishna Myneni wrote:
>> ...
>
>>> Good idea to keep T1 and T2 on the stack. There might be a more
>>> efficient
>>> way to implement the shift register. ...
>>
>> I have implemented the shift register idea, now using a contiguous
>> block of 8 CELLS to hold the a--h values. Now a shift by 1 cell can be
>> implemented with a single MOVE instead of performing g TO h  f TO g
>> ... etc.
>>
>> The new inline word replacing SLIDE_WITH_ADD is SHIFT_WITH_ADD. It
>> gives a significant speedup in kforth64 (see below). The version of
>> sha512.4th has been bumped up to 0.02.
>>
>> --
>> Krishna
>>
>>
>> ---
>> shaspeed
>>
>> Processing 40 Mbytes ...   8625 ms elapsed
>>   ok
>> 40000000e 8.625e f/ f.
>> 4.63768e+06  ok  \ Hashing rate of 4.6 MB/s; previous was 4.1 MB/s
>> ---
>>
>>
>
> Also keep T1 and T2 on the stack.
>
> ---
> shaspeed
>
> Processing 40 Mbytes ...   8496 ms elapsed
>  ok
> 4e7 8.496e f/ f.
> 4.7081e+06  ok
> ---

While the 64-bit assembler for kForth-64 is still in progress, this does
not impede us from examining efficiency improvements possible in the
present implementation of SHA512. I have put in machine code
replacements for some of the words to see how much improvement will
result. The new sha512.4th may be found here:

https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512.4th

I measure roughly 5.6x increase in speed, now at 26 MB/s. I did not try
to optimize the assembly code -- it's a direct coding. However, when
compared with native code compilers, e.g. VFX, there is still a factor
of about 10 to be obtained with optimization. The present version is
only slightly slower on my system than gforth-fast, which clocks in at
about 28 MB/s.

--
Krishna

Speed Test with kforth64 v 0.2.4
---
s" abc" SHA512_Data type
DDAF35A193617ABACC417349AE20413112E6FA4E89A97EA20A9EEEE64B55D39A2192992A274FC1A836BA3C23A3FEEBBD454D4423643CE80E2A9AC94FA54CA49F
ok
..s
<empty>
ok
SHAspeed

Processing 40 Mbytes ... 1532 ms elapsed
ok
40e6 1.536e f/ f.
2.60417e+07 ok
---

Speed Test with gforth-fast 0.7.9_20220120
---
\ The machine code placement and calling features of the program
\ are not used by Gforth. Only the Forth source is executed.

include sha512-test.fs
sha512-test.fs:11:43: warning: redefined table
table.fs:37:3: warning: original location ok
s" abc" SHA512_Data type
DDAF35A193617ABACC417349AE20413112E6FA4E89A97EA20A9EEEE64B55D39A2192992A274FC1A836BA3C23A3FEEBBD454D4423643CE80E2A9AC94FA54CA49F
ok
ok
SHAspeed
Processing 40 Mbytes ... 1415 ms elapsed
ok
40e6 1.415e f/ f. 28268551.2367491 ok
---

Listing of sha512-test.4th (for kforth64)
---
\ Test file hashes for the Forth SHA512 implementation.
\

include ans-words
include modules
include syscalls
include mc \ Remove this include to benchmark pure Forth code.
include strings
include files
include utils
include dump
include slurp-file
include sha512.4th

also sha512

variable rfileid
create buf[] SHA512_BLOCK_LENGTH ALLOT

\ Read n bytes from input file, store at addr array
: bytes@ ( adr u -- ) rfileid @ READ-FILE 2DROP ;
: block@ buf[] SHA512_BLOCK_LENGTH bytes@ ;

: File_SHA512 ( caddr u -- )
R/O BIN OPEN-FILE SWAP rfileid !
ABORT" Invalid input file."
SHA512_Init \ Valid file, init transform
rfileid @ FILE-SIZE DROP ( ud ) \ Get bytesize of input file
CR ." Bytesize: " 2DUP UD.
SHA512_BLOCK_LENGTH UM/MOD ( rembytes nblocks ) \ Compute
nblocks & rembytes
0 ?DO
block@
buf[] SHA512_BLOCK_LENGTH SHA512_Update
LOOP \ Do n full blocks
buf[] swap 2dup bytes@
SHA512_Update
SHA512_End
CR TYPE CR \ Show SHA512 hash for file
rfileid @ CLOSE-FILE DROP
; ---

Listing of sha512-test.fs (for Gforth)
---
\ Test file hashes for the Forth SHA512 implementation.
\

include kforth-compat.fs
\ include strings.fs
\ include utils.fs
include modules.fs

: table ( v1 v2 ... vn n <name> -- | create a table of singles )
create dup cells allot? over 1- cells + swap
0 ?do dup >r ! r> 1 cells - loop drop ;

include sha512.fs \ exact same file as sha512.4th from kForth-64 repo

also sha512

variable rfileid
create buf[] SHA512_BLOCK_LENGTH ALLOT

\ Read n bytes from input file, store at addr array
: bytes@ ( adr u -- ) rfileid @ READ-FILE 2DROP ;
: block@ buf[] SHA512_BLOCK_LENGTH bytes@ ;

: File_SHA512 ( caddr u -- )
R/O BIN OPEN-FILE SWAP rfileid !
ABORT" Invalid input file."
SHA512_Init \ Valid file, init transform
rfileid @ FILE-SIZE DROP ( ud ) \ Get bytesize of input file
CR ." Bytesize: " 2DUP UD.
SHA512_BLOCK_LENGTH UM/MOD ( rembytes nblocks ) \ Compute
nblocks & rembytes
0 ?DO
block@
buf[] SHA512_BLOCK_LENGTH SHA512_Update
LOOP \ Do n full blocks
buf[] swap 2dup bytes@
SHA512_Update
SHA512_End
CR TYPE CR \ Show SHA512 hash for file
rfileid @ CLOSE-FILE DROP
; ---

Compatibility file for Gforth, kforth-compat.fs, and an
ANS-Forth-compatible modules.fs may be found at this link:

https://github.com/mynenik/kForth-64/tree/master/forth-src/compat

On 2/19/22 20:39, Krishna Myneni wrote:
....
> While the 64-bit assembler for kForth-64 is still in progress, this does
> not impede us from examining efficiency improvements possible in the
> present implementation of SHA512. I have put in machine code
> replacements for some of the words to see how much improvement will
> result. The new sha512.4th may be found here:
>
> https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512.4th
>
> I measure roughly 5.6x increase in speed, now at 26 MB/s. I did not try
> to optimize the assembly code -- it's a direct coding.
>
> ...

I reverted sha512.4th to pure Forth source, and created a separate
version, sha512-x86_64.4th, which is a hybrid of Forth source and
machine code calls used from within the Forth environment. I also
optimized the machine code a bit (v0.04). The current version gives a
hashing rate of about 37 MB/s (using SHASPEED on my system). A link to
the new hybrid file is given below.

--
Krishna

https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512-x86_64.4th

On Tuesday, 22 February 2022 at 02:16:23 UTC+1, Krishna Myneni wrote:
> On 2/19/22 20:39, Krishna Myneni wrote:
> ...
> > While the 64-bit assembler for kForth-64 is still in progress, this does
> > not impede us from examining efficiency improvements possible in the
> > present implementation of SHA512. I have put in machine code
> > replacements for some of the words to see how much improvement will
> > result. The new sha512.4th may be found here:
> >
> > https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512.4th
> >
> > I measure roughly 5.6x increase in speed, now at 26 MB/s. I did not try
> > to optimize the assembly code -- it's a direct coding.
> >
> > ...
>
> I reverted sha512.4th to pure Forth source, and created a separate
> version, sha512-x86_64.4th, which is a hybrid of Forth source and
> machine code calls used from within the Forth environment. I also
> optimized the machine code a bit (v0.04). The current version gives a
> hashing rate of about 37 MB/s (using SHASPEED on my system). A link to
> the new hybrid file is given below.
>
> --
> Krishna
>
>
> https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512-x86_64.4th

I have also been testing out my NTF64/LXF64 on your sha512 implementation.
Specifically I have been testing the code-generator I am developing.
I concentrated on the complete sha512_transform function.
My findings running on a XEON E5-4657L v2 CPU are

Forth, Original, With asm functions
kForth, 21.8 sec, 2.7 sec
LXF64, 17.2 sec, 2.4 sec

so quite similar improvements.
Looking at the shift_with_add function I see it uses MOVE to to speed up.
On LXF64 in this case that translates to using CMOVE> as it is overwriting its buffer
In LXF64 this compiles to a rep movsb with the direction flag set. It is copying down
in memory, a slow operation. Instead I tested with:

m: shift_with_add ( T1 T2 -- ) a b c d >r >r >r >r over + &a ! r> &b ! r> &c ! r> &d ! r> + e f g >r >r >r &e ! r> &f ! r> &g ! r> &h ! ;

This looks ugly with all its >r operations, but the code-generator translates this to

comp shift_with_add
START:
mov rax , QWORD PTR [0x4078F0]
mov rcx , QWORD PTR [0x4078F8]
mov rdx , QWORD PTR [0x407900]
mov rdi , QWORD PTR [0x407908]
add rbx , QWORD PTR [rbp+0]
mov QWORD PTR [0x4078F0], rbx
mov QWORD PTR [0x4078F8], rax
mov QWORD PTR [0x407900], rcx
mov QWORD PTR [0x407908], rdx
add rdi , QWORD PTR [rbp+0]
mov rbx , QWORD PTR [0x407910]
mov rax , QWORD PTR [0x407918]
mov rcx , QWORD PTR [0x407920]
mov QWORD PTR [0x407910], rdi
mov QWORD PTR [0x407918], rbx
mov QWORD PTR [0x407920], rax
mov QWORD PTR [0x407928], rcx
mov rbx , QWORD PTR [rbp+8]
lea rbp, [rbp+16]
ret
(rbx is top of stack and rbp stackpointer)

The result is that it is now running the 40MB shaspeed in 350 ms!

This was a very good exercise. It took me one week to get the results correct.
I searched for problems in my code-generator but in the end it was the assembler I
used that miss-compiled. The code generator produces assembler text that is sent
to an external assembler, in this case Keystone-engine. I switched to another FCML-LIB
but also that had problem. FASM produces correct result. I later found the problems in
Keystone and could recompile a correct library (but there could of course be other problems)

BR
Peter Fälth

On 2/22/22 16:09, P Falth wrote:
> On Tuesday, 22 February 2022 at 02:16:23 UTC+1, Krishna Myneni wrote:
>> On 2/19/22 20:39, Krishna Myneni wrote:
>> ...
>>> While the 64-bit assembler for kForth-64 is still in progress, this does
>>> not impede us from examining efficiency improvements possible in the
>>> present implementation of SHA512. I have put in machine code
>>> replacements for some of the words to see how much improvement will
>>> result. The new sha512.4th may be found here:
>>>
>>> https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512.4th
>>>
>>> I measure roughly 5.6x increase in speed, now at 26 MB/s. I did not try
>>> to optimize the assembly code -- it's a direct coding.
>>>
>>> ...
>>
>> I reverted sha512.4th to pure Forth source, and created a separate
>> version, sha512-x86_64.4th, which is a hybrid of Forth source and
>> machine code calls used from within the Forth environment. I also
>> optimized the machine code a bit (v0.04). The current version gives a
>> hashing rate of about 37 MB/s (using SHASPEED on my system). A link to
>> the new hybrid file is given below.
>>
>> --
>> Krishna
>>
>>
>> https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512-x86_64.4th
>
> I have also been testing out my NTF64/LXF64 on your sha512 implementation.
> Specifically I have been testing the code-generator I am developing.
> I concentrated on the complete sha512_transform function.
> My findings running on a XEON E5-4657L v2 CPU are
>
> Forth, Original, With asm functions
> kForth, 21.8 sec, 2.7 sec
> LXF64, 17.2 sec, 2.4 sec
>
> so quite similar improvements.
> Looking at the shift_with_add function I see it uses MOVE to to speed up.
> On LXF64 in this case that translates to using CMOVE> as it is overwriting its buffer
> In LXF64 this compiles to a rep movsb with the direction flag set. It is copying down
> in memory, a slow operation. Instead I tested with:
>
> m: shift_with_add ( T1 T2 -- ) a b c d >r >r >r >r over + &a ! r> &b ! r> &c ! r> &d ! r> + e f g >r >r >r &e ! r> &f ! r> &g ! r> &h ! ;
>
> This looks ugly with all its >r operations, but the code-generator translates this to
>
> comp shift_with_add
> START:
> mov rax , QWORD PTR [0x4078F0]
> mov rcx , QWORD PTR [0x4078F8]
> mov rdx , QWORD PTR [0x407900]
> mov rdi , QWORD PTR [0x407908]
> add rbx , QWORD PTR [rbp+0]
> mov QWORD PTR [0x4078F0], rbx
> mov QWORD PTR [0x4078F8], rax
> mov QWORD PTR [0x407900], rcx
> mov QWORD PTR [0x407908], rdx
> add rdi , QWORD PTR [rbp+0]
> mov rbx , QWORD PTR [0x407910]
> mov rax , QWORD PTR [0x407918]
> mov rcx , QWORD PTR [0x407920]
> mov QWORD PTR [0x407910], rdi
> mov QWORD PTR [0x407918], rbx
> mov QWORD PTR [0x407920], rax
> mov QWORD PTR [0x407928], rcx
> mov rbx , QWORD PTR [rbp+8]
> lea rbp, [rbp+16]
> ret
> (rbx is top of stack and rbp stackpointer)
>
> The result is that it is now running the 40MB shaspeed in 350 ms!
>
> This was a very good exercise. It took me one week to get the results correct.
> I searched for problems in my code-generator but in the end it was the assembler I
> used that miss-compiled. The code generator produces assembler text that is sent
> to an external assembler, in this case Keystone-engine. I switched to another FCML-LIB
> but also that had problem. FASM produces correct result. I later found the problems in
> Keystone and could recompile a correct library (but there could of course be other problems)
>

Excellent. Thank you for reporting your results. I was puzzling over
where the bottleneck might be in the code. Although I had improved the
execution speed of the Forth-only source from about 5 MB/s to nearly 40
MB/s by replacing parts of SHA512_TRANSFORM with calls to machine code,
I did not think SHIFT_WITH_ADD would be such a bottleneck. If possible
it might be best to keep the shift register, values a--h, in actual
registers, as Anton had previously suggested, but I'm not sure there are
enough registers available to do it conveniently. I'll revise my x86_64
version presently to see how it fares with a machine code call to
SHIFT_WITH_ADD.

--
Krishna

On 2/22/22 16:09, P Falth wrote:
> On Tuesday, 22 February 2022 at 02:16:23 UTC+1, Krishna Myneni wrote:
>> On 2/19/22 20:39, Krishna Myneni wrote:
....
>>
>> https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512-x86_64.4th
>
....
> My findings running on a XEON E5-4657L v2 CPU are
>
> Forth, Original, With asm functions
> kForth, 21.8 sec, 2.7 sec
> LXF64, 17.2 sec, 2.4 sec
>
> so quite similar improvements.
> Looking at the shift_with_add function I see it uses MOVE to to speed up.
> On LXF64 in this case that translates to using CMOVE> as it is overwriting its buffer
> In LXF64 this compiles to a rep movsb with the direction flag set. It is copying down
> in memory, a slow operation. Instead I tested with:
>
> m: shift_with_add ( T1 T2 -- ) a b c d >r >r >r >r over + &a ! r> &b ! r> &c ! r> &d ! r> + e f g >r >r >r &e ! r> &f ! r> &g ! r> &h ! ;
>
> This looks ugly with all its >r operations, but the code-generator translates this to
>
> comp shift_with_add
> START:
> mov rax , QWORD PTR [0x4078F0]
> mov rcx , QWORD PTR [0x4078F8]
> mov rdx , QWORD PTR [0x407900]
> mov rdi , QWORD PTR [0x407908]
> add rbx , QWORD PTR [rbp+0]
> mov QWORD PTR [0x4078F0], rbx
> mov QWORD PTR [0x4078F8], rax
> mov QWORD PTR [0x407900], rcx
> mov QWORD PTR [0x407908], rdx
> add rdi , QWORD PTR [rbp+0]
> mov rbx , QWORD PTR [0x407910]
> mov rax , QWORD PTR [0x407918]
> mov rcx , QWORD PTR [0x407920]
> mov QWORD PTR [0x407910], rdi
> mov QWORD PTR [0x407918], rbx
> mov QWORD PTR [0x407920], rax
> mov QWORD PTR [0x407928], rcx
> mov rbx , QWORD PTR [rbp+8]
> lea rbp, [rbp+16]
> ret
> (rbx is top of stack and rbp stackpointer)
>
> The result is that it is now running the 40MB shaspeed in 350 ms!
>

I used the following equivalent machine code macro for SHIFT_WITH_ADD in
sha512-x86_64.4th

---
\ in: r11 = ashiftreg, rbx points to T2, Forth stack ( T1 T2 ... )
\ out: shift register is modified per algorithm, no change to Forth stack
\ uses: rax, rcx, rdx, rdi, r8
: shift_with_add
49 8b 03 \ 0 [r11] rax mov, \ rax = a
49 8b 4b 08 \ 8 [r11] rcx mov, \ rcx = b
49 8b 53 10 \ 16 [r11] rdx mov, \ rdx = c
49 8b 7b 18 \ 24 [r11] rdi mov, \ rdi = d
4c 8b 43 08 \ 8 [rbx] r8 mov,
4c 03 03 \ [rbx] r8 add, \ r8 = T1 + T2
4d 89 03 \ r8 0 [r11] mov, \ new a = T1 + T2
49 89 43 08 \ rax 8 [r11] mov, \ new b = old a
49 89 4b 10 \ rcx 16 [r11] mov, \ new c = old b
49 89 53 18 \ rdx 24 [r11] mov, \ new d = old c
49 8b 43 20 \ 32 [r11] rax mov, \ rax = e
49 8b 4b 28 \ 40 [r11] rcx mov, \ rcx = f
49 8b 53 30 \ 48 [r11] rdx mov, \ rdx = g
48 03 7b 08 \ 8 [rbx] rdi add, \ rdi = old d + T1
49 89 7b 20 \ rdi 32 [r11] mov, \ new e = old d + T1
49 89 43 28 \ rax 40 [r11] mov, \ new f = old e
49 89 4b 30 \ rcx 48 [r11] mov, \ new g = old f
49 89 53 38 \ rdx 56 [r11] mov, \ new h = old g
; ---

The revised version of the hybrid Forth+machine code program, version
0.05, increases the hashing rate from 37 MB/s to 63 MB/s with kforth64
on my system -- SHASPEED reports an elapsed time for 40 MB of 639 ms. A
nice improvement!

--
Krishna

On Wednesday, February 23, 2022 at 4:15:31 AM UTC+1, Krishna Myneni wrote:
> On 2/22/22 16:09, P Falth wrote:
> > On Tuesday, 22 February 2022 at 02:16:23 UTC+1, Krishna Myneni wrote:
> >> On 2/19/22 20:39, Krishna Myneni wrote:
[..]
> > Looking at the shift_with_add function I see it uses MOVE to to speed up.
> > On LXF64 in this case that translates to using CMOVE> as it is overwriting its buffer
> > In LXF64 this compiles to a rep movsb with the direction flag set. It is copying down
> > in memory, a slow operation. Instead I tested with:
[..]
> >
> > The result is that it is now running the 40MB shaspeed in 350 ms!
> >
> I used the following equivalent machine code macro for SHIFT_WITH_ADD in
> sha512-x86_64.4th
> The revised version of the hybrid Forth+machine code program, version
> 0.05, increases the hashing rate from 37 MB/s to 63 MB/s with kforth64
> on my system -- SHASPEED reports an elapsed time for 40 MB of 639 ms. A
> nice improvement!

For iForth64 Hanno Schwalm put a lot of work in CMOVE and all of
its variants. The problem is that OS calls are unbeatable for large
size transfers, but these calls are expensive to set up and clean up
afterwards. We have found that for a certain upper bound, CODE
words of the REP MOV type are useful, but for very small size
(I think it was below 32 bytes) one better uses !+, !- etc. The
problem for the compiler is to figure out the transfer size
at compile time. Shaspeed is a good example of this.

However, optimizing CMOVE with !+ only decreases the runspeed
by 10ms or so (currently at 113 ms and really no ideas what to
improve next).

-marcel

Marcel Hendrix <mhx@iae.nl> writes:
>For iForth64 Hanno Schwalm put a lot of work in CMOVE and all of
>its variants. The problem is that OS calls are unbeatable for large
>size transfers,

I was puzzled by that statement, because I don't know a system call
that helps here, at least in the general case; in very special cases
you can mmap the same physical memory to another virtual address
range, but I doubt that you mean that.

So my guess is that you mean library calls, and basically you can do
all the things in your user-level code that the library can do in its
user-level code. It may be that the library author has spent more
time finding out about the twisty ways to get more performance,
however.

I have ventured in that area myself
<https://github.com/AntonErtl/move>, with results in
<2017Sep19.082137@mips.complang.tuwien.ac.at>
<2017Sep20.184358@mips.complang.tuwien.ac.at>
<2017Sep23.174313@mips.complang.tuwien.ac.at>
<2019Dec12.085706@mips.complang.tuwien.ac.at>
<2019Dec14.190943@mips.complang.tuwien.ac.at>

I did not optimize for large blocks (approaching the size of the L1
cache and bigger), though. AMD64 CPUs have "non-temporal" move
instructions (e.g., VMOVNTDQ, VMOVNTDQA), which tell the CPU that the
memory operand is not going to be accessed soon and does not need to
be kept in the cache; this avoids trampling over the old cache
contents, and the read-for-ownership that is needed for stores on some
(all?) microarchitectures. These instructions are weakly ordered and
need a slow fencing instruction for multicore consistency.

Depending on the way the MOVE is used, it may be a good idea to use
non-temporal move instructions already for smaller blocks. E.g., if
you know that you will not use the from block of a 2KB MOVE soon, it
may be worthwhile to use non-temporal loads to avoid the overhead of
reloading the cache lines evicted by ordinary loads. Or if you know
that the from block of a MOVE will not be used soon, the same is true
for stores. However, we probably don't want to introduce MOVE-NT>T
MOVE-T>NT MOVE-NT>NT in addition to the ordinary MOVE (I thing
temporal is a good default for block sizes < 1/2 L1).

> We have found that for a certain upper bound, CODE
>words of the REP MOV type are useful,

REP MOVSB has been optimized on some microarchitectures, but is slow
on some others. Even on those where it has been optimized, code
consisting of simpler instructions tends to beat it on many use cases.
E.g., looking at the Skylake results in
<2017Sep23.174313@mips.complang.tuwien.ac.at>, REP MOVSB beats my
avxmemcpy only if both the block size is 16KB and the aligned move is
benchmarked. My guess is that REP MOVSB on Skylake uses non-temporal
memory accesses plus a fence, which causes a slowdown for all smaller
blocks in these benchmarks, but the temporal accesses in avxmemcpy
lead to slowdowns due to cache conflicts with 16KB blocks (16KB from
block, 16KB to block, and likely a virtual-memory mapping that
introduces a conflict).

You need to use wide-memory instructions (SSE, AVX, AVX512) for
optimal performance with simpler instructions, though.

>really no ideas what to
>improve next).

Keep all the a-h values in registers all the time. With lxf64 this
may be possible to achieve with the locals-to-stack-to-locals
technique I used for your (incorrect) implementation of SHA512
<2022Jan30.232519@mips.complang.tuwien.ac.at> (plus some way to work
around the lack of inlining, if that lack still exists). For iForth
you would need to put locals in registers, or rewrite the code to use
only the stacks.

- 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 2021: https://euro.theforth.net/2021

On 2/23/22 02:15, Marcel Hendrix wrote:
> On Wednesday, February 23, 2022 at 4:15:31 AM UTC+1, Krishna Myneni wrote:
>> On 2/22/22 16:09, P Falth wrote:
>>> On Tuesday, 22 February 2022 at 02:16:23 UTC+1, Krishna Myneni wrote:
>>>> On 2/19/22 20:39, Krishna Myneni wrote:
> [..]
>>> Looking at the shift_with_add function I see it uses MOVE to to speed up.
>>> On LXF64 in this case that translates to using CMOVE> as it is overwriting its buffer
>>> In LXF64 this compiles to a rep movsb with the direction flag set. It is copying down
>>> in memory, a slow operation. Instead I tested with:
> [..]
>>>
>>> The result is that it is now running the 40MB shaspeed in 350 ms!
>>>
>> I used the following equivalent machine code macro for SHIFT_WITH_ADD in
>> sha512-x86_64.4th
>> The revised version of the hybrid Forth+machine code program, version
>> 0.05, increases the hashing rate from 37 MB/s to 63 MB/s with kforth64
>> on my system -- SHASPEED reports an elapsed time for 40 MB of 639 ms. A
>> nice improvement!
>
> For iForth64 Hanno Schwalm put a lot of work in CMOVE and all of
> its variants. The problem is that OS calls are unbeatable for large
> size transfers, but these calls are expensive to set up and clean up
> afterwards. We have found that for a certain upper bound, CODE
> words of the REP MOV type are useful, but for very small size
> (I think it was below 32 bytes) one better uses !+, !- etc. The
> problem for the compiler is to figure out the transfer size
> at compile time. Shaspeed is a good example of this.
>
> However, optimizing CMOVE with !+ only decreases the runspeed
> by 10ms or so (currently at 113 ms and really no ideas what to
> improve next).
>

The utility sha512sum on Linux appears to have a hashing rate in excess
of 500 MB/s on my system, so it may be worthwhile to examine its source
code.

To clarify, my intent with the Forth/machine code hybrid program is
simply to determine how much efficiency can be gained from a
straightforward Forth/assembly code mixed source within a non-optimizing
indirect threaded code Forth compiler. It is not intended to be an
argument against the need to use an optimizing Forth compiler with pure
Forth source. The goal of an optimizing compiler is worthwhile, although
it is not always necessary.

--
Krishna

On Saturday, February 19, 2022 at 8:39:14 PM UTC-6, Krishna Myneni wrote:

> s" abc" SHA512_Data type
> >DDAF35A193617ABACC417349AE20413112E6FA4E89A97EA20A9EEEE64B55D39A2192992A274FC1A836BA3C23A3FEEBBD454D4423643CE80E2A9AC94FA54CA49F

That does agree with document, but I'm getting:
:) echo abc|sha512sum
4f285d0c0cc77286d8731798b7aae2639e28270d4166f40d769cbbdca5230714d848483d364e2f39fe6cb9083c15229b39a33615ebc6d57605f7c43f6906739d -
Any guess as to why?
--
me

On Wednesday, February 23, 2022 at 9:17:40 AM UTC-6, S Jack wrote:
> On Saturday, February 19, 2022 at 8:39:14 PM UTC-6, Krishna Myneni wrote:
>
> > s" abc" SHA512_Data type
> > >DDAF35A193617ABACC417349AE20413112E6FA4E89A97EA20A9EEEE64B55D39A2192992A274FC1A836BA3C23A3FEEBBD454D4423643CE80E2A9AC94FA54CA49F
> That does agree with document, but I'm getting:
> :) echo abc|sha512sum
> 4f285d0c0cc77286d8731798b7aae2639e28270d4166f40d769cbbdca5230714d848483d364e2f39fe6cb9083c15229b39a33615ebc6d57605f7c43f6906739d -
> Any guess as to why?
> --
> me

ok found it.
:) echo -n abc|sha512sum
ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f -
--
me

On Wednesday, February 23, 2022 at 11:17:56 AM UTC+1, Anton Ertl wrote:
> Marcel Hendrix <m...@iae.nl> writes:
[..]
> >really no ideas what to
> >improve next).
> Keep all the a-h values in registers all the time. [..] For iForth
> you would need to put locals in registers, or rewrite the code to use
> only the stacks.

Thank you for cleaning up my terminology.

In your opinion, would be it be effective to store/load locals in the
SSE/AVX registers (I only use the FPU in iForth)? There is, or was,
overhead in switching between floating-point modes but I notice
that the Intel C/Fortran compilers can mix e.g. SSE with FPU instructions.
I don't know if this is because of wishing to use the 80-bit extended
floats, or if the FPU can actually run in parallel with wide-memory
instructions.

-marcel

Marcel Hendrix <mhx@iae.nl> writes:
>In your opinion, would be it be effective to store/load locals in the
>SSE/AVX registers (I only use the FPU in iForth)?

I would put cells in the GPRs (rax-r15); should be enough for a-h plus
a few temporary values, plus the stack pointers. I tend to avoid
moving data between GPRs and XMM/YMM registers, so I don't know if
that is fast or slow. I think for stuff like SHA512 where (I think)
the data is not used as addresses, you could run the whole computation
in XMM/YMM/ZMM registers. But I would design my Forth system to use
GPRs and instructions that work on that, so that's more a CODE word
option for me.

> the Intel C/Fortran compilers can mix e.g. SSE with FPU instructions.
>I don't know if this is because of wishing to use the 80-bit extended
>floats, or if the FPU can actually run in parallel with wide-memory
>instructions.

Running the FPU in parallel with the load/store unit is not a problem
for recent (or not so recent) CPU cores.

- 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 2021: https://euro.theforth.net/2021

On Wednesday, February 23, 2022 at 11:20:10 PM UTC+1, Anton Ertl wrote:
> Marcel Hendrix <m...@iae.nl> writes:
> >In your opinion, would be it be effective to store/load locals in the
> >SSE/AVX registers (I only use the FPU in iForth)?
> I would put cells in the GPRs (rax-r15); should be enough for a-h plus
> a few temporary values, plus the stack pointers.

This is part of the main sha512 loop:
[...]
e f g Ch +
e sigma1_512u + h + ( T1 )
a sigma0_512u a b c Maj + ( T2 )
[ HERE H. ]
g TO h f TO g e TO f
OVER ( T1 ) d + TO e
c TO d b TO c a TO b
( T1 T2 ) + TO a
LOOP
[...]
The HERE H. is to find out the address idis needs:

FORTH> $013480C1 idis
$013480C1 mov r9, $01342540 qword-offset
$013480C8 mov $01342560 qword-offset, r9
$013480CF mov r9, $01342520 qword-offset
$013480D6 mov $01342540 qword-offset, r9
$013480DD mov r9, $01342500 qword-offset
$013480E4 mov $01342520 qword-offset, r9
\ apparently T1 is in rax
$013480EB mov r9, rax
$013480EE add r9, $013424E0 qword-offset
$013480F5 mov $01342500 qword-offset, r9
$013480FC mov r9, $013424C0 qword-offset
$01348103 mov $013424E0 qword-offset, r9
$0134810A mov r9, $013424A0 qword-offset
$01348111 mov $013424C0 qword-offset, r9
$01348118 mov r9, $01342480 qword-offset
$0134811F mov $013424A0 qword-offset, r9
\ looks like T2 is known as the sum of rdi and rdx ( Maj + )
$01348126 lea rdi, [rdi rdx*1] qword
$0134812A lea rcx, [rax rdi*1] qword
$0134812E mov $01342480 qword-offset, rcx
[...]
There is quite an overuse of r9, but isn't AMD doing register
renaming behind our backs by now?

LOOP is still as bad as when you last criticized it
so I won't show it.

-marcel

Marcel Hendrix <mhx@iae.nl> writes:
>On Wednesday, February 23, 2022 at 11:20:10 PM UTC+1, Anton Ertl wrote:
>> Marcel Hendrix <m...@iae.nl> writes:
>> >In your opinion, would be it be effective to store/load locals in the
>> >SSE/AVX registers (I only use the FPU in iForth)?
>> I would put cells in the GPRs (rax-r15); should be enough for a-h plus
>> a few temporary values, plus the stack pointers.
>
>This is part of the main sha512 loop:
>[...]
> e f g Ch +
> e sigma1_512u + h + ( T1 )
> a sigma0_512u a b c Maj + ( T2 )
>[ HERE H. ]
> g TO h f TO g e TO f
> OVER ( T1 ) d + TO e
> c TO d b TO c a TO b
> ( T1 T2 ) + TO a
> LOOP
>[...]
>The HERE H. is to find out the address idis needs:
>
>FORTH> $013480C1 idis
>$013480C1 mov r9, $01342540 qword-offset
>$013480C8 mov $01342560 qword-offset, r9
>$013480CF mov r9, $01342520 qword-offset
>$013480D6 mov $01342540 qword-offset, r9
>$013480DD mov r9, $01342500 qword-offset
>$013480E4 mov $01342520 qword-offset, r9
>\ apparently T1 is in rax
>$013480EB mov r9, rax
>$013480EE add r9, $013424E0 qword-offset
>$013480F5 mov $01342500 qword-offset, r9
>$013480FC mov r9, $013424C0 qword-offset
>$01348103 mov $013424E0 qword-offset, r9
>$0134810A mov r9, $013424A0 qword-offset
>$01348111 mov $013424C0 qword-offset, r9
>$01348118 mov r9, $01342480 qword-offset
>$0134811F mov $013424A0 qword-offset, r9
>\ looks like T2 is known as the sum of rdi and rdx ( Maj + )
>$01348126 lea rdi, [rdi rdx*1] qword
>$0134812A lea rcx, [rax rdi*1] qword
>$0134812E mov $01342480 qword-offset, rcx
>[...]
>There is quite an overuse of r9, but isn't AMD doing register
>renaming behind our backs by now?

Yes, AMD has been using hardware register renaming since the K5 (and
Intel since the Pentium Pro), so I would not expect an improvement if
you used different registers. What I mean is getting rid of all these
stores by keeping a-h in registers.

If you keep them in memory, you can use the AVX instructions to reduce
the 8 64-bit loads to 2 256-bit loads, and the 8 stores to 2 256-bit
stores and 2 64-bit store (or you merge the new results while the data
in in YMM registers; but I think that would require so many
instructions that it would be a loss). I would arrange the data such
that the 256-bit stores are 256-bit-aligned.

>LOOP is still as bad as when you last criticized it
>so I won't show it.

The loop body takes more than the 5-6 cycles minimum latency caused by
keeping the loop counter in memory, so I don't think it causes a
significant slowdown here.

- 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 2021: https://euro.theforth.net/2021

On 2/22/22 21:15, Krishna Myneni wrote:
> On 2/22/22 16:09, P Falth wrote:
....
>> The result is that it is now running the 40MB shaspeed in 350 ms!
>>
>
....
> The revised version of the hybrid Forth+machine code program, version
> 0.05, increases the hashing rate from 37 MB/s to 63 MB/s with kforth64
> on my system -- SHASPEED reports an elapsed time for 40 MB of 639 ms. A
> nice improvement!
>

Further improvements include rounds looping within the assembler code,
as well as the accumulation of the a--h constants. My revised
SHA512_TRANSFORM is

: SHA512_Transform ( addr -- )
>r
sreg_acc shiftreg 8 CELLS MOVE
shiftreg K512[] W512[] r> roundsA
shiftreg K512[] W512[] roundsB
shiftreg sreg_acc accumulate ;

The SHASPEED test (hashing 40 MB) takes 196 ms, giving a hashing rate in
excess of 200 MB/s with kforth64 on my system.

The updated file, sha512-x86_64.4th, may be found at

https://github.com/mynenik/kForth-64/blob/master/forth-src/sha512-x86_64.4th

--
Krishna

On Thursday, February 24, 2022 at 9:40:56 AM UTC+1, Anton Ertl wrote:
> Marcel Hendrix <m...@iae.nl> writes:
> >On Wednesday, February 23, 2022 at 11:20:10 PM UTC+1, Anton Ertl wrote:
> >> Marcel Hendrix <m...@iae.nl> writes:
> >> >In your opinion, would be it be effective to store/load locals in the
> >> >SSE/AVX registers (I only use the FPU in iForth)?
> >> I would put cells in the GPRs (rax-r15); should be enough for a-h plus
> >> a few temporary values, plus the stack pointers.
> >
> >This is part of the main sha512 loop:
> >[...]
> > e f g Ch +
> > e sigma1_512u + h + ( T1 )
> > a sigma0_512u a b c Maj + ( T2 )
> >[ HERE H. ]
> > g TO h f TO g e TO f
> > OVER ( T1 ) d + TO e
> > c TO d b TO c a TO b
> > ( T1 T2 ) + TO a
> > LOOP
> >[...]
> >The HERE H. is to find out the address idis needs:
> >
> >FORTH> $013480C1 idis
> >$013480C1 mov r9, $01342540 qword-offset
> >$013480C8 mov $01342560 qword-offset, r9
> >$013480CF mov r9, $01342520 qword-offset
> >$013480D6 mov $01342540 qword-offset, r9
> >$013480DD mov r9, $01342500 qword-offset
> >$013480E4 mov $01342520 qword-offset, r9
> >\ apparently T1 is in rax
> >$013480EB mov r9, rax
> >$013480EE add r9, $013424E0 qword-offset
> >$013480F5 mov $01342500 qword-offset, r9
> >$013480FC mov r9, $013424C0 qword-offset
> >$01348103 mov $013424E0 qword-offset, r9
> >$0134810A mov r9, $013424A0 qword-offset
> >$01348111 mov $013424C0 qword-offset, r9
> >$01348118 mov r9, $01342480 qword-offset
> >$0134811F mov $013424A0 qword-offset, r9
> >\ looks like T2 is known as the sum of rdi and rdx ( Maj + )
> >$01348126 lea rdi, [rdi rdx*1] qword
> >$0134812A lea rcx, [rax rdi*1] qword
> >$0134812E mov $01342480 qword-offset, rcx
> >[...]
> >There is quite an overuse of r9, but isn't AMD doing register
> >renaming behind our backs by now?
> Yes, AMD has been using hardware register renaming since the K5 (and
> Intel since the Pentium Pro), so I would not expect an improvement if
> you used different registers. What I mean is getting rid of all these
> stores by keeping a-h in registers.
>
> If you keep them in memory, you can use the AVX instructions to reduce
> the 8 64-bit loads to 2 256-bit loads, and the 8 stores to 2 256-bit
> stores and 2 64-bit store (or you merge the new results while the data
> in in YMM registers; but I think that would require so many
> instructions that it would be a loss). I would arrange the data such
> that the 256-bit stores are 256-bit-aligned.
> >LOOP is still as bad as when you last criticized it
> >so I won't show it.
> The loop body takes more than the 5-6 cycles minimum latency caused by
> keeping the loop counter in memory, so I don't think it causes a
> significant slowdown here.

I hoped for an easier win here, but it is not so simple. I added 8 register
vars to iForth64 (lower 64-bit half of xmm0 ... xmm7). The code now
looks like the below. Unfortunately our disassembler is not good enough
yet for this job, so I can't show everything. This is somewhere around
the #80 #16 DO ... location in SHA512_transform.
....
$013A8856 mov rdi, [rbp 0 +] qword
$013A885A add rdx, [rdi*8 $013A2CA0 +] qword
$013A8862 lea rbx, [rbx #32 +] qword
$013A8866 push rbx
$013A8867 mov rbx, rdx
$013A886A push rbx
$013A886B movq rbx, xmm4
$013A8870 push rbx
$013A8871 movq rbx, xmm5
$013A8876 push rbx
$013A8877 movq rbx, xmm6
$013A887C pop rdi
$013A887D pop rax
$013A887E and rdi, rax
$013A8881 not rax
$013A8884 and rax, rbx
$013A8887 xor rdi, rax
$013A888A pop rbx
$013A888B lea rbx, [rbx rdi*1] qword
$013A888F push rbx
$013A8890 movq rbx, xmm4
$013A8895 mov rdi, rbx
$013A8898 ror rdi, #14 b#
$013A889C mov rax, rbx
$013A889F ror rax, #18 b#
$013A88A3 xor rdi, rax
$013A88A6 ror rbx, #41 b#
$013A88AA xor rdi, rbx
....
etc.

It is actually quite a bit slower than when using ordinary locals.
FORTH> S" abc" SHA512_Data .SHA512
DDAF35A1 93617ABA CC417349 AE204131 12E6FA4E 89A97EA2
0A9EEEE6 4B55D39A 2192992A 274FC1A8 36BA3C23 A3FEEBBD
454D4423 643CE80E 2A9AC94F A54CA49F ok
FORTH> SHAspeed
Processing 40 Mbytes ... 0.142 seconds elapsed. ok

With locals this is 0.113 ms.

A simple benchmark with the new regvars shows that the SSE
instructions are about 50% slower than instructions between GPRs.
Maybe I should use both halves of the XMM register, per your
suggestion.

: MAKE-REGVARS ( -- )
'i' 'a' DO I 'a' - S" FROM-REG " I CHAR-APPEND EVALUATE
I 'a' - S" TO-REG TO_" I CHAR-APPEND EVALUATE
LOOP ;

MAKE-REGVARS

: tt1 CR ." \ tt1 " TIMER-RESET
0 TO_a 1 TO_b 2 TO_c 3 TO_d 4 TO_e 5 TO_f 6 TO_g 7 TO_h
0 #1000000000
0 DO a + b + c + d + e + f + g + h + LOOP .ELAPSED SPACE . ;

0 VALUE t0 0 VALUE t1 0 VALUE t2 0 VALUE t3
0 VALUE t4 0 VALUE t5 0 VALUE t6 0 VALUE t7

: tt2 CR ." \ tt2 " TIMER-RESET
0 TO t0 1 TO t1 2 TO t2 3 TO t3 4 TO t4 5 TO t5 6 TO t6 7 TO t7
0 #1000000000
0 DO t0 + t1 + t2 + t3 + t4 + t5 + t6 + t7 + LOOP .ELAPSED SPACE . ;

FORTH> tt1 tt2 ( disappointing ... )
\ tt1 2.485 seconds elapsed. 28000000000
\ tt2 1.730 seconds elapsed. 28000000000 ok

-marcel