Optimizing the 68020+ 32-bit math

[Bruce Abbott]

Originally Posted by litwr

Thank you for the clarification. However I use VASM and this is a legal syntax there. I suspect that this is true for many other assemblers.

Perhaps, but ProAsm, BAsm and PhxAss don't accept it. Since these are the only assemblers I use...

[Don_Adan]

And of course you can replace your strange

lsl.l D5

with

add.l D5,D5

[Don_Adan]

Minimum one bug was in previous version. Here is fixed version. I hope.

 clr.l -(SP) ; cv
.l0
....
 add.w (SP),D5 ; cv
 move.l D5,(SP) ; cv
 bsr PR0000
 endif
 sub.w #14,d6 ;kv
 bne .l0
 addq.l #4,SP ; restore stack

.....


PR0000 ;prints d5, uses a0,a1(scratch),d0,d1,d2,d3

 lea $100.W,A0
 move.l #$303A3030,D2
 move.w #1000,D3
b1000
 sub.w D3,D5
 bcs.b n100
 add.w A0,D2
 bra.b b1000

n100
 add.w D3,D5
 moveq #100,D3
b100
 sub.w D3,D5
 bcs.b n10
 addq.b #1,D2
 bra.b b100

n10
 add.w D3,D5
 swap D2
 moveq #10,D3
b10
 sub.w D3,D5
 bcs.b n1
 add.w A0,D2
 bra.b b10
n1
 add.b D5,D2

 lea cout(PC),A0
 move.l (A0)+,D1 
 move.l D2,(A0)
 move.l A0,D2 ; buf
 moveq #4,D3
 jmp Write(A6) ;call Write(stdout,buff,size)



 time dc.l 0 
 cout dc.l 0
 buf dc.l 0

[saimo]

Originally Posted by Bruce Abbott

What is the 'tiny showstopper', and what very specific machine induces it?

(Keeping it short because this is way OT.)
On one specific Amiga CD32 my custom NVRAM routines do not seem to work properly. The owner can't run tests for me at the moment. Details are in this post and in the thread it belongs to (you already know it).

[litwr]

Originally Posted by Don_Adan

You can use next version too, shortest next 2 bytes.

clr.l -(SP)  ; cv

I use the top of the stack as an additional variable in some PDP-11 versions of pi-spigot. The PDP-11 has only 6 registers and this is not enough sometime. You know the 68k assembler is derived from the PDP-11 assembly...
Maybe I will use an optimization similar to this one but the gain is very little so I will rather hesitate.

Originally Posted by Don_Adan

Write code works in loop too. You can check this version. If no my bugs can be fastest more than 100 cycles.

Thank you. However let us do some analysis. Your code is IMHO about 50 cycles faster. But it is also several dozen bytes larger. Let us check the exact speed gain. The Write-call for 4 chars takes about 75,000 cycles on the A500 and about 45,000 on the Amiga1200. So the total gain is less than 50*100/50000 = 0.1%. This value is undetectable.
Moreover, more digits of the pi we count, the less gain we get from your optimization. Let us examine 1000 digits case. The main loop takes place about 400,000 times, the output loop takes place exactly 250 times. The main loop takes more than 100 cycles. So your optimization gives us less than 50*250*100/400000/100 approx. = 0.03%. This value is also undetectable.
So we need at least 1000 saved cycles in the output loop to get some detectable gain.

Originally Posted by roondar

So for anyone else who, like me, might misread this: as long as you remember that EA means Effective Address, it'll all be fine.

It is quite logical to consider register addressing as a particular case of EA. In some architectures register addressing is a way to access memory. I can point to the TMS9900 and TMS9995 which were used in several popular home computers.
The attached screenshot from the manual confirms my point. This manual is available here - http://wpage.unina.it/rcanonic/didat...docs/68000.pdf
The same information is available in the other manual - https://web.njit.edu/~rosensta/class...tware/code.pdf
The official manual - https://www.nxp.com/docs/en/referenc.../M68000PRM.pdf also confirms my point. So britelite is rather not correct.

Originally Posted by saimo

It's a minor game _not_ written in assembly, but in AMOS Professional (the fun is precisely to make a game that implements original effects that would have been unthinkable before in such a language). Basically, all that's left to do is the music - I have the base ready, but I'm rather uninspired lately It's called Follix, and you can see the last (and a bit outdated) preview in this video: [ Show youtube player ]. (For completeness, I've had also the update of this 100% assembly game in the works since a very long time, and I'm stuck because there's one last tiny showstopper that happens only on a very specific machine, the one betatester of mine that could run tests for me isn't able to help me at the moment and I couldn't find someone else with an appropriate machine.)

Follix looks good and interesting. It is difficult to believe that it is written in Basic! I remember similar sensation when I first touched the 8 MHz Acorn Archimedes in 1991. They showed 3D animated graphics written in Basic!
Skillgrid looks perfect for me. I would like to have opportunities to help but now it is rather impossible.

Originally Posted by saimo

To be honest, no, I didn't know about it. It looks like a research/"science" game, right?

It is ok. I have only made two announcements on EAB and Lemon-Amiga. However I has just been very surprized that my post was moderated - http://eab.abime.net/showthread.php?t=107031 It is really very odd. I actually don't know how to understand this. Of course, it is the expanded Conway's Game of Life. IMHO every computer geek knows it.

Originally Posted by modrobert

Will try xlife-8, assuming it is a port of "game of life"?

Thank you. Xlife-8 is a simplified port of Xlife - http://litwr2.atspace.eu/xlife.php
However it has more colorful graphics and less scientific. I have also plan to port Xlife for the Amiga but I must convert X Window calls to Amiga function calls at first.
Of course, Xlife-8 is GoL but it also allows you to define new rules.

Originally Posted by Bruce Abbott

Perhaps, but ProAsm, BAsm and PhxAss don't accept it. Since these are the only assemblers I use...

Thank you. It is interesting because the strict logic of the manual allows it.

Originally Posted by Don_Adan

And of course you can replace your strange
lsl.l D5
with
add.l D5,D5

It is the briefest.

[Don_Adan]

Really? You are funny. Only 50 cycles fastest. How you calculated this? Less divu.w, less bsr.b, less rts and less some other code. And dozen bytes larger? How you calc this, again this is full optimisation not partially.
Now only 8 bytes in total for cv handling.

Your old version, still available on github:

clr cv ;6 bytes

add cv(pc),d5 ;4 bytes
swap d5 ; 2 bytes
move d5,cv ; 6 bytes
clr d5 ; 2 bytes
swap d5 ; 2 bytes

cv
dc.w 0 ; 2 bytes

24 bytes vs 8 bytes.

Your PR0000 has 54 bytes, my version of PR0000 has 66 bytes.

In total 78 bytes (Your) vs 74 bytes (my). Where is your DOZEN bytes larger code? You was too lazy to check? Or you still must learn more about 68k coding?

[Don_Adan]

btw. you can gain 2 bytes more.

         move.l #start+$10000-ra,d0
         divu #7,d0
         ext.l d0
         and.b #$fc,d0
         move.l d0,d7     ;d7=maxn

         move.l #start+$10000-ra,d7
         divu.w #7,d7
         ext.l d7
         and.b #$fc,d7    ;d7=maxn

[saimo]

Originally Posted by litwr

It is quite logical to consider register addressing as a particular case of EA. In some architectures register addressing is a way to access memory. I can point to the TMS9900 and TMS9995 which were used in several popular home computers.
The attached screenshot from the manual confirms my point. This manual is available here - http://wpage.unina.it/rcanonic/didat...docs/68000.pdf
The same information is available in the other manual - https://web.njit.edu/~rosensta/class...tware/code.pdf
The official manual - https://www.nxp.com/docs/en/referenc.../M68000PRM.pdf also confirms my point. So britelite is rather not correct.

No offense meant, but I have to say it: this attitude does not do any good to you, nor is respectful to whom you're talking with. Now, some experienced M68k coders here explained why you (not an experienced coder) are wrong, and provided you with precise information. How about dropping the attitude and checking out what they are saying? Please read carefully the following.

Pages 4-113 through 4-115 of the very same manual you linked to describe the LSL and LSR instructions. The assembler syntax they provide is:

LSd Dx,Dy
LSd # < data > ,Dy
LSd < ea >

Then, regarding the instructions working on registers (first two syntax forms) it says:

The shift count for the shifting of a register is specified in two different ways: ... The size of the operation for register destinations may be specified as byte, word, or long.

That's followed by an explanation of the last syntax form:

The contents of memory, < ea > , can be shifted one bit only, and the operand size is restricted to a word.

Note that: this last explanation can't refer to the first two forms because they have a variable count, not a fixed count; <ea> is explicitly said to refer to memory.
Further on, where the instruction formats are provided, the manual has two sections: REGISTER SHIFTS and MEMORY SHIFTS. The first section deals with the first two syntax forms and does not mention <ea>; the latter deals with the third form and, unsurprisingly, it mentions <ea> and shows its encodings, which exclude registers (and there's even an explicit note that says "Only memory alterable addressing modes can be used").

In short: shift (as well as rotate - check out the description or ROd) instructions applied to registers require a count and thus lsr.l d5 is not syntactically correct.

Follix looks good and interesting. It is difficult to believe that it is written in Basic!

Well, the trick is that it hits the hardware directly with tons of PEEKs and POKEs and doesn't have lots of moving/animated graphics.

Skillgrid looks perfect for me. I would like to have opportunities to help but now it is rather impossible.

Thanks for the indirect offer, but the only help I need is tests by somebody who has a certain type of Amiga CD32.

[litwr]

Originally Posted by modrobert

> pi-align
number pi calculator v12 (68020)
number of digits (up to 9280)? 3000
 30.74

> pi-na
number pi calculator v12 (68020)
number of digits (up to 9280)? 3000
 30.50

Thank you. But your results are very unexpected. I can't understand how is this possible?! Could anyone find any explanation for this?
We have the same sequence of instructions in both programs. The only difference is a position of a label for a branch.

    bra .enddiv
    align 2  ; this is used only in pi-align
.l2        ;aligned in pi-align, and not aligned in pi-na
    ...
    bcc .l2  ; this branch is aligned pi-align and not aligned in pi-na

Maybe it was a random case? Did you run programs several times? Were results the same?

Originally Posted by Don_Adan

Really? You are funny. Only 50 cycles fastest. How you calculated this? Less divu.w, less bsr.b, less rts and less some other code. And dozen bytes larger? How you calc this, again this is full optimisation not partially.
Now only 8 bytes in total for cv handling.

You replaced DIVUs by loops which can be executed up to 10 times and this is longer than DIVU execution time. You replaced BSR/RTS with branches - it is a bit faster. However I doubt that it is possible to count 50 saved cycles...
I removed CLR CV long ago but committed it only several minutes ago. Thank you again.

Originally Posted by Don_Adan

btw. you can gain 2 bytes more.

Thank you very much! Your changes are committed.
EDIT. Both versions (the 68000 and 68020/30) can now show up to 9280 digits!

[litwr]

Originally Posted by saimo

The contents of memory, < ea > , can be shifted one bit only, and the operand size is restricted to a word.

Note that: this last explanation can't refer to the first two forms because they have a variable count, not a fixed count; <ea> is explicitly said to refer to memory.
Further on, where the instruction formats are provided, the manual has two sections: REGISTER SHIFTS and MEMORY SHIFTS. The first section deals with the first two syntax forms and does not mention <ea>; the latter deals with the third form and, unsurprisingly, it mentions <ea> and shows its encodings, which exclude registers (and there's even an explicit note that says "Only memory alterable addressing modes can be used").

Please do take this dispute too personal. It is just a logic exercise. A kind of mind training.
Of course, the contents of memory, <ea> , can be shifted one bit only. But this doesn't mean that <ea> means only contents of memory in the assembly syntax headlines. I posted a screenshot that proves that <ea> may be used as a reference to a register.
In the chapter Instruction Format Summary they don't show exact instruction syntax, they show only encoding. So it is irrelevant to assembly language syntax.
The claim "LSL.L D5 is not syntactically correct" is also controversial because this syntax is correct in VASM. Bruce Abbott confirmed that in several popular assemblers it is not syntactically correct. But we can't generalize this. There are always some diversity in assemblies. Foe example, we have several popular syntaxes for the x86.

[Don_Adan]

Originally Posted by litwr

Thank you. But your results are very unexpected. I can't understand how is this possible?! Could anyone find any explanation for this?
We have the same sequence of instructions in both programs. The only difference is a position of a label for a branch.

    bra .enddiv
    align 2  ; this is used only in pi-align
.l2        ;aligned in pi-align, and not aligned in pi-na
    ...
    bcc .l2  ; this branch is aligned pi-align and not aligned in pi-na

Maybe it was a random case? Did you run programs several times? Were results the same?



You replaced DIVUs by loops which can be executed up to 10 times and this is longer than DIVU execution time. You replaced BSR/RTS with branches - it is a bit faster. However I doubt that it is possible to count 50 saved cycles...
I removed CLR CV long ago but committed it only several minutes ago. Thank you again.


Thank you very much! Your changes are committed.
EDIT. Both versions (the 68000 and 68020/30) can now show up to 9280 digits!

Especially for you.

68000 timings

divu #1000,d5 ; 144 cycles
bsr .l0 ; 18 cycles
clr d5 ; 4 cycles
swap d5 ; 4 cycles
....
.l0
eori.b #'0',d5 ; 8 cycles
move.b d5,(a0)+ ; 8 cycles
rts ; 16 cycles

in total for one divu.w 202 cycles


b1000
sub.w D3,D5 ; 4 cycles
bcs.b n100 ; 8 cycles, 10 if taken
add.w A0,D2 ; 4 cycles
bra.b b1000 ; 10 cycles

best case 14 cycles, worst case 284 cycles, average 298/2=149 cycles

202-149=53 cycles

3 times divu.w called, 3x53 cycles, average about 150 cycles less per one access to PR0000 routine. Plus much fastest code for cv handling. In total, about 165 cycles fastest per one access.

[modrobert]

Originally Posted by litwr

Maybe it was a random case? Did you run programs several times? Were results the same?

I tested now running in reverse order, exactly the same results, 'pi-na' is 0.24 seconds faster than 'pi-align'.

Try using 'cnop 0,4' to align with next long word address instead.

[saimo]

Originally Posted by litwr

Please do take this dispute too personal. It is just a logic exercise. A kind of mind training.
Of course, the contents of memory, <ea> , can be shifted one bit only. But this doesn't mean that <ea> means only contents of memory in the assembly syntax headlines. I posted a screenshot that proves that <ea> may be used as a reference to a register.
In the chapter Instruction Format Summary they don't show exact instruction syntax, they show only encoding. So it is irrelevant to assembly language syntax.
The claim "LSL.L D5 is not syntactically correct" is also controversial because this syntax is correct in VASM. Bruce Abbott confirmed that in several popular assemblers it is not syntactically correct. But we can't generalize this. There are always some diversity in assemblies. Foe example, we have several popular syntaxes for the x86.

Don't worry, I'm not taking this conversation personally at all: I just had to point out that, unfortunately, your stubbord attitude is preventing you to see something that is very simple and also shows disrespect to who's trying to help you see.
Now, there is nothing controversial here: the pages of Motorola's official manual define clearly the syntax of the instructions, how the instructions work and how they are encoded. You simply fail to understand those pages. I tried to help you with an almost word-by-word guidance, but given that you choose not to see, I won't add anything else.

[Don_Adan]

Next 2 bytes less.

         move.l #start+$10000-ra,D7
         divu.w #7*4,D7
         ext.l D7
         lsl.w #2,D7    ;d7=maxn

For my version of PR0000, 2 more bytes gained.

         move.l #start+$10000-ra,D7
         divu.w #7*4,D7
         lsl.w #2,D7    ;d7=maxn

[Bruce Abbott]

Originally Posted by litwr

Of course, the contents of memory, <ea> , can be shifted one bit only.

Only because the 68000 has this arbitrary limitation. To shift by more than 1 bit (without a barrel shifter or temporary registers to store intermediate results) it would have to perform multiple reads and writes to memory, which would be very slow. Also the 16 bit opcode does not have enough space to specify both shift value and <ea>.

But this doesn't mean that <ea> means only contents of memory in the assembly syntax headlines. I posted a screenshot that proves that <ea> may be used as a reference to a register.

Yes. However in this case - as in many others - not all <ea> modes are valid. Specifically, modes An and Dn are illegal for shift/rotate, and will cause an exception if you try to execute them (even though some debuggers or disassemblers may think they are valid code).

There are equivalent opcodes using Dn explicitly that are valid, which an assembler could alias to for 'convenience'. This also applies to some other instructions that do have an equivalent <ea> opcode, which is a pain when the assembler silently changes one to the other without asking or providing any way to avoid it (sometimes we need to have the exact opcode we asked for!).

In the chapter Instruction Format Summary they don't show exact instruction syntax, they show only encoding. So it is irrelevant to assembly language syntax.

Encoding is relevant though, because it tells you which modes are valid for particular instructions.

The claim "LSL.L D5 is not syntactically correct" is also controversial because this syntax is correct in VASM. Bruce Abbott confirmed that in several popular assemblers it is not syntactically correct. But we can't generalize this.

"The great thing about standards is that there are so many of them!"

Yes, some code that is "syntactically correct" in one assembler may not be in another. To avoid confusion and maintain compatibility it is best to stick to a common subset with unambiguous syntax where possible, and specify the syntax used when it isn't. Otherwise people may have trouble understanding and using your code.

[Bruce Abbott]

Originally Posted by Don_Adan

Next 2 bytes less.

For my version of PR0000, 2 more bytes gained.

Time for summary of progress so far?

How much space and time have we now saved (or gained) over litwr's original code, as a proportion of it?

[Don_Adan]

Originally Posted by Bruce Abbott

Time for summary of progress so far?

How much space and time have we now saved (or gained) over litwr's original code, as a proportion of it?

I dont know, seems he not always like fastest code, maybe Amiga version will be too fast? At first is necessary to understand Litwr code, later code can be optimised. Critical code perhaps can be shortest/fastest only a few, but other code called only once still can be shortened.

Here is example:
from
move #10,d4
to
moveq #10,D4

Mostly time calculation routine can be optimised for space.

[Don_Adan]

Perhaps this code can be shortened/optimised too. A few shortet a few fastest.

.l7 
;     lsr d6
         mulu #7,d6          ;kv = d6
         move.l d6,d3
         lea.l ra(pc),a3

         exg.l a5,a6
         jsr Forbid(a6)
         moveq.l #INTB_VERTB,d0
         lea.l VBlankServer(pc),a1
         jsr AddIntServer(a6)
         exg.l a5,a6
         ;move.w #$4000,$dff096    ;DMA off
 ;        lsr d3

     lsr.w #2,D3
        subq #1,d3
         move.l #2000*65537,d0
         move.l a3,a0
.fill    move.l d0,(a0)+
         dbra d3,.fill

.l0      clr.l d5       ;d <- 0
;         clr.l d4
         clr.l d7
 ;        move d6,d4     ;i <- kv
 ;        add.l d4,d4     ;i <- i*2

  move.l D6,D4
         adda.l d4,a3
.....

endif
 ;        sub.w #14,d6   ;kv
        sub.w #28,D6
         bne .l0

[Bruce Abbott]

Originally Posted by Don_Adan

I dont know, seems he not always like fastest code, maybe Amiga version will be too fast?

I think litwr wants fastest and smallest, so it's a bit tricky. Is a 5% speedup worthwhile if it adds 4 bytes to the file size?

On litwr's benchmark site the main loop code size is 54 bytes on a 50MHz 68030 vs 57 bytes (~6% larger) on a 25MHz 386, while the 386 would theoretically be ~5% faster if running at the same clock speed. Some speed optimization might make the Amiga code 5% quicker but 5% larger, and therefore virtually identical to the 386 (except that the 030 is 25% faster in real terms because 386's top out at 40MHz).

It's also good to see the Amiga 1200 with Blizzard 1230-IV beating a 36MHz ARM3 and a 33MHz 80486 (though of course these figures don't mean much in the real world).

At first is necessary to understand Litwr code, later code can be optimised. Critical code perhaps can be shortest/fastest only a few, but other code called only once still can be shortened.

Fair enough, but ultimately we want to know what our efforts have achieved. Hoping to see a side-by-side comparison between the original code and the final optimized version.

Here is example:
from
move #10,d4
to
moveq #10,D4

Mostly time calculation routine can be optimised for space.

Wow, such easy pickings! Perhaps the total size can still be shrunk quite a lot and get even quicker!

[meynaf]

Originally Posted by litwr

The claim "LSL.L D5 is not syntactically correct" is also controversial because this syntax is correct in VASM. Bruce Abbott confirmed that in several popular assemblers it is not syntactically correct. But we can't generalize this. There are always some diversity in assemblies. Foe example, we have several popular syntaxes for the x86.

It is in the domain of tolerances. VASM's compatibility with other assemblers - even old and/or buggy ones - is quite high.
As an example, most assemblers will accept moveq.l even though it is technically incorrect (moveq has no size).
Phxass - and vasm in phxass compatibility mode - will accept move.b to/from ccr but this is also incorrect (operand size is .w).

So about LSL.L D5 being syntaxically correct or not, it is a matter of how you see it -- but it is always cleaner to not depend on anything incompatible when it is easy to do otherwise.