Article illustration 1

Performance engineer Bruce Dawson's observation about O(n²) algorithms proved brutally accurate for Sentry's engineering team: "Fast enough to make it into production, but slow enough to make things fall down once it gets there." This axiom became reality when Sentry's Size Analysis tool—designed to help optimize mobile app sizes—suddenly slowed from seconds to 12-minute processing times for customer applications.

The Android O(n²) Crisis

During Android app analysis, Sentry's tool parses DEX files and deobfuscates method names using ProGuard mapping files. Initial parsing without symbolication took mere seconds:

$ time python -m launchpad profile-dex-parsing classes.dex
________________________________________________________
Executed in 2.36 secs

But symbol processing ballooned runtime to 91 seconds—a 40x increase. The culprit lay in the deobfuscation logic:

class DexMapping:
  def deobfuscate_method(self, class_name, obfuscated_method_name):
    clazz = self.lookup_obfuscated_class(class_name)
    if clazz is None:
      clazz = self.lookup_deobfuscated_signature(class_name)
    # ... rest of method ...

  def lookup_deobfuscated_signature(self, deobfuscated_class_signature):
    for clazz in self._classes.values():
      if clazz.deobfuscated_signature == deobfuscated_class_signature:
        return clazz
    return None

This implementation triggered a worst-case O(n²) scenario: For each of 52,202 classes, the fallback path performed a full linear scan through all classes. The result? Over 2.7 billion operations. The solution replaced linear scans with dictionary lookups:

class DexMapping:
  def __init__(self):
    self._classes_by_deobfuscated = {clazz.deobfuscated_signature: clazz for clazz in classes}

  def lookup_deobfuscated_signature(self, deobfuscated_class_signature):
    return self._classes_by_deobfuscated.get(deobfuscated_class_signature)

Runtime immediately dropped back to 5 seconds—demonstrating how algorithmic complexity trumps micro-optimizations.

The iOS Déjà Vu

Sentry's iOS analysis encountered identical scaling issues when using the LIEF library for Mach-O binary parsing. Export trie processing inexplicably took 45 minutes for one customer's app. Investigation revealed:

auto search = memoized_symbols_.find(symbol_name);
if (search != memoized_symbols_.end()) {
  symbol = search->second;
} else {
  symbol = binary_->get_symbol(symbol_name); // Linear scan!
}

The cache (memoized_symbols_) was never populated, turning trie parsing into another O(n²) operation. Sentry submitted a patch after discovering this dormant flaw survived nearly four years in production—exposed only when processing binaries with unusually high symbol counts.

The Quadratic Reality Check

Both incidents validate Dawson's law: Quadratic algorithms are uniquely dangerous because they:

  1. Pass testing with smaller datasets
  2. Scale acceptably during initial deployment
  3. Catastrophically degrade with real-world data volumes

The pattern manifests as nested loops or hidden linear operations within iterations—a code smell engineers should aggressively hunt. As mobile apps grow increasingly complex and dependency trees deepen, these scaling cliffs become more prevalent. Sentry's experience underscores that "fast enough" during development often masks ticking time bombs. Performance engineering must prioritize algorithmic scrutiny over localized optimizations, because when scaling fails, it fails exponentially.

For teams building data-intensive systems, the lesson is clear: Treat O(n²) patterns as production vulnerabilities. Audit loops for hidden linear operations, validate against production-scale datasets, and remember—if your code could be quadratic, it eventually will be.

Source: Sentry Engineering Blog