Algorithms in a Nutshell

Side Story | 9

Algorithms

Matter

ProgramA and ProgramC took just a few milliseconds longer than ProgramB. The

performance improvement reflected approximately a 5,000-fold speedup. This is

what might be expected when you consider that the average number of nodes to

visit drops from 500,000 to 20. Actually, this is an order of magnitude off: you

might expect a 25,000-fold speedup, but that is offset by the computation over-

head of balancing the tree. Still, the results are dramatic, and Graham’s memory

leak detector could be released (with Gary’s modifications) in the next version of

the product.

Side Story

Given the efficiency of using red-black binary trees, is it possible that themalloc()

implementation itself is coded to use them? After all, the memory allocation func-

tionality must somehow maintain the set of allocated regions so they can be safely

deallocated. Also, note that each of the programs listed previously make alloca-

tion requests for 32 bytes. Does the size of the request affect the performance of

malloc()andfree()requests? To investigate the behavior ofmalloc(), we ran a

set of experiments. First, we timed how long it took to allocate 4,096 chunks ofn

bytes, withnranging from 1 to 2,048. Then, we timed how long it took to deallo-

cate the same memory using three strategies:

freeUp

In the order in which it was allocated; this is identical to ProgramC

freeDown

In the reverse order in which it was allocated

freeScattered

In a scattered order that ultimately frees all memory

For each value ofnwe ran the experiment 100 times and discarded the best and

worst performing runs. Figure 1-3 contains the average results of the remaining 98

trials. As one might expect, the performance of the allocation follows a linear

trend—as the size ofnincreases, so does the performance, proportional ton.

Surprisingly, the way in which the memory is deallocated changes the perfor-

mance.freeUphas the best performance, for example, whilefreeDownexecutes

about four times as slowly.

The empirical evidence does not answer whethermalloc()andfree()use binary

trees (balanced or not!) to store information; without inspecting the source for

free(), there is no easy explanation for the different performance based upon the

order in which the memory is deallocated.

Showing this example serves two purposes. First, the algorithm(s) behind memory

allocation and deallocation are surprisingly complex, often highly tuned based

upon the specific capabilities of the operating system (in this case a high-end

computer). As we will learn throughout this book, various algorithms have “sweet

spots” in which their performance has no equal and designers can take advantage

of specific information about a problem to improve performance. Second, we also

describe throughout the book different algorithms and explain why one algo-

rithm outperforms another. We return again and again to empirically support

these mathematical claims.

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