![]()
|
|
- earx presents - | | -+------------------------------+- --| some more optimisation crap! |-- -+------------------------------+- | | - introduction ------------------------------------------------------------- I hope you have some 68k and general coding knowledge before you start! Also, alot of examples prolly won't work on plain 68000, because of word access on odd address. - unrolling and using chunks ----------------------------------------------- Definetely a must on older 68k's and not entirely crap even on the newer 68060: unrolling a loop is still something that every coder should know. As you can see by the following example, trivial tasks such as copying a byte repeatedly takes overhead. We use bytes here. Yes, it could have been words as well, but it's just to give an impression. ; d0.w=number of bytes to move -1 loop: move.b (a0)+,(a1)+ ; Copy a word. dbf d0,loop Ofcourse the 'dbf' instruction takes some cycles. This is not as much as the 'move' cost, but still considerable. To make things worse there is a second and more implicit form of overhead. You see, a byte 'move' takes up as much time as an aligned word move. (*) So speaking in general we're twice as slow as wanted, or even slower as we will see later on. (*): this hasn't been verified for 040 or 060! The obvious way to speed up this situation is using word moves. In this case we have to take care of the one remaining byte move, like so: ; d0.w=number of bytes to move lsr.w d0 ; d0.w=number of words to move bcc.s amount_even ; Number was even -> skip byte! move.b (a0)+,(a1)+ ; Copy a byte. amount_even: ; d0.w=number of words to move subq.w #1,d0 ; d0.w=number of words to move -1 bmi.s end ; No words -> end! loop: move.w (a0)+,(a1)+ ; Copy a word. dbf d0,loop end: This is faster. Moving two bytes in one go is good. ; d0.w=number of bytes to move lsr.w d0 ; d0.w=number of words to move bcc.s amount_even ; Number was even -> skip byte! move.b (a0)+,(a1)+ ; Copy a byte. amount_even: ; d0.w=number of words to move lsr.w d0 ; d0.w=number of long to move bcc.s amount_longeven ; Number was even -> skip word! move.w (a0)+,(a1)+ ; Copy a word. amount_longeven: ; d0.w=number of longs to move subq.w #1,d0 ; d0.w=number of longs to move -1 bmi.s end ; No words -> end! loop: move.l (a0)+,(a1)+ ; Copy a long. dbf d0,loop end: Better still. This method has a drawback however, if we look closer at the 68k databus we see a hazard. The databus width is 16 or 32. This means the processor works on a 16bit (even) or 32bit (longeven) aligned addresses. So accessing a word/longword at an odd address actually implies two seperate accesses. This is all transparant to the coder. And it's also slower... Let's see how we can avoid this bummer. There are four situations: a) source even, destination even b) source even, destination odd c) source odd, destination even d) source odd, destination odd Situation a is trivial. Situation d needs an extra byte move to compensate for the oddness. For situations b and c there are remedies as well. Let's assume situation b here: ; d7.w=number of words to copy -1 clr.l d0 move.w (a0)+,d0 ; d0.l=$0000aabb lsl.l #8,d0 ; d0.l=$00aabb00 move.l d0,d1 ; d1.l=$00aabb00 swap d0 ; d0.l=$bb0000aa move.b d0,(a1)+ ; Store a (first byte). loop: lsl.l #8,d1 ; d1.l=$aabb0000 move.w (a0)+,d1 ; d1.l=$aabbccdd ror.l #8,d1 ; d1.l=$ddaabbcc move.w d1,(a1)+ ; Store word. dbf d7,loop As you can see this requires shifts and therefore it's useless on a 68000 without a barrelshifter. the 68030 and up have one of these, though. Also, we need alot of combining to account for all of these particularities. Noone said it would be easy ;) Let's neglect the technical details for a while and continue. Now we only have one branch instruction on average per two bytes. It can be far far less. We can unroll the whole wordloop, but besides taking up a possibly very large instructionspace, this doesn't help on machines with instruction cache... The best alternative is to unroll to a more humble sized loop that will fit in your cpu's cache. The jumptree loop method springs to mind. For convenience we use a situation where we copy words only: ; d0.w=#number of words to copy-1 move.w d0,d1 andi.w #32-1,d0 ; d0.w mod 32 lsr.w #5,d1 ; d1.w=/32=number of loops neg.w d0 jmp endjumptree(pc,d0.w*2) ; Jump into loop. loop: REPT 32 move.w (a0)+,(a1)+ ENDR endjumptree: dbf d1,loop This will fit into a 030's cache at least. And that about covers the byte copy issue. Unrolling techniques are ofcourse useful for alot of other situations. And it seems that for all operations there is a good unrolling solution. Let's take a linear interpolation example (used for gouraud shading for instance). This illustrates that even operations that have a size different from {2,4,8,16,..} bytes are easy to handle: ; d0.l,d1.l=fixed point index, step ; d7.w=number of words to process ; a0: destination array ; a1: source shading array lea jumpCountTable,a2 move.l (a2,d7.w*4),d7 ; Get offset and loops. move.w d7,d2 ; d2.w=number of loops swap d7 ; d7.w=offset in loop jmp endjumptree(pc,d7.w) ; Jump into loop. loop: REPT 16 move.w (a1,d0.w*2),(a0)+ addx.l d1,d0 ENDR endjumptree: dbf d2,loop Ofcourse we need some additional code to prepare the lookup table: lea jumpCountTable,a0 clr.l d0 move.w #MAX_WORDS-1,d7 loop: move.l d0,d1 divu.w #16,d1 ; Divide by unroll-amount. ; d1.l=remainder|quotient move.l d1,d2 swap d2 ; d2.w=remainder mulu.w #6,d2 ; d2.w=offset=remainder*opsize swap d2 move.w d1,d2 ; d2.l=offset|quotient move.l d2,(a0)+ addq.w #1,d0 dbf d7,loop This is the fastest way on a 020/030/040. On a 68000 it might be faster to unroll completely, if that is possible. On a 68060 it might not be required to unroll. One last note, ofcourse the fasest way to copy longwords is still a movem.l: movem.l (a5),d0-a4 movem.l d0-a4,(a6) From the 020 and on it's not a must because of the fast instructioncache. That about wraps it up for this part. - conditional branches ----------------------------------------------------- Selection is a process that has it's ugly sides. Think of pipeline stalls in the 040/060 when a conditional branch happens. Or using alot of cases which can reduce code to a bowl of spaghetti. Ofcourse conditional branches are inevitable, but are they required everywhere we use the process of selection? The answer is: no! Often there is a solution that takes less work, gives a better overview. And mostly is faster. A good start is a clipping problem. A straightforward example would be: tst.b d0 bpl.s clipped ; d0>=0 -> no clip clr.b d0 ; Clip to zero. clipped: The core of the code being the bcc instruction ofcourse. Now this might seem like a detour, but a reasonable approach is the following: tst.b d0 spl d1 ; d0>=0 -> d1.b=$FF else d1.b=0 and.b d1,d0 ; Mask out d0, if d0 was negative. Seems like a waste of registers, but think about being freed from pipeline stalls. Also, you don't need labels. You can make bugs with these if you just copy a piece of code and forget to update the branch-label. Another example is using the carry bit instructions. Instead of working clumsily like so... ; a := a + b ; d0.l=b.lo, d1.l=a.lo, d2.l=b.hi, d3.l=a.hi add.l d0,d1 bcc.s carry_done addq.l #1,d3 ; Perform carry-add. carry_done: add.l d2,d3 ... we do it like this: add.l d0,d1 addx.l d2,d3 A well known and often used application no doubt. Instructions like subx and rox(r/l) also have their uses. Routines that handle cases mostly suffer from a huge amount of compares and branch combinations. We know how this looks, but just for the purpose of illustration: cmpi.w #0,d0 beq case0 cmpi.w #1,d0 beq case1 cmpi.w #2,d0 beq case2 cmpi.w #3,d0 beq case3 cmpi.w #4,d0 beq case4 ... As we know, there is a more sensible approach: jsr jumptable(pc,d0.w*4) jumptable: bra.w case0 bra.w case1 bra.w case2 bra.w case3 bra.w case4 bra.w .. So a constant time solution is possible. This works nicely on integers, but what about more complex datatypes? Strings are a good example. They consist of a variable amount of primitive datatypes (bytes). Let's say we just use such a case-handler on a small number of strings: cmpi.l #"ASSW",(a0) bne.s no_asswipe_found move.l 4(a0),d0 move.b #" ",d0 cmpi.l #"IPE ",d0 beq handle_asswipe no_asswipe_found: cmpi.l #"ASSH",(a0) bne.s no_asshole_found move.l 4(a0),d0 move.b #" ",d0 cmpi.l #"OLE ",d0 beq handle_asshole no_asshole_found: cmpi.l #"BUTT",(a0) bne.s no_buttmunch_found cmpi.l #"MUNC",4(a0) bne.s no_buttmunch_found cmpi.b #"H",8(a0) bne.s no_buttmunch_found beq handle_asswipe no_buttmunch_found: cmpi.l #"BITC",(a0) bne.s no_bitch_found cmpi.l #"H",4(a0) beq handle_bitch no_bitch_found: .... handle_asswipe: ... handle_asshole: ... handle_buttmunch: ... handle_bitch: ... As we can see, there are four cases. Since the stringsizes differ, we can't use the good old jumptable approach. And doing the searching (linear search) like above does take some time. Especially when we consider alot of possible strings in our 'dictionary'. How on earth are we going to optimise this little baby then? The answer is found in any decent book on algorithms and is called hashing. This alone however, is no guarantee for speed-optimised code. There are many forms of hashing. There are static and dynamic flavours, true constant time lookups, or 'almost' constant time lookups, etc. You can even hardcode your hashing table if it's static. For those of you unfamiliar with the concept, allow me to explain. Hashing is a process of generating keys for datatypes and using these keys to index (almost) in constant time to the information we want. In this case: datatype: string of bytes, key: integer, information: handler routine. We could discuss the entire topic of hashing, but that would take up alot of time and space. We'll limit the scope to static hashing of strings in a hardcoded way, since this is easy to do in assembler. If we take only the four strings of the above example we get a pretty bad impression of the algorithm. So, keep in mind that it also works for dozens of strings. The way we handle this is by using a treestructure. We use jumptables for parts of a string. handle_string: lea jumptable,a1 ; a1: root jumptable loop: ; a1: jumptable of choice clr.l d0 move.b (a0)+,d0 ; d0.b=character cmpi.b #"A",d0 blt.s end cmpi.b #"Z",d0 bhi.s end ; d0<"A" | d0>"Z" -> not found subi.b #"A",d0 ; d0.l=index jsr (a1,d0.l*4) tst.l d0 beq loop ; d0=0 -> char is legal, loop end: ; d0.l= <0:not found, >1:found rts jumptable: bra.w test_ass ; 4 bytes bra.w handle_b ; 4 bytes moveq #-1,d0 ; / rts ; \ 4 bytes moveq #-1,d0 ; / rts ; \ 4 bytes ... .. test_ass: cmpi.w #"SS",(a0)+ bne.s no_ass lea ass_jumptable,a1 moveq #0,d0 rts no_ass: moveq #-1,d0 rts handle_b: lea b_jumptable,a1 moveq #0,d0 rts ass_jumptable: moveq #-1,d0 ; a rts moveq #-1,d0 ; b rts ... .. bra.w test_asshole ; h ... .. bra.w test_asswipe ; w ... .. test_asshole: cmpi.l #"HOLE",(a0)+ bne.s no_asshole ; asshole handling here.. moveq #1,d0 ; Found. rts no_asshole: moveq #-1,d0 ; Not found. rts test_asswipe: cmpi.l #"WIPE",(a0)+ bne.s no_asswipe ; asswipe handling here.. moveq #1,d0 ; Found. rts no_asswipe: moveq #-1,d0 ; Not found. rts b_jumptable: moveq #-1,d0 ; a rts moveq #-1,d0 ; b rts ... .. bra.w test_bitch ; i ... .. bra.w test_butthole ; u ... .. test_bitch: cmpi.l #"ITCH",(a0)+ bne.s no_bitch ; bitch handling here.. moveq #1,d0 ; Found. rts no_bitch: moveq #-1,d0 ; Not found. rts test_butthole: cmpi.l #"UTTH",(a0)+ bne.s no_butthole move.l (a0)+,d0 move.b #" ",d0 cmpi.l #"OLE ",d0 bne.s no_butthole ; butthole handling here.. moveq #1,d0 ; Found. rts no_buttho old_cacr: DS.L 1 Well.. that's about it. Have fun optimising! - earx -------------------------------------------------------------- 2002 - |
|