Ruby’s reject!
Accidentally Quadratic (Hacker News):
The code used to be linear, but it regressed in response to bug #2545, which concerned the behavior when the block passed to
reject!executed abreakor otherwise exited early. Becausereject!is in-place, any partial modifications it makes are still visible after an early exit, andreject!was leaving the array in a nonsensical state. The obvious fix was to ensure that the array was always in a consistent state, which is what resulted in the “delete every time” behavior.I find this interesting as a cautionary tale of how several of Ruby’s features (here, ubiquitous mutability, blocks, and nonlocal exits) interact to create suprising edge cases that need to be addressed, and how addressing those edge cases can easily result in yet more problems (here, quadratic performance).
