Two production incidents at Sentry were caused by O(n^2) algorithms that passed testing but failed with larger datasets. The Android case involved DEX file symbolication where a linear scan fallback created quadratic complexity with 52,202 classes, solved by adding a dictionary lookup. The iOS case involved LIEF library's export trie parsing with an unpopulated cache causing linear scans, fixed with a simple patch. Both demonstrate how O(n^2) algorithms are fast enough to reach production but slow enough to cause failures at scale.

6m read timeFrom sentry.engineering
Post cover image
Table of contents
BackgroundAndroidiOSIn conclusion

Sort: