Case Study 2: PennyWise Performance Audit — Profiling Expense Operations, Identifying Bottlenecks, and Choosing Better Algorithms

The Scenario

Rosa's PennyWise has grown to 10,000 expenses over two years of use. She notices that some operations feel sluggish. Rather than guessing, she performs a systematic performance audit.

The Audit Process

Step 1: Identify Operations to Profile

Rosa's typical session involves: 1. Loading all expenses from file (~once per session) 2. Searching for specific expenses (~20 times per session) 3. Sorting by different criteria (~5 times per session) 4. Computing category totals (~10 times per session) 5. Adding new expenses (~3 per session)

Step 2: Measure Current Performance

program PerformanceAudit;

uses
  SysUtils;

const
  N = 10000;

{ Simplified timing results for 10,000 expenses: }

procedure RunAudit;
var
  Start: QWord;
begin
  WriteLn('=== PennyWise Performance Audit ===');
  WriteLn('Expense count: ', N);
  WriteLn;

  { Operation 1: Linear search (current) }
  Start := GetTickCount64;
  { 1000 linear searches }
  WriteLn('Linear search (x1000):       ~', 4200, ' ms');

  { Operation 2: Binary search (proposed) }
  Start := GetTickCount64;
  { 1000 binary searches on sorted data }
  WriteLn('Binary search (x1000):       ~', 2, ' ms');

  { Operation 3: Insertion sort (bad choice) }
  WriteLn('Insertion sort:              ~', 3500, ' ms');

  { Operation 4: Quicksort (good choice) }
  WriteLn('Quicksort:                   ~', 8, ' ms');

  { Operation 5: Category total (tree traversal) }
  WriteLn('Category total (7 cats):     ~', 1, ' ms');

  { Operation 6: Add expense (array append) }
  WriteLn('Add expense:                 ~', 0, ' ms');
end;

Step 3: Identify Bottlenecks

The search operations dominate Rosa's session time. Everything else is acceptably fast.

Step 4: Optimize the Bottleneck

Current approach: Linear search each time (O(n) per search). Proposed approach: Sort once at load time (O(n log n)), then binary search (O(log n) per search).

New session profile: | Operation | Time | Frequency | Session Total | |-----------|------|-----------|---------------| | Load + sort | 58 ms | 1x | 58 ms | | Binary search | 0.002 ms each | 20x | 0.04 ms | | Re-sort (if field changes) | 8 ms | 5x | 40 ms | | Category totals | <1 ms each | 10x | 5 ms | | Add expense + re-sort | 8 ms | 3x | 24 ms | | Total session | | | ~127 ms |

Session time reduced by 30%. More importantly, the search bottleneck is eliminated — searches are now 2,100x faster.

Step 5: Consider Further Optimizations

For even better performance on frequent searches:

1. Hash table index: O(1) average lookup, but uses O(n) extra memory.
2. Multiple sorted copies: Keep one copy sorted by date, another by amount. Doubles memory but eliminates re-sorting.
3. BST index: O(log n) search + dynamic insert/delete. Better than sorted array if expenses are added/removed frequently.

Rosa chooses the BST approach because she adds expenses regularly and wants search performance without re-sorting.

The Complete Audit Report

=== PennyWise Performance Audit Report ===

Environment:
  Expenses: 10,000
  Free Pascal 3.2.2, Windows 10
  Compiled with: fpc -O2

Before Optimization:
  Session time: ~181 ms
  Bottleneck: Linear search (84 ms, 46% of session)

After Optimization (sort + binary search):
  Session time: ~127 ms
  Search time: 0.04 ms (99.95% reduction)
  Overall speedup: 1.4x

Recommendation:
  - Pre-sort expenses on load
  - Use binary search for all lookups
  - Consider BST if search/insert ratio > 10:1
  - No micro-optimization needed — all operations under 100 ms

Conclusion:
  The algorithmic change (linear → binary search) delivered
  a 2,100x speedup on the bottleneck operation. No code-level
  optimization was necessary.

Key Lessons

1. Profile before optimizing. Rosa's intuition might have pointed to sorting as the bottleneck, but measurement revealed it was actually searching.

2. Focus on the bottleneck. Optimizing the 5 ms sorting operation would save at most 5 ms per session. Optimizing the 84 ms searching operation saves 84 ms — a much better investment.

3. Algorithmic improvement >> code optimization. The switch from O(n) to O(log n) search delivered a 2,100x speedup. No amount of loop unrolling or register optimization could achieve this.

4. Consider the full workflow. Binary search requires sorted data. If the data changes frequently (inserts and deletes), the cost of maintaining sorted order must be included in the analysis. This is why the choice of data structure (sorted array vs. BST vs. hash table) depends on the workload pattern.

Discussion Questions

1. If Rosa had 100,000 expenses instead of 10,000, how would the audit results change? Would the same optimization strategy apply?

2. Rosa typically searches by date but occasionally by amount or category. How would you handle multiple search criteria without maintaining multiple sorted copies?

3. At what expense count does it become worth building a BST index instead of sorting an array? Consider the costs of initial construction, search, and insertion.

4. Rosa's performance audit took about 30 minutes. The optimization saved 54 ms per session. If Rosa uses PennyWise 300 times per year, how long until the optimization "pays for itself" in saved time? Is this the right way to think about optimization?