CMOVE/CMOVE>

[Mark Wills]

I'm aware of the word MOVE which will choose to perform either a CMOVE or CMOVE> depending on overlap and direction. My system doesn't have MOVE though I'd like to implement it.

Does anyone have any nice concise logic for checking the parameters and calling either CMOVE or CMOVE> accordingly?

Many thanks

Mark

[Anton Ertl]

Mark Wills <markwi...@gmail.com> writes:
>I'm aware of the word MOVE which will choose to perform either a CMOVE or CMOVE> depending on overlap and direction. My system doesn't have MOVE though I'd like to implement it.
>
>Does anyone have any nice concise logic for checking the parameters and calling either CMOVE or CMOVE> accordingly?

: move ( from to count -- )
>r 2dup u< if
r> cmove>
else
r> cmove
then ;

Better branch prediction accuracy:

: move ( from to count -- )
>r 2dup dup r@ + within if
r> cmove
else
r> cmove>
then ;

Both not tested.

- 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.mpeforth.com/euroforth2015/euroforth2015.htm

[novembe...@gmail.com]

for the second example ;

shouldn't that be : >r 2dup over r@ + within if ( from + count ) ?

NN

[Anton Ertl]

novembe...@gmail.com writes:
>
>for the second example ;
>
>shouldn't that be : >r 2dup over r@ + within if ( from + count ) ?

My idea was to test whether FROM is within [TO, TO+COUNT), so I think
my version is right. Other variations are also possible, of course.

[Mark Wills]

That's nice code, thank you. Mine also included WITHIN but your first
example is neater IMO. I just tested it quickly and it seems to work fine.

Thanks.

Mark

[Michael Barry]

On Tuesday, August 18, 2015 at 9:59:02 AM UTC-7, Mark Wills wrote:
>
> > : move ( from to count -- )
> > >r 2dup u< if
> > r> cmove>
> > else
> > r> cmove
> > then ;
> >
> > Better branch prediction accuracy:
> >
> > : move ( from to count -- )
> > >r 2dup dup r@ + within if
> > r> cmove
> > else
> > r> cmove>
> > then ;
> >
> > Both not tested.
> >
> > - anton
> > --
> >
>

> That's nice code, thank you. Mine also included WITHIN but your first
> example is neater IMO. I just tested it quickly and it seems to work fine.
>
> Thanks.
>
> Mark

Isn't it true that the decision can be made based simply on whether source start is less than destination start, regardless of count? Mine does that, but CMOVE> and CMOVE have equivalent performance, which might mot always be the case.

[code]

;----------- 65m32: smart move --------
; Move memory up/down (1 W to 4 GW)
; x = source start address
; y = destination start address
; b = number of words to move
; (4 GW are moved if b == 0 !!)
;
:88020000 move: cpy #,x
:42420000 mvdown: lda [cc],x+
:a2440000 sta [cc],y+
:8c49fffd dbn [cc]mvdown,b
:5e4c0000 rts [cc]
:e4080000 adx #,b
:e8080000 ady #,b
:43020000 moveup: lda ,-x
:a3040000 sta ,-y
:8c09fffd dbn moveup,b
:5e0c0000 rts
[/code]

Mike B.

[hughag...@gmail.com]

On Tuesday, August 18, 2015 at 10:10:22 AM UTC-7, Michael Barry wrote:
> On Tuesday, August 18, 2015 at 9:59:02 AM UTC-7, Mark Wills wrote:
> >
> > > : move ( from to count -- )
> > > >r 2dup u< if
> > > r> cmove>
> > > else
> > > r> cmove
> > > then ;
> > >
> > > Better branch prediction accuracy:
> > >
> > > : move ( from to count -- )
> > > >r 2dup dup r@ + within if
> > > r> cmove
> > > else
> > > r> cmove>
> > > then ;
> > >
> > > Both not tested.
> > >
> > > - anton
> > > --
> > >
> >
> > That's nice code, thank you. Mine also included WITHIN but your first
> > example is neater IMO. I just tested it quickly and it seems to work fine.
> >
> > Thanks.
> >
> > Mark
>
> Isn't it true that the decision can be made based simply on whether source start is less than destination start, regardless of count? Mine does that, but CMOVE> and CMOVE have equivalent performance, which might mot always be the case.

Yes, it is only necessary to compare the start addresses.

Checking the count to determine if CMOVE> is strictly necessary presumes that CMOVE> should be avoided as much as possible. I don't really know why there would be any difference in speed on any processor though. There is a slight overhead with CMOVE> in that you have to add the counts to the start-addresses to obtain the limit-addresses, but that is done only once and should be over-shadowed by the time needed to do all the moves.

It would be a good idea to have a MOVE that is only for structs whose size is a cell-multiple (this is always true in the novice-package because FIELD cell-aligns the fields in a struct).

It would also be a good idea to have an EXCHANGE like I do in the novice-package (but it is very slow when written in Forth rather than assembly-language). Note that mine assumes that the struct size is a cell-multiple.

Anyway --- none of these good ideas will be in Forth-200x --- at least, not unless Leon Wagner says so.

> [code]
>
> ;----------- 65m32: smart move --------
> ; Move memory up/down (1 W to 4 GW)
> ; x = source start address
> ; y = destination start address
> ; b = number of words to move
> ; (4 GW are moved if b == 0 !!)
> ;
> :88020000 move: cpy #,x
> :42420000 mvdown: lda [cc],x+
> :a2440000 sta [cc],y+
> :8c49fffd dbn [cc]mvdown,b
> :5e4c0000 rts [cc]
> :e4080000 adx #,b
> :e8080000 ady #,b
> :43020000 moveup: lda ,-x
> :a3040000 sta ,-y
> :8c09fffd dbn moveup,b
> :5e0c0000 rts
> [/code]
>
> Mike B.

Oh, I just noticed that your code does move cells. I think you mentioned that you don't have byte-addressing.

Why don't you publish a document describing your 65m32 similar to my document describing the FMITE processor? Nobody knows what any of those instructions do. BTW: does the 'm' in 65m32 stand for "Michael"?

[Mark Wills]

I think so, yes.

I just knocked this up to move blocks around. It's for my hobby Forth
system running on antiquated (>30 years old) hardware. Think 5.25"
floppies and you're in the ball park.

It uses locals. From some quick experiments, locals on a dumb (non-
optimising) ITC makes things faster. The reason? All the stack juggling
goes away. Those ROTs DUPs SWAPs etc are burning up time just getting
the stack arranged. Locals on a dumb system takes that away. The
argument doesn't hold on modern optimising systems.

Anyway, it's moot... The disk I/O is millions of times slower than
the code! But locals sure makes it easy... Like falling of a log.

Ignore FLUSH? It just checks the block buffers and one or more is
not flushed (dirty?) it offers the choice to do a flush first.

: movblk ( src dest cnt -- )
locals{ src dest cnt cpydir }
set cnt set dest set src
src dest < if
cnt 1- +set src
cnt 1- +set dest
-1 set cpydir
else
1 set cpydir
then flush?
cnt 0 do
2 spaces src . ." to " dest .
src block drop 0 dest setblk 0 dirty flush
cpydir +set src
cpydir +set dest
loop ;

[Mark Wills]

Woops....

37 CLOAD LOCALS{
: flush? ( -- ) \ offer choice to flush if buffers are dirty
0 #buf @ 0 do i dirty? or loop if ." Flush? (Y/N)" key dup
ascii Y = swap ascii y = or if flush then then empty-buffers ;

[Alex McDonald]

on 18/08/2015 18:41:19, wrote:
> > On Tuesday, August 18, 2015 at 10:10:22 AM UTC-7, Michael Barry wrote:

>>
>> Isn't it true that the decision can be made based simply on whether sourc
> e start is less than destination start, regardless of count? Mine does

> tha t, but CMOVE> and CMOVE have equivalent performance, which might

> mot always be the case.
>
> Yes, it is only necessary to compare the start addresses.

No, because if there's an overlap then there may be advantages in using
larger than CHAR sized moves. When there is an overlap, CMOVE> should
always do a character by character move (for instance, on the x86 REP
MOVS BYTE); otherwise much larger units can be CMOVE>d if there is no
overlap (REP MOVS DWORD or QWORD or MOVDQU thru XMM registers, etc). The
difference in performance can be considerable.

[Bernd Paysan]

Anton Ertl wrote:

> Mark Wills <markwi...@gmail.com> writes:
>>I'm aware of the word MOVE which will choose to perform either a CMOVE or
>>CMOVE> depending on overlap and direction. My system doesn't have MOVE
>>though I'd like to implement it.
>>
>>Does anyone have any nice concise logic for checking the parameters and
>>calling either CMOVE or CMOVE> accordingly?
>
> : move ( from to count -- )
> >r 2dup u< if
> r> cmove>
> else
> r> cmove
> then ;
>
> Better branch prediction accuracy:
>
> : move ( from to count -- )
> >r 2dup dup r@ + within if
> r> cmove
> else
> r> cmove>
> then ;
>
> Both not tested.

The first one is tested, we use it in Gforth EC.

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

[Rod Pemberton]

On Tue, 18 Aug 2015 12:59:01 -0400, Mark Wills <markwi...@gmail.com> wrote:

> On Tuesday, 18 August 2015 17:16:28 UTC+1, Anton Ertl wrote:
>> Mark Wills <markwi...@gmail.com> writes:

>> >I'm aware of the word MOVE which will choose to perform either a CMOVE
>> >or CMOVE> depending on overlap and direction. My system doesn't have
>> >MOVE though I'd like to implement it.
>> >
>> >Does anyone have any nice concise logic for checking the parameters and
>> >calling either CMOVE or CMOVE> accordingly?
>>
>> : move ( from to count -- )
>> >r 2dup u< if
>> r> cmove>
>> else
>> r> cmove
>> then ;
>>
>> Better branch prediction accuracy:
>>

>> [...]

>
> That's nice code, thank you. Mine also included WITHIN but your first
> example is neater IMO. I just tested it quickly and it seems to work fine.

There is lots of useful information to be found in Google Groups
archive of comp.lang.forth.


BruceMcF Dec 2010
https://groups.google.com/d/msg/comp.lang.forth/zFEW7-NWJXM/rI8nbNsw9z0J

His '>' should probably be 'U>'. His IF sections are reversed too.


Michael L Gassanenko's CMOVE CMOVE> MOVE Mar 2002
https://groups.google.com/d/msg/comp.lang.forth/hYokH0zY9RY/xSFFFb2CSJ0J

He has a slight variation for MOVE. He moves the duplicate R> outside
the conditional.


I have the same as Anton's, except the IF sections are reversed from
Anton's, like BruceMcF did too, i.e., U> instead of U< . Both CMOVE
and CMOVE> should perform the copy of the region if 'from' = 'to'.
So, this shouldn't matter, unless there is an implementation issue
with CMOVE or CMOVE> . I.e., it's possibly worth checking to make
sure it actually works when 'from' = 'to'. If 'from' and 'to' are
actually equal - unlikely, but possible - you might want to kick out
of the definition, i.e., to not waste time doing a useless copy.


Rod Pemberton

--
Scientists now say we'll experience a mini-ice in 2030.
So, I guess we need more global warming today ...

[Mark Wills]

Great stuff. Thanks for the links, Rod.

[Anton Ertl]

Michael Barry <barry...@yahoo.com> writes:
>On Tuesday, August 18, 2015 at 9:59:02 AM UTC-7, Mark Wills wrote:
>>
>> > : move ( from to count -- )
>> > >r 2dup u< if
>> > r> cmove>
>> > else
>> > r> cmove
>> > then ;
>> >
>> > Better branch prediction accuracy:
>> >
>> > : move ( from to count -- )
>> > >r 2dup dup r@ + within if
>> > r> cmove
>> > else
>> > r> cmove>
>> > then ;
>> >
>> > Both not tested.
>> >
>> > - anton
>> > --
>> >
>>
>> That's nice code, thank you. Mine also included WITHIN but your first
>> example is neater IMO. I just tested it quickly and it seems to work fine.
>>
>> Thanks.
>>
>> Mark
>
>Isn't it true that the decision can be made based simply on whether source start is less than destination start, regardless of count?

Correct (assuming that neither source nor destination regions cross
the -1..0 boundary), that's what the U< version does. The WITHIN
version always uses CMOVE> for the non-overlap case, and thus will
probably produce better branch prediction (if the CPU has a branch
predictor).

[Anton Ertl]

If you implement MOVE, you can use larger granularity for either
direction (of course, you need to take care of the remainder at the
start and/or end). I would hope that on an IA-32/AMD64 CPU the CPU
does that for you if you use REP MOVSB and the parameters are
appropriate. Unfortunately, it seems that doing it in software is
faster, at least for microbenchmarks, and this has lead to glibc's
memmove() having 11KB of code. This is likely to be slower in
applications due to I-cache misses, but as long as it produces good
microbenchmark results...

Even for CMOVE or CMOVE> you can usually use a larger granularity even
for the overlap case; the granularity for CMOVE must just be at most
TO-FROM for CMOVE and FROM-TO for CMOVE>.

[Alex McDonald]

on 19/08/2015 09:40:45, wrote:
> "Alex McDonald" <bl...@rivadpm.com> writes:
>>on 18/08/2015 18:41:19, wrote:
>>> > On Tuesday, August 18, 2015 at 10:10:22 AM UTC-7, Michael Barry wrote:
>>
>>>>
>>>> Isn't it true that the decision can be made based simply on whether sourc
>>> e start is less than destination start, regardless of count? Mine does
>>> tha t, but CMOVE> and CMOVE have equivalent performance, which might
>>> mot always be the case.
>>>
>>> Yes, it is only necessary to compare the start addresses.
>>
>>No, because if there's an overlap then there may be advantages in using

s/there's an overlap/there's not an overlap/ but you got my drift.

>>larger than CHAR sized moves. When there is an overlap, CMOVE> should
>>always do a character by character move (for instance, on the x86 REP
>>MOVS BYTE); otherwise much larger units can be CMOVE>d if there is no
>>overlap (REP MOVS DWORD or QWORD or MOVDQU thru XMM registers, etc). The
>>difference in performance can be considerable.
>
> If you implement MOVE, you can use larger granularity for either
> direction (of course, you need to take care of the remainder at the
> start and/or end). I would hope that on an IA-32/AMD64 CPU the CPU
> does that for you if you use REP MOVSB and the parameters are
> appropriate. Unfortunately, it seems that doing it in software is
> faster, at least for microbenchmarks, and this has lead to glibc's
> memmove() having 11KB of code. This is likely to be slower in
> applications due to I-cache misses, but as long as it produces good
> microbenchmark results...

On further reading, it appears that (for instance, the Intel Haswell) REP
MOVS BYTE is optimised iif both source and dest are aligned to 32 bytes.
http://www.agner.org/optimize/microarchitecture.pdf pg 142 where it
recommends 256 bit registers otherwise. The net is full of contrarian
advice and equally varied code.

This is BSD's memmove()
http://cvsweb.openbsd.org/cgi-bin/cvsweb/~checkout~/src/sys/lib/libkern/arch/amd64/memmove.S?rev=1.5&content-type=text/plain
It's much shorter and the very paragon of simplicity compared to the
glibc version.

My CMOVE CMOVE> use MOVS BYTE; MOVE uses MOVS DWORD for the bulk word
aligned and MOVS BYTE for the remaining top and tail. I wrote a bulk copy
based on MOVDQU. I haven't benchmarked it properly, but it was marginally
but measurably faster than MOVE for large blocks.

>
> Even for CMOVE or CMOVE> you can usually use a larger granularity even
> for the overlap case; the granularity for CMOVE must just be at most
> TO-FROM for CMOVE and FROM-TO for CMOVE>.

Point taken; the overlap still needs checked to do so.

>
> - anton

[HAA]

Mark Wills wrote:
> >
> > I just knocked this up to move blocks around. It's for my hobby Forth
> > system running on antiquated (>30 years old) hardware. Think 5.25"
> > floppies and you're in the ball park.
> >
> > It uses locals. From some quick experiments, locals on a dumb (non-
> > optimising) ITC makes things faster. The reason? All the stack juggling
> > goes away. Those ROTs DUPs SWAPs etc are burning up time just getting
> > the stack arranged. Locals on a dumb system takes that away. The
> > argument doesn't hold on modern optimising systems.
> >
> > Anyway, it's moot... The disk I/O is millions of times slower than
> > the code! But locals sure makes it easy... Like falling of a log.

> > ...
>
> 37 CLOAD LOCALS{
> : flush? ( -- ) \ offer choice to flush if buffers are dirty
> 0 #buf @ 0 do i dirty? or loop if ." Flush? (Y/N)" key dup
> ascii Y = swap ascii y = or if flush then then empty-buffers ;
>
> : movblk ( src dest cnt -- )
> locals{ src dest cnt cpydir }
> set cnt set dest set src
> src dest < if
> cnt 1- +set src
> cnt 1- +set dest
> -1 set cpydir
> else
> 1 set cpydir
> then flush?
> cnt 0 do
> 2 spaces src . ." to " dest .
> src block drop 0 dest setblk 0 dirty flush
> cpydir +set src
> cpydir +set dest
> loop ;

Too many variables.

: bcopy ( src dest -- )
cr ." Copy " swap u. ." to " u.
\ swap block swap buffer 1024 cmove
\ update save-buffers
;

: movblk ( src dest cnt -- )

?dup if
swap 2 pick - >r 1- over +
r@ 0< if 1+ swap 1 else -1 then
r> 2swap do i 2dup + bcopy over +loop
then 2drop ;

10 12 bcopy
Copy 10 to 12 ok

10 12 5 movblk
Copy 14 to 16
Copy 13 to 15
Copy 12 to 14
Copy 11 to 13
Copy 10 to 12 ok

12 10 5 movblk
Copy 12 to 10
Copy 13 to 11
Copy 14 to 12
Copy 15 to 13
Copy 16 to 14 ok

[Elizabeth D. Rather]

The code with locals looks to me a lot messier than the earlier example.
In any case, a traditional block move would be quite simple:

: BMOVE (n1 n2 -- ) \ Moves the content of block n1 to n2.
>R BLOCK R> BLOCK 1024 CMOVE UPDATE ;

Very simple; locals would not be helpful. When BLOCK gets a buffer for a
block not already in memory, it will automatically write it to disk if
the selected buffer's contents are marked as UPDATED, so that's not
something the MOVE word needs to know about. Further, you know you can
count on there not being any overlap. If you have a version of MOVE that
does cell-wise moves, as Anton points out, that's preferable to CMOVE in
this case.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[HAA]

Mark Wills wrote:
>
> It uses locals. From some quick experiments, locals on a dumb (non-
> optimising) ITC makes things faster. The reason? All the stack juggling
> goes away. Those ROTs DUPs SWAPs etc are burning up time just getting
> the stack arranged. Locals on a dumb system takes that away. The
> argument doesn't hold on modern optimising systems.

I implemented TurboForth locals for LMI PC/Forth 3.2 (8086 ITC)
and ran a benchmark based on MOVBLK with and without locals.
A Pentium PC was used for the test.

Speed (I/O and CMOVE code replaced with 2DROP)

locals without locals
63 sec 52 sec

Code size (less headers)

locals without locals
122 bytes 92 bytes

Using an 8086 DTC forth

locals without locals
21 sec 9 sec

The benchmark used for the test is shown below. I'll post the source for
the LMI TurboForth locals if anyone wants it and you have no objection.
Your website doesn't mention whether derivative works are permitted.

13
0 \ TEST2
1
2 : bcopy ( src dest -- )
3 \ CR ." Copy " SWAP U. ." to " U.
4 SWAP BLOCK SWAP BUFFER 1024 CMOVE UPDATE FLUSH
5 ;
6 : movblk1 ( src dest cnt -- )
7 ?DUP IF
8 SWAP 2 PICK - >R OVER +
9 R@ 0< IF SWAP 1 ELSE 1- -1 THEN
10 R> 2SWAP DO I 2DUP + 2DROP ( bcopy) OVER +LOOP
11 THEN 2DROP ;
12
13
14
15

14
0 \ TEST2
1
2 : movblk2 ( src dest cnt -- )
3 LOCALS{ src dest cnt cpydir }
4 SET cnt SET dest SET src
5 1 SET cpydir src dest < IF
6 cnt 1- +SET src cnt 1- +SET dest -1 SET cpydir
7 THEN ( flush? ) cnt 0 ?DO
8 \ 2 SPACES src . ." to " dest .
9 \ src block drop 0 dest setblk 0 dirty flush
10 \ src BLOCK dest BUFFER 1024 CMOVE UPDATE FLUSH
11 src dest 2DROP
12 cpydir +SET src cpydir +SET dest
13 LOOP ;
14
15

15
0 \ TEST2
1 : T1 7 EMIT 20 0 DO
2 0 0 DO 10 12 5 movblk1 12 10 5 movblk1 LOOP
3 LOOP 7 EMIT ;
4
5 : T2 7 EMIT 20 0 DO
6 0 0 DO 10 12 5 movblk2 12 10 5 movblk2 LOOP
7 LOOP 7 EMIT ;
8
9
10
11
12
13
14
15

[Coos Haak]

Op Fri, 28 Aug 2015 22:39:42 +1000 schreef HAA:

Why the FLUSH? BUFFER knows when to write an UPDATEd blockbuffer.

groet Coos

[Mark Wills]

Sure. Feel free to publish. No problem at all.

Mark

[Mark Wills]

Interesting that the DTC version is twice as slow using locals. I wonder why?

[HAA]

Mark Wills wrote:
> Interesting that the DTC version is twice as slow using locals. I wonder why?

My guess is that with removal of the indirection you're starting to see the
real difference between the locals and non-locals version.

[m...@iae.nl]

On Friday, August 28, 2015 at 2:38:10 PM UTC+2, HAA wrote:
> Mark Wills wrote:
[..]

> Speed (I/O and CMOVE code replaced with 2DROP)

If the stack-code is one instruction, and the local code
two, the difference using your test is a factor of two.

The result is what it is, but presented in this way
it is not insightful. What were the timings of the
full test? How large was cnt?

-marcel

[HAA]

Coos Haak wrote:
>
> Why the FLUSH? BUFFER knows when to write an UPDATEd blockbuffer.
>
> groet Coos

BUFFER won't FLUSH the last block.

[HAA]

Don't know what you mean by 'full test'. The test used to
produce the timings are given in T1 and T2 which set cnt to 5.

[Coos Haak]

Op Sat, 29 Aug 2015 17:15:27 +1000 schreef HAA:

Admitted, but once is enough.

groet Coos

[Elizabeth D. Rather]

BUFFER should write the content of any block that has been marked
UPDATEd before reusing that buffer. You really only need to FLUSH when
you're about to shut down the computer.

[HAA]

Elizabeth D. Rather wrote:
> On 8/28/15 9:15 PM, HAA wrote:
> > Coos Haak wrote:
> >>
> >> Why the FLUSH? BUFFER knows when to write an UPDATEd blockbuffer.
> >>
> >> groet Coos
> >
> > BUFFER won't FLUSH the last block.
>
> BUFFER should write the content of any block that has been marked
> UPDATEd before reusing that buffer. You really only need to FLUSH when
> you're about to shut down the computer.

Or when there is an unacceptable risk of losing data you can't afford to lose.

[HAA]

For this application there is little to be gained putting FLUSH outside the loop.