Homec4science

Googletest export

Authored by Abseil Team <absl-team@google.com> on Aug 27 2018, 20:53.

Description

Googletest export

Fix Theta(N^2) memory usage of EXPECT_EQ(string) when the strings don't match.

The underlying CalculateOptimalEdits() implementation used a simple
dynamic-programming approach that always used N^2 memory and time. This meant
that tests for equality of large strings were ticking time bombs: They'd work
fine as long as the test passed, but as soon as the strings differed the test
would OOM, which is very hard to debug.
I switched it out for a Dijkstra search, which is still worst-case O(N^2), but
in the usual case of mostly-matching strings, it is much closer to linear.

PiperOrigin-RevId: 210405025

Details

Committed
Gennadiy Civil <misterg@google.com>Aug 28 2018, 22:53
Pushed
trottetDec 4 2019, 13:52
Parents
R9484:1bb76182caee: Googletest export
Branches
Unknown
Tags
Unknown

Event Timeline

Gennadiy Civil <misterg@google.com> committed R9484:167c5e8188be: Googletest export (authored by Abseil Team <absl-team@google.com>).Aug 28 2018, 22:53