Splay Tree vs. Treap Patch Benchmark

splay-vs-treap-benchmark.diff

diff --git a/test/patch.test.js b/test/patch.test.js
index 5c32503..da9ba5b 100644
--- a/test/patch.test.js
+++ b/test/patch.test.js
@@ -48,6 +48,184 @@ describe('Patch', function () {
     assert.deepEqual(iterator.getMetadata(), {b: 2})
   })
 
+  function runBenchmark (fn, setup = () => {}, iterations = 3000) {
+    let t0, t1
+    let splayTreeTime = 0
+    let treapTime = 0
+    let splayPatch = new Patch({combineChanges: true, batchMode: true})
+    let treapPatch = new Patch({combineChanges: true, batchMode: false})
+    for (var i = 1; i <= iterations; i++) {
+      let seed = Date.now()
+      setup(splayPatch, i, seed)
+      setup(treapPatch, i, seed)
+    }
+
+    for (var i = 1; i <= iterations; i++) {
+      let seed = Date.now()
+      t0 = window.performance.now()
+      fn(splayPatch, i, seed)
+      t1 = window.performance.now()
+      splayTreeTime += t1 - t0
+
+      t0 = window.performance.now()
+      fn(treapPatch, i, seed)
+      t1 = window.performance.now()
+      treapTime += t1 - t0
+    }
+
+    return {splayTreeTime, treapTime}
+  }
+
+  it('benchmark', function () {
+    this.timeout(Infinity)
+
+    {
+      document.write(`<h3>Sequential Non-Overlapping Insertions Time:</h3>`)
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i, seed) => {
+        let start = {row: i, column: 0}
+        let oldExtent = {row: 0, column: 0}
+        let newExtent = {row: 0, column: 1}
+        patch.splice(start, oldExtent, newExtent)
+      })
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Repeated Sequential Non-Overlapping Insertions Time:</h3>`)
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i, seed) => {
+        for (var j = 0; j < 3000; j++) {
+          let start = {row: j, column: i}
+          let oldExtent = {row: 0, column: 0}
+          let newExtent = {row: 0, column: 1}
+          patch.splice(start, oldExtent, newExtent)
+        }
+      }, () => {}, 10)
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Repeated Sequential Non-Overlapping Insertions Time (with rebalance):</h3>`)
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i, seed) => {
+        for (var j = 0; j < 3000; j++) {
+          let start = {row: j, column: i}
+          let oldExtent = {row: 0, column: 0}
+          let newExtent = {row: 0, column: 1}
+          patch.splice(start, oldExtent, newExtent)
+        }
+
+        if (patch.batchMode) patch.rebalance()
+      }, () => {}, 10)
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Randomized Insertions Time:</h3>`)
+      let inputs = []
+      let setup = (i, seed) => {
+        let random = new Random(seed)
+        let start = {row: random.intBetween(0, 100), column: random.intBetween(0, 100)}
+        let oldExtent = {row: random.intBetween(0, 0), column: random.intBetween(0, 60)}
+        let newExtent = {row: random.intBetween(0, 0), column: random.intBetween(0, 60)}
+        inputs.push(start, oldExtent, newExtent)
+      }
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i, seed) => {
+        patch.splice(inputs.shift(), inputs.shift(), inputs.shift())
+      }, setup)
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Lookups close to each sequential insertion:</h3>`)
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i) => {
+        patch.splice({row: i, column: 0}, {row: 0, column: 0}, {row: 0, column: 1})
+
+        patch.translateOutputPosition({row: i - 1, column: i})
+        patch.translateOutputPosition({row: i + 1, column: i})
+        patch.translateOutputPosition({row: i, column: i})
+      })
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Lookups far from each sequential insertion:</h3>`)
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i) => {
+        patch.splice({row: i, column: 0}, {row: 0, column: 0}, {row: 0, column: 1})
+
+        patch.translateOutputPosition({row: Math.floor(i / 5), column: i})
+        patch.translateOutputPosition({row: i * 5, column: i})
+      })
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Randomized insertions, then sequential lookups:</h3>`)
+      let setup = (patch, i, seed) => {
+        let random = new Random(seed)
+        let start = {row: random.intBetween(0, 100), column: random.intBetween(0, 100)}
+        let oldExtent = {row: random.intBetween(0, 60), column: random.intBetween(0, 60)}
+        let newExtent = {row: random.intBetween(0, 60), column: random.intBetween(0, 60)}
+        patch.splice(start, oldExtent, newExtent)
+      }
+
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i) => {
+        patch.translateOutputPosition({row: i, column: i})
+      }, setup)
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Sequential insertions, then sequential lookups:</h3>`)
+      let setup = (patch, i, seed) => {
+        patch.splice({row: i, column: 0}, {row: 0, column: 0}, {row: 0, column: 1})
+      }
+
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i) => {
+        patch.translateOutputPosition({row: i, column: 1})
+      }, setup)
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+
+    {
+      document.write(`<h3>Sequential insertions, rebalance, then sequential lookups:</h3>`)
+      let setup = (patch, i, seed) => {
+        patch.splice({row: i, column: 0}, {row: 0, column: 0}, {row: 0, column: 1})
+      }
+
+      let {splayTreeTime, treapTime} = runBenchmark((patch, i) => {
+        if (i === 1 && patch.batchMode) patch.rebalance()
+        patch.translateOutputPosition({row: i, column: 1})
+      }, setup)
+      document.write(`<ul>`)
+      document.write(`<li>Treap: ${treapTime}ms.</li>`)
+      document.write(`<li>Splay Tree: ${splayTreeTime}ms.</li>`)
+      document.write(`</ul>`)
+    }
+  })
+
   it('correctly records random splices', function () {
     this.timeout(Infinity)