Algorithms in a Nutshell

Performance Families | 27

AlgorithmsThe Math of

Do these seemingly small implementation details affect the performance of an

algorithm? Let’s consider two other potential factors that can impact the algo-

rithm’s performance:

• Programming language is one factor.addandlastcan trivially be converted
  into C programs. How does the choice of language affect the algorithm’s
  performance?


• The programs can be executed on different computers. How does the choice
  of computer hardware affect the algorithm’s performance?
  The implementations were executed 10,000 times on numbers ranging from 256
  digits to 32,768 digits. For each digit size a random number of that size was gener-
  ated; thereafter, for each of the 10,000 trials, these two numbers were circular
  shifted (one left and one right) to create two different numbers to be added. Two
  machines were used: a desktop PC and a high-end computer, as discussed in
  Chapter 10. Two different programming languages were used (C and Java). We
  start with the hypothesis that as the problem size doubles, the execution time for
  the algorithm doubles as well. We would like to also be reassured that this overall
  behavior occurs regardless of the machine, programming language, or implemen-
  tation variation used.
  Figure 2-5 contains a graph plotting problem size (shown on the X axis) against
  the execution time (in milliseconds) to compute 10,000 executions (shown on the
  Y axis). Each variation was executed on a set of configurations:
  g
  C version was compiled with debugging information included.
  none
  C version was compiled without any specific optimization.
  O1, O2, O3
  C version was compiled under these different optimization levels. In general,
  increasing numbers imply better optimization and thus better expected
  performance.
  Java
  Java version of algorithms.
  PC-Java
  This is the only configuration executed on a PC; the previous ones were all
  executed on the high-end computer.
  Note how each of the computed lines for the graphs on the left side of Figure 2-5
  (labeled “Desktop PC”) can be approximated by a fixed linear slope, thus
  supporting the view that there is a linear relationship between the X and Y values.
  The computations using optimized code on the high-end computer cannot so
  simply be classified as linear, suggesting that the advanced processor has a signifi-
  cant impact.
  Table 2-3 contains a subset of the charted data in numeric form. The code
  provided with this book generates this information as needed. The seventh and
  final column in Table 2-3 directly compares the performance times of the

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use