List.myers_difference is very slow and memory hungry

[smetana]

Running it on two lists of 5000 elements takes 20 seconds and 1.7 Gigabytes (!) of memory
There is probably a lot of room for improvement :)

ex(1)> a = String.duplicate("a", 5000) |> String.graphemes()
iex(2)> b = String.duplicate("b", 5000) |> String.graphemes()
iex(3)> :erlang.memory()
[total: 22780608, processes: 5842616, processes_used: 5841624, system: 16937992,
 atom: 264529, atom_used: 260532, binary: 40448, code: 7295199, ets: 375008]

iex(4)> List.myers_difference(a, b)  # takes 20 seconds
iex(5)> :erlang.memory()           
[total: 1816622088, processes: 1799695120, processes_used: 1799694128,
 system: 16926968, atom: 264529, atom_used: 260622, binary: 23688,
 code: 7298655, ets: 376544]         # And 1.7Gb of memory

[josevalim]

@smetana the algorithm has complexity of O(M + N + D²) for both time and space. The issue is that in your case, D is really large because the strings are completely different. There is a refinement of the algorithm, which is linear in regards to space, but it is not implemented right now. You can read more about it in the section 4.2 of the paper. A pull request that brings those improvements is welcome but it is not something the core team is planning to tackle right now.