Post #3672315
2026-07-08 12:27 UTC
Doing fuzz testing, I've seen the same performance bug in parsers for at least 3 systems, where a line number for location reporting is determined from a byte offset by looping through the input, itself done in a loop. Surprise O(n^2)!
It probably doesn't show up easily in "normal" use patterns, but when you start fuzz testing you hit it all the time.
Replies (1)
-
@pkhuong@discuss.systems 2026-07-08 12:31
@bradlarsen@infosec.exchange Back in the dark ages, linked list of arrays were a classic way to implement file buffers in editors, and there were two kinds of people: some who thought we should use fancier data structures with better asymptotics, and others who decreed long lines were user error.