26.5. Routines

26.5. Routines

One of the most powerful tools in code tuning is a good routine decomposition. Small, well-defined routines save space because they take the place of doing jobs separately in multiple places. They make a program easy to optimize because you can refactor code in one routine and thus improve every routine that calls it. Small routines are relatively easy to rewrite in a low-level language. Long, tortuous routines are hard enough to understand on their own; in a low-level language like assembler, they're impossible .

Cross-Reference

For details on working with routines, see Chapter 7, "High-Quality Routines."

26.6. Recoding in a Low-Level Language

One long-standing piece of conventional wisdom that shouldn't be left unmentioned is the advice that when you run into a performance bottleneck, you should recode in a low-level language. If you're coding in C++, the low-level language might be assembler. If you're coding in Python, the low-level language might be C. Recoding in a lowlevel language tends to improve both speed and code size . Here is a typical approach to optimizing with a low-level language:

1. Write 100 percent of an application in a high-level language.

2. Fully test the application, and verify that it's correct.

3. If performance improvements are needed after that, profile the application to identify hot spots. Since about 5 percent of a program usually accounts for about 50 percent of the running time, you can usually identify small pieces of the program as hot spots.

   Cross-Reference

   For details on the phenomenon of a small percentage of a program accounting for most of its run time, see "The Pareto Principle" in Section 25.2.

   
   

4. Recode a few small pieces in a low-level language to improve overall performance.

Whether you follow this well-beaten path depends on how comfortable you are with low-level languages, how well-suited the problem is to low-level languages, and on your level of desperation. I got my first exposure to this technique on the Data Encryption Standard program I mentioned in the previous chapter. I had tried every optimization I'd ever heard of, and the program was still twice as slow as the speed goal. Recoding part of the program in assembler was the only remaining option. As an assembler novice, about all I could do was make a straight translation from a high-level language to assembler, but I got a 50 percent improvement even at that rudimentary level.

Suppose you have a routine that converts binary data to uppercase ASCII characters . The next example shows the Delphi code to do it:

Delphi Example of Code That's Better Suited to Assembler

procedure HexExpand(var source: ByteArray;

   var target: WordArray;

   byteCount: word);

var

   index: integer;

   lowerByte: byte;

   upperByte: byte;

   targetIndex: integer;

begin

   targetIndex := 1;

   for index := 1 to byteCount do begin

      target[ targetIndex ] := ((source[ index ] and $F0) shr 4) + ;

      target[ targetIndex+1 ] := (source[ index ] and
procedure HexExpand(var source: ByteArray; var target: WordArray; byteCount: word); var index: integer; lowerByte: byte; upperByte: byte; targetIndex: integer; begin targetIndex := 1; for index := 1 to byteCount do begin target[ targetIndex ] := ((source[ index ] and $F0) shr 4) + $41; target[ targetIndex+1 ] := (source[ index ] and $0f) + $41; targetIndex := targetIndex + 2; end; end;

f) + ;

      targetIndex := targetIndex + 2;

   end;

end;

Although it's hard to see where the fat is in this code, it contains a lot of bit manipulation, which isn't exactly Delphi's forte. Bit manipulation is assembler's forte, however, so this code is a good candidate for recoding. Here's the assembler code:

Example of a Routine Recoded in Assembler

procedure HexExpand(var source;

   var target;

   byteCount : Integer);

   label

   EXPAND;



   asm

         MOV   ECX,byteCount      // load number of bytes to expand

         MOV   ESI,source         // source offset

         MOV   EDI,target         // target offset

         XOR   EAX,EAX            // zero out array offset



   EXPAND:

         MOV   EBX,EAX            // array offset

         MOV   DL,[ESI+EBX]       // get source byte

         MOV   DH,DL              // copy source byte



         AND   DH,$F              // get msbs

         ADD   DH,             // add 65 to make upper case



         SHR   DL,4               // move lsbs into position

         AND   DL,$F              // get lsbs

         ADD   DL,             // add 65 to make upper case

         SHL   BX,1               // double offset for target array offset

         MOV   [EDI+EBX],DX       // put target word



         INC   EAX                // increment array offset

         LOOP  EXPAND             // repeat until finished

   end;

Rewriting in assembler in this case was profitable, resulting in a time savings of 41 percent. It's logical to assume that code in a language that's more suited to bit manipulation C++, for instancewould have less to gain than Delphi code would. Here are the results: