68000 code optimisations

[meynaf]

Does optimisation reduce readability ?
Not always, but sometimes yes. However you should notice that at the time of doing it. And then it might be a good idea to add some comment explaining what you've done, so it doesn't get abused later.

[VladR]

Originally Posted by StingRay

Optimising doesn't necessarily equals unreadable!




And neither does it mean the code is unmaintainable.

It's probably just my patience (or lack thereof), but to me, unmaintainable means that I have to spend more than 30 seconds figuring out what I did there. It's perhaps just side effect of getting older

[VladR]

Originally Posted by meynaf

Does optimisation reduce readability ?
Not always, but sometimes yes. However you should notice that at the time of doing it. And then it might be a good idea to add some comment explaining what you've done, so it doesn't get abused later.

That's a Catch-22 right there for me unfortunately

But, on 1.79 MHz 6502, the approach I found works best is wrapping each version in a separate compile-time block with two lines of description of the changes to the previous one.

One such texturing method received about dozen versions and it never takes more than 15 minutes to understand them.

But if I had just the last one, it would be merely WTF moment

I'm all ears how you guys handle this.

[Galahad/FLT]

Originally Posted by VladR

That's a Catch-22 right there for me unfortunately

But, on 1.79 MHz 6502, the approach I found works best is wrapping each version in a separate compile-time block with two lines of description of the changes to the previous one.

One such texturing method received about dozen versions and it never takes more than 15 minutes to understand them.

But if I had just the last one, it would be merely WTF moment

I'm all ears how you guys handle this.

Always comment your code

[StingRay]

Originally Posted by VladR

It's probably just my patience (or lack thereof), but to me, unmaintainable means that I have to spend more than 30 seconds figuring out what I did there. It's perhaps just side effect of getting older

That can be avoided by properly commenting the code. I guess each of us has a different definition what unmaintainable means, in the end it is important that, no matter how much you optimise code, you should still be able to understand why/how something has been done.

[hooverphonique]

Interesting and relevant, but I think we're getting off topic here

[jotd]

anyone took a look at this old page?

https://web.archive.org/web/20040905...ldin/main.html

algorithm

signum(x)
if x > 0 then return 1
else if x < 0 then return -1
else return 0

there's some optimization of signum which is baffling (and also computed automatically!). I think this is 68000

(x in D0)

ADD.L             D0,D0              (Add D0 to itself)
SUBX.L           D1,D1              (Subtract (D1 + Carry) from D1)
NEGX.L           D0                   (Put (0 – D0 – Carry) into D0)
ADDX.L           D1,D1              (Add (D1 + Carry) to D1

(signum(x) is now in D1)

At first glimpse, this makes absolutely no sense. Most glaringly, there are no conditional jumps, while the original code was made of nothing but conditional jumps. Some closer analysis reveals what is actually going on.


ADD.L D0,D0 doubles D0. This is unimportant, as it will not be referenced again, but it takes advantage of a peculiarity of 2’s-complement notation, which is used to store number in registers in binary. Any negative number will be stored as a bit string beginning with 1; thus, when it is doubled, it will overflow, and the carry bit on the processor will be set. SUBX.L D1,D1 clears D1 (by subtracting it from itself), then subtracts the carry bit from it. Since this was set by the previous instruction, D1 is now -1 if the original number was negative, and 0 otherwise. NEGX.L D0 negates D0, which is not important, and sets the carry bit to 1 if and only if D0 was not originally equal to zero. ADDX.L D1,D1 now puts this entire process together by adding D1 to itself, then adding the carry bit. If D0 was originally positive, D1 will be zero and the carry bit will be set. Thus, 0 + 0 + 1 = 1, and D1 will contain 1. If D0 was equal to zero, D1 will be equal to zero and the carry bit will not be set, so 0 + 0 + 0 =0. If D0 was negative, D1 will equal -1 and the carry bit will be set, so -1 + -1 + 1 = -1.

This code is bizarre in ways rarely seen, and would be nearly unreadable to anyone who did not know what was going on. Yet, it works every time, and is considerably faster than the original. Other code fragments generated by Superoptimizer as just as cryptic, but always work perfectly and more efficiently than their predecessors.

Seems that an automated way of doing this is possible. If it is and there's a 68k version somewhere, it could be very interesting for our old machines...

[meynaf]

Originally Posted by jotd

there's some optimization of signum which is baffling (and also computed automatically!). I think this is 68000

SGN is a known one. See post #62.

[jotd]

yeah it's exactly the same code. But it just illustrated the result of a machine optimizing asm. I fail to see how it works exactly but I'd like to see that in action.

Let's imagine some 3D games or otherwise slow games benefitting from this... (if it's not a blitter limitation)

[DanScott]

Originally Posted by jotd

yeah it's exactly the same code. But it just illustrated the result of a machine optimizing asm. I fail to see how it works exactly but I'd like to see that in action.

Let's imagine some 3D games or otherwise slow games benefitting from this... (if it's not a blitter limitation)

I've never used a signum in any of my Amiga code

Don't think it will magically speed up many games to be honest.

[Antiriad_UK]

Originally Posted by DanScott

I've never used a signum in any of my Amiga code

Don't think it will magically speed up many games to be honest.

I've got a few routines that do something whether a value is -ve/0/+ve but it's always within a loop where just bmi/beq are easier to do.

I've never used negx. Trying to think of a useful scenario for it. I guess you could save a couple of cycles if you were counting the number of zeros in a steam or something:

	moveq	#0,d2	;number of non zeros
	moveq	#0,d1	;leave 0
	...
	moveq	#0,d0	;get number to test
	negx.w	d0	;carry set unless 0
	addx.w	d1,d2	;Increase count by 1 if non zero
.notzero:

vs

	moveq	#0,d2	;number of non zeros
	...
	moveq	#0,d0	;get number to test
	beq.s	.zero
	addq.w	#1,d2
.zero:

Edit: All above is wrong

Any other creative uses?

[roondar]

The article isn't about signum though (that's just the example they picked to showcase what it's about). It's about a rather extreme way to optimise code where the optimizer doesn't use pre-designed optimisations but instead tries out every single combination of instructions that exists for that particular problem and leads to a valid result. Then the optimizer picks the smallest/fastest result out of the valid solutions it generated.

They point out it's only viable for very small algorithms as the required computing & storage power quickly spirals out of control. Still, an interesting approach.

[DanScott]

i'm not sure negx.w does exactly what you want there

[Antiriad_UK]

Originally Posted by DanScott

i'm not sure negx.w does exactly what you want there

Hmm you are right.
"Subtracts the destination operand AND the extend bit from zero"

wtf is it used for?

[DanScott]

Originally Posted by Antiriad_UK

wtf is it used for?

a sigma optimisation only currently

I don't think I've used it, but probably there are some good use cases for it

[Thomas Richter]

Originally Posted by Antiriad_UK

wtf is it used for?

For higher precision arithmetic. To negate a multi-byte/word/longword number, you start by negating the least significant field with "NEG", and then work upwards to the more significant digits by "NEGX".

[jotd]

you're getting me wrong

I mean: if there's a tool that can super-optimize people code automatically, then using it on some existing code (3D for instance) could speed it up. For instance 3D games, or games requiring a lot of CPU. Signum was just an example.

[meynaf]

This kind of optimizer dies as soon as the code is more than just a few lines. For this reason i doubt it's of any use for 3d (or any game at all).

[jotd]

that was just too good to be true
seemed to rely on bruteforce check of all combinations... but maybe this kind of optimizer is able to work by blocks to reduce combinatorics. Combining that and winuae hotspots to know where the code spends the most of the time...

[jotd]

I saw that in Supercars 2

		move.l	a0,(a4)+	;mask
		move.l	a1,(a4)+	;data0
		move.l	a2,(a4)+	;scn0

wouldn't it be faster to use

   movem.l a0-a2,(a4)+

(and would it be equivalent) ? Maybe there's a threshold where movem is faster. Is it 2, 3, or more registers?