sebastianbergmann/diff — pull request #11 by mimrock (2014-08-08 15:20:48+00:00)
Title: Remove memory limit from diffing

I was using PHPUnit when a test, which compared two big DOMDocument files, stopped due to the exceeding of the memory limit. I investigated the story, and found that the method which generates the diff for the failed tests is using a dynamic programming-based approach. This algorithm have a quadratic running time, and requires quadratic memory.

If the available time-frame to run the tests is not extremely tight, the memory consumption is a stricter bottleneck.

In this pull request I replaced the old LCS method with a new one based on an algorithm called Hirschberg's algorithm, which also have a quadratic running time, but only uses linear space. The new algorithm is a bit slower (30-40%), but removes the memory bottleneck, thus makes PHPUnit suitable for comparing bigger items.