6502.org • View topic - Comparisons and contrasts

View unanswered posts | View active topics

Board index » 6502.org Users Forum » General Discussions

All times are UTC

Comparisons and contrasts

Page 5 of 11

[ 163 posts ]

Go to page Previous 1, 2, 3, 4, 5, 6, 7, 8 ... 11 Next

Previous topic | Next topic

Author

Message

BillG

Post subject: Re: Comparisons and contrasts

Posted: Tue Oct 13, 2020 8:04 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

I am not familiar with the other benchmark, so I had to characterize it:

Code:

program Test;

  var
    Max_x : integer;
    Max_y : integer;
    Max_z : integer;
    Min_x : integer;
    Min_y : integer;
    Min_z : integer;

  function tarai(x : integer;
                 y : integer;
                 z : integer)
                   : integer;

    begin
      if x < Min_x then Min_x := x;
      if x > Max_x then Max_x := x;
      if y < Min_y then Min_y := y;
      if y > Max_y then Max_y := y;
      if z < Min_z then Min_z := z;
      if z > Max_z then Max_z := z;

      if x <= y
        then
          tarai := y
        else
          tarai := tarai(tarai(x - 1, y, z),
                         tarai(y - 1, z, x),
                         tarai(z - 1, x, y))

    end;  { tarai }

  begin
    Min_x := 10;
    Max_x := 10;
    Min_y := 1;
    Max_y := 1;
    Min_z := 0;
    Max_z := 0;
    writeln(tarai(10, 1, 0));
    writeln('(min,max): x = (', Min_x, ',', Max_x, '), y = (', Min_y, ',',
        Max_y, '), z = (', Min_z, ',', Max_z, ')')
  end.  { Test }

Quote:

10
(min,max): x = (-1,10), y = (0,10), z = (0,10)

It is recursive, but the variables can all be signed bytes.

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 2:31 am

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

This is the tarai program as a compiler might write it. Instead of setting up a register to point to the stack frame, it tracks locations relative to the stack pointer.

It is just over twice as fast as the time reported for gcc6809.

Code:

                                  00001 *
                                  00002 * program Test;
                                  00003 *
                                  00004 *   function tarai(x : shortint;
                                  00005 *                  y : shortint;
                                  00006 *                  z : shortint)
                                  00007 *                    : shortint;
                                  00008 *
                                  00009 *     begin
                                  00010 *       if x <= y
                                  00011 *         then
                                  00012 *           tarai := y
                                  00013 *         else
                                  00014 *           tarai := tarai(tarai(x - 1, y, z),
                                  00015 *                          tarai(y - 1, z, x),
                                  00016 *                          tarai(z - 1, x, y))
                                  00017 *
                                  00018 *     end;  { tarai }
                                  00019 *
                                  00020 *   begin
                                  00021 *     tarai(10, 1, 0)
                                  00022 *   end.  { Test }
                                  00023 *
                                  00024 * 53,628,345 cycles
                                  00025 *
                                  00026
 0100                             00027          org    $100
                                  00028
 0002                             00029 X_Offset equ    2
 0001                             00030 Y_Offset equ    1
 0000                             00031 Z_Offset equ    0
                                  00032
 0100                             00033 tarai
                                  00034
 0002                             00035 Frame    set    2         ; After return address
                                  00036
 0100 A6 63                   [5] 00037          lda    Frame+Y_Offset,S ; Get y
 0102 A1 64                   [5] 00038          cmpa   Frame+X_Offset,S ; Is it >= x?
 0104 2C 39 (013F)            [3] 00039          bge    Return    ; Yes, go return y
                                  00040
 0106 A6 64                   [5] 00041          lda    Frame+X_Offset,S ; Push x - 1
 0108 4A                      [2] 00042          deca
 0109 34 02                   [6] 00043          pshs   A
 0003                             00044 Frame    set    Frame+1
 010B A6 64                   [5] 00045          lda    Frame+Y_Offset,S ; Push y
 010D 34 02                   [6] 00046          pshs   A
 0004                             00047 Frame    set    Frame+1
 010F A6 64                   [5] 00048          lda    Frame+Z_Offset,S ; Push z
 0111 34 02                   [6] 00049          pshs   A
 0005                             00050 Frame    set    Frame+1
 0113 BD 0100                 [8] 00051          jsr    tarai     ; tarai(x - 1, y, z)
 0002                             00052 Frame    set    Frame-3
                                  00053
 0116 34 02                   [6] 00054          pshs   A         ; Push its value
 0003                             00055 Frame    set    Frame+1
                                  00056
 0118 A6 64                   [5] 00057          lda    Frame+Y_Offset,S ; Push y - 1
 011A 4A                      [2] 00058          deca
 011B 34 02                   [6] 00059          pshs   A
 0004                             00060 Frame    set    Frame+1
 011D A6 64                   [5] 00061          lda    Frame+Z_Offset,S ; Push z
 011F 34 02                   [6] 00062          pshs   A
 0005                             00063 Frame    set    Frame+1
 0121 A6 67                   [5] 00064          lda    Frame+X_Offset,S ; Push x
 0123 34 02                   [6] 00065          pshs   A
 0006                             00066 Frame    set    Frame+1
                                  00067
 0125 BD 0100                 [8] 00068          jsr    tarai     ; tarai(y - 1, z, x),
 0003                             00069 Frame    set    Frame-3
                                  00070
 0128 34 02                   [6] 00071          pshs   A         ; Push its value
 0004                             00072 Frame    set    Frame+1
                                  00073
 012A A6 64                   [5] 00074          lda    Frame+Z_Offset,S ; Push z - 1
 012C 4A                      [2] 00075          deca
 012D 34 02                   [6] 00076          pshs   A
 0005                             00077 Frame    set    Frame+1
 012F A6 67                   [5] 00078          lda    Frame+X_Offset,S ; Push x
 0131 34 02                   [6] 00079          pshs   A
 0006                             00080 Frame    set    Frame+1
 0133 A6 67                   [5] 00081          lda    Frame+Y_Offset,S ; Push y
 0135 34 02                   [6] 00082          pshs   A
 0007                             00083 Frame    set    Frame+1
                                  00084
 0137 BD 0100                 [8] 00085          jsr    tarai     ; tarai(z - 1, x, y)
 0004                             00086 Frame    set    Frame-3
                                  00087
 013A 34 02                   [6] 00088          pshs   A         ; Push its value
 0005                             00089 Frame    set    Frame+1
                                  00090
 013C BD 0100                 [8] 00091          jsr    tarai     ; The final call
 0002                             00092 Frame    set    Frame-3
                                  00093
 013F                             00094 Return
 013F 35 20                   [7] 00095          puls   Y         ; Get return address
                                  00096
 0141 32 63                   [5] 00097          leas   3,S       ; Clean the stack
                                  00098
 0143 6E A4                   [3] 00099          jmp    ,Y        ; Return
                                  00100
 0145                             00101 Test
 0145 86 0A                   [2] 00102          lda    #10
 0147 34 02                   [6] 00103          pshs   A
 0149 86 01                   [2] 00104          lda    #1
 014B 34 02                   [6] 00105          pshs   A
 014D 4F                      [2] 00106          clra
 014E 34 02                   [6] 00107          pshs   A
 0150 BD 0100                 [8] 00108          jsr    tarai
                                  00109
 0145                             00110          end    Test

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 4:21 am

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

Using the 6809 version as a guide, the version for the mediocre 6800 is not as ugly as feared. But it is substantially slower.

Code:

                          00001 *
                          00002 * program Test;
                          00003 *
                          00004 *   function tarai(x : shortint;
                          00005 *                  y : shortint;
                          00006 *                  z : shortint)
                          00007 *                    : shortint;
                          00008 *
                          00009 *     begin
                          00010 *       if x <= y
                          00011 *         then
                          00012 *           tarai := y
                          00013 *         else
                          00014 *           tarai := tarai(tarai(x - 1, y, z),
                          00015 *                          tarai(y - 1, z, x),
                          00016 *                          tarai(z - 1, x, y))
                          00017 *
                          00018 *     end;  { tarai }
                          00019 *
                          00020 *   begin
                          00021 *     tarai(10, 1, 0)
                          00022 *   end.  { Test }
                          00023 *
                          00024 * 75,320,710 cycles
                          00025 *
                          00026
 0000                     00027 Tmp      rmb    1
                          00028
 0100                     00029          org    $100
                          00030
 0002                     00031 X_Offset equ    2
 0001                     00032 Y_Offset equ    1
 0000                     00033 Z_Offset equ    0
                          00034
 0100                     00035 tarai
                          00036
 0100 30              [4] 00037          tsx              ; Address the stack
                          00038
 0002                     00039 Frame    set    2         ; After return address
                          00040
 0101 A6 03           [5] 00041          ldaa   Frame+Y_Offset,X ; Get y
 0103 A1 04           [5] 00042          cmpa   Frame+X_Offset,X ; Is it >= x?
 0105 2C 2F (0136)    [4] 00043          bge    Return    ; Yes, go return y
                          00044
 0107 A6 04           [5] 00045          ldaa   Frame+X_Offset,X ; Push x - 1
 0109 4A              [2] 00046          deca
 010A 36              [4] 00047          psha
 010B A6 03           [5] 00048          ldaa   Frame+Y_Offset,X ; Push y
 010D 36              [4] 00049          psha
 010E A6 02           [5] 00050          ldaa   Frame+Z_Offset,X ; Push z
 0110 36              [4] 00051          psha
 0111 BD 0100         [9] 00052          jsr    tarai     ; tarai(x - 1, y, z)
                          00053
 0114 36              [4] 00054          psha             ; Push its value
                          00055
 0115 30              [4] 00056          tsx              ; Address the stack
                          00057
 0003                     00058 Frame    set    3         ; After return address and 1 byte pushed
                          00059
 0116 A6 04           [5] 00060          ldaa   Frame+Y_Offset,X ; Push y - 1
 0118 4A              [2] 00061          deca
 0119 36              [4] 00062          psha
 011A A6 03           [5] 00063          ldaa   Frame+Z_Offset,X ; Push z
 011C 36              [4] 00064          psha
 011D A6 05           [5] 00065          ldaa   Frame+X_Offset,X ; Push x
 011F 36              [4] 00066          psha
                          00067
 0120 BD 0100         [9] 00068          jsr    tarai     ; tarai(y - 1, z, x),
                          00069
 0123 36              [4] 00070          psha             ; Push its value
                          00071
 0124 30              [4] 00072          tsx              ; Address the stack
                          00073
 0004                     00074 Frame    set    4         ; After return address and 2 bytes pushed
                          00075
 0125 A6 04           [5] 00076          ldaa   Frame+Z_Offset,X ; Push z - 1
 0127 4A              [2] 00077          deca
 0128 36              [4] 00078          psha
 0129 A6 06           [5] 00079          ldaa   Frame+X_Offset,X ; Push x
 012B 36              [4] 00080          psha
 012C A6 05           [5] 00081          ldaa   Frame+Y_Offset,X ; Push y
 012E 36              [4] 00082          psha
                          00083
 012F BD 0100         [9] 00084          jsr    tarai     ; tarai(z - 1, x, y)
                          00085
 0132 36              [4] 00086          psha             ; Push its value
                          00087
 0133 BD 0100         [9] 00088          jsr    tarai     ; The final call
                          00089
 0136                     00090 Return
 0136 33              [4] 00091          pulb             ; Get return address
 0137 D7 00           [4] 00092          stab   Tmp
 0139 33              [4] 00093          pulb
                          00094
 013A 31              [4] 00095          ins              ; Clean the stack
 013B 31              [4] 00096          ins
 013C 31              [4] 00097          ins
                          00098
 013D 37              [4] 00099          pshb             ; Return
 013E D6 00           [3] 00100          ldab   Tmp
 0140 37              [4] 00101          pshb
                          00102
 0141 39              [5] 00103          rts
                          00104
 0142                     00105 Test
 0142 86 0A           [2] 00106          ldaa   #10
 0144 36              [4] 00107          psha
 0145 86 01           [2] 00108          ldaa   #1
 0147 36              [4] 00109          psha
 0148 4F              [2] 00110          clra
 0149 36              [4] 00111          psha
 014A BD 0100         [9] 00112          jsr    tarai
                          00113
 0142                     00114          end    Test

Top

Chromatix

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 7:30 am

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462

Okay, let's have a stab at tarai() for the 6502. As noted above, the arguments and return value can be regarded as signed bytes for the test case given. I'll adopt the same technique of implementing a "user stack" for values separate from the system stack for return addresses, and trying to preserve the arguments on return so their values don't have to be copied by the caller.

Code:

tarai:    ; arguments are pointed to by X, result returned in A
  LDA 1,X
  SEC
  SBC 0,X
  BMI :+      ; if(x <= y) return y;
  LDA 1,X
  RTS
: DEC 0,X
  JSR tarai  ; tarai(x-1, y, z)
  LDY 0,X
  INY
  STY 3,X
  STA 0,X
  INX
  DEC 0,X
  JSR tarai  ; tarai(y-1, z, x)
  LDY 0,X
  INY
  STY 3,X
  STA 0,X
  INX
  DEC 0,X
  JSR tarai  ; tarai(z-1, x, y)
  INC 0,X
  DEX
  DEX
  STA 5,X  ; restore original arguments, move results up stack
  LDA 1,X
  LDY 4,X
  STY 1,X
  STA 4,X
  LDA 0,X
  LDY 3,X
  STY 0,X
  STA 3,X
  INX
  INX
  INX
  JSR tarai  ; tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) )
  DEX
  DEX
  DEX
  RTS

This uses two bytes of system stack and three bytes of user stack per level of recursion, but the rearrangement of the stack before the final call is ugly. I'll see if I can improve it.

Last edited by Chromatix on Wed Oct 14, 2020 8:02 am, edited 1 time in total.

Top

Chromatix

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 7:55 am

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462

Code:

tarai:    ; arguments are pointed to by X, result returned in A
  LDA 1,X
  SEC
  SBC 0,X
  BMI :+      ; if(x <= y) return y;
  LDA 1,X
  RTS
: LDA 0,X    ; duplicate x,y on stack
  LDY 1,X
  STA 3,X
  STY 4,X
  INX
  INX
  DEC 0,X
  JSR tarai  ; tarai(z-1, x, y)
  STA 3,X
  INC 0,X
  DEX
  DEC 0,X
  JSR tarai  ; tarai(y-1, z, x)
  STA 3,X
  INC 0,X
  DEX
  DEC 0,X
  JSR tarai  ; tarai(x-1, y, z)
  STA 3,X
  INC 0,X
  INX
  INX
  INX
  JSR tarai  ; tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) )
  DEX
  DEX
  DEX
  RTS

That's better. Three bytes of user stack, two of system stack, per recursion level. With a maximum depth of 55, that requires 165 bytes of user stack, which is well within one page.

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 11:44 am

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

I cannot get it to work.

How do you call it?

I am trying something like

Code:

    lda     #10
    sta     0
    lda     #1
    sta     1
    lda     #0
    sta     2
    ldx     #0
    jsr     tarai

What answer did you get? Any cycle count or elapsed time?

From looking at the code, it would seem that return values from tarai stored with "sta 3,x" may get overwritten should a call to tarai downstream recurse.

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 11:46 am

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

tarai tarai tarai

reminds me of this: https://www.youtube.com/watch?v=sva0nQ3JFuo

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 9:22 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

This is my first try at a Z80 version along the lines of what a good compiler might produce. It is not fast, but still faster than quoted for SDCC.

Code:

                          00001 ;
                          00002 ; program Test;
                          00003 ;
                          00004 ;   function tarai(x : shortint;
                          00005 ;                  y : shortint;
                          00006 ;                  z : shortint)
                          00007 ;                    : shortint;
                          00008 ;
                          00009 ;     begin
                          00010 ;       if x <= y
                          00011 ;         then
                          00012 ;           tarai := y
                          00013 ;         else
                          00014 ;           tarai := tarai(tarai(x - 1, y, z),
                          00015 ;                          tarai(y - 1, z, x),
                          00016 ;                          tarai(z - 1, x, y))
                          00017 ;
                          00018 ;     end;  { tarai }
                          00019 ;
                          00020 ;   begin
                          00021 ;     tarai(10, 1, 0)
                          00022 ;   end.  { Test }
                          00023 ;
                          00024 ; 174,944,873 cycles
                          00025 ;
                          00026
 0100                     00027         org     100h
                          00028
 0003                     00029 X_Offset        equ     3
 0001                     00030 Y_Offset        equ     1
 0000                     00031 Z_Offset        equ     0
                          00032
 0100                     00033 tarai:
                          00034
 0100 DD21 0000      [14] 00035         ld      IX,0            ; Address the stack
 0104 DD39           [15] 00036         add     IX,SP
                          00037
 0002                     00038 Frame   =       2               ; After return address
                          00039
 0106 DD7E03         [19] 00040         ld      A,(IX+Frame+Y_Offset)   ; Get y
 0109 DDBE05         [19] 00041         cp      (IX+Frame+X_Offset)     ; Is it >= x?
 010C F2 0150        [10] 00042         jp      P,Return                ; Yes, go return y
                          00043
 010F DD7E05         [19] 00044         ld      A,(IX+Frame+X_Offset)   ; Push x - 1
 0112 3D              [4] 00045         dec     A
 0113 F5             [11] 00046         push    AF
 0114 DD4603         [19] 00047         ld      B,(IX+Frame+Y_Offset)   ; Get y
 0117 DD4E02         [19] 00048         ld      C,(IX+Frame+Z_Offset)   ; Get z
 011A C5             [11] 00049         push    BC              ; Push them
 011B CD 0100        [17] 00050         call    tarai           ; tarai(x - 1, y, z)
                          00051
 011E F5             [11] 00052         push    AF              ; Push its value
                          00053
 011F DD21 0000      [14] 00054         ld      IX,0            ; Address the stack
 0123 DD39           [15] 00055         add     IX,SP
                          00056
 0004                     00057 Frame   =       4               ; After return address and 2 bytes pushed
                          00058
 0125 DD7E05         [19] 00059         ld      A,(IX+Frame+Y_Offset)   ; Push y - 1
 0128 3D              [4] 00060         dec     A
 0129 F5             [11] 00061         push    AF
 012A DD4604         [19] 00062         ld      B,(IX+Frame+Z_Offset)   ; Get z
 012D DD4E07         [19] 00063         ld      C,(IX+Frame+X_Offset)   ; Get x
 0130 C5             [11] 00064         push    BC              ; Push them
                          00065
 0131 CD 0100        [17] 00066         call    tarai           ; tarai(y - 1, z, x),
                          00067
 0134 F5             [11] 00068         push    AF              ; Push its value
                          00069
 0135 DD21 0000      [14] 00070         ld      IX,0            ; Address the stack
 0139 DD39           [15] 00071         add     IX,SP
                          00072
 0006                     00073 Frame   =       6               ; After return address and 4 bytes pushed
                          00074
 013B DD7E06         [19] 00075         ld      A,(IX+Frame+Z_Offset)   ; Push z - 1
 013E 3D              [4] 00076         dec     A
 013F F5             [11] 00077         push    AF
 0140 DD4609         [19] 00078         ld      B,(IX+Frame+X_Offset)   ; Get x
 0143 DD4E07         [19] 00079         ld      C,(IX+Frame+Y_Offset)   ; Get y
 0146 C5             [11] 00080         push    BC              ; Push them
                          00081
 0147 CD 0100        [17] 00082         call    tarai           ; tarai(z - 1, x, y)
                          00083
 014A C1             [10] 00084         pop     BC              ; Combine last two values
 014B 4F              [4] 00085         ld      C,A
 014C C5             [11] 00086         push    BC              ; Push them
                          00087
 014D CD 0100        [17] 00088         call    tarai           ; The final call
                          00089
 0150                     00090 Return:
 0150 E1             [10] 00091         pop     HL              ; Get return address
                          00092
 0151 C1             [10] 00093         pop     BC              ; Clean the stack
 0152 C1             [10] 00094         pop     BC
                          00095
 0153 E9              [4] 00096         jp      (HL)            ; Return
                          00097
 0154                     00098 Test
 0154 3E0A            [7] 00099         ld      A,10
 0156 F5             [11] 00100         push    AF
 0157 01 0100        [10] 00101         ld      BC,100h
 015A C5             [11] 00102         push    BC
 015B CD 0100        [17] 00103         call    tarai
                          00104
 0154                     00105         end     Test

Top

Chromatix

Post subject: Re: Comparisons and contrasts

Posted: Wed Oct 14, 2020 9:51 pm

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462

BillG wrote:

From looking at the code, it would seem that return values from tarai stored with "sta 3,x" may get overwritten should a call to tarai downstream recurse.

Yeah, that's what I get for trying to do this just before bed…

Code:

tarai:    ; arguments are pointed to by X, result returned in A
  LDA 1,X
  SEC
  SBC 0,X
  BMI :+      ; if(x <= y) return y;
  LDA 1,X
  RTS
: LDA 0,X    ; duplicate x,y on stack
  LDY 1,X
  STA 3,X
  STY 4,X
  INX
  INX
  DEC 0,X
  JSR tarai  ; tarai(z-1, x, y)
  PHA
  INC 0,X
  DEX
  DEC 0,X
  JSR tarai  ; tarai(y-1, z, x)
  PHA
  INC 0,X
  DEX
  DEC 0,X
  JSR tarai  ; tarai(x-1, y, z)
  INC 0,X
  STA 3,X
  PLA
  STA 4,X
  PLA
  STA 5,X
  INX
  INX
  INX
  JSR tarai  ; tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) )
  DEX
  DEX
  DEX
  RTS

The peak system stack usage is now 4 bytes per level of recursion, so in the region of 220 bytes, but it should now work correctly. But it now seems that reversing the order of calls might not be optimal, so going back to the first version and optimising that:

Code:

tarai:    ; arguments are pointed to by X, result returned in A
  LDA 1,X
  SEC
  SBC 0,X
  BMI :+      ; if(x <= y) return y;
  LDA 1,X
  RTS
: DEC 0,X
  JSR tarai  ; tarai(x-1, y, z)
  LDY 0,X
  INY
  STY 3,X
  PHA
  INX
  DEC 0,X
  JSR tarai  ; tarai(y-1, z, x)
  LDY 0,X
  INY
  STY 3,X
  PHA
  INX
  DEC 0,X
  JSR tarai  ; tarai(z-1, x, y)
  INC 0,X
  INX
  STA 2,X
  PLA
  STA 1,X
  PLA
  STA 0,X
  JSR tarai  ; tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) )
  DEX
  DEX
  DEX
  RTS

Four bytes of system stack and three of user stack per level of recursion.

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Thu Oct 15, 2020 12:04 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

I could not get the last one to work; it finished way too early and did not give the same answer. The code in the first part does work...

Code:

                          00001 ; 41,577,030 cycles
                          00002
 0200                     00003          org    $200
                          00004
 0200                     00005 tarai:                    ; arguments are pointed to by X, result returned in A
 0200 B5 01           [4] 00006          LDA    1,X
 0202 38              [2] 00007          SEC
 0203 F5 00           [4] 00008          SBC    0,X
 0205 30 03 (020A)  [2/3] 00009          BMI    2f        ; if(x <= y) return y;
 0207 B5 01           [4] 00010          LDA    1,X
 0209 60              [6] 00011          RTS
 020A B5 00           [4] 00012 2:       LDA    0,X       ; duplicate x,y on stack
 020C B4 01           [4] 00013          LDY    1,X
 020E 95 03           [4] 00014          STA    3,X
 0210 94 04           [4] 00015          STY    4,X
 0212 E8              [2] 00016          INX
 0213 E8              [2] 00017          INX
 0214 D6 00           [6] 00018          DEC    0,X
 0216 20 0200         [6] 00019          JSR    tarai     ; tarai(z-1, x, y)
 0219 48              [3] 00020          PHA
 021A F6 00           [6] 00021          INC    0,X
 021C CA              [2] 00022          DEX
 021D D6 00           [6] 00023          DEC    0,X
 021F 20 0200         [6] 00024          JSR    tarai     ; tarai(y-1, z, x)
 0222 48              [3] 00025          PHA
 0223 F6 00           [6] 00026          INC    0,X
 0225 CA              [2] 00027          DEX
 0226 D6 00           [6] 00028          DEC    0,X
 0228 20 0200         [6] 00029          JSR    tarai     ; tarai(x-1, y, z)
 022B F6 00           [6] 00030          INC    0,X
 022D 95 03           [4] 00031          STA    3,X
 022F 68              [4] 00032          PLA
 0230 95 04           [4] 00033          STA    4,X
 0232 68              [4] 00034          PLA
 0233 95 05           [4] 00035          STA    5,X
 0235 E8              [2] 00036          INX
 0236 E8              [2] 00037          INX
 0237 E8              [2] 00038          INX
 0238 20 0200         [6] 00039          JSR    tarai     ; tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) )
 023B CA              [2] 00040          DEX
 023C CA              [2] 00041          DEX
 023D CA              [2] 00042          DEX
 023E 60              [6] 00043          RTS
                          00044
 023F                     00045 Test:
 023F A2 00           [2] 00046          ldx    #0
 0241 A9 0A           [2] 00047          lda    #10
 0243 85 00           [3] 00048          sta    0
 0245 A9 01           [2] 00049          lda    #1
 0247 85 01           [3] 00050          sta    1
 0249 A9 00           [2] 00051          lda    #0
 024B 85 02           [3] 00052          sta    2
 024D 20 0200         [6] 00053          jsr    tarai
                          00054
 023F                     00055          end    Test

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Thu Oct 15, 2020 12:04 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

The Z80 version was modified to remove the need for an index register and surprisingly, it turns out to be much faster. This result confirms many comments that the Z80 index registers are too slow to be very useful. Long live the 8080...

Code:

                          00001 ;
                          00002 ; program Test;
                          00003 ;
                          00004 ;   function tarai(x : shortint;
                          00005 ;                  y : shortint;
                          00006 ;                  z : shortint)
                          00007 ;                    : shortint;
                          00008 ;
                          00009 ;     begin
                          00010 ;       if x <= y
                          00011 ;         then
                          00012 ;           tarai := y
                          00013 ;         else
                          00014 ;           tarai := tarai(tarai(x - 1, y, z),
                          00015 ;                          tarai(y - 1, z, x),
                          00016 ;                          tarai(z - 1, x, y))
                          00017 ;
                          00018 ;     end;  { tarai }
                          00019 ;
                          00020 ;   begin
                          00021 ;     tarai(10, 1, 0)
                          00022 ;   end.  { Test }
                          00023 ;
                          00024 ; 135,778,117 cycles
                          00025 ;
                          00026
 0100                     00027         org     100h
                          00028
 0003                     00029 X_Offset        equ     3
 0002                     00030 Y_Offset        equ     2
 0001                     00031 Z_Offset        equ     1
                          00032
 0100                     00033 tarai:
                          00034
 0002                     00035 Frame   set     2               ; After return address
                          00036
 0100 21 0004        [10] 00037         lxi     H,Frame+Y_Offset        ; Address the stack
 0103 39             [10] 00038         dad     SP
                          00039
 0104 7E              [7] 00040         mov     A,M             ; Get y
 0105 23              [5] 00041         inx     H               ; Is it >= x?
 0106 BE              [7] 00042         cmp     M
 0107 F2 013D        [10] 00043         jp      Return          ; Yes, go return y
                          00044
 010A 46              [7] 00045         mov     B,M             ; Get x - 1
 010B 05              [5] 00046         dcr     B
 010C 2B              [5] 00047         dcx     H               ; Get y
 010D 4E              [7] 00048         mov     C,M
 010E C5             [11] 00049         push    B               ; Push them
 010F 2B              [5] 00050         dcx     H               ; Push z
 0110 7E              [7] 00051         mov     A,M
 0111 F5             [11] 00052         push    PSW
 0112 CD 0100        [17] 00053         call    tarai           ; tarai(x - 1, y, z)
                          00054
 0115 F5             [11] 00055         push    PSW             ; Push its value
                          00056
 0004                     00057 Frame   set     4               ; After return address and 2 bytes pushed
                          00058
 0116 21 0006        [10] 00059         lxi     H,Frame+Y_Offset        ; Address the stack
 0119 39             [10] 00060         dad     SP
                          00061
 011A 46              [7] 00062         mov     B,M             ; Get y - 1
 011B 05              [5] 00063         dcr     B
 011C 2B              [5] 00064         dcx     H               ; Get z
 011D 4E              [7] 00065         mov     C,M
 011E C5             [11] 00066         push    B               ; Push them
 011F 23              [5] 00067         inx     H               ; Push x
 0120 23              [5] 00068         inx     H
 0121 7E              [7] 00069         mov     A,M
 0122 F5             [11] 00070         push    PSW
                          00071
 0123 CD 0100        [17] 00072         call    tarai           ; tarai(y - 1, z, x),
                          00073
 0126 C1             [10] 00074         pop     B               ; Combine last two values
 0127 4F              [5] 00075         mov     C,A
 0128 C5             [11] 00076         push    B               ; Push them
                          00077
 0129 21 0005        [10] 00078         lxi     H,Frame+Z_Offset        ; Address the stack
 012C 39             [10] 00079         dad     SP
                          00080
 012D 46              [7] 00081         mov     B,M             ; Get z - 1
 012E 05              [5] 00082         dcr     B
 012F 23              [5] 00083         inx     H               ; Get x
 0130 23              [5] 00084         inx     H
 0131 4E              [7] 00085         mov     C,M
 0132 C5             [11] 00086         push    B               ; Push them
 0133 2B              [5] 00087         dcx     H               ; Push y
 0134 7E              [7] 00088         mov     A,M
 0135 F5             [11] 00089         push    PSW
                          00090
 0136 CD 0100        [17] 00091         call    tarai           ; tarai(z - 1, x, y)
                          00092
 0139 F5             [11] 00093         push    PSW             ; Push its value
                          00094
 013A CD 0100        [17] 00095         call    tarai           ; The final call
                          00096
 013D                     00097 Return:
 013D E1             [10] 00098         pop     H               ; Get return address
                          00099
 013E C1             [10] 00100         pop     B               ; Clean the stack
 013F C1             [10] 00101         pop     B
                          00102
 0140 E9              [5] 00103         pchl                    ; Return
                          00104
 0141                     00105 Test
 0141 01 0A01        [10] 00106         lxi     B,10*256+1h
 0144 C5             [11] 00107         push    B
 0145 AF              [4] 00108         xra     A
 0146 F5             [11] 00109         push    PSW
 0147 CD 0100        [17] 00110         call    tarai
                          00111
 0141                     00112         end     Test

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Thu Oct 15, 2020 6:49 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

Enough with trying to work out what a compiler may do.

Fire up those afterburners and let's speed this thing up.

Start with the low hanging fruit...

Code:

                          00024 * 74,517,289 cycles after replacing jsr with bsr
                          00025 * 75,320,710 cycles originally
                          00026 *
                          00027
 0000                     00028 Tmp      rmb    1
                          00029
 0100                     00030          org    $100
                          00031
 0002                     00032 X_Offset equ    2
 0001                     00033 Y_Offset equ    1
 0000                     00034 Z_Offset equ    0
                          00035
 0100                     00036 tarai
                          00037
 0100 30              [4] 00038          tsx              ; Address the stack
                          00039
 0002                     00040 Frame    set    2         ; After return address
                          00041
 0101 A6 03           [5] 00042          ldaa   Frame+Y_Offset,X ; Get y
 0103 A1 04           [5] 00043          cmpa   Frame+X_Offset,X ; Is it >= x?
 0105 2C 2B (0132)    [4] 00044          bge    Return    ; Yes, go return y
                          00045
 0107 A6 04           [5] 00046          ldaa   Frame+X_Offset,X ; Push x - 1
 0109 4A              [2] 00047          deca
 010A 36              [4] 00048          psha
 010B A6 03           [5] 00049          ldaa   Frame+Y_Offset,X ; Push y
 010D 36              [4] 00050          psha
 010E A6 02           [5] 00051          ldaa   Frame+Z_Offset,X ; Push z
 0110 36              [4] 00052          psha
 0111 8D ED (0100)    [8] 00053          bsr    tarai     ; tarai(x - 1, y, z)
                          00054
 0113 36              [4] 00055          psha             ; Push its value
                          00056
 0114 30              [4] 00057          tsx              ; Address the stack
                          00058
 0003                     00059 Frame    set    3         ; After return address and 1 byte pushed
                          00060
 0115 A6 04           [5] 00061          ldaa   Frame+Y_Offset,X ; Push y - 1
 0117 4A              [2] 00062          deca
 0118 36              [4] 00063          psha
 0119 A6 03           [5] 00064          ldaa   Frame+Z_Offset,X ; Push z
 011B 36              [4] 00065          psha
 011C A6 05           [5] 00066          ldaa   Frame+X_Offset,X ; Push x
 011E 36              [4] 00067          psha
                          00068
 011F 8D DF (0100)    [8] 00069          bsr    tarai     ; tarai(y - 1, z, x),
                          00070
 0121 36              [4] 00071          psha             ; Push its value
                          00072
 0122 30              [4] 00073          tsx              ; Address the stack
                          00074
 0004                     00075 Frame    set    4         ; After return address and 2 bytes pushed
                          00076
 0123 A6 04           [5] 00077          ldaa   Frame+Z_Offset,X ; Push z - 1
 0125 4A              [2] 00078          deca
 0126 36              [4] 00079          psha
 0127 A6 06           [5] 00080          ldaa   Frame+X_Offset,X ; Push x
 0129 36              [4] 00081          psha
 012A A6 05           [5] 00082          ldaa   Frame+Y_Offset,X ; Push y
 012C 36              [4] 00083          psha
                          00084
 012D 8D D1 (0100)    [8] 00085          bsr    tarai     ; tarai(z - 1, x, y)
                          00086
 012F 36              [4] 00087          psha             ; Push its value
                          00088
 0130 8D CE (0100)    [8] 00089          bsr    tarai     ; The final call
                          00090
 0132                     00091 Return
 0132 33              [4] 00092          pulb             ; Get return address
 0133 D7 00           [4] 00093          stab   Tmp
 0135 33              [4] 00094          pulb
                          00095
 0136 31              [4] 00096          ins              ; Clean the stack
 0137 31              [4] 00097          ins
 0138 31              [4] 00098          ins
                          00099
 0139 37              [4] 00100          pshb             ; Return
 013A D6 00           [3] 00101          ldab   Tmp
 013C 37              [4] 00102          pshb
                          00103
 013D 39              [5] 00104          rts
                          00105
 013E                     00106 Test
 013E 86 0A           [2] 00107          ldaa   #10
 0140 36              [4] 00108          psha
 0141 86 01           [2] 00109          ldaa   #1
 0143 36              [4] 00110          psha
 0144 4F              [2] 00111          clra
 0145 36              [4] 00112          psha
 0146 8D B8 (0100)    [8] 00113          bsr    tarai
                          00114
 013E                     00115          end    Test

That code to tidy up the stack does not look as tight as it can be...

Code:

                          00024 * 71,303,605 cycles with faster return
                          00025 * 74,517,289 cycles after replacing jsr with bsr
                          00026 * 75,320,710 cycles originally
                          00027 *
                          00028
 0000                     00029 Tmp      rmb    2
                          00030
 0100                     00031          org    $100
                          00032
 0002                     00033 X_Offset equ    2
 0001                     00034 Y_Offset equ    1
 0000                     00035 Z_Offset equ    0
                          00036
 0100                     00037 tarai
                          00038
 0100 30              [4] 00039          tsx              ; Address the stack
                          00040
 0002                     00041 Frame    set    2         ; After return address
                          00042
 0101 A6 03           [5] 00043          ldaa   Frame+Y_Offset,X ; Get y
 0103 A1 04           [5] 00044          cmpa   Frame+X_Offset,X ; Is it >= x?
 0105 2C 2B (0132)    [4] 00045          bge    Return    ; Yes, go return y
                          00046
 0107 A6 04           [5] 00047          ldaa   Frame+X_Offset,X ; Push x - 1
 0109 4A              [2] 00048          deca
 010A 36              [4] 00049          psha
 010B A6 03           [5] 00050          ldaa   Frame+Y_Offset,X ; Push y
 010D 36              [4] 00051          psha
 010E A6 02           [5] 00052          ldaa   Frame+Z_Offset,X ; Push z
 0110 36              [4] 00053          psha
 0111 8D ED (0100)    [8] 00054          bsr    tarai     ; tarai(x - 1, y, z)
                          00055
 0113 36              [4] 00056          psha             ; Push its value
                          00057
 0114 30              [4] 00058          tsx              ; Address the stack
                          00059
 0003                     00060 Frame    set    3         ; After return address and 1 byte pushed
                          00061
 0115 A6 04           [5] 00062          ldaa   Frame+Y_Offset,X ; Push y - 1
 0117 4A              [2] 00063          deca
 0118 36              [4] 00064          psha
 0119 A6 03           [5] 00065          ldaa   Frame+Z_Offset,X ; Push z
 011B 36              [4] 00066          psha
 011C A6 05           [5] 00067          ldaa   Frame+X_Offset,X ; Push x
 011E 36              [4] 00068          psha
                          00069
 011F 8D DF (0100)    [8] 00070          bsr    tarai     ; tarai(y - 1, z, x),
                          00071
 0121 36              [4] 00072          psha             ; Push its value
                          00073
 0122 30              [4] 00074          tsx              ; Address the stack
                          00075
 0004                     00076 Frame    set    4         ; After return address and 2 bytes pushed
                          00077
 0123 A6 04           [5] 00078          ldaa   Frame+Z_Offset,X ; Push z - 1
 0125 4A              [2] 00079          deca
 0126 36              [4] 00080          psha
 0127 A6 06           [5] 00081          ldaa   Frame+X_Offset,X ; Push x
 0129 36              [4] 00082          psha
 012A A6 05           [5] 00083          ldaa   Frame+Y_Offset,X ; Push y
 012C 36              [4] 00084          psha
                          00085
 012D 8D D1 (0100)    [8] 00086          bsr    tarai     ; tarai(z - 1, x, y)
                          00087
 012F 36              [4] 00088          psha             ; Push its value
                          00089
 0130 8D CE (0100)    [8] 00090          bsr    tarai     ; The final call
                          00091
 0132                     00092 Return
 0132 33              [4] 00093          pulb             ; Get return address
 0133 D7 00           [4] 00094          stab   Tmp
 0135 33              [4] 00095          pulb
 0136 D7 01           [4] 00096          stab   Tmp+1
                          00097
 0138 31              [4] 00098          ins              ; Clean the stack
 0139 31              [4] 00099          ins
 013A 31              [4] 00100          ins
                          00101
 013B DE 00           [4] 00102          ldx    Tmp       ; Return
 013D 6E 00           [4] 00103          jmp    ,X
                          00104
 013F                     00105 Test
 013F 86 0A           [2] 00106          ldaa   #10
 0141 36              [4] 00107          psha
 0142 86 01           [2] 00108          ldaa   #1
 0144 36              [4] 00109          psha
 0145 4F              [2] 00110          clra
 0146 36              [4] 00111          psha
 0147 8D B7 (0100)    [8] 00112          bsr    tarai
                          00113
 013F                     00114          end    Test

Why mess with the stack any more than absolutely necessary?

Code:

                          00024 * 68,491,635 cycles after tail recursion elimination
                          00025 * 71,303,605 cycles with faster return
                          00026 * 74,517,289 cycles after replacing jsr with bsr
                          00027 * 75,320,710 cycles originally
                          00028 *
                          00029
 0000                     00030 Tmp      rmb    2
                          00031
 0100                     00032          org    $100
                          00033
 0002                     00034 X_Offset equ    2
 0001                     00035 Y_Offset equ    1
 0000                     00036 Z_Offset equ    0
                          00037
 0100                     00038 tarai
                          00039
 0100 30              [4] 00040          tsx              ; Address the stack
                          00041
 0002                     00042 Frame    set    2         ; After return address
                          00043
 0101 A6 03           [5] 00044          ldaa   Frame+Y_Offset,X ; Get y
 0103 A1 04           [5] 00045          cmpa   Frame+X_Offset,X ; Is it >= x?
 0105 2C 33 (013A)    [4] 00046          bge    Return    ; Yes, go return y
                          00047
 0107 A6 04           [5] 00048          ldaa   Frame+X_Offset,X ; Push x - 1
 0109 4A              [2] 00049          deca
 010A 36              [4] 00050          psha
 010B A6 03           [5] 00051          ldaa   Frame+Y_Offset,X ; Push y
 010D 36              [4] 00052          psha
 010E A6 02           [5] 00053          ldaa   Frame+Z_Offset,X ; Push z
 0110 36              [4] 00054          psha
 0111 8D ED (0100)    [8] 00055          bsr    tarai     ; tarai(x - 1, y, z)
                          00056
 0113 36              [4] 00057          psha             ; Push its value
                          00058
 0114 30              [4] 00059          tsx              ; Address the stack
                          00060
 0003                     00061 Frame    set    3         ; After return address and 1 byte pushed
                          00062
 0115 A6 04           [5] 00063          ldaa   Frame+Y_Offset,X ; Push y - 1
 0117 4A              [2] 00064          deca
 0118 36              [4] 00065          psha
 0119 A6 03           [5] 00066          ldaa   Frame+Z_Offset,X ; Push z
 011B 36              [4] 00067          psha
 011C A6 05           [5] 00068          ldaa   Frame+X_Offset,X ; Push x
 011E 36              [4] 00069          psha
                          00070
 011F 8D DF (0100)    [8] 00071          bsr    tarai     ; tarai(y - 1, z, x),
                          00072
 0121 36              [4] 00073          psha             ; Push its value
                          00074
 0122 30              [4] 00075          tsx              ; Address the stack
                          00076
 0004                     00077 Frame    set    4         ; After return address and 2 bytes pushed
                          00078
 0123 A6 04           [5] 00079          ldaa   Frame+Z_Offset,X ; Push z - 1
 0125 4A              [2] 00080          deca
 0126 36              [4] 00081          psha
 0127 A6 06           [5] 00082          ldaa   Frame+X_Offset,X ; Push x
 0129 36              [4] 00083          psha
 012A A6 05           [5] 00084          ldaa   Frame+Y_Offset,X ; Push y
 012C 36              [4] 00085          psha
                          00086
 012D 8D D1 (0100)    [8] 00087          bsr    tarai     ; tarai(z - 1, x, y)
                          00088
 012F 30              [4] 00089          tsx              ; Address the stack
                          00090
 0130 A7 04           [6] 00091          staa   Frame+Z_Offset,X ; Replace z with the result
                          00092
 0132 32              [4] 00093          pula             ; Get new y
                          00094
 0133 A7 05           [6] 00095          staa   Frame+Y_Offset,X ; Replace y
                          00096
 0135 32              [4] 00097          pula             ; Get new x
                          00098
 0136 A7 06           [6] 00099          staa   Frame+X_Offset,X ; Replace x
                          00100
 0138 20 C6 (0100)    [4] 00101          bra    tarai     ; The final "call"
                          00102
 013A                     00103 Return
 013A 33              [4] 00104          pulb             ; Get return address
 013B D7 00           [4] 00105          stab   Tmp
 013D 33              [4] 00106          pulb
 013E D7 01           [4] 00107          stab   Tmp+1
                          00108
 0140 31              [4] 00109          ins              ; Clean the stack
 0141 31              [4] 00110          ins
 0142 31              [4] 00111          ins
                          00112
 0143 DE 00           [4] 00113          ldx    Tmp       ; Return
 0145 6E 00           [4] 00114          jmp    ,X
                          00115
 0147                     00116 Test
 0147 86 0A           [2] 00117          ldaa   #10
 0149 36              [4] 00118          psha
 014A 86 01           [2] 00119          ldaa   #1
 014C 36              [4] 00120          psha
 014D 4F              [2] 00121          clra
 014E 36              [4] 00122          psha
 014F 8D AF (0100)    [8] 00123          bsr    tarai
                          00124
 0147                     00125          end    Test

Does it seem wasteful to you to have to call tarai when x <= y only to have it return y? Yeah, me too...

Code:

                          00024 * 29,101,036 cycles checking x <= y before calling tarai
                          00025 * 68,491,635 cycles after tail recursion elimination
                          00026 * 71,303,605 cycles with faster return
                          00027 * 74,517,289 cycles after replacing jsr with bsr
                          00028 * 75,320,710 cycles originally
                          00029 *
                          00030
 0000                     00031 Tmp      rmb    2
                          00032
 0100                     00033          org    $100
                          00034
 0002                     00035 X_Offset equ    2
 0001                     00036 Y_Offset equ    1
 0000                     00037 Z_Offset equ    0
                          00038
 0100                     00039 tarai
                          00040
 0100 30              [4] 00041          tsx              ; Address the stack
                          00042
 0002                     00043 Frame    set    2         ; After return address
                          00044
 0101 E6 04           [5] 00045          ldab   Frame+X_Offset,X ; Get x - 1
 0103 5A              [2] 00046          decb
 0104 A6 03           [5] 00047          ldaa   Frame+Y_Offset,X ; Get y
 0106 11              [2] 00048          cba              ; Is x - 1 <= y
 0107 2C 07 (0110)    [4] 00049          bge    2f        ; Yes, "return value" is y
                          00050
 0109 37              [4] 00051          pshb             ; Push x - 1
 010A 36              [4] 00052          psha             ; Push y
 010B A6 02           [5] 00053          ldaa   Frame+Z_Offset,X ; Push z
 010D 36              [4] 00054          psha
 010E 8D F0 (0100)    [8] 00055          bsr    tarai     ; tarai(x - 1, y, z)
                          00056
 0110                     00057 2
 0110 36              [4] 00058          psha             ; Push its value
                          00059
 0111 30              [4] 00060          tsx              ; Address the stack
                          00061
 0003                     00062 Frame    set    3         ; After return address and 1 byte pushed
                          00063
 0112 E6 04           [5] 00064          ldab   Frame+Y_Offset,X ; Get y - 1
 0114 5A              [2] 00065          decb
 0115 A6 03           [5] 00066          ldaa   Frame+Z_Offset,X ; Get z
 0117 11              [2] 00067          cba              ; Is y - 1 <= z
 0118 2C 07 (0121)    [4] 00068          bge    2f        ; Yes, "return value" is z
                          00069
 011A 37              [4] 00070          pshb             ; Push y - 1
 011B 36              [4] 00071          psha             ; Push z
 011C A6 05           [5] 00072          ldaa   Frame+X_Offset,X ; Push x
 011E 36              [4] 00073          psha
                          00074
 011F 8D DF (0100)    [8] 00075          bsr    tarai     ; tarai(y - 1, z, x),
                          00076
 0121                     00077 2
 0121 36              [4] 00078          psha             ; Push its value
                          00079
 0122 30              [4] 00080          tsx              ; Address the stack
                          00081
 0004                     00082 Frame    set    4         ; After return address and 2 bytes pushed
                          00083
 0123 E6 04           [5] 00084          ldab   Frame+Z_Offset,X ; Get z - 1
 0125 5A              [2] 00085          decb
 0126 A6 06           [5] 00086          ldaa   Frame+X_Offset,X ; Get x
 0128 11              [2] 00087          cba              ; Is z - 1 <= x
 0129 2C 07 (0132)    [4] 00088          bge    2f        ; Yes, "return value" is x
                          00089
 012B 37              [4] 00090          pshb             ; Push z - 1
 012C 36              [4] 00091          psha             ; Push x
 012D A6 05           [5] 00092          ldaa   Frame+Y_Offset,X ; Push y
 012F 36              [4] 00093          psha
                          00094
 0130 8D CE (0100)    [8] 00095          bsr    tarai     ; tarai(z - 1, x, y)
                          00096
 0132                     00097 2
 0132 30              [4] 00098          tsx              ; Address the stack
                          00099
 0133 A7 04           [6] 00100          staa   Frame+Z_Offset,X ; Replace z with the result
                          00101
 0135 32              [4] 00102          pula             ; Get new y
 0136 33              [4] 00103          pulb             ; Get new x
 0137 11              [2] 00104          cba              ; Is new x <= new y
 0138 2C 06 (0140)    [4] 00105          bge    Return    ; Yes, return new y
                          00106
 013A A7 05           [6] 00107          staa   Frame+Y_Offset,X ; Replace y
 013C E7 06           [6] 00108          stab   Frame+X_Offset,X ; Replace x
                          00109
 013E 20 C0 (0100)    [4] 00110          bra    tarai     ; The final "call"
                          00111
 0140                     00112 Return
 0140 33              [4] 00113          pulb             ; Get return address
 0141 D7 00           [4] 00114          stab   Tmp
 0143 33              [4] 00115          pulb
 0144 D7 01           [4] 00116          stab   Tmp+1
                          00117
 0146 31              [4] 00118          ins              ; Clean the stack
 0147 31              [4] 00119          ins
 0148 31              [4] 00120          ins
                          00121
 0149 DE 00           [4] 00122          ldx    Tmp       ; Return
 014B 6E 00           [4] 00123          jmp    ,X
                          00124
 014D                     00125 Test
 014D 86 0A           [2] 00126          ldaa   #10
 014F 36              [4] 00127          psha
 0150 86 01           [2] 00128          ldaa   #1
 0152 36              [4] 00129          psha
 0153 4F              [2] 00130          clra
 0154 36              [4] 00131          psha
 0155 8D A9 (0100)    [8] 00132          bsr    tarai
                          00133
 014D                     00134          end    Test

But wait, there's more. There is one more highly prodigious change with an almost thermonuclear effect.

I will hold off posting it for a little while so that you may try to find it...

If the values returned from the first two calls to tarai satisfy x <= y, there is no need to call tarai for the third and fourth times...

Code:

                          00024 *      6,454 cycles checking x <= y after tarai(x - 1, ...) and (y - 1, ...)
                          00025 * 29,101,036 cycles checking x <= y before calling tarai
                          00026 * 68,491,635 cycles after tail recursion elimination
                          00027 * 71,303,605 cycles with faster return
                          00028 * 74,517,289 cycles after replacing jsr with bsr
                          00029 * 75,320,710 cycles originally
                          00030 *
                          00031
 0000                     00032 Tmp      rmb    2
                          00033
 0100                     00034          org    $100
                          00035
 0002                     00036 X_Offset equ    2
 0001                     00037 Y_Offset equ    1
 0000                     00038 Z_Offset equ    0
                          00039
 0100                     00040 tarai
                          00041
 0100 30              [4] 00042          tsx              ; Address the stack
                          00043
 0002                     00044 Frame    set    2         ; After return address
                          00045
 0101 E6 04           [5] 00046          ldab   Frame+X_Offset,X ; Get x - 1
 0103 5A              [2] 00047          decb
 0104 A6 03           [5] 00048          ldaa   Frame+Y_Offset,X ; Get y
 0106 11              [2] 00049          cba              ; Is x - 1 <= y
 0107 2C 07 (0110)    [4] 00050          bge    2f        ; Yes, "return value" is y
                          00051
 0109 37              [4] 00052          pshb             ; Push x - 1
 010A 36              [4] 00053          psha             ; Push y
 010B A6 02           [5] 00054          ldaa   Frame+Z_Offset,X ; Push z
 010D 36              [4] 00055          psha
 010E 8D F0 (0100)    [8] 00056          bsr    tarai     ; tarai(x - 1, y, z)
                          00057
 0110                     00058 2
 0110 36              [4] 00059          psha             ; Push its value
                          00060
 0111 30              [4] 00061          tsx              ; Address the stack
                          00062
 0003                     00063 Frame    set    3         ; After return address and 1 byte pushed
                          00064
 0112 E6 04           [5] 00065          ldab   Frame+Y_Offset,X ; Get y - 1
 0114 5A              [2] 00066          decb
 0115 A6 03           [5] 00067          ldaa   Frame+Z_Offset,X ; Get z
 0117 11              [2] 00068          cba              ; Is y - 1 <= z
 0118 2C 07 (0121)    [4] 00069          bge    2f        ; Yes, "return value" is z
                          00070
 011A 37              [4] 00071          pshb             ; Push y - 1
 011B 36              [4] 00072          psha             ; Push z
 011C A6 05           [5] 00073          ldaa   Frame+X_Offset,X ; Push x
 011E 36              [4] 00074          psha
                          00075
 011F 8D DF (0100)    [8] 00076          bsr    tarai     ; tarai(y - 1, z, x),
                          00077
 0121                     00078 2
 0121 33              [4] 00079          pulb             ; Get new x
 0122 11              [2] 00080          cba              ; Is new x <= new y
 0123 2C 1D (0142)    [4] 00081          bge    Return    ; Yes, return new y
                          00082
 0125 37              [4] 00083          pshb             ; Push new x
 0126 36              [4] 00084          psha             ; Push new y
                          00085
 0127 30              [4] 00086          tsx              ; Address the stack
                          00087
 0004                     00088 Frame    set    4         ; After return address and 2 bytes pushed
                          00089
 0128 E6 04           [5] 00090          ldab   Frame+Z_Offset,X ; Get z - 1
 012A 5A              [2] 00091          decb
 012B A6 06           [5] 00092          ldaa   Frame+X_Offset,X ; Get x
 012D 11              [2] 00093          cba              ; Is z - 1 <= x
 012E 2C 07 (0137)    [4] 00094          bge    2f        ; Yes, "return value" is x
                          00095
 0130 37              [4] 00096          pshb             ; Push z - 1
 0131 36              [4] 00097          psha             ; Push x
 0132 A6 05           [5] 00098          ldaa   Frame+Y_Offset,X ; Push y
 0134 36              [4] 00099          psha
                          00100
 0135 8D C9 (0100)    [8] 00101          bsr    tarai     ; tarai(z - 1, x, y)
                          00102
 0137                     00103 2
 0137 30              [4] 00104          tsx              ; Address the stack
                          00105
 0138 A7 04           [6] 00106          staa   Frame+Z_Offset,X ; Replace z with the result
                          00107
 013A 32              [4] 00108          pula             ; Get new y
 013B 33              [4] 00109          pulb             ; Get new x
                          00110
 013C A7 05           [6] 00111          staa   Frame+Y_Offset,X ; Replace y
 013E E7 06           [6] 00112          stab   Frame+X_Offset,X ; Replace x
                          00113
 0140 20 BE (0100)    [4] 00114          bra    tarai     ; The final "call"
                          00115
 0142                     00116 Return
 0142 33              [4] 00117          pulb             ; Get return address
 0143 D7 00           [4] 00118          stab   Tmp
 0145 33              [4] 00119          pulb
 0146 D7 01           [4] 00120          stab   Tmp+1
                          00121
 0148 31              [4] 00122          ins              ; Clean the stack
 0149 31              [4] 00123          ins
 014A 31              [4] 00124          ins
                          00125
 014B DE 00           [4] 00126          ldx    Tmp       ; Return
 014D 6E 00           [4] 00127          jmp    ,X
                          00128
 014F                     00129 Test
 014F 86 0A           [2] 00130          ldaa   #10
 0151 36              [4] 00131          psha
 0152 86 01           [2] 00132          ldaa   #1
 0154 36              [4] 00133          psha
 0155 4F              [2] 00134          clra
 0156 36              [4] 00135          psha
 0157 8D A7 (0100)    [8] 00136          bsr    tarai
                          00137
 014F                     00138          end    Test

Edit:

Top

barrym95838

Post subject: Re: Comparisons and contrasts

Posted: Fri Oct 16, 2020 4:04 am

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1949
Location: Sacramento, CA, USA

Is there a possibility for "caching" one input and one return value in a register or register pair? It should reduce parameter stack usage, but I'm not sure how significant it would be.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Fri Oct 16, 2020 5:10 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

It is not clear what you mean. Pass one or two of the numbers in registers instead of on the stack?

All three have to eventually go onto the stack anyway in order to make the recursive calls.

That was what I was about to do with x and y so that they may be compared quicker when it became obvious that comparing before the call was even better.

Top

BillG

Post subject: Re: Comparisons and contrasts

Posted: Sat Oct 17, 2020 3:17 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 704
Location: North Tejas

Speeding up the 8080 version:

The code for the 8080 did not have any easy improvements like the 6800.

So here are the structural changes:

Code:

                          00024 ;  67,519,041 cycles checking x <= y before calling tarai
                          00025 ; 135,778,117 cycles originally
                          00026 ;
                          00027
 0100                     00028         org     100h
                          00029
 0003                     00030 X_Offset        equ     3
 0002                     00031 Y_Offset        equ     2
 0001                     00032 Z_Offset        equ     1
                          00033
 0100                     00034 tarai:
                          00035
 0002                     00036 Frame   set     2               ; After return address
                          00037
 0100 21 0005        [10] 00038         lxi     H,Frame+X_Offset        ; Address the stack
 0103 39             [10] 00039         dad     SP
                          00040
 0104 46              [7] 00041         mov     B,M             ; Get x - 1
 0105 05              [5] 00042         dcr     B
 0106 2B              [5] 00043         dcx     H               ; Get y
 0107 7E              [7] 00044         mov     A,M
 0108 B8              [4] 00045         cmp     B               ; Is x - 1 <= y?
 0109 F2 0114        [10] 00046         jp      2f              ; Yes, "return value" is y
                          00047
 010C 4F              [5] 00048         mov     C,A             ; Get y in position
 010D C5             [11] 00049         push    B               ; Push them
 010E 2B              [5] 00050         dcx     H               ; Push z
 010F 7E              [7] 00051         mov     A,M
 0110 F5             [11] 00052         push    PSW
 0111 CD 0100        [17] 00053         call    tarai           ; tarai(x - 1, y, z)
                          00054
 0114                     00055 2:
 0114 F5             [11] 00056         push    PSW             ; Push its value
                          00057
 0004                     00058 Frame   set     4               ; After return address and 2 bytes pushed
                          00059
 0115 21 0006        [10] 00060         lxi     H,Frame+Y_Offset        ; Address the stack
 0118 39             [10] 00061         dad     SP
                          00062
 0119 46              [7] 00063         mov     B,M             ; Get y - 1
 011A 05              [5] 00064         dcr     B
 011B 2B              [5] 00065         dcx     H               ; Get z
 011C 7E              [7] 00066         mov     A,M
 011D B8              [4] 00067         cmp     B               ; Is y - 1 <= z?
 011E F2 012A        [10] 00068         jp      2f              ; Yes, "return value" is y
                          00069
 0121 4F              [5] 00070         mov     C,A             ; Get z in position
 0122 C5             [11] 00071         push    B               ; Push them
 0123 23              [5] 00072         inx     H               ; Push x
 0124 23              [5] 00073         inx     H
 0125 7E              [7] 00074         mov     A,M
 0126 F5             [11] 00075         push    PSW
                          00076
 0127 CD 0100        [17] 00077         call    tarai           ; tarai(y - 1, z, x),
                          00078
 012A                     00079 2:
 012A C1             [10] 00080         pop     B               ; Combine last two values
 012B 4F              [5] 00081         mov     C,A
 012C C5             [11] 00082         push    B               ; Push them
                          00083
 012D 21 0005        [10] 00084         lxi     H,Frame+Z_Offset        ; Address the stack
 0130 39             [10] 00085         dad     SP
                          00086
 0131 46              [7] 00087         mov     B,M             ; Get z - 1
 0132 05              [5] 00088         dcr     B
 0133 23              [5] 00089         inx     H               ; Get x
 0134 23              [5] 00090         inx     H
 0135 7E              [7] 00091         mov     A,M
 0136 B8              [4] 00092         cmp     B               ; Is y - 1 <= z?
 0137 F2 0142        [10] 00093         jp      2f              ; Yes, "return value" is y
                          00094
 013A 4F              [5] 00095         mov     C,A             ; Get x in position
 013B C5             [11] 00096         push    B               ; Push them
 013C 2B              [5] 00097         dcx     H               ; Push y
 013D 7E              [7] 00098         mov     A,M
 013E F5             [11] 00099         push    PSW
                          00100
 013F CD 0100        [17] 00101         call    tarai           ; tarai(z - 1, x, y)
                          00102
 0142                     00103 2:
 0142 57              [5] 00104         mov     D,A             ; Stash its value
                          00105
 0143 C1             [10] 00106         pop     B               ; Get first and second value
 0144 79              [5] 00107         mov     A,C             ; The second value
 0145 B8              [4] 00108         cmp     B               ; Is second value <= first value?
 0146 F2 014E        [10] 00109         jp      Return          ; Yes, "return value" is second value
                          00110
 0149 C5             [11] 00111         push    B               ; Push first and second values
 014A D5             [11] 00112         push    D               ; Push third value
                          00113
 014B CD 0100        [17] 00114         call    tarai           ; The final call
                          00115
 014E                     00116 Return:
 014E E1             [10] 00117         pop     H               ; Get return address
                          00118
 014F C1             [10] 00119         pop     B               ; Clean the stack
 0150 C1             [10] 00120         pop     B
                          00121
 0151 E9              [5] 00122         pchl                    ; Return
                          00123
 0152                     00124 Test
 0152 01 0A01        [10] 00125         lxi     B,10*256+1h
 0155 C5             [11] 00126         push    B
 0156 AF              [4] 00127         xra     A
 0157 F5             [11] 00128         push    PSW
 0158 CD 0100        [17] 00129         call    tarai
                          00130
 0152                     00131         end     Test

Finally, the big one:

Code:

                          00024 ;      13,524 cycles checking x <= y after tarai(x - 1, ...) and (y - 1, ...)
                          00025 ;  67,519,041 cycles checking x <= y before calling tarai
                          00026 ; 135,778,117 cycles originally
                          00027 ;
                          00028
 0100                     00029         org     100h
                          00030
 0003                     00031 X_Offset        equ     3
 0002                     00032 Y_Offset        equ     2
 0001                     00033 Z_Offset        equ     1
                          00034
 0100                     00035 tarai:
                          00036
 0002                     00037 Frame   set     2               ; After return address
                          00038
 0100 21 0005        [10] 00039         lxi     H,Frame+X_Offset        ; Address the stack
 0103 39             [10] 00040         dad     SP
                          00041
 0104 46              [7] 00042         mov     B,M             ; Get x - 1
 0105 05              [5] 00043         dcr     B
 0106 2B              [5] 00044         dcx     H               ; Get y
 0107 7E              [7] 00045         mov     A,M
 0108 B8              [4] 00046         cmp     B               ; Is x - 1 <= y?
 0109 F2 0114        [10] 00047         jp      2f              ; Yes, "return value" is y
                          00048
 010C 4F              [5] 00049         mov     C,A             ; Get y in position
 010D C5             [11] 00050         push    B               ; Push them
 010E 2B              [5] 00051         dcx     H               ; Push z
 010F 7E              [7] 00052         mov     A,M
 0110 F5             [11] 00053         push    PSW
 0111 CD 0100        [17] 00054         call    tarai           ; tarai(x - 1, y, z)
                          00055
 0114                     00056 2:
 0114 F5             [11] 00057         push    PSW             ; Push its value
                          00058
 0004                     00059 Frame   set     4               ; After return address and 2 bytes pushed
                          00060
 0115 21 0006        [10] 00061         lxi     H,Frame+Y_Offset        ; Address the stack
 0118 39             [10] 00062         dad     SP
                          00063
 0119 46              [7] 00064         mov     B,M             ; Get y - 1
 011A 05              [5] 00065         dcr     B
 011B 2B              [5] 00066         dcx     H               ; Get z
 011C 7E              [7] 00067         mov     A,M
 011D B8              [4] 00068         cmp     B               ; Is y - 1 <= z?
 011E F2 012A        [10] 00069         jp      2f              ; Yes, "return value" is y
                          00070
 0121 4F              [5] 00071         mov     C,A             ; Get z in position
 0122 C5             [11] 00072         push    B               ; Push them
 0123 23              [5] 00073         inx     H               ; Push x
 0124 23              [5] 00074         inx     H
 0125 7E              [7] 00075         mov     A,M
 0126 F5             [11] 00076         push    PSW
                          00077
 0127 CD 0100        [17] 00078         call    tarai           ; tarai(y - 1, z, x),
                          00079
 012A                     00080 2:
 012A C1             [10] 00081         pop     B               ; Get new x
 012B B8              [4] 00082         cmp     B               ; Is new y <= new x?
 012C F2 014A        [10] 00083         jp      Return          ; Yes, "return value" is new y
                          00084
 012F 4F              [5] 00085         mov     C,A             ; Combine last two values
 0130 C5             [11] 00086         push    B               ; Push them
                          00087
 0131 21 0005        [10] 00088         lxi     H,Frame+Z_Offset        ; Address the stack
 0134 39             [10] 00089         dad     SP
                          00090
 0135 46              [7] 00091         mov     B,M             ; Get z - 1
 0136 05              [5] 00092         dcr     B
 0137 23              [5] 00093         inx     H               ; Get x
 0138 23              [5] 00094         inx     H
 0139 7E              [7] 00095         mov     A,M
 013A B8              [4] 00096         cmp     B               ; Is y - 1 <= z?
 013B F2 0146        [10] 00097         jp      2f              ; Yes, "return value" is y
                          00098
 013E 4F              [5] 00099         mov     C,A             ; Get x in position
 013F C5             [11] 00100         push    B               ; Push them
 0140 2B              [5] 00101         dcx     H               ; Push y
 0141 7E              [7] 00102         mov     A,M
 0142 F5             [11] 00103         push    PSW
                          00104
 0143 CD 0100        [17] 00105         call    tarai           ; tarai(z - 1, x, y)
                          00106
 0146                     00107 2:
 0146 F5             [11] 00108         push    PSW             ; Push its value
                          00109
 0147 CD 0100        [17] 00110         call    tarai           ; The final call
                          00111
 014A                     00112 Return:
 014A E1             [10] 00113         pop     H               ; Get return address
                          00114
 014B C1             [10] 00115         pop     B               ; Clean the stack
 014C C1             [10] 00116         pop     B
                          00117
 014D E9              [5] 00118         pchl                    ; Return
                          00119
 014E                     00120 Test:
 014E 01 0A01        [10] 00121         lxi     B,10*256+1h
 0151 C5             [11] 00122         push    B
 0152 AF              [4] 00123         xra     A
 0153 F5             [11] 00124         push    PSW
 0154 CD 0100        [17] 00125         call    tarai
                          00126
 014E                     00127         end     Test

Speeding up the 6809 version:

Like the 6800, start with some easy changes, using bsr instead of jsr, moving data two bytes at a time when possible:

Code:

                                  00024 * 49,209,528 cycles after replacing jsr with bsr
                                  00025 * 53,628,345 cycles originally
                                  00026 *
                                  00027
 0100                             00028          org    $100
                                  00029
 0002                             00030 X_Offset equ    2
 0001                             00031 Y_Offset equ    1
 0000                             00032 Z_Offset equ    0
                                  00033
 0100                             00034 tarai
                                  00035
 0002                             00036 Frame    set    2         ; After return address
                                  00037
 0100 A6 63                   [5] 00038          lda    Frame+Y_Offset,S ; Get y
 0102 A1 64                   [5] 00039          cmpa   Frame+X_Offset,S ; Is it >= x?
 0104 2C 2D (0133)            [3] 00040          bge    Return    ; Yes, go return y
                                  00041
 0106 A6 64                   [5] 00042          lda    Frame+X_Offset,S ; Push x - 1
 0108 4A                      [2] 00043          deca
 0109 34 02                   [6] 00044          pshs   A
 0003                             00045 Frame    set    Frame+1
 010B EC 63                   [6] 00046          ldd    Frame+Z_Offset,S ; Push y and z
 010D 34 06                   [7] 00047          pshs   D
 0005                             00048 Frame    set    Frame+2
 010F 8D EF (0100)            [7] 00049          bsr    tarai     ; tarai(x - 1, y, z)
 0002                             00050 Frame    set    Frame-3
                                  00051
 0111 34 02                   [6] 00052          pshs   A         ; Push its value
 0003                             00053 Frame    set    Frame+1
                                  00054
 0113 A6 64                   [5] 00055          lda    Frame+Y_Offset,S ; Push y - 1
 0115 4A                      [2] 00056          deca
 0116 34 02                   [6] 00057          pshs   A
 0004                             00058 Frame    set    Frame+1
 0118 A6 64                   [5] 00059          lda    Frame+Z_Offset,S ; Push z
 011A 34 02                   [6] 00060          pshs   A
 0005                             00061 Frame    set    Frame+1
 011C A6 67                   [5] 00062          lda    Frame+X_Offset,S ; Push x
 011E 34 02                   [6] 00063          pshs   A
 0006                             00064 Frame    set    Frame+1
                                  00065
 0120 8D DE (0100)            [7] 00066          bsr    tarai     ; tarai(y - 1, z, x),
 0003                             00067 Frame    set    Frame-3
                                  00068
 0122 34 02                   [6] 00069          pshs   A         ; Push its value
 0004                             00070 Frame    set    Frame+1
                                  00071
 0124 A6 64                   [5] 00072          lda    Frame+Z_Offset,S ; Push z - 1
 0126 4A                      [2] 00073          deca
 0127 34 02                   [6] 00074          pshs   A
 0005                             00075 Frame    set    Frame+1
 0129 EC 66                   [6] 00076          ldd    Frame+Y_Offset,S ; Push x and y
 012B 34 06                   [7] 00077          pshs   D
 0007                             00078 Frame    set    Frame+2
                                  00079
 012D 8D D1 (0100)            [7] 00080          bsr    tarai     ; tarai(z - 1, x, y)
 0004                             00081 Frame    set    Frame-3
                                  00082
 012F 34 02                   [6] 00083          pshs   A         ; Push its value
 0005                             00084 Frame    set    Frame+1
                                  00085
 0131 8D CD (0100)            [7] 00086          bsr    tarai     ; The final call
 0002                             00087 Frame    set    Frame-3
                                  00088
 0133                             00089 Return
 0133 35 20                   [7] 00090          puls   Y         ; Get return address
                                  00091
 0135 32 63                   [5] 00092          leas   3,S       ; Clean the stack
                                  00093
 0137 6E A4                   [3] 00094          jmp    ,Y        ; Return
                                  00095
 0139                             00096 Test
 0139 CC 010A                 [3] 00097          ldd    #10+1*256
 013C 34 06                   [7] 00098          pshs   D
 013E 4F                      [2] 00099          clra
 013F 34 02                   [6] 00100          pshs   A
 0141 8D BD (0100)            [7] 00101          bsr    tarai
                                  00102
 0139                             00103          end    Test

Stack unwinding had some room to improve, though not as much as on the 6800:

Code:

                                  00024 * 47,803,543 cycles after tail recursion elimination
                                  00025 * 49,209,528 cycles after replacing jsr with bsr
                                  00026 * 53,628,345 cycles originally
                                  00027 *
                                  00028
 0100                             00029          org    $100
                                  00030
 0002                             00031 X_Offset equ    2
 0001                             00032 Y_Offset equ    1
 0000                             00033 Z_Offset equ    0
                                  00034
 0100                             00035 tarai
                                  00036
 0002                             00037 Frame    set    2         ; After return address
                                  00038
 0100 A6 63                   [5] 00039          lda    Frame+Y_Offset,S ; Get y
 0102 A1 64                   [5] 00040          cmpa   Frame+X_Offset,S ; Is it >= x?
 0104 2C 31 (0137)            [3] 00041          bge    Return    ; Yes, go return y
                                  00042
 0106 A6 64                   [5] 00043          lda    Frame+X_Offset,S ; Push x - 1
 0108 4A                      [2] 00044          deca
 0109 34 02                   [6] 00045          pshs   A
 0003                             00046 Frame    set    Frame+1
 010B EC 63                   [6] 00047          ldd    Frame+Z_Offset,S ; Push y and z
 010D 34 06                   [7] 00048          pshs   D
 0005                             00049 Frame    set    Frame+2
 010F 8D EF (0100)            [7] 00050          bsr    tarai     ; tarai(x - 1, y, z)
 0002                             00051 Frame    set    Frame-3
                                  00052
 0111 34 02                   [6] 00053          pshs   A         ; Push its value
 0003                             00054 Frame    set    Frame+1
                                  00055
 0113 A6 64                   [5] 00056          lda    Frame+Y_Offset,S ; Push y - 1
 0115 4A                      [2] 00057          deca
 0116 34 02                   [6] 00058          pshs   A
 0004                             00059 Frame    set    Frame+1
 0118 A6 64                   [5] 00060          lda    Frame+Z_Offset,S ; Push z
 011A 34 02                   [6] 00061          pshs   A
 0005                             00062 Frame    set    Frame+1
 011C A6 67                   [5] 00063          lda    Frame+X_Offset,S ; Push x
 011E 34 02                   [6] 00064          pshs   A
 0006                             00065 Frame    set    Frame+1
                                  00066
 0120 8D DE (0100)            [7] 00067          bsr    tarai     ; tarai(y - 1, z, x),
 0003                             00068 Frame    set    Frame-3
                                  00069
 0122 34 02                   [6] 00070          pshs   A         ; Push its value
 0004                             00071 Frame    set    Frame+1
                                  00072
 0124 A6 64                   [5] 00073          lda    Frame+Z_Offset,S ; Push z - 1
 0126 4A                      [2] 00074          deca
 0127 34 02                   [6] 00075          pshs   A
 0005                             00076 Frame    set    Frame+1
 0129 EC 66                   [6] 00077          ldd    Frame+Y_Offset,S ; Push x and y
 012B 34 06                   [7] 00078          pshs   D
 0007                             00079 Frame    set    Frame+2
                                  00080
 012D 8D D1 (0100)            [7] 00081          bsr    tarai     ; tarai(z - 1, x, y)
 0004                             00082 Frame    set    Frame-3
                                  00083
 012F A7 64                   [5] 00084          sta    Frame+Z_Offset,S ; Replace z value
                                  00085
 0131 35 06                   [7] 00086          puls   D         ; Get first and second values
 0002                             00087 Frame    set    Frame-2
                                  00088
 0133 ED 63                   [6] 00089          std    Frame+Y_Offset,S ; Replace x and y values
                                  00090
 0135 20 C9 (0100)            [3] 00091          bra    tarai     ; The final "call"
                                  00092
 0137                             00093 Return
 0137 35 20                   [7] 00094          puls   Y         ; Get return address
                                  00095
 0139 32 63                   [5] 00096          leas   3,S       ; Clean the stack
                                  00097
 013B 6E A4                   [3] 00098          jmp    ,Y        ; Return
                                  00099
 013D                             00100 Test
 013D CC 010A                 [3] 00101          ldd    #10+1*256
 0140 34 06                   [7] 00102          pshs   D
 0142 4F                      [2] 00103          clra
 0143 34 02                   [6] 00104          pshs   A
 0145 8D B9 (0100)            [7] 00105          bsr    tarai
                                  00106
 013D                             00107          end    Test

Now we get serious...

This step revealed an area where Motorola took a huge step backward with the design of the 6809. The 6800 had some instructions for interacting between the two accumulators such as transfer, add, subtract, compare, etc.

These were removed. In its place was the TFR (transfer) instruction and suggestions to use the new addressing modes.

In this particular case, instead of the CBA (compare accumulators) instruction, Motorola suggested doing:

Code:

    pshs    B
    cmpa    ,S+

which is three bytes bigger and a whopping ten cycles slower. Using a temporary variable is a bit faster.

Code:

                                  00024 * 27,860,317 cycles checking x <= y before calling tarai
                                  00025 * 47,803,543 cycles after tail recursion elimination
                                  00026 * 49,209,528 cycles after replacing jsr with bsr
                                  00027 * 53,628,345 cycles originally
                                  00028 *
                                  00029
 0000                             00030 Tmp      rmb    1
                                  00031
 0100                             00032          org    $100
                                  00033
 0002                             00034 X_Offset equ    2
 0001                             00035 Y_Offset equ    1
 0000                             00036 Z_Offset equ    0
                                  00037
 0100                             00038 tarai
                                  00039
 0002                             00040 Frame    set    2         ; After return address
                                  00041
 0100 A6 63                   [5] 00042          lda    Frame+Y_Offset,S ; Get y
 0102 E6 64                   [5] 00043          ldb    Frame+X_Offset,S ; Get x - 1
 0104 5A                      [2] 00044          decb
 0105 D7 00                   [4] 00045          stb    Tmp
 0107 91 00                   [4] 00046          cmpa   Tmp       ; Is it >= x - 1?
 0109 2C 0A (0115)            [3] 00047          bge    2f        ; Yes, "return value" is y
                                  00048
 010B 34 04                   [6] 00049          pshs   B         ; Push x - 1
 0003                             00050 Frame    set    Frame+1
 010D 34 02                   [6] 00051          pshs   A         ; Push y
 0004                             00052 Frame    set    Frame+1
 010F A6 64                   [5] 00053          lda    Frame+Z_Offset,S ; Push z
 0111 34 02                   [6] 00054          pshs   A
 0005                             00055 Frame    set    Frame+1
 0113 8D EB (0100)            [7] 00056          bsr    tarai     ; tarai(x - 1, y, z)
 0002                             00057 Frame    set    Frame-3
                                  00058
 0115                             00059 2
 0115 34 02                   [6] 00060          pshs   A         ; Push its value
 0003                             00061 Frame    set    Frame+1
                                  00062
 0117 A6 63                   [5] 00063          lda    Frame+Z_Offset,S ; Get z
 0119 E6 64                   [5] 00064          ldb    Frame+Y_Offset,S ; Get y - 1
 011B 5A                      [2] 00065          decb
 011C D7 00                   [4] 00066          stb    Tmp
 011E 91 00                   [4] 00067          cmpa   Tmp       ; Is it >= y - 1?
 0120 2C 0A (012C)            [3] 00068          bge    2f        ; Yes, "return value" is z
                                  00069
 0122 34 04                   [6] 00070          pshs   B         ; Push y - 1
 0004                             00071 Frame    set    Frame+1
 0124 34 02                   [6] 00072          pshs   A         ; Push z
 0005                             00073 Frame    set    Frame+1
 0126 A6 67                   [5] 00074          lda    Frame+X_Offset,S ; Push x
 0128 34 02                   [6] 00075          pshs   A
 0006                             00076 Frame    set    Frame+1
                                  00077
 012A 8D D4 (0100)            [7] 00078          bsr    tarai     ; tarai(y - 1, z, x),
 0003                             00079 Frame    set    Frame-3
                                  00080
 012C                             00081 2
 012C 34 02                   [6] 00082          pshs   A         ; Push its value
 0004                             00083 Frame    set    Frame+1
                                  00084
 012E A6 66                   [5] 00085          lda    Frame+X_Offset,S ; Get x
 0130 E6 64                   [5] 00086          ldb    Frame+Z_Offset,S ; Get z - 1
 0132 5A                      [2] 00087          decb
 0133 D7 00                   [4] 00088          stb    Tmp
 0135 91 00                   [4] 00089          cmpa   Tmp       ; Is it > z?
 0137 2C 0A (0143)            [3] 00090          bge    2f        ; Yes, "return value" is x
                                  00091
 0139 34 04                   [6] 00092          pshs   B         ; Push z - 1
 0005                             00093 Frame    set    Frame+1
 013B 34 02                   [6] 00094          pshs   A         ; Push x
 0006                             00095 Frame    set    Frame+1
 013D A6 67                   [5] 00096          lda    Frame+Y_Offset,S ; Push y
 013F 34 02                   [6] 00097          pshs   A
 0007                             00098 Frame    set    Frame+1
                                  00099
 0141 8D BD (0100)            [7] 00100          bsr    tarai     ; tarai(z - 1, x, y)
 0004                             00101 Frame    set    Frame-3
                                  00102
 0143                             00103 2
 0143 A7 64                   [5] 00104          sta    Frame+Z_Offset,S ; Replace z value
                                  00105
 0145 35 02                   [6] 00106          puls   A         ; Get second value
 0003                             00107 Frame    set    Frame-1
                                  00108
 0147 A1 E4                   [4] 00109          cmpa   ,S        ; Is it >= first value?
 0149 2C 06 (0151)            [3] 00110          bge    Return    ; Yes, "return value" is the second value
                                  00111
 014B 35 04                   [6] 00112          puls   B         ; Get first value
 0002                             00113 Frame    set    Frame-1
 014D ED 63                   [6] 00114          std    Frame+Y_Offset,S ; Replace x and y values
                                  00115
 014F 20 AF (0100)            [3] 00116          bra    tarai     ; The final "call"
                                  00117
 0151                             00118 Return
 0151 35 04                   [6] 00119          puls   B         ; Get rid of first value
                                  00120
 0153 35 20                   [7] 00121          puls   Y         ; Get return address
                                  00122
 0155 32 63                   [5] 00123          leas   3,S       ; Clean the stack
                                  00124
 0157 6E A4                   [3] 00125          jmp    ,Y        ; Return
                                  00126
 0159                             00127 Test
 0159 CC 010A                 [3] 00128          ldd    #10+1*256
 015C 34 06                   [7] 00129          pshs   D
 015E 4F                      [2] 00130          clra
 015F 34 02                   [6] 00131          pshs   A
 0161 8D 9D (0100)            [7] 00132          bsr    tarai
                                  00133
 0159                             00134          end    Test

And the nuclear option:

Code:

                                  00024 *      5,926 cycles checking x <= y after tarai(x - 1, ...) and (y - 1, ...)
                                  00025 * 27,860,317 cycles checking x <= y before calling tarai
                                  00026 * 47,803,543 cycles after tail recursion elimination
                                  00027 * 49,209,528 cycles after replacing jsr with bsr
                                  00028 * 53,628,345 cycles originally
                                  00029 *
                                  00030
 0000                             00031 Tmp      rmb    1
                                  00032
 0100                             00033          org    $100
                                  00034
 0002                             00035 X_Offset equ    2
 0001                             00036 Y_Offset equ    1
 0000                             00037 Z_Offset equ    0
                                  00038
 0100                             00039 tarai
                                  00040
 0002                             00041 Frame    set    2         ; After return address
                                  00042
 0100 A6 63                   [5] 00043          lda    Frame+Y_Offset,S ; Get y
 0102 E6 64                   [5] 00044          ldb    Frame+X_Offset,S ; Get x - 1
 0104 5A                      [2] 00045          decb
 0105 D7 00                   [4] 00046          stb    Tmp
 0107 91 00                   [4] 00047          cmpa   Tmp       ; Is it >= x - 1?
 0109 2C 0A (0115)            [3] 00048          bge    2f        ; Yes, "return value" is y
                                  00049
 010B 34 04                   [6] 00050          pshs   B         ; Push x - 1
 0003                             00051 Frame    set    Frame+1
 010D 34 02                   [6] 00052          pshs   A         ; Push y
 0004                             00053 Frame    set    Frame+1
 010F A6 64                   [5] 00054          lda    Frame+Z_Offset,S ; Push z
 0111 34 02                   [6] 00055          pshs   A
 0005                             00056 Frame    set    Frame+1
 0113 8D EB (0100)            [7] 00057          bsr    tarai     ; tarai(x - 1, y, z)
 0002                             00058 Frame    set    Frame-3
                                  00059
 0115                             00060 2
 0115 34 02                   [6] 00061          pshs   A         ; Push its value
 0003                             00062 Frame    set    Frame+1
                                  00063
 0117 A6 63                   [5] 00064          lda    Frame+Z_Offset,S ; Get z
 0119 E6 64                   [5] 00065          ldb    Frame+Y_Offset,S ; Get y - 1
 011B 5A                      [2] 00066          decb
 011C D7 00                   [4] 00067          stb    Tmp
 011E 91 00                   [4] 00068          cmpa   Tmp       ; Is it >= y - 1?
 0120 2C 0A (012C)            [3] 00069          bge    2f        ; Yes, "return value" is z
                                  00070
 0122 34 04                   [6] 00071          pshs   B         ; Push y - 1
 0004                             00072 Frame    set    Frame+1
 0124 34 02                   [6] 00073          pshs   A         ; Push z
 0005                             00074 Frame    set    Frame+1
 0126 A6 67                   [5] 00075          lda    Frame+X_Offset,S ; Push x
 0128 34 02                   [6] 00076          pshs   A
 0006                             00077 Frame    set    Frame+1
                                  00078
 012A 8D D4 (0100)            [7] 00079          bsr    tarai     ; tarai(y - 1, z, x),
 0003                             00080 Frame    set    Frame-3
                                  00081
 012C                             00082 2
 012C A1 E4                   [4] 00083          cmpa   ,S        ; Is it >= first value?
 012E 2C 1F (014F)            [3] 00084          bge    Return    ; Yes, "return value" is the second value
                                  00085
 0130 34 02                   [6] 00086          pshs   A         ; Push its value
 0004                             00087 Frame    set    Frame+1
                                  00088
 0132 A6 66                   [5] 00089          lda    Frame+X_Offset,S ; Get x
 0134 E6 64                   [5] 00090          ldb    Frame+Z_Offset,S ; Get z - 1
 0136 5A                      [2] 00091          decb
 0137 D7 00                   [4] 00092          stb    Tmp
 0139 91 00                   [4] 00093          cmpa   Tmp       ; Is it > z?
 013B 2C 0A (0147)            [3] 00094          bge    2f        ; Yes, "return value" is x
                                  00095
 013D 34 04                   [6] 00096          pshs   B         ; Push z - 1
 0005                             00097 Frame    set    Frame+1
 013F 34 02                   [6] 00098          pshs   A         ; Push x
 0006                             00099 Frame    set    Frame+1
 0141 A6 67                   [5] 00100          lda    Frame+Y_Offset,S ; Push y
 0143 34 02                   [6] 00101          pshs   A
 0007                             00102 Frame    set    Frame+1
                                  00103
 0145 8D B9 (0100)            [7] 00104          bsr    tarai     ; tarai(z - 1, x, y)
 0004                             00105 Frame    set    Frame-3
                                  00106
 0147                             00107 2
 0147 A7 64                   [5] 00108          sta    Frame+Z_Offset,S ; Replace z value
                                  00109
 0149 35 06                   [7] 00110          puls   D         ; Get first and second values
 0002                             00111 Frame    set    Frame-2
                                  00112
 014B ED 63                   [6] 00113          std    Frame+Y_Offset,S ; Replace x and y values
                                  00114
 014D 20 B1 (0100)            [3] 00115          bra    tarai     ; The final "call"
                                  00116
 014F                             00117 Return
 014F 35 04                   [6] 00118          puls   B         ; Get rid of first value
                                  00119
 0151 35 20                   [7] 00120          puls   Y         ; Get return address
                                  00121
 0153 32 63                   [5] 00122          leas   3,S       ; Clean the stack
                                  00123
 0155 6E A4                   [3] 00124          jmp    ,Y        ; Return
                                  00125
 0157                             00126 Test
 0157 CC 010A                 [3] 00127          ldd    #10+1*256
 015A 34 06                   [7] 00128          pshs   D
 015C 4F                      [2] 00129          clra
 015D 34 02                   [6] 00130          pshs   A
 015F 8D 9F (0100)            [7] 00131          bsr    tarai
                                  00132
 0157                             00133          end    Test

Top

Page 5 of 11

[ 163 posts ]

Go to page Previous 1, 2, 3, 4, 5, 6, 7, 8 ... 11 Next

Board index » 6502.org Users Forum » General Discussions

All times are UTC

Who is online

Users browsing this forum: Google [Bot] and 28 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum