Suppose two data structures have attractive theoretical running times, but one has more complicated code. Which is faster in your application? Profiling measures the running time—and sometimes memory consumption—of an executable program on chosen inputs. It helps answer that practical question, but its results describe the implementations and workloads measured, not every possible implementation or input. section 2.10.1 section 3.5.3
Profile where a result could change an important decision:
- Start at the level of major function calls. Find the critical code path before spending time on instruction-level measurements or tuning. section 2.10.1 section 2.10.4
- Choose inputs and data volumes that represent the intended workload. Repeat measurements across varied, possibly pseudorandom inputs; a narrow sample can reward an edge-case optimization. section 2.10.1 section 2.10.4
- Measure the resource that matters to the decision. CPU time can reveal an implementation’s overhead; memory allocation can expose a different cost. section 3.5.3 section 3.5.4
Tuning a heap parameter
A heap’s branching factor can change practical running time without changing its methods’ asymptotic running time. A Python implementation of Huffman encoding and d-ary heaps provides a setting for measuring that choice. First identify whether heap operations account for enough of the encoding time to justify tuning them; then compare branching factors on representative inputs. The best choice depends on both implementation and input. section 2.10.1 section 2.10.4 section 2.11
A comparison that reverses
A plain binary search tree and a randomized treap receive the same sequences of insertions and removals. Tree height offers an initial clue because these operations take steps proportional to height, but CPU measurements reveal implementation costs that asymptotic analysis hides. With random, largely nonduplicate integer keys, treap insertion takes almost twice the cumulative time and removal about 3.5 times the time. Restricting random keys to 0–1000 reverses the result: the plain tree takes about eight times as long to insert and almost 15 times as long to remove. The workload determines which cost dominates. section 3.5.2 section 3.5.3
Figure 3.21 Profiling CPU usage when inserting/removing random integers between 0 and 1000 in a BST and Randomized Treap
Compare the CPU results for keys restricted to 0–1000 with the unbounded-key case: changing the input distribution changes which tree performs better. section 3.5.3
Speed is not the whole trade-off. For similarly sized trees with random insertions and removals, the treap allocates slightly more than twice the memory of the plain tree when keys are integers; with four- to ten-character string keys, the ratio falls to 1.25. Profile critical code only when a plausible improvement is worth the measurement and added complexity. section 3.5.4 section 2.10.1
