[Chapter Twenty-Five][Previous] [Art of Assembly][Randall Hyde]

Art of Assembly: Chapter Twenty-Five


25.5 - Improving the Implementation of an Algorithm

25.5 Improving the Implementation of an Algorithm


One easy way to partially demonstrate how to optimize a piece of code is to provide an example of some program and the optimization steps you can apply to that program. This section will present a short program that blurs an eight-bit gray scale image. Then, this section will lead though through several optimization steps and show you how to get that program running over 16 times faster.

The following code assumes that you provide it with a file containing a 251x256 gray scale photographic image. The data structure for this file is as follows:








	Image: array [0..250, 0..255] of byte;

Each byte contains a value in the range 0..255 with zero denoting black, 255 representing white, and the other values representing even shades of gray between these two extremes.

The blurring algorithm averages a pixel with its eight closest neighbors. A single blur operation applies this average to all interior pixels of an image (that is, it does not apply to the pixels on the boundary of the image because they do not have the same number of neighbors as the other pixels). The following Pascal program implements the blurring algorithm and lets the user specify the amount of blurring (by looping through the algorithm the number of times the user specifies):









program PhotoFilter(input,output);

(* Here is the raw file data type produced by the Photoshop program *)

type
 image = array [0..250] of array [0..255] of byte;

(* The variables we will use. Note that the "datain" and "dataout" *)
(* variables are pointers because Turbo Pascal will not allow us to *)
(* allocate more than 64K data in the one global data segment it *)
(* supports. *)

var
 h,i,j,k,l,sum,iterations:integer;
 datain, dataout: ^image;
 f,g:file of image;

begin

 (* Open the files and real the input data *)

 assign(f, 'roller1.raw');
 assign(g, 'roller2.raw');
 reset(f);
 rewrite(g);
 new(datain);
 new(dataout);
 read(f,datain^);

 (* Get the number of iterations from the user *)

 write('Enter number of iterations:');
 readln(iterations);

 writeln('Computing result');

 (* Copy the data from the input array to the output array. *)
 (* This is a really lame way to copy the border from the *)
 (* input array to the output array. *)

 for i := 0 to 250 do
        for j := 0 to 255 do
                dataout^ [i][j] := datain^ [i][j];

 (* Okay, here's where all the work takes place. The outside                                                            *)
 (* loop repeats this blurring operation the number of                                                          *)
 (* iterations specified by the user.                                                           *)

 for h := 1 to iterations do begin

        (* For each row except the first and the last, compute                                                  *)
        (* a new value for each element.                                                        *)

        for i := 1 to 249 do

                (* For each column except the first and the last, com-                                                  *)
                (* pute a new value for each element.                                                   *)

                for j := 1 to 254 do begin

                        (* For each element in the array, compute a new
                           blurred value by adding up the eight cells
                           around an array element along with eight times
                           the current cell's value. Then divide this by
                           sixteen to compute a weighted average of the
                           nine cells forming a square around the current
                           cell. The current cell has a 50% weighting,
                           the other eight cells around the current cel
                           provide the other 50% weighting (6.25% each). *)

                        sum := 0;
                        for k := -1 to 1 do
                            for l := -1 to 1 do
                                sum := sum + datain^ [i+k][j+l];

                        (* Sum currently contains the sum of the nine     *)
                        (* cells, add in seven times the current cell so  *)
                        (* we get a total of eight times the current cell. *)

                        dataout^ [i][j] := (sum + datain^ [i][j]*7) div 16;

                end;

                (* Copy the output cell values back to the input cells                                                  *)
                (* so we can perform the blurring on this new data on                                                   *)
                (* the next iteration.                                                  *)

                for i := 0 to 250 do
                    for j := 0 to 255 do
                        datain^ [i][j] := dataout^ [i][j];

 end;

 writeln('Writing result');
 write(g,dataout^);
 close(f);
 close(g);

end.

The Pascal program above, compiled with Turbo Pascal v7.0, takes 45 seconds to compute 100 iterations of the blurring algorithm. A comparable program written in C and compiled with Borland C++ v4.02 takes 29 seconds to run. The same source file compiled with Microsoft C++ v8.00 runs in 21 seconds. Obviously the C compilers produce better code than Turbo Pascal. It took about three hours to get the Pascal version running and tested. The C versions took about another hour to code and test. The following two images provide a "before" and "after" example of this program's function:

Before blurring:

After blurring (10 iterations):

The following is a crude translation from Pascal directly into assembly language of the above program. It requires 36 seconds to run. Yes, the C compilers did a better job, but once you see how bad this code is, you'll wonder what it is that Turbo Pascal is doing to run so slow. It took about an hour to translate the Pascal version into this assembly code and debug it to the point it produced the same output as the Pascal version.









; IMGPRCS.ASM
;
; An image processing program.
;
; This program blurs an eight-bit grayscale image by averaging a pixel
; in the image with the eight pixels around it. The average is computed
; by (CurCell*8 + other 8 cells)/16, weighting the current cell by 50%.
;
; Because of the size of the image (almost 64K), the input and output
; matrices are in different segments.
;
; Version #1: Straight-forward translation from Pascal to Assembly.
;
;       Performance comparisons (66 MHz 80486 DX/2 system).
;
;       This code-                              36 seconds.
;       Borland Pascal v7.0-                    45 seconds.
;       Borland C++ v4.02-                      29 seconds.
;       Microsoft C++ v8.00-                    21 seconds.

                .xlist
                include         stdlib.a
                includelib      stdlib.lib
                .list
                .286

dseg            segment para public 'data'

; Loop control variables and other variables:

h               word    ?
i               word    ?
j               word    ?
k               word    ?
l               word    ?
sum             word    ?
iterations      word    ?

; File names:

InName          byte    "roller1.raw",0
OutName         byte    "roller2.raw",0

dseg            ends


; Here is the input data that we operate on.

InSeg           segment para public 'indata'

DataIn          byte    251 dup (256 dup (?))

InSeg           ends


; Here is the output array that holds the result.

OutSeg          segment para public 'outdata'

DataOut         byte    251 dup (256 dup (?))

OutSeg          ends




cseg            segment para public 'code'
                assume  cs:cseg, ds:dseg

Main            proc
                mov     ax, dseg
                mov     ds, ax
                meminit

                mov     ax, 3d00h               ;Open input file for reading.
                lea     dx, InName
                int     21h
                jnc     GoodOpen
                print
                byte    "Could not open input file.",cr,lf,0
                jmp     Quit

GoodOpen:       mov     bx, ax                  ;File handle.
                mov     dx, InSeg               ;Where to put the data.
                mov     ds, dx
                lea     dx, DataIn
                mov     cx, 256*251             ;Size of data file to read.
                mov     ah, 3Fh
                int     21h
                cmp     ax, 256*251             ;See if we read the data.
                je      GoodRead
                print
                byte    "Did not read the file properly",cr,lf,0
                jmp     Quit

GoodRead:       mov     ax, dseg
                mov     ds, ax
                print
                byte    "Enter number of iterations: ",0
                getsm
                atoi
                free
                mov     iterations, ax
                print
                byte    "Computing Result",cr,lf,0

; Copy the input data to the output buffer.

                mov     i, 0
iloop0:         cmp     i, 250
                ja      iDone0
                mov     j, 0
jloop0:         cmp     j, 255
                ja      jDone0

                mov     bx, i                   ;Compute index into both
                shl     bx, 8                   ; arrays using the formula
                add     bx, j                   ; i*256+j (row major).

                mov     cx, InSeg               ;Point at input segment.
                mov     es, cx
                mov     al, es:DataIn[bx]       ;Get DataIn[i][j].

                mov     cx, OutSeg              ;Point at output segment.
                mov     es, cx
                mov     es:DataOut[bx], al      ;Store into DataOut[i][j]

                inc     j                       ;Next iteration of j loop.
                jmp     jloop0

jDone0:         inc     i                       ;Next iteration of i loop.
                jmp     iloop0

iDone0:

; for h := 1 to iterations-

                mov     h, 1
hloop:          mov     ax, h
                cmp     ax, iterations
                ja      hloopDone



; for i := 1 to 249 -

                mov     i, 1
iloop:          cmp     i, 249
                ja      iloopDone

; for j := 1 to 254 -
                mov     j, 1
jloop:          cmp     j, 254
                ja      jloopDone


; sum := 0;
; for k := -1 to 1 do for l := -1 to 1 do

                mov     ax, InSeg               ;Gain access to InSeg.
                mov     es, ax

                mov     sum, 0
                mov     k, -1
kloop:          cmp     k, 1
                jg      kloopDone

                mov     l, -1
lloop:          cmp     l, 1
                jg      lloopDone

; sum := sum + datain [i+k][j+l]

                mov     bx, i
                add     bx, k
                shl     bx, 8                   ;Multiply by 256.
                add     bx, j
                add     bx, l

                mov     al, es:DataIn[bx]
                mov     ah, 0
                add     Sum, ax

                inc     l
                jmp     lloop

lloopDone:      inc     k
                jmp     kloop


; dataout [i][j] := (sum + datain[i][j]*7) div 16;

kloopDone:      mov     bx, i
                shl     bx, 8                   ;*256
                add     bx, j
                mov     al, es:DataIn[bx]
                mov     ah, 0
                imul    ax, 7
                add     ax, sum
                shr     ax, 4                   ;div 16

                mov     bx, OutSeg
                mov     es, bx

                mov     bx, i
                shl     bx, 8
                add     bx, j
                mov     es:DataOut[bx], al

                inc     j
                jmp     jloop

jloopDone:              inc     i
                jmp     iloop

iloopDone:
; Copy the output data to the input buffer.

                mov     i, 0
iloop1:         cmp     i, 250
                ja      iDone1
                mov     j, 0
jloop1:         cmp     j, 255
                ja      jDone1

                mov     bx, i                   ;Compute index into both
                shl     bx, 8                   ; arrays using the formula
                add     bx, j                   ; i*256+j (row major).

                mov     cx, OutSeg              ;Point at input segment.
                mov     es, cx
                mov     al, es:DataOut[bx]      ;Get DataIn[i][j].

                mov     cx, InSeg               ;Point at output segment.
                mov     es, cx
                mov     es:DataIn[bx], al       ;Store into DataOut[i][j]

                inc     j                       ;Next iteration of j loop.
                jmp     jloop1

jDone1:         inc     i                       ;Next iteration of i loop.
                jmp     iloop1

iDone1:         inc     h
                jmp     hloop

hloopDone:      print
                byte    "Writing result",cr,lf,0


; Okay, write the data to the output file:

                mov     ah, 3ch         ;Create output file.
                mov     cx, 0           ;Normal file attributes.
                lea     dx, OutName
                int     21h
                jnc     GoodCreate
                print
                byte    "Could not create output file.",cr,lf,0
                jmp     Quit

GoodCreate:     mov     bx, ax          ;File handle.
                push    bx
                mov     dx, OutSeg      ;Where the data can be found.
                mov     ds, dx
                lea     dx, DataOut
                mov     cx, 256*251     ;Size of data file to write.
                mov     ah, 40h         ;Write operation.
                int     21h
                pop     bx              ;Retrieve handle for close.
                cmp     ax, 256*251     ;See if we wrote the data.
                je      GoodWrite
                print
                byte    "Did not write the file properly",cr,lf,0
                jmp     Quit

GoodWrite:      mov     ah, 3eh         ;Close operation.
                int     21h


Quit:           ExitPgm                 ;DOS macro to quit program.
Main            endp

cseg            ends

sseg            segment para stack 'stack'
stk             byte    1024 dup ("stack ")
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       byte    16 dup (?)
zzzzzzseg       ends
                end     Main

This assembly code is a very straight-forward, line by line translation of the previous Pascal code. Even beginning programmers (who've read and understand Chapters Eight and Nine) should easily be able to improve the performance of this code.

While we could run a profiler on this program to determine where the "hot spots" are in this code, a little analysis, particularly of the Pascal version, should make it obvious that there are a lot of nested loops in this code. As Chapter Ten points out, when optimizing code you should always start with the innermost loops. The major change between the code above and the following assembly language version is that we've unrolled the innermost loops and we've replaced the array index computations with some constant computations. These minor changes speed up the execution by a factor of six! The assembly version now runs in six seconds rather than 36. A Microsoft C++ version of the same program with comparable optimzations runs in eight seconds. It required nearly four hours to develop, test, and debug this code. It required an additional hour to apply these same modifications to the C version.









; IMGPRCS2.ASM
;
; An image processing program (First optimization pass).
;
; This program blurs an eight-bit grayscale image by averaging a pixel
; in the image with the eight pixels around it. The average is computed
; by (CurCell*8 + other 8 cells)/16, weighting the current cell by 50%.
;
; Because of the size of the image (almost 64K), the input and output
; matrices are in different segments.
;
; Version #1: Straight-forward translation from Pascal to Assembly.
; Version #2: Three major optimizations. (1) used movsd instruction rather
;        than a loop to copy data from DataOut back to DataIn.
;        (2) Used repeat..until forms for all loops. (3) unrolled
;        the innermost two loops (which is responsible for most of
;        the performance improvement).
;
;
;       Performance comparisons (66 MHz 80486 DX/2 system).
;
;       This code-                              6 seconds.
;       Original ASM code-                      36 seconds.
;       Borland Pascal v7.0-                    45 seconds.
;       Borland C++ v4.02-                      29 seconds.
;       Microsoft C++ v8.00-                    21 seconds.


;       // Lots of omitted code goes here, see the previous version//


                print
                byte    "Computing Result",cr,lf,0

; for h := 1 to iterations-

                mov     h, 1
hloop:

; Copy the input data to the output buffer.
; Optimization step #1: Replace with movs instruction.

                push    ds
                mov     ax, OutSeg
                mov     ds, ax
                mov     ax, InSeg
                mov     es, ax
                lea     si, DataOut
                lea     di, DataIn
                mov     cx, (251*256)/4
        rep     movsd
                pop     ds


; Optimization Step #1: Convert loops to repeat..until form.

; for i := 1 to 249 -

                mov     i, 1
iloop:

; for j := 1 to 254 -

                mov     j, 1
jloop:


; Optimization. Unroll the innermost two loops:

                mov     bh, byte ptr i          ;i is always less than 256.
                mov     bl, byte ptr j          ;Computes i*256+j!

                push    ds
                mov     ax, InSeg               ;Gain access to InSeg.
                mov     ds, ax

                mov     cx, 0                   ;Compute sum here.
                mov     ah, ch
                mov     cl, ds:DataIn[bx-257]   ;DataIn[i-1][j-1]
                mov     al, ds:DataIn[bx-256]   ;DataIn[i-1][j]
                add     cx, ax
                mov     al, ds:DataIn[bx-255]   ;DataIn[i-1][j+1]
                add     cx, ax
                mov     al, ds:DataIn[bx-1]     ;DataIn[i][j-1]
                add     cx, ax
                mov     al, ds:DataIn[bx+1]     ;DataIn[i][j+1]
                add     cx, ax
                mov     al, ds:DataIn[bx+255]   ;DataIn[i+1][j-1]
                add     cx, ax
                mov     al, ds:DataIn[bx+256]   ;DataIn[i+1][j]
                add     cx, ax
                mov     al, ds:DataIn[bx+257]   ;DataIn[i+1][j+1]
                add     cx, ax

                mov     al, ds:DataIn[bx]       ;DataIn[i][j]
                shl     ax, 3                   ;DataIn[i][j]*8
                add     cx, ax
                shr     cx, 4                   ;Divide by 16
                mov     ax, OutSeg
                mov     ds, ax
                mov     ds:DataOut[bx], cl
                pop     ds

                inc     j
                cmp     j, 254
                jbe     jloop

                inc     i
                cmp     i, 249
                jbe     iloop

                inc     h
                mov     ax, h
                cmp     ax, Iterations
                jnbe    Done
                jmp     hloop

Done:           print
                byte    "Writing result",cr,lf,0

;       //More omitted code goes here, see the previous version//


The second version above still uses memory variables for most computations. The optimizations applied to the original code were mainly language-independent optimizations. The next step was to begin applying some assembly language specific optimizations to the code. The first optimization we need to do is to move as many variables as possible into the 80x86's register set. The following code provides this optimization. Although this only improves the running time by 2 seconds, that is a 33% improvement (six seconds down to four)!









; IMGPRCS.ASM
;
; An image processing program (Second optimization pass).
;
; This program blurs an eight-bit grayscale image by averaging a pixel
; in the image with the eight pixels around it. The average is computed
; by (CurCell*8 + other 8 cells)/16, weighting the current cell by 50%.
;
; Because of the size of the image (almost 64K), the input and output
; matrices are in different segments.
;
; Version #1: Straight-forward translation from Pascal to Assembly.
; Version #2: Three major optimizations. (1) used movsd instruction rather
;        than a loop to copy data from DataOut back to DataIn.
;        (2) Used repeat..until forms for all loops. (3) unrolled
;        the innermost two loops (which is responsible for most of
;        the performance improvement).
; Version #3: Used registers for all variables. Set up segment registers
;        once and for all through the execution of the main loop so
;        the code didn't have to reload ds each time through. Computed
;        index into each row only once (outside the j loop).
;
;
;       Performance comparisons (66 MHz 80486 DX/2 system).
;
;       This code-                              4 seconds.
;       1st optimization pass-                  6 seconds.
;       Original ASM code-                      36 seconds.


;       <<Lots of delete code goes here»

                print
                byte    "Computing Result",cr,lf,0


; Copy the input data to the output buffer.


hloop:          mov     ax, InSeg
                mov     es, ax
                mov     ax, OutSeg
                mov     ds, ax
                lea     si, DataOut
                lea     di, DataIn
                mov     cx, (251*256)/4
        rep     movsd

                assume  ds:InSeg, es:OutSeg
                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax



                mov     cl, 249
iloop:          mov     bh, cl                  ;i*256
                mov     bl, 1                   ;Start at j=1.
                mov     ch, 254                 ;# of times through loop.
jloop:
                mov     dx, 0                   ;Compute sum here.
                mov     ah, dh
                mov     dl, DataIn[bx-257]      ;DataIn[i-1][j-1]
                mov     al, DataIn[bx-256]      ;DataIn[i-1][j]
                add     dx, ax
                mov     al, DataIn[bx-255]      ;DataIn[i-1][j+1]
                add     dx, ax
                mov     al, DataIn[bx-1]        ;DataIn[i][j-1]
                add     dx, ax
                mov     al, DataIn[bx+1]        ;DataIn[i][j+1]
                add     dx, ax
                mov     al, DataIn[bx+255]      ;DataIn[i+1][j-1]
                add     dx, ax
                mov     al, DataIn[bx+256]      ;DataIn[i+1][j]
                add     dx, ax
                mov     al, DataIn[bx+257]      ;DataIn[i+1][j+1]
                add     dx, ax

                mov     al, DataIn[bx]          ;DataIn[i][j]
                shl     ax, 3                   ;DataIn[i][j]*8
                add     dx, ax
                shr     dx, 4                   ;Divide by 16
                mov     DataOut[bx], dl

                inc     bx
                dec     ch
                jne     jloop

                dec     cl
                jne     iloop

                dec     bp
                jne     hloop

Done:           print
                byte    "Writing result",cr,lf,0

;       //More deleted code goes here, see the original version//

Note that on each iteration, the code above still copies the output data back to the input data. That's almost six and a half megabytes of data movement for 100 iterations! The following version of the blurring program unrolls the hloop twice. The first occurrence copies the data from DataIn to DataOut while computing the blur, the second instance copies the data from DataOut back to DataIn while blurring the image. By using these two code sequences, the program save copying the data from one point to another. This version also maintains some common computations between two adjacent cells to save a few instructions in the innermost loop. This version arranges instructions in the innermost loop to help avoid data hazards on 80486 and later processors. The end result is almost 40% faster than the previous version (down to 2.5 seconds from four seconds).









; IMGPRCS.ASM
;
; An image processing program (Third optimization pass).
;
; This program blurs an eight-bit grayscale image by averaging a pixel
; in the image with the eight pixels around it. The average is computed
; by (CurCell*8 + other 8 cells)/16, weighting the current cell by 50%.
;
; Because of the size of the image (almost 64K), the input and output
; matrices are in different segments.
;
; Version #1: Straight-forward translation from Pascal to Assembly.
;
; Version #2: Three major optimizations. (1) used movsd instruction rather
;        than a loop to copy data from DataOut back to DataIn.
;        (2) Used repeat..until forms for all loops. (3) unrolled
;        the innermost two loops (which is responsible for most of
;        the performance improvement).
;
; Version #3: Used registers for all variables. Set up segment registers
;        once and for all through the execution of the main loop so
;        the code didn't have to reload ds each time through. Computed
;        index into each row only once (outside the j loop).
;
; Version #4: Eliminated copying data from DataOut to DataIn on each pass.
;        Removed hazards. Maintained common subexpressions. Did some
;        more loop unrolling.
;
;
;       Performance comparisons (66 MHz 80486 DX/2 system, 100 iterations).
;
;       This code-                              2.5 seconds.
;       2nd optimization pass-                  4 seconds.
;       1st optimization pass-                  6 seconds.
;       Original ASM code-                      36 seconds.

;       <<Lots of deleted code here, see the original version»

                print
                byte    "Computing Result",cr,lf,0


                assume  ds:InSeg, es:OutSeg

                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax

; Copy the data once so we get the edges in both arrays.

                mov     cx, (251*256)/4
                lea     si, DataIn
                lea     di, DataOut
        rep     movsd


; "hloop" repeats once for each iteration.

hloop:
                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax

; "iloop" processes the rows in the matrices.

                mov     cl, 249
iloop:          mov     bh, cl                  ;i*256
                mov     bl, 1                   ;Start at j=1.
                mov     ch, 254/2               ;# of times through loop.
                mov     si, bx
                mov     dh, 0                   ;Compute sum here.
                mov     bh, 0
                mov     ah, 0

; "jloop" processes the individual elements of the array.
; This loop has been unrolled once to allow the two portions to share
; some common computations.

jloop:

; The sum of DataIn [i-1][j] + DataIn[i-1][j+1] + DataIn[i+1][j] +
; DataIn [i+1][j+1] will be used in the second half of this computation.
; So save its value in a register (di) until we need it again.

                mov     dl, DataIn[si-256]      ;[i-1,j]
                mov     al, DataIn[si-255]      ;[i-1,j+1]
                mov     bl, DataIn[si+257]      ;[i+1,j+1]
                add     dx, ax
                mov     al, DataIn[si+256]      ;[I+1,j]
                add     dx, bx
                mov     bl, DataIn[si+1]        ;[i,j+1]
                add     dx, ax
                mov     al, DataIn[si+255]      ;[i+1,j-1]

                mov     di, dx                  ;Save partial result.

                add     dx, bx
                mov     bl, DataIn[si-1]        ;[i,j-1]
                add     dx, ax
                mov     al, DataIn[si]          ;[i,j]
                add     dx, bx
                mov     bl, DataIn[si-257]      ;[i-1,j-1]
                shl     ax, 3                   ;DataIn[i,j] * 8.
                add     dx, bx
                add     dx, ax
                shr     ax, 3                   ;Restore DataIn[i,j].
                shr     dx, 4                   ;Divide by 16.
                add     di, ax
                mov     DataOut[si], dl

; Okay, process the next cell over. Note that we've got a partial sum
; sitting in DI already. Don't forget, we haven't bumped SI at this point,
; so the offsets are off by one. (This is the second half of the unrolled
; loop.)

                mov     dx, di                  ;Partial sum.
                mov     bl, DataIn[si-254]      ;[i-1,j+1]
                mov     al, DataIn[si+2]        ;[i,j+1]
                add     dx, bx
                mov     bl, DataIn[si+258]      ;[i+1,j+1];
                add     dx, ax
                mov     al, DataIn[si+1]        ;[i,j]
                add     dx, bx
                shl     ax, 3                   ;DataIn[i][j]*8
                add     si, 2                   ;Bump array index.
                add     dx, ax
                mov     ah, 0                   ;Clear for next iter.
                shr     dx, 4                   ;Divide by 16
                dec     ch
                mov     DataOut[si-1], dl
                jne     jloop

                dec     cl
                jne     iloop

                dec     bp
                je      Done


; Special case so we don't have to move the data between the two arrays.
; This is an unrolled version of the hloop that swaps the input and output
; arrays so we don't have to move data around in memory.

                mov     ax, OutSeg
                mov     ds, ax
                mov     ax, InSeg
                mov     es, ax
                assume  es:InSeg, ds:OutSeg

hloop2:

                mov     cl, 249
iloop2:         mov     bh, cl
                mov     bl, 1
                mov     ch, 254/2
                mov     si, bx
                mov     dh, 0
                mov     bh, 0
                mov     ah, 0
jloop2:
                mov     dl, DataOut[si-256]
                mov     al, DataOut[si-255]
                mov     bl, DataOut[si+257]
                add     dx, ax
                mov     al, DataOut[si+256]
                add     dx, bx
                mov     bl, DataOut[si+1]
                add     dx, ax
                mov     al, DataOut[si+255]

                mov     di, dx

                add     dx, bx
                mov     bl, DataOut[si-1]
                add     dx, ax
                mov     al, DataOut[si]
                add     dx, bx
                mov     bl, DataOut[si-257]
                shl     ax, 3
                add     dx, bx
                add     dx, ax
                shr     ax, 3
                shr     dx, 4
                mov     DataIn[si], dl

                mov     dx, di
                mov     bl, DataOut[si-254]
                add     dx, ax
                mov     al, DataOut[si+2]
                add     dx, bx
                mov     bl, DataOut[si+258]
                add     dx, ax
                mov     al, DataOut[si+1]
                add     dx, bx
                shl     ax, 3
                add     si, 2
                add     dx, ax
                mov     ah, 0
                shr     dx, 4
                dec     ch
                mov     DataIn[si-1], dl
                jne     jloop2

                dec     cl
                jne     iloop2

                dec     bp
                je      Done2
                jmp     hloop


; Kludge to guarantee that the data always resides in the output segment.

Done2:
                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax
                mov     cx, (251*256)/4
                lea     si, DataIn
                lea     di, DataOut
        rep     movsd

Done:           print
                byte    "Writing result",cr,lf,0

;       //Lots of deleted code here, see the original program//

This code provides a good example of the kind of optimization that scares a lot of people. There is a lot of cycle counting, instruction scheduling, and other crazy stuff that makes program very difficult to read and understand. This is the kind of optimization for which assembly language programmers are famous; the stuff that spawned the phrase "never optimize early." You should never try this type of optimization until you feel you've exhausted all other possibilities. Once you write your code in this fashion, it is going to be very difficult to make further changes to it. By the way, the above code took about 15 hours to develop and debug (debugging took the most time). That works out to a 0.1 second improvement (for 100 iterations) for each hour of work. Although this code certainly isn't optimal yet, it is difficult to justify more time attempting to improve this code by mechanical means (e.g., moving instructions around, etc.) because the performance gains would be so little.

In the four steps above, we've reduced the running time of the assembly code from 36 seconds down to 2.5 seconds. Quite an impressive feat. However, you shouldn't get the idea that this was easy or even that there were only four steps involved. During the actual development of this example, there were many attempts that did not improve performance (in fact, some modifications wound up reducing performance) and others did not improve performance enough to justify their inclusion. Just to demonstrate this last point, the following code included a major change in the way the program organized data. The main loop operates on 16 bit objects in memory rather than eight bit objects. On some machines with large external caches (256K or better) this algorithm provides a slight improvement in performance (2.4 seconds, down from 2.5). However, on other machines it runs slower. Therefore, this code was not chosen as the final implementation:









; IMGPRCS.ASM
;
; An image processing program (Fourth optimization pass).
;
; This program blurs an eight-bit grayscale image by averaging a pixel
; in the image with the eight pixels around it. The average is computed
; by (CurCell*8 + other 8 cells)/16, weighting the current cell by 50%.
;
; Because of the size of the image (almost 64K), the input and output
; matrices are in different segments.
;
; Version #1: Straight-forward translation from Pascal to Assembly.
;
; Version #2: Three major optimizations. (1) used movsd instruction rather
;        than a loop to copy data from DataOut back to DataIn.
;        (2) Used repeat..until forms for all loops. (3) unrolled
;        the innermost two loops (which is responsible for most of
;        the performance improvement).
;
; Version #3: Used registers for all variables. Set up segment registers
;        once and for all through the execution of the main loop so
;        the code didn't have to reload ds each time through. Computed
;        index into each row only once (outside the j loop).
;
; Version #4: Eliminated copying data from DataOut to DataIn on each pass.
;        Removed hazards. Maintained common subexpressions. Did some
;        more loop unrolling.
;
; Version #5: Converted data arrays to words rather than bytes and operated
;        on 16-bit values. Yielded minimal speedup.
;
;       Performance comparisons (66 MHz 80486 DX/2 system).
;
;       This code-                              2.4 seconds.
;       3rd optimization pass-                  2.5 seconds.
;       2nd optimization pass-                  4 seconds.
;       1st optimization pass-                  6 seconds.
;       Original ASM code-                      36 seconds.

                .xlist
                include         stdlib.a
                includelib      stdlib.lib
                .list
                .386
                option          segment:use16



dseg            segment para public 'data'

ImgData         byte    251 dup (256 dup (?))

InName          byte    "roller1.raw",0
OutName         byte    "roller2.raw",0
Iterations      word    0

dseg            ends


; This code makes the naughty assumption that the following
; segments are loaded contiguously in memory! Also, because these
; segments are paragraph aligned, this code assumes that these segments
; will contain a full 65,536 bytes. You cannot declare a segment with
; exactly 65,536 bytes in MASM. However, the paragraph alignment option
; ensures that the extra byte of padding is added to the end of each
; segment.

DataSeg1        segment para public 'ds1'
Data1a          byte    65535 dup (?)
DataSeg1        ends

DataSeg2        segment para public 'ds2'
Data1b          byte    65535 dup (?)
DataSeg2        ends

DataSeg3        segment para public 'ds3'
Data2a          byte    65535 dup (?)
DataSeg3        ends

DataSeg4        segment para public 'ds4'
Data2b          byte    65535 dup (?)
DataSeg4        ends




cseg            segment para public 'code'
                assume  cs:cseg, ds:dseg

Main            proc
                mov     ax, dseg
                mov     ds, ax
                meminit

                mov     ax, 3d00h       ;Open input file for reading.
                lea     dx, InName
                int     21h
                jnc     GoodOpen
                print
                byte    "Could not open input file.",cr,lf,0
                jmp     Quit

GoodOpen:       mov     bx, ax          ;File handle.
                lea     dx, ImgData
                mov     cx, 256*251     ;Size of data file to read.
                mov     ah, 3Fh
                int     21h
                cmp     ax, 256*251     ;See if we read the data.
                je      GoodRead
                print
                byte    "Did not read the file properly",cr,lf,0
                jmp     Quit

GoodRead:       print
                byte    "Enter number of iterations: ",0
                getsm
                atoi
                free
                mov     Iterations, ax
                cmp     ax, 0
                jle     Quit

                printf
                byte    "Computing Result for %d iterations",cr,lf,0
                dword   Iterations



; Copy the data and expand it from eight bits to sixteen bits.
; The first loop handles the first 32,768 bytes, the second loop
; handles the remaining bytes.

                mov     ax, DataSeg1
                mov     es, ax
                mov     ax, DataSeg3
                mov     fs, ax

                mov     ah, 0
                mov     cx, 32768
                lea     si, ImgData
                xor     di, di          ;Output data is at ofs zero.
CopyLoop:       lodsb                   ;Read a byte
                mov     fs:[di], ax     ;Store a word in DataSeg3
                stosw                   ;Store a word in DataSeg1
                dec     cx
                jne     CopyLoop

                mov     di, DataSeg2
                mov     es, di
                mov     di, DataSeg4
                mov     fs, di
                mov     cx, (251*256) - 32768
                xor     di, di
CopyLoop1:      lodsb                   ;Read a byte
                mov     fs:[di], ax     ;Store a word in DataSeg4
                stosw                   ;Store a word in DataSeg2
                dec     cx
                jne     CopyLoop1

; hloop completes one iteration on the data moving it from Data1a/Data1b
; to Data2a/Data2b

hloop:          mov     ax, DataSeg1
                mov     ds, ax
                mov     ax, DataSeg3
                mov     es, ax

; Process the first 127 rows (65,024 bytes) of the array):

                mov     cl, 127
                lea     si, Data1a+202h ;Start at [1,1]
iloop0:         mov     ch, 254/2       ;# of times through loop.
jloop0:         mov     dx, [si]        ;[i,j]
                mov     bx, [si-200h]   ;[i-1,j]
                mov     ax, dx
                shl     dx, 3           ;[i,j] * 8
                add     bx, [si-1feh]   ;[i-1,j+1]
                mov     bp, [si+2]      ;[i,j+1]
                add     bx, [si+200h]   ;[i+1,j]
                add     dx, bp
                add     bx, [si+202h]   ;[i+1,j+1]
                add     dx, [si-202h]   ;[i-1,j-1]
                mov     di, [si-1fch]   ;[i-1,j+2]
                add     dx, [si-2]      ;[i,j-1]
                add     di, [si+4]      ;[i,j+2]
                add     dx, [si+1feh]   ;[i+1,j-1]
                add     di, [si+204h]   ;[i+1,j+2]
                shl     bp, 3           ;[i,j+1] * 8
                add     dx, bx
                add     bp, ax
                shr     dx, 4           ;Divide by 16.
                add     bp, bx
                mov     es:[si], dx     ;Store [i,j] entry.
                add     bp, di
                add     si, 4           ;Affects next store operation!
                shr     bp, 4           ;Divide by 16.
                dec     ch
                mov     es:[si-2], bp   ;Store [i,j+1] entry.
                jne     jloop0

                add     si, 4           ;Skip to start of next row.

                dec     cl
                jne     iloop0

; Process the last 124 rows of the array). This requires that we switch from
; one segment to the next. Note that the segments overlap.

                mov     ax, DataSeg2
                sub     ax, 40h         ;Back up to last 2 rows in DS2
                mov     ds, ax
                mov     ax, DataSeg4
                sub     ax, 40h         ;Back up to last 2 rows in DS4
                mov     es, ax

                mov     cl, 251-127-1   ;Remaining rows to process.
                mov     si, 202h        ;Continue with next row.
iloop1:         mov     ch, 254/2       ;# of times through loop.
jloop1:         mov     dx, [si]        ;[i,j]
                mov     bx, [si-200h]   ;[i-1,j]
                mov     ax, dx
                shl     dx, 3           ;[i,j] * 8
                add     bx, [si-1feh]   ;[i-1,j+1]
                mov     bp, [si+2]      ;[i,j+1]
                add     bx, [si+200h]   ;[i+1,j]
                add     dx, bp
                add     bx, [si+202h]   ;[i+1,j+1]
                add     dx, [si-202h]   ;[i-1,j-1]
                mov     di, [si-1fch]   ;[i-1,j+2]
                add     dx, [si-2]      ;[i,j-1]
                add     di, [si+4]      ;[i,j+2]
                add     dx, [si+1feh]   ;[i+1,j-1]
                add     di, [si+204h]   ;[i+1,j+2]
                shl     bp, 3           ;[i,j+1] * 8
                add     dx, bx
                add     bp, ax
                shr     dx, 4           ;Divide by 16
                add     bp, bx
                mov     es:[si], dx     ;Store [i,j] entry.
                add     bp, di
                add     si, 4           ;Affects next store operation!
                shr     bp, 4
                dec     ch
                mov     es:[si-2], bp   ;Store [i,j+1] entry.
                jne     jloop1

                add     si, 4           ;Skip to start of next row.

                dec     cl
                jne     iloop1

                mov     ax, dseg
                mov     ds, ax
                assume  ds:dseg

                dec     Iterations
                je      Done0

; Unroll the iterations loop so we can move the data from DataSeg2/4 back
; to DataSeg1/3 without wasting extra time. Other than the direction of the
; data movement, this code is virtually identical to the above.

                mov     ax, DataSeg3
                mov     ds, ax
                mov     ax, DataSeg1
                mov     es, ax

                mov     cl, 127
                lea     si, Data1a+202h
iloop2:         mov     ch, 254/2
jloop2:         mov     dx, [si]
                mov     bx, [si-200h]
                mov     ax, dx
                shl     dx, 3
                add     bx, [si-1feh]
                mov     bp, [si+2]
                add     bx, [si+200h]
                add     dx, bp
                add     bx, [si+202h]
                add     dx, [si-202h]
                mov     di, [si-1fch]
                add     dx, [si-2]
                add     di, [si+4]
                add     dx, [si+1feh]
                add     di, [si+204h]
                shl     bp, 3
                add     dx, bx
                add     bp, ax
                shr     dx, 4
                add     bp, bx
                mov     es:[si], dx
                add     bp, di
                add     si, 4
                shr     bp, 4
                dec     ch
                mov     es:[si-2], bp
                jne     jloop2

                add     si, 4

                dec     cl
                jne     iloop2


                mov     ax, DataSeg4
                sub     ax, 40h
                mov     ds, ax
                mov     ax, DataSeg2
                sub     ax, 40h
                mov     es, ax

                mov     cl, 251-127-1
                mov     si, 202h
iloop3:         mov     ch, 254/2
jloop3:         mov     dx, [si]
                mov     bx, [si-200h]
                mov     ax, dx
                shl     dx, 3
                add     bx, [si-1feh]
                mov     bp, [si+2]
                add     bx, [si+200h]
                add     dx, bp
                add     bx, [si+202h]
                add     dx, [si-202h]
                mov     di, [si-1fch]
                add     dx, [si-2]
                add     di, [si+4]
                add     dx, [si+1feh]
                add     di, [si+204h]
                shl     bp, 3
                add     dx, bx
                add     bp, ax
                shr     dx, 4
                add     bp, bx
                mov     es:[si], dx
                add     bp, di
                add     si, 4
                shr     bp, 4
                dec     ch
                mov     es:[si-2], bp
                jne     jloop3

                add     si, 4

                dec     cl
                jne     iloop3

                mov     ax, dseg
                mov     ds, ax
                assume  ds:dseg

                dec     Iterations
                je      Done2
                jmp     hloop

Done2:          mov     ax, DataSeg1
                mov     bx, DataSeg2
                jmp     Finish

Done0:          mov     ax, DataSeg3
                mov     bx, DataSeg4
Finish:         mov     ds, ax
                print
                byte    "Writing result",cr,lf,0

; Convert data back to byte form and write to the output file:

                mov     ax, dseg
                mov     es, ax

                mov     cx, 32768
                lea     di, ImgData
                xor     si, si          ;Output data is at offset zero.
CopyLoop3:      lodsw                   ;Read a word from final array.
                stosb                   ;Write a byte to output array.
                dec     cx
                jne     CopyLoop3

                mov     ds, bx
                mov     cx, (251*256) - 32768
                xor     si, si
CopyLoop4:      lodsw                   ;Read final data word.
                stosb                   ;Write data byte to output array.
                dec     cx
                jne     CopyLoop4


; Okay, write the data to the output file:

                mov     ah, 3ch         ;Create output file.
                mov     cx, 0           ;Normal file attributes.
                mov     dx, dseg
                mov     ds, dx
                lea     dx, OutName
                int     21h
                jnc     GoodCreate
                print
                byte    "Could not create output file.",cr,lf,0
                jmp     Quit

GoodCreate:     mov     bx, ax          ;File handle.
                push    bx
                mov     dx, dseg        ;Where the data can be found.
                mov     ds, dx
                lea     dx, ImgData
                mov     cx, 256*251     ;Size of data file to write.
                mov     ah, 40h         ;Write operation.
                int     21h
                pop     bx              ;Retrieve handle for close.
                cmp     ax, 256*251     ;See if we wrote the data.
                je      GoodWrite
                print
                byte    "Did not write the file properly",cr,lf,0
                jmp     Quit

GoodWrite:      mov     ah, 3eh         ;Close operation.
                int     21h


Quit:           ExitPgm                 ;DOS macro to quit program.
Main            endp

cseg            ends

sseg            segment para stack 'stack'
stk             byte    1024 dup ("stack ")
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       byte    16 dup (?)
zzzzzzseg       ends
                end     Main

Of course, the absolute best way to improve the performance of any piece of code is with a better algorithm. All of the above assembly language versions were limited by a single requirement - they all must produce the same output file as the original Pascal program. Often, programmers lose sight of what it is that they are trying to accomplish and get so caught up in the computations they are performing that they fail to see other possibilities. The optimization example above is a perfect example. The assembly code faithfully preserves the semantics of the original Pascal program; it computes the weighted average of all interior pixels as the sum of the eight neighbors around a pixel plus eight times the current pixel's value, with the entire sum divided by 16. Now this is a good blurring function, but it is not the only blurring function. A Photoshop (or other image processing program) user doesn't care about algorithms or such. When that user selects "blur image" they want it to go out of focus. Exactly how much out of focus is generally immaterial. In fact, the less the better because the user can always run the blur algorithm again (or specify some number of iterations). The following assembly language program shows how to get better performance by modifying the blurring algorithm to reduce the number of instructions it needs to execute in the innermost loops. It computes blurring by averaging a pixel with the four neighbors above, below, to the left, and to the right of the current pixel. This modification yields a program that runs 100 iterations in 2.2 seconds, a 12% improvement over the previous version:









; IMGPRCS.ASM
;
; An image processing program (Fifth optimization pass).
;
; This program blurs an eight-bit grayscale image by averaging a pixel
; in the image with the eight pixels around it. The average is computed
; by (CurCell*8 + other 8 cells)/16, weighting the current cell by 50%.
;
; Because of the size of the image (almost 64K), the input and output
; matrices are in different segments.
;
; Version #1: Straight-forward translation from Pascal to Assembly.
;
; Version #2: Three major optimizations. (1) used movsd instruction rather
;        than a loop to copy data from DataOut back to DataIn.
;        (2) Used repeat..until forms for all loops. (3) unrolled
;        the innermost two loops (which is responsible for most of
;        the performance improvement).
;
; Version #3: Used registers for all variables. Set up segment registers
;        once and for all through the execution of the main loop so
;        the code didn't have to reload ds each time through. Computed
;        index into each row only once (outside the j loop).
;
; Version #4: Eliminated copying data from DataOut to DataIn on each pass.
;        Removed hazards. Maintained common subexpressions. Did some
;        more loop unrolling.
;
; Version #6: Changed the blurring algorithm to use fewer computations.
;        This version does *NOT* produce the same data as the other
;        programs.
;
;
;       Performance comparisons (66 MHz 80486 DX/2 system, 100 iterations).
;
;       This code-                              2.2 seconds.
;       3rd optmization pass-                   2.5 seconds.
;       2nd optimization pass-                  4 seconds.
;       1st optimization pass-                  6 seconds.
;       Original ASM code-                      36 seconds.

;       <<Lots of deleted code here, see the original program»


                print
                byte    "Computing Result",cr,lf,0


                assume  ds:InSeg, es:OutSeg

                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax

; Copy the data once so we get the edges in both arrays.

                mov     cx, (251*256)/4
                lea     si, DataIn
                lea     di, DataOut
        rep     movsd


; "hloop" repeats once for each iteration.

hloop:
                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax

; "iloop" processes the rows in the matrices.

                mov     cl, 249
iloop:          mov     bh, cl                  ;i*256
                mov     bl, 1                   ;Start at j=1.
                mov     ch, 254/2               ;# of times through loop.
                mov     si, bx
                mov     dh, 0                   ;Compute sum here.
                mov     bh, 0
                mov     ah, 0

; "jloop" processes the individual elements of the array.
; This loop has been unrolled once to allow the two portions to share
; some common computations.

jloop:

; The sum of DataIn [i-1][j] + DataIn[i-1][j+1] + DataIn[i+1][j] +
; DataIn [i+1][j+1] will be used in the second half of this computation.
; So save its value in a register (di) until we need it again.

                mov     dl, DataIn[si]          ;[i,j]
                mov     al, DataIn[si-256]      ;[I-1,j]
                shl     dx, 2                   ;[i,j]*4
                mov     bl, DataIn[si-1]        ;[i,j-1]
                add     dx, ax
                mov     al, DataIn[si+1]        ;[i,j+1]
                add     dx, bx
                mov     bl, DataIn[si+256]      ;[i+1,j]
                add     dx, ax
                shl     ax, 2                   ;[i,j+1]*4
                add     dx, bx
                mov     bl, DataIn[si-255]      ;[i-1,j+1]
                shr     dx, 3                   ;Divide by 8.
                add     ax, bx
                mov     DataOut[si], dl
                mov     bl, DataIn[si+2]        ;[i,j+2]
                mov     dl, DataIn[si+257]      ;[i+1,j+1]
                add     ax, bx
                mov     bl, DataIn[si]          ;[i,j]
                add     ax, dx
                add     ax, bx
                shr     ax, 3
                dec     ch
                mov     DataOut[si+1], al
                jne     jloop

                dec     cl
                jne     iloop

                dec     bp
                je      Done


; Special case so we don't have to move the data between the two arrays.
; This is an unrolled version of the hloop that swaps the input and output
; arrays so we don't have to move data around in memory.

                mov     ax, OutSeg
                mov     ds, ax
                mov     ax, InSeg
                mov     es, ax
                assume  es:InSeg, ds:OutSeg

hloop2:

                mov     cl, 249
iloop2:         mov     bh, cl
                mov     bl, 1
                mov     ch, 254/2
                mov     si, bx
                mov     dh, 0
                mov     bh, 0
                mov     ah, 0
jloop2:
                mov     dl, DataOut[si-256]
                mov     al, DataOut[si-255]
                mov     bl, DataOut[si+257]
                add     dx, ax
                mov     al, DataOut[si+256]
                add     dx, bx
                mov     bl, DataOut[si+1]
                add     dx, ax
                mov     al, DataOut[si+255]

                mov     di, dx

                add     dx, bx
                mov     bl, DataOut[si-1]
                add     dx, ax
                mov     al, DataOut[si]
                add     dx, bx
                mov     bl, DataOut[si-257]
                shl     ax, 3
                add     dx, bx
                add     dx, ax
                shr     ax, 3
                shr     dx, 4
                mov     DataIn[si], dl

                mov     dx, di
                mov     bl, DataOut[si-254]
                add     dx, ax
                mov     al, DataOut[si+2]
                add     dx, bx
                mov     bl, DataOut[si+258]
                add     dx, ax
                mov     al, DataOut[si+1]
                add     dx, bx
                shl     ax, 3
                add     si, 2
                add     dx, ax
                mov     ah, 0
                shr     dx, 4
                dec     ch
                mov     DataIn[si-1], dl
                jne     jloop2

                dec     cl
                jne     iloop2

                dec     bp
                je      Done2
                jmp     hloop


; Kludge to guarantee that the data always resides in the output segment.

Done2:
                mov     ax, InSeg
                mov     ds, ax
                mov     ax, OutSeg
                mov     es, ax
                mov     cx, (251*256)/4
                lea     si, DataIn
                lea     di, DataOut
        rep     movsd

Done:           print
                byte    "Writing result",cr,lf,0


;       //Lots of delete code here, see the original program//

One very important thing to keep in mind about the codein this section is that we've optimized it for 100 iterations. While it turns out that these optimizations apply equally well to more iterations, this isn't necessarily true for fewer iterations. In particular, if we run only one iteration, any copying of data at the end of the operation will easily consume a large part of the time we save by the optimizations. Since it is very rare for a user to blur an image 100 times in a row, our optimizations may not be as good as we could make them. However, this section does provide a good example of the steps you must go through in order to optimize a given program. One hundred iterations was a good choice for this example because it was easy to measure the running time of all versions of the program. However, you must keep in mind that you should optimize your programs for the expected case, not an arbitrary case.

25.5 - Improving the Implementation of an Algorithm


Art of Assembly: Chapter Twenty-Five - 29 SEP 1996

[Chapter Twenty-Five][Previous] [Art of Assembly][Randall Hyde]



Number of Web Site Hits since Jan 1, 2000: