samg/diffy — pull request #43 by JasonBarnabe (2014-06-15 05:58:23+00:00)
Title: Performance improvement for HTML formatter when there are many changes in a single line

diffy 3.0.4's HTML formatter is incredibly slow when there are many changes in a single line. I diffed jQuery 2.0.0 and 2.1.1, once with the development version (lots of changes on lots of lines) and once with the minified version (lots of changes on very few lines). Diffing the development version gives reasonable times, but for the minified versions, it takes nearly 2 minutes!

```
Comparing jQuery 2.0.0 and 2.1.1, development versions
Text:
0.030000 0.000000 0.050000 ( 0.059692)
HTML Simple:
0.170000 0.010000 0.180000 ( 0.180582)
HTML:
14.370000 1.940000 19.580000 ( 19.236228)
Comparing jQuery 2.0.0 and 2.1.1, minified versions
Text:
0.040000 0.000000 0.040000 ( 0.042111)
HTML Simple:
0.010000 0.000000 0.010000 ( 0.009504)
HTML:
112.100000 0.980000 113.450000 (113.863912)
```

Profiling shows 98% of the time is spent in `reconstruct_characters`. For each change, the list of changes is converted to an array. With a simple change, we can convert it to an array once and get:

```
Comparing jQuery 2.0.0 and 2.1.1, minified versions
Text:
0.000000 0.000000 0.000000 ( 0.004409)
HTML Simple:
0.030000 0.000000 0.030000 ( 0.039216)
HTML:
4.790000 0.050000 5.200000 ( 5.206322)
```
22 times faster!