|
|}
|}
=== Assembly language ===
No attempt is made to optimize the lookup in coding for this first example (for [[IBM/360]] maximum 16Mb address range or [[Z/Architecture]]), and it uses instead a simple [[linear search]] technique – purely to illustrate the concept and demonstrate fewer source lines. To handle all 256 different input values, approximately 265 lines of source code would be required (mainly single line table entries) whereas multiple 'compare and branch' would have normally required around 512 source lines (the size of the [[binary file|binary]] is also approximately halved, each table entry requiring only 4 bytes instead of approximately 8 bytes for a series of 'compare immediate'/branch instructions (For larger input variables, the saving is even greater).
* ------------------ interpreter --------------------------------------------*
LM R14,R0,=A(4,CT1,N) Set R14=4, R15 --> table, and R0 =no. of entries in table (N)
TRY CLC INPUT1,0(R15) ********* Found value in table entry ?
BE ACTION * loop * YES, Load register pointer to sub-routine from table
AR R15,R14 * * NO, Point to next entry in CT1 by adding R14 (=4)
BCT R0,TRY ********* Back until count exhausted, then drop through
. default action ... none of the values in table match, do something else
LA R15,4(R15) point to default entry (beyond table end)
ACTION L R15,0(R15) get pointer into R15,from where R15 points
BALR R14,R15 Perform the sub-routine ("CALL" and return)
B END go terminate this program
* ------------------ control table -----------------------------------------*
* | this column of allowable EBCDIC or ASCII values is tested '=' against variable 'input1'
* | | this column is the 3-byte address of the appropriate subroutine
* v v
'''CT1''' DC C'A',AL3(ADD) START of Control Table (4 byte entry length)
DC C'S',AL3(SUBTRACT)
DC C'M',AL3(MULTIPLY)
DC C'D',AL3(DIVIDE)
N EQU (*-CT1)/4 number of valid entries in table (total length / entry length)
DC C'?',AL3(DEFAULT) default entry – used on drop through to catch all
INPUT1 DS C input variable is in this variable
* ------------------ sub-routines ------------------------------------------*
ADD CSECT sub-routine #1 (shown as separate CSECT here but might
. alternatively be in-line code)
. instruction(s) to add
BR R14 return
SUBTRACT CSECT sub-routine #2
. instruction(s) to subtract
BR R14 return
. etc..
'''improving the performance of the interpreter in above example '''
:To make a selection in the example above, the average [[instruction path length]] (excluding the subroutine code) is '4n/2 +3', but can easily be reduced, where n = 1 to 64, to a [[Linear time|constant time]] <math>O(1)\,</math> with a path length of '5' with ''zero comparisons'', if a 256 byte translate table is first utilized to create a ''direct'' index to CT1 from the raw EBCDIC data. Where n = 6, this would then be equivalent to just 3 sequential compare & branch instructions. However, where n<=64, on average it would need approximately 13 ''times'' less instructions than using multiple compares. Where n=1 to 256, on average it would use approximately 42 ''times'' less instructions – since, in this case, one additional instruction would be required (to multiply the index by 4).
'''Improved interpreter''' (up to '''26 times less executed instructions''' than the above example on average, where n= 1 to 64 and up to 13 times less than would be needed using multiple comparisons).
To handle 64 different input values, approximately 85 lines of source code (or less) are required (mainly single line table entries) whereas multiple 'compare and branch' would require around 128 lines (the size of the [[binary file|binary]] is also almost halved – despite the additional 256 byte table required to extract the 2nd index).
* ------------------ interpreter --------------------------------------------*
SR R14,R14 ********* Set R14=0
CALC IC R14,INPUT1 * calc * put EBCDIC byte into lo order bits (24–31) of R14
IC R14,CT1X(R14) * * use EBCDIC value as index on table 'CT1X' to get new index
FOUND L R15,CT1(R14) ********* get pointer to subroutine using index (0,4, 8 etc.)
BALR R14,R15 Perform the sub-routine ("CALL" and return or Default)
B END go terminate this program
* --------------- additional translate table (EBCDIC --> pointer table INDEX) 256 bytes----*
CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 identical sets of 16 bytes of x'00
* representing X'00 – x'BF'
DC AL1(00,'''04''',00,00,'''16''',00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF'
DC AL1(00,00,00,00,'''12''',00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF'
DC AL1(00,00,'''08''',00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF'
DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF'
* the assembler can be used to automatically calculate the index values and make the values more user friendly
* (for e.g. '04' could be replaced with the symbolic expression 'PADD-CT1' in table CT1X above)
* modified CT1 (added a default action when index = 00, single dimension, full 31 bit address)
'''CT1''' DC A(DEFAULT) index =00 START of Control Table (4 byte address constants)
PADD DC A(ADD) =04
PSUB DC A(SUBTRACT) =08
PMUL DC A(MULTIPLY) =12
PDIV DC A(DIVIDE) =16
* the rest of the code remains the same as first example
'''Further improved interpreter''' (up to '''21 times less executed instructions (where n>=64)''' than the first example on average and up to 42 ''times'' less than would be needed using multiple comparisons).
To handle 256 different input values, approximately 280 lines of source code or less, would be required (mainly single line table entries), whereas multiple 'compare and branch' would require around 512 lines (the size of the [[binary file|binary]] is also almost halved once more).
* ------------------ interpreter --------------------------------------------*
SR R14,R14 ********* Set R14=0
CALC IC R14,INPUT1 * calc * put EBCDIC byte into lo order bits (24–31) of R14
IC R14,CT1X(R14) * * use EBCDIC value as index on table 'CT1X' to get new index
SLL R14,2 * * '''multiply index by 4 (additional instruction)'''
FOUND L R15,CT1(R14) ********* get pointer to subroutine using index (0,4, 8 etc.)
BALR R14,R15 Perform the sub-routine ("CALL" and return or Default)
B END go terminate this program
* --------------- additional translate table (EBCDIC --> pointer table INDEX) 256 bytes----*
CT1X DC 12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 identical sets of 16 bytes of x'00'
* representing X'00 – x'BF'
DC AL1(00,'''01''',00,00,'''04''',00,00,00,00,00,00,00,00,00,00,00) ..x'C0' – X'CF'
DC AL1(00,00,00,00,'''03''',00,00,00,00,00,00,00,00,00,00,00) ..x'D0' – X'DF'
DC AL1(00,00,'''02''',00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'E0' – X'EF'
DC AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00) ..x'F0' – X'FF'
* the assembler can be used to automatically calculate the index values and make the values more user friendly
* (for e.g. '01' could be replaced with the symbolic expression 'PADD-CT1/4' in table CT1X above)
* modified CT1 (index now based on 0,1,2,3,4 not 0,4,8,12,16 to allow all 256 variations)
'''CT1''' DC A(DEFAULT) index =00 START of Control Table (4 byte address constants)
PADD DC A(ADD) =01
PSUB DC A(SUBTRACT) =02
PMUL DC A(MULTIPLY) =03
PDIV DC A(DIVIDE) =04
* the rest of the code remains the same as the 2nd example
=== C language ===
|
