TweetFollow Us on Twitter

Efficient 68000
Volume Number:8
Issue Number:2
Column Tag:Assembly workshop

Efficient 68000 Programming

If a new CPU speeds up inefficient code, what do you think it will do to efficient code?

By Mike Scanlin, MacTutor Regular Contributing Author

The dew is cold. It is quiet. I hear nothing except for crackling sounds coming from the little fire burning two inches to the left of my keyboard. It wasn’t there a minute ago. Seems that Doo-Dah, the god of efficient programming, is upset with me for typing “Adda.W #10,A0” and just sent me a warning in the form of a lightning bolt. I hate it when he does that. You’d think that after three years in his service, researching which 68000 assembly language instructions are the most efficient ones for any given job, that he would lighten up a little. I guess that’s what makes him a god and me a mere mortal striving for enlightenment through the use of optimal instructions. As I extinguish the fire with a little Mountain Dew, I reflect upon the last three years.

My first lesson in the service of Doo-Dah was that proficiency in assembly language is a desirable skill in programmers so long as performance is a desirable attribute of software. The nay-sayers who depend upon faster and faster CPUs to make their sluggish software run at acceptable speeds don’t realize the underlying relativeness of the universe. If a new CPU will speed up a set of non-optimal instructions by 10%, then it will also speed up a set of optimal instructions by 10%. One should strive to be right on the edge of absolute maximum performance all the time. Users may not notice the difference in a 2K document but when they start working with 20MB documents they will soon be able to separate the optimal software from the non-optimal.

In the months following that lesson, I was given the task of compiling a list of instructions that should only very rarely appear in any program executing on a 68000 (and only then because you’re dealing with either self-modifying code or special hardware that depends on certain types of reads and writes from the processor). They are:

Don't Use Use Save

Move.B #0,Dx Clr.B Dx 8 cycles, 2 bytes

Move.W #0,Dx Clr.W Dx 8 cycles, 2 bytes

Clr.L Dx Moveq #0,Dx 2 cycles

Move.L #0,Dx Moveq #0,Dx 8 cycles, 4 bytes

Move.L #0,Ax Suba.L Ax,Ax 4 cycles, 4 bytes

Move.L #[-128..127],Dx Moveq #[-128..127],Dx 8 cycles, 4 bytes

Move.L #[-128..127],ea Moveq #[-128..127],Dx 4 cycles, 2 bytes

Move.L Dx,ea

Move.L #[128..254],Dx Moveq #[64..127],Dx 4 cycles, 2 bytes

Add Dx,Dx

Move.L #[-256..-130],Dx Moveq #[-128..-65],Dx 0 cycles, 2 bytes

Add.L Dx,Dx

Lea [1..8](Ax),Ax Addq #[1..8],Ax 0 cycles, 2 bytes

Add.W #[9..32767],Ax Lea [9..32767](Ax),Ax 4 cycles

Lea [-8..-1](Ax),Ax Subq #[1..8],Ax 0 cycles, 2 bytes

Sub.W #[9..32767],Ax Lea [-32767..-9](Ax),Ax 4 cycles

Asl.W #1,Dx Add.W Dx,Dx 4 cycles

Asl.L #1,Dx Add.L Dx,Dx 2 cycles

Cmp.x #0,ea Tst.x ea 4-10 cycles, 2 bytes

And.L #$0000FFFF,Dx Swap Dx 4 cycles

Clr.W Dx

Swap Dx

In addition, if you don’t care about the values of the condition codes then the following may be optimized:

Don't Use Use Save

Move.W #nnnn,-(SP) Move.L #ppppnnnn,-(SP) 4 cycles, 2 bytes

Move.W #pppp,-(SP)

Move.L #$0000nnnn,-(SP) Pea $nnnn 4 cycles, 2 bytes

Move.B #255,Dx St Dx 2 cycles, 2 bytes

Move.L #$00nn0000,Dx Moveq #[0..127],Dx 4 cycles, 2 bytes

Swap Dx

Movem (SP)+,Dx Move (SP)+,Dx 4 cycles

Ext.L Dx

Movem.L Dx,-(SP) Move.L Dx,-(SP) 4 cycles, 2 bytes

Movem.L (SP)+,Dx Move.L (SP)+,Dx 8 cycles, 2 bytes

Movem.L (SP)+,<2 regs> Move.L (SP)+,<reg 1> 4 cycles

Move.L (SP)+,<reg 2>

Note that pushing 2 regs or popping 3 with Movem.L is equivalent in cycles to doing it with multiple Move.L’s, but popping 3 regs with Move.L’s costs you two extra bytes. An easy rule to remember is to always use Movem.L whenever you’re dealing with 3 or more registers.

There are other optimizations you can make with minimal assumptions. For instance, if you are making room for a function result then don’t use Clr:

Don't UseUseSave
Clr.W -(SP)Subq #2,SP6 cycles
_Random _Random
Clr.L -(SP)Subq #4,SP14 cycles
_FrontWindow _FrontWindow

If you’re trying to set, clear, or change one of the low 16 bits of a data register and you don’t need to test it first, then don’t use these:

Don't UseUseSave
Bset #n,DxOr.W #mask,Dx4 cycles
Bclr #n,DxAnd.W #mask,Dx4 cycles
Bchg #n,DxEor.W #mask,Dx4 cycles

You should use registers wherever possible, not memory (because memory is much slower to access). If you need to test for a NIL handle or pointer, for instance, do this:

Don't UseUseSave
Move.L A0,-(SP)Move.L A0,D016 cycles, 2 bytes
Addq #4,SPBeq.S ItsNil
Beq.S ItsNil

Use the “quick” operations wherever you can. Many times you can reverse the order of two instructions to use a Moveq (since Moveq handles bigger numbers than Addq/Subq):

Don't UseUseSave
Move.L D0,D1Moveq #10,D16 cycles, 4 bytes
Add.L #10,D1Add.L D0,D1

Also, use two Addq’s or Subq’s when dealing with longs in the range of 9..16:

Don't UseUseSave
Addi.L #10,D0Addq.L #2,D04 cycles, 2 bytes
Addq.L #8,D0

The following three optimizations will reduce the size of your program but at the expense of a few cycles. This is good for user interface code, but you probably don’t want to use these optimizations in tight loops where speed is important:

Don't UseUseSave
Move.B #0,-(SP)Clr.B -(SP)-2 cycles, 2 bytes
Move.W #0,-(SP)Clr.W -(SP)-2 cycles, 2 bytes
Move.L #0,-(SP)Clr.L -(SP)-2 cycles, 4 bytes

Most of the optimizations from here onward are only applicable in some cases. Many times you can use a slightly different version of the exact code given here to get an optimization that works well for your particular set of circumstances. These optimizations don’t always have the same set of side effects or overflow/underflow conditions that the original code has, so use them with caution.

Shifting left by 2 bits (to multiply by 4) should be avoided if you’re coding for speed:

Don't UseUseSave
Asl.W #2,DxAdd.W Dx,Dx2 cycles, -2 bytes
Add.W Dx,Dx

Use bytes for booleans instead of bits. They’re faster to access (and less code in some cases). If you have many booleans, though, bits may be the way to go because of reduced memory requirements (of the data, that is, not the code).

Don't UseUseSave
Btst #1,myBools(A6)Tst.B aBool(A6)4 cycles, 2 bytes
Btst #1,D0Tst.B D06 cycles, 2 bytes

Avoid the use of multiply and divide instructions like the plague. Use shifts and adds for immediate operands or loops of adds and subtracts for variable operands. For instance, to multiply by 14 you could do this:

Don't UseUseSave
Mulu #14,D0Add D0,D0many cycles, -4 bytes
Move D0,D1
Lsl #3,D0
Sub D1,D0

If you have a variable source operand, but you know that it is typically small (and positive, for this example), then use a loop instead of a multiply instruction. This works really well in the case of a call to FixMul if you know one of the operands is a small integer -- you can avoid the trap overhead and the routine itself by using a loop similar to this one (in fact, the FixMul routine itself checks if either parameter is 1.0 before doing any real work):

Don't UseUseSave
Mulu D1,D0Move D0,D2many cycles, -8 bytes
Neg D2
@1 Add D0,D2
Subq #1,D1
Bne.S @1

Likewise, for division, use a subtract loop if you know that the quotient isn’t going to be huge (and if the destination fits in 16 bits):

Don't UseUseSave
Divu D1,D0Moveq #0,D2many cycles, -10 bytes
Cmp D1,D0
Bra.S @2
@1 Addq #1,D2
Sub D1,D0
@2 Bhi.S @1

Don’t use Bsr/Rts in tight loops where speed is important. Put the return address in an unused address register instead.

Don't UseUseSave
Bsr MyProcLea @1,A08 cycles, -4 bytes
;<blah>Bra MyProc
@1 ;<blah>
MyProc:MyProc:
;<blah blah>;<blah blah>
RtsJmp (A0)

You can eliminate a complete Bsr/Rts pair (or equivalent above) if the Bsr is the last instruction before an Rts by changing the Bsr to a Bra:

Don't UseUseSave
Bsr MyProcBra MyProc24 cycles, 2 bytes
Rts

Don’t use BlockMove for moves of 80 bytes or less where you know the source and destination don’t overlap. The trap overhead and preflighting that BlockMove does make it inefficient for such small moves. Use this loop instead (assuming Dx > 0 on entry):

Don't UseUseSave
_BlockMoveSubq #1,Dxmany cycles, -6 bytes
@1 Move.B (A0)+,(A1)+
Dbra Dx,@1

I base this conclusion on time trials done on a Mac IIci with a cache card. The actual results were (for several thousand iterations):

Figure 1: How fast do blocks move?

I did the same tests on a Mac SE and found that it was only beneficial to call BlockMove on that machine for moves of 130 bytes or more. However, since you should optimize for the lowest common denominator across all machines, you should only use the Dbra loop for non-overlapping moves of 80 bytes or less.

Be warned, though: on the Quadras, BlockMove has been modified to flush the 040 caches because of the possibility that you (or the memory manager) are BlockMoving executable code. So don’t use the above loop for moving small amounts of code (like you might do in some INIT installation code). Apple did this for compatibility reasons with existing non-040 aware applications running in 040 copy-back mode (high performance mode). However, because of this, your non-code BlockMoves are unnecessarily clearing the caches, too. I don’t know if it’s worth it to write a dedicated BlockMove for non-code moves, but it seems like it’s worth doing and then timing to see if there’s a difference.

Unroll loops. At the expense of a few extra bytes you can make any tight loop run faster. This is because short branch instructions that are not taken are faster than those that are taken. Here’s an even faster version of the above loop:

;1

 Subq #1,Dx
 @1 Move.B (A0)+,(A1)+
 Subq #1,Dx
 Bcs.S @2
 Move.B (A0)+,(A1)+
 Subq #1,Dx
 Bcs.S @2
 Move.B (A0)+,(A1)+
 Dbra Dx,@1
 @2

Beware when using the above trick, though, because it doesn’t work for long branches. In that case, a taken branch is faster than a branch not taken.

Preserving pointers into relocatable blocks across code that moves memory: If you need to lock a handle because you’re going to call a routine that moves memory but the handle (and the dereferenced handle) isn’t a parameter to that routine, then you can usually avoid locking the handle with a trick (which has the desirable side effect of reducing memory fragmentation). Assume the handle is in A3 and the pointer into the middle of the block is in A2. All you really have to do is save/restore the offset into the block; you don’t care if the block moves or not:

Don't UseUseSave
Move.L A3,A0Sub.L (A3),A2many cycles, 4 bytes
_HLock
;<move memory> ;<move memory>
Move.L A3,A0Add.L (A3),A2
_HUnlock

If the end of a routine is executing the same set of instructions two or more times, then you may be able to use this trick to save some bytes (at the expense of a few cycles). If the end of the routine looks like a subroutine, then have it Bsr to itself, like this (this example is drawing a BCD byte in D3):

Don't UseUseSave
Ror #4,D3Ror #4,D3many bytes
Move.B D3,D0Bsr @1
And #$000F,D0Rol #4,D3
Add #'0',D0
Move D0,-(SP)
_DrawChar
Rol #4,D3
Move.B D3,D0@1 Move D3,D0
And #$000F,D0And #$000F,D0
Add #'0',D0Add #'0',D0
Move D0,-(SP)Move D0,-(SP)
_DrawChar _DrawChar
Rts Rts

Use multiple entry points to set common parameters. Suppose you have a routine that takes a boolean value in D0 as an input and suppose you call this routine 20 times with the value of True and 30 times with the value of False. It would save code if you made two entry points that each set D0, and then branched to common code. For instance:

Don't UseUseSave
St D0Bsr MyProcTruemany bytes
Bsr MyProc
Sf D0Bsr MyProcFalse
Bsr MyProc
MyProcTrue:
St D0
Bra.S MyProc
MyProcFalse:
Sf D0
MyProc:MyProc:
;<blah>;<blah>
RtsRts

Clean up the stack with Unlk. If your routine already has a stack frame and you create some temporary data on the stack (in addition to the stack frame) then you don’t always need to remove it when you’re done with it -- the Unlk will clean it up for you. For instance, suppose you make a temporary Rect on the stack. You would normally remove it with Addq #8,SP but if it’s near the end of a function that does an Unlk, then leave the Rect there; it’ll be gone when the Unlk executes.

Well, hopefully Doo-Dah has many more learned disciples now. Don’t forget to sacrifice a copy of FullWrite in his honor at least once a year. That makes him happy.

P.S. If you want even more 68000 optimizations there is an excellent article by Mike Morton in the September, 1986, issue of Byte magazine called “68000 Tricks and Traps” (pgs. 163-172). There are more than half a dozen or so tricks in that article not covered in this article (sorry for not listing them here but I didn’t want to get sued for plagiarism).

 
AAPL
$98.15
Apple Inc.
-0.23
MSFT
$43.58
Microsoft Corpora
-0.31
GOOG
$587.42
Google Inc.
+1.81

MacTech Search:
Community Search:

Software Updates via MacUpdate

Knock 1.1.7 - Unlock your Mac by knockin...
Knock is a faster, safer way to sign in. You keep your iPhone with you all the time. Now you can use it as a password. You never have to open the app -- just knock on your phone twice, even when it's... Read more
Mellel 3.3.6 - Powerful word processor w...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
LibreOffice 4.3.0.4 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Freeway Pro 7.0 - Drag-and-drop Web desi...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With it's user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Drive Genius 3.2.4 - Powerful system uti...
Drive Genius is an OS X utility designed to provide unsurpassed storage management. Featuring an easy-to-use interface, Drive Genius is packed with powerful tools such as a drive optimizer, a... Read more
Vitamin-R 2.15 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
Toast Titanium 12.0 - The ultimate media...
Toast Titanium goes way beyond the very basic burning in the Mac OS and iLife software, and sets the standard for burning CDs, DVDs, and now Blu-ray discs on the Mac. Create superior sounding audio... Read more
OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more

Latest Forum Discussions

See All

Murl the Squirrel (Games)
Murl the Squirrel 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Meet Murl. He is teased by a group of flying squirrels because he can't fly. Determined to show them he's can fly, he meets... | Read more »
Celleste (Games)
Celleste 0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 0.1 (iTunes) Description: Lots of cute action with amazing 3D graphics and a new type of gameplay! Take control over the forces of the universe to help a group... | Read more »
Super Heavy Sword (Games)
Super Heavy Sword 0.0.1 Device: iOS Universal Category: Games Price: $.99, Version: 0.0.1 (iTunes) Description: Get Ready to Get HEAVY! Monster Robot Studios presents SUPER Heavy Sword! The sequel to the smash hit HEAVY sword which... | Read more »
Angels In The Sky (Games)
Angels In The Sky 1.00 Device: iOS Universal Category: Games Price: $6.99, Version: 1.00 (iTunes) Description: - This game is only for the iPhone 5s. please do not use the iPad, iPhone 5 or earlier devices.- Just touch or holding... | Read more »
80 Days (Games)
80 Days 1.0.2 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.2 (iTunes) Description: 1872, with a steampunk twist. Phileas Fogg has wagered he can circumnavigate the world in just eighty days. Choose your own route... | Read more »
Micromon (Games)
Micromon 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: 130+ Animated Monsters to Catch & Battle! No waiting, play at your own pace! Embark on an epic monster capture RPG like none... | Read more »
Empire Manager (Games)
Empire Manager 1.0 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: Become ruler of an empire. Manage your economy, develop technology, hire an army and conquer the world in this addictive turn-... | Read more »
Empire Manager HD (Games)
Empire Manager HD 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: Become ruler of an empire. Manage your economy, develop technology, hire an army and conquer the world in this addictive... | Read more »
Star Admiral Review
Star Admiral Review By Rob Thomas on July 30th, 2014 Our Rating: :: ADMIRABLE ADMIRALSUniversal App - Designed for iPhone and iPad While this new digital CCG may feel a bit familiar, Star Admiral offers a sci-fi twist and galaxy’s... | Read more »
Zap! Pow! Become a Badass Wizard in Phan...
Zap! Pow! | Read more »

Price Scanner via MacPrices.net

iPad Cannibalization Threat “Overblown”
Seeking Alpha’s Kevin Greenhalgh observes that while many commentators think Apple’s forthcoming 5.5-inch panel iPhone 6 will cannibalize iPad sales, in his estimation, these concerns are being... Read more
Primate Labs Releases July 2014 MacBook Pro P...
Primate Labs’ John Poole has posted Geekbench 3 results for most of the new MacBook Pro models that Apple released on Tuesday. Poole observes that overall performance improvements for the new MacBook... Read more
Apple Re-Releases Bugfixed MacBook Air EFI Fi...
Apple has posted a bugfixed version EFI Firmware Update 2.9 a for MacBook Air (Mid 2011) models. The update addresses an issue where systems may take longer to wake from sleep than expected, and... Read more
Save $50 on the 2.5GHz Mac mini, plus free sh...
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more
Save up to $140 on an iPad Air with Apple ref...
Apple is offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. Stock tends to come and go with some of these... Read more
$250 price drop on leftover 15-inch Retina Ma...
B&H Photo has dropped prices on 2013 15″ Retina MacBook Pros by $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.3GHz Retina MacBook Pro: $2249, $250 off... Read more
More iPad Upgrade Musings – The ‘Book Mystiqu...
Much discussed recently, what with Apple reporting iPad sales shrinkage over two consecutive quarters, is that it had apparently been widely assumed that tablet users would follow a two-year hardware... Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $999.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Save up to $300 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $300 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. These are the best prices on... Read more
WaterField Unveils 15″ Outback Solo & 13″...
Hard on the heels of Apple’s refreshed MacBook Pro Retina laptops announcement, WaterField Designs has unveiled a 15-inch version of the waxed-canvas and leather Outback Solo and a 13-inch version of... Read more

Jobs Board

Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.