Big performance regression calling merge() on 1.0.1 preview

[josephg]

Sorry the example is a bit long, but this is a simple fuzzer which inserts a bunch of items randomly into 3 simulated peers, and syncs them. In automerge 0.14 on npm this runs reasonably quickly (10000 edits in 5 seconds). Using automerge 1.0.1-preview it runs much more slowly (40 iterations in 5 seconds)

The time is spent in the merge() function - you can see the inflation of merge time as the document grows:

merge 0: 2.462ms
merge 1: 2.966ms
merge 2: 5.468ms
merge 3: 5.777ms
merge 5: 7.821ms
...
merge 13: 51.929ms
merge 14: 62.927ms
merge 15: 77.269ms
merge 17: 104.805ms
...
merge 33: 508.224ms
merge 35: 555.231ms
merge 36: 669.424ms
merge 37: 736.736ms

The majority of the time (96%) is spent in decodeColumns

Code:

const automerge = require('automerge')
const assert = require('assert')

const amInit = automerge.from({arr: []})

const randInt = (n) => Math.floor(Math.random() * n)

const docs = [
  automerge.merge(automerge.init('01'), amInit),
  automerge.merge(automerge.init('02'), amInit),
  automerge.merge(automerge.init('03'), amInit),
]

let nextItem = 0
const start = Date.now()

let i
for (i = 0;; i++) {
  if (Date.now() - start > 5000) break // Run for 5 seconds
  // console.log(i)
  // if (i % 100 === 0) console.log(i)

  // Generate a random operation
  const d = randInt(docs.length)
  let doc = docs[d]

  const len = doc.arr.length

  // Insert an item
  const content = ++nextItem
  const pos = randInt(len + 1)
  doc = automerge.change(doc, d => {
    d.arr.splice(pos, 0, content)
  })

  docs[d] = doc

  // Pick a pair of documents and merge them
  const a = randInt(docs.length)
  const b = randInt(docs.length)
  if (a !== b) {
    console.time(`merge ${i}`)
    docs[a] = automerge.merge(docs[a], docs[b])
    docs[b] = automerge.merge(docs[b], docs[a])
    console.timeEnd(`merge ${i}`)
    assert.deepStrictEqual(docs[a], docs[b])
  }
}

console.log(`In 5 seconds ran ${i} iterations`)

[ept]

Thanks @josephg for this nice clear test case. On my laptop the performance disparity between 0.14.1 and 1.0.1-preview1 is a factor of 24, somewhat lower than the factor of 250 you report. Still bad of course, but I'm wondering where that extra factor of 10 came from. Was that a typo?

I will also note that this performance regression probably won't show up in real apps, since it only affects the function Automerge.merge(), which is intended primarily for testing purposes (since this function can only be used if you are simulating two nodes in the same process; actual communication via a network would not use this function). However, Automerge.merge() is useful in benchmarks, and a benchmark is not very useful if it's dominated by this function, so it does seem reasonable to make it faster.

I have put up PR #368, which brings performance back fairly close to where it was in 0.14. Could you give it a try and see how much it improves things on your machine?

[josephg]

Still bad of course, but I'm wondering where that extra factor of 10 came from. Was that a typo?

Not a typo. It looks like webpack is partially to blame. Replied in more detail in #368.