Performance of the diff algorithm

[guibou]

In multiple cases, we observe that sydtest is hanging for a long time (multiples minutes) when the diff (generated by a failing shouldBe or golden test) is large.

The following example:

import Test.Syd
import Control.Monad
import System.Random

n = 10

main = sydTest $ do
  it "test" $ do
    numbers <- replicateM n (randomIO @Double)
    numbers' <- replicateM n (randomIO @Double)
    numbers `shouldBe` numbers'

Build with ghc -O2 Main.hs, it fails and the runtime of the test suite (mostly spent in the diff computation) varies with n:

• n = 10: 13ms
• n = 100: 203ms (15x with n = 10)
• n = 1000: 29s (142x with n = 100)
• n = 10000: (killed after 10 minutes).

Note that the diff algorithm is generating an impressive number of added/removed chunks, see:

In our codebase, we mitigated the issue by pre simplifying the diff. Mostly for golden tests, all of our golden tests are done on json output, so we have a "post process" in the goldenTestCompare logic which recursively replaces "big diff" nodes in the json tree by a smaller diff (e.g. for a json array of numbers, we replace the array by a string containing some statistical values about the array). However, it does not always work and users are able to break tests in ways which lead to sydtest hanging. Our CI is also hanging a lot.

A few possible action points:

a) Add a timeout on the diff algorithm in sydtest. If the diff takes more than (e.g. 100ms), just stop computing the diff and display a message. User can still do --golden-reset and use local (and possibly more efficient) diff tools. This won't fix the shouldBe unfortunately.
b) Improve the diff algorithm. Most of the time, git diff is able to diff these files in a matter of millisec. Note that having the current diff algorithm takes great care of generating the "smallest" diff possible and this usually leads to a lot of diff chunks and I suspect that this is the reason why it is slow. Unfortunately, having so much diff chunks makes also the diff someone not readable. For example, for me, it is more readable to have something like common prefix {- 1.3456 -} {+ 2.3457 +} common suffix instead of common prefix {- 1 -} {+ 2 +}.345 {- 6 -} {+ 7 +} common suffix
c) Could the diff algorithm be parametrized at runtime in sydtest configuration record?

[NorfairKing]

@guibou It's a bit funny that you should run into this problem because I already implemented a faster diffing algorithm specifically for sydtest: fast-myers-diff.
It looks like that wasn't fast enough yet.

1. I like the timeout idea. We could do that irrespective of what else we do.
2. I'm open to improvements to the diffing algorithm. I also own that code so it'll be easy to get changes merged but it's the ugliest code I've ever written so good luck.
3. I'm happy to support other diffing algorithms too, but I'm not sure how they would work differently. They'd have to work on something other than bare Strings I guess?

EDIT: A good starting point may be to check if hspecs diffing is faster on this input and why.

[guibou]

Using:

import Test.Hspec
import Control.Monad
import System.Random

n = 1000

main = hspec $ do
  it "test" $ do
    numbers <- replicateM n (randomIO @Double)
    numbers' <- replicateM n (randomIO @Double)
    numbers `shouldBe` numbers'

• n = 10: 12ms (same as sydtest, not representative)
• n = 100: 23ms (10x faster than sydtest)
• n = 1000: 0.5s (50x faster than sydtest)
• n = 10000: (2s, which is faster than "killed after 10 minutes")

What I can see, with n = 10:

Seems that there is way less "diff chunks". Each float number is considered as a unique diff chunk, just keeping the 0. as common prefix. This behavior appears also for n = 100, 1000. for n = 10000 it is funny because colouring seems to be disabled:

Their diff algo is implemented here: https://github.com/hspec/hspec/blob/9db7aacb85443fefdbcb078e09df3b7bbf380d2c/hspec-core/src/Test/Hspec/Core/Formatters/Diff.hs

And actually, I just found that: hspec/hspec#415, actually, hspec had the same problem with the Diff package, tried to optimise it, then the finally implemented a timeout and the option to use external diff command.

So to summerize:

1. let's implement the timeout (I'll take care of that whenever I find some bandwith)
2. let's try to find if reducing the size of chunks in the diff algorithm helps. Maybe we can also just steal the Diff code from hspec (however, I have doubts about the licences compatibilities?
3. I suppose that an external diff setting working on ByteString (e.g. BS -> BS -> IO DiffStructure or BS -> BS -> IO BS if we don't want to post process the result) could be easy to integrate in sydtest haskell configuration. on hspec they just use a command line with placeholder for files to diff. If timeout is implemented, I don't see reason to bother about an external algo actually.

[guibou]

Now that I'm thinking a bit more, maybe the diff algo is not at fault (you already implemented something as supposed faster than the original diff package). Maybe the issue is with the formatter of the diff chunks. Need a benchmark before starting to work on the algo.

[guibou]

Fast and dirt profiling (using -O2 -p on the top level program here with n = 1000) gives:

COST CENTRE     MODULE     SRC                                 %time %alloc

getEditScriptBy Myers.Diff src/Myers/Diff.hs:(148,1)-(353,34)   99.8   99.8

[NorfairKing]

@guibou I know very little about performance but could it be that getEditScriptBy could be faster if it were inlined?

[guibou]

@NorfairKing I had not looked at getEditScriptBy until now, and yes, it could be faster if inlined. However the use sites are in the same module (in our context, we call getTextDiff which calls getEditScriptBy which is in the same module, so chances are that GHC is already inlining it.

However, now that I'm having a look at getEditScriptBy, there may be some trivial optimisations:

• It uses MVector of Int, using unboxed vector could dramatically improve the performances (because right now, each mutation operation requires allocating / boxing then later unboxing an Int.
• There are a few utilities functions, such as forUntilJust and whileM for which it MUST be checked that they are correctly inlined (otherwise you pay a heavy cost for >>= and pure.
• forUntilJust is not guaranteed to not allocate, I would highly suggest to rewrite it as a function iterating over the int.
• There are a lot of STRef and this thing is actually a nightmare. Most of the time you do not want to use STRef (in short, you want to use them in concurrent algorithm, where you really need a ref which can be shared between multiples threads), but otherwise, you want to use recursion, because STRef s Int cannot be optimised away (Well, that's complicated) and instead of optimising your code to simple unboxed integer, you need to follow the STRef pointer, read the boxed integer, unbox it, do some operation with it, and reallocate a new boxed pointer.
• Similar observation happen with computeWhileCond which uses STRef for the Double

So actually there are pletty of room for performance improvments. This being said, I still think the timeout is important and both tasks can be tackled separately.

[NorfairKing]

@NorfairKing I had not looked at getEditScriptBy until now, and yes, it could be faster if inlined. However the use sites are in the same module (in our context, we call getTextDiff which calls getEditScriptBy which is in the same module, so chances are that GHC is already inlining it.

Alright thanks for checking!

However, now that I'm having a look at getEditScriptBy, there may be some trivial optimisations:

* It uses `MVector` of `Int`, using unboxed vector could dramatically improve the performances (because right now, each mutation operation requires allocating / boxing then later unboxing an `Int`.

* There are a few utilities functions, such as `forUntilJust` and `whileM` for which it MUST be checked that they are correctly inlined (otherwise you pay a heavy cost for `>>=` and `pure`.

* `forUntilJust` is not guaranteed to not allocate, I would highly suggest to rewrite it as a function iterating over the int.

* There are a lot of `STRef` and this thing is actually a nightmare. Most of the time you do not want to use `STRef` (in short, you want to use them in concurrent algorithm, where you really need a ref which can be shared between multiples threads), but otherwise, you want to use recursion, because `STRef s Int` cannot be optimised away (Well, that's complicated) and instead of optimising your code to simple unboxed integer, you need to follow the STRef pointer, read the boxed integer, unbox it, do some operation with it, and reallocate a new boxed pointer.

* Similar observation happen with `computeWhileCond` which uses `STRef` for the `Double`

I just literally translated the algorithm for Python.
I'm not surprised (but still impressed) that you've found room for improvement.

So actually there are pletty of room for performance improvments. This being said, I still think the timeout is important and both tasks can be tackled separately.

Hard agree!

[guibou]

I'm not surprised (but still impressed) that you've found room for improvement.

I have a large mouth, as usual with performance, only the benchmark can talk. I've tried to replace the boxed vector by unboxed ones and the different STRef.

I've got a 2x improvment, which is great, but not perfect. I need to profile correctly to get something more valuable, but I need to add a few SCC in the code. I'll do that later.