Benchmark of shex.js and the-square-hole.md

count	shex.js	tsh
1	0.17014 ± 3.11889 µs (n=587751)	0.06511 ± 0.49940 µs (n=1535788)
2	0.23037 ± 8.12863 µs (n=434080)	0.08112 ± 0.35122 µs (n=1232745)
3	0.20537 ± 1.31053 µs (n=486922)	0.08034 ± 0.40406 µs (n=1244741)
4	0.20620 ± 1.23736 µs (n=484957)	0.07732 ± 0.23356 µs (n=1293543)
5	0.21096 ± 1.98588 µs (n=474022)	0.07593 ± 0.20618 µs (n=1317037)
6	0.20471 ± 1.38091 µs (n=488497)	0.07594 ± 0.29618 µs (n=1316793)
7	0.20729 ± 1.52471 µs (n=482413)	0.07752 ± 0.45075 µs (n=1289920)
8	0.20527 ± 3.10052 µs (n=487157)	0.07497 ± 0.23520 µs (n=1333792)
9	0.21829 ± 6.68834 µs (n=458117)	0.07740 ± 0.21075 µs (n=1291968)
10	0.24983 ± 19.98562 µs (n=400267)	0.07974 ± 0.26026 µs (n=1254081)
11	0.30927 ± 56.60609 µs (n=323345)	0.07798 ± 0.23228 µs (n=1282414)
12	8.86212 ± 912.95762 µs (n=11284)	0.07524 ± 0.19789 µs (n=1329127)
13	334767.77700 ± 0.00000 µs (n=1)	0.07543 ± 0.87857 µs (n=1325781)
14	1252435.96300 ± 0.00000 µs (n=1)	0.07971 ± 1.03535 µs (n=1254479)
15	7597313.88000 ± 0.00000 µs (n=1)	0.08022 ± 0.83489 µs (n=1246567)
16	34299929.31100 ± 0.00000 µs (n=1)	0.07462 ± 0.89567 µs (n=1340042)
17	146816882.31000 ± 0.00000 µs (n=1)	0.07969 ± 0.26284 µs (n=1254798)

benchmark.js

import fs from 'fs'
import path from 'path'

const results = JSON.parse(fs.readFileSync(path.resolve('output.json'), 'utf8'))

const counts = {}
for (const [name, result] of results) {
  const [method, count] = name
  if (!counts[count]) counts[count] = {}
  counts[count][method] = result
}

function formatResult (stats) {
  const mean = stats.mean * 1e3
  const sd = stats.sd * 1e3
  return `${mean.toFixed(5)} ± ${sd.toFixed(5)} µs (n=${stats.n})`
}

const table = []
for (const count in counts) {
  const row = { count }
  for (const method in counts[count]) {
    row[method] = formatResult(counts[count][method])
  }
  table.push(row)
}

function printTable () {
  console.table(table)
}

function printMarkdown () {
  const header = Object.keys(table[0])
  const divider = Array(header.length).fill('---')
  const rows = table.map(row => header.map(key => row[key]))

  console.log([header, divider, ...rows].map(row => '|' + row.join('|') + '|').join('\n'))
}

function printTsv () {
  const header = Object.keys(table[0])
  const rows = table.map(row => header.map(key => row[key]))

  console.log([header, divider, ...rows].map(row => row.join('\t')).join('\n'))
}

printMarkdown()

data.ttl

<A1>
  <b1> "bar".

<A2>
  <b1> "bar";
  <b2> "bar".

<A3>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar".

<A4>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar".

<A5>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar".

<A6>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar".

<A7>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar".

<A8>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar".

<A9>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar".

<A10>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar".

<A11>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar".

<A12>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar";
  <b12> "bar".

<A13>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar";
  <b12> "bar";
  <b13> "bar".

<A14>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar";
  <b12> "bar";
  <b13> "bar";
  <b14> "bar".

<A15>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar";
  <b12> "bar";
  <b13> "bar";
  <b14> "bar";
  <b15> "bar".

<A16>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar";
  <b12> "bar";
  <b13> "bar";
  <b14> "bar";
  <b15> "bar";
  <b16> "bar".

<A17>
  <b1> "bar";
  <b2> "bar";
  <b3> "bar";
  <b4> "bar";
  <b5> "bar";
  <b6> "bar";
  <b7> "bar";
  <b8> "bar";
  <b9> "bar";
  <b10> "bar";
  <b11> "bar";
  <b12> "bar";
  <b13> "bar";
  <b14> "bar";
  <b15> "bar";
  <b16> "bar";
  <b17> "bar".

format-results.js

import fs from 'fs'
import path from 'path'

const results = JSON.parse(fs.readFileSync(path.resolve('output.json'), 'utf8'))

const counts = {}
for (const [name, result] of results) {
  const [method, count] = name
  if (!counts[count]) counts[count] = {}
  counts[count][method] = result
}

function formatResult (stats) {
  if (stats.mean < 1e-3) {
    const mean = stats.mean * 1e3
    const sd = stats.sd * 1e3
    return `${mean.toFixed(5)} ± ${sd.toFixed(5)} µs (n=${stats.n})`
  } else {
    return `${stats.mean.toFixed(5)} ± ${stats.sd.toFixed(5)} ms (n=${stats.n})`
  }
}

const table = []
for (const count in counts) {
  const row = { count }
  for (const method in counts[count]) {
    row[method] = formatResult(counts[count][method])
  }
  table.push(row)
}

console.table(table)

package.json

{
  "name": "043-shex-benchmarks",
  "private": true,
  "type": "module",
  "dependencies": {
    "@shexjs/neighborhood-rdfjs": "^1.0.0-alpha.29",
    "@shexjs/parser": "^1.0.0-alpha.28",
    "@shexjs/term": "^1.0.0-alpha.27",
    "@shexjs/validator": "^1.0.0-alpha.29",
    "n3": "^1.26.0",
    "the-square-hole": "^0.1.0"
  }
}

prepare-data.js

import fs from 'fs'

const DATA = buildData()
function buildData () {
  let schema = ''
  for (let i = 1; i <= 17; i++) {
    schema += `\n<A${i}>\n`
    for (let j = 1; j <= i; j++) {
      schema += `  <b${j}> "bar"` + ((j < i) ? ';\n' : '.\n')
    }
  }
  return schema
}

const SCHEMA = buildSchema()
function buildSchema () {
  let schema = ''
  for (let i = 1; i <= 17; i++) {
    schema += `\n<C${i}> IRI CLOSED {\n`
    for (let j = 1; j <= i; j++) {
      schema += `  <b${j}> LITERAL?` + ((j < i) ? ';\n' : '\n')
    }
    schema += '}\n\n'
  }
  return schema
}

fs.writeFileSync('data.ttl', DATA)
fs.writeFileSync('schema.shex', SCHEMA)

run-benchmark.js

import fs from 'fs'

import * as Benchmark from './benchmark.js'
import n3 from 'n3'
import ShExParser from '@shexjs/parser'

import ShExTerm from '@shexjs/term'
import RdfJs from '@shexjs/neighborhood-rdfjs'
import { ShExValidator } from '@shexjs/validator'

import { Validator as TshValidator } from 'the-square-hole'

const BASE = 'https://example.org/'
const DATA = fs.readFileSync('data.ttl', 'utf8')
const SCHEMA = fs.readFileSync('schema.shex', 'utf8')

async function loadData (data, base, format = 'turtle') {
  return new Promise(function (resolve, reject) {
    const parser = new n3.Parser({ baseIRI: base, format, blankNodePrefix: '' })
    const db = new n3.Store()
    parser.parse(data, function (error, quad, _prefixes) {
      if (error) {
        reject(error)
      } else if (quad) {
        db.addQuad(quad)
      } else {
        resolve(db)
      }
    })
  })
}

const data = await loadData(DATA, BASE)
const schema = ShExParser.construct(BASE, {}, { index: true }).parse(SCHEMA)
const shexValidator = new ShExValidator(schema, RdfJs.ctor(data))
const tshValidator = new TshValidator(schema, data)

const suite = new Benchmark.Suite({ maxRuntime: 100 })

for (let i = 1; i <= 17; i++) {
  const focus = BASE + 'A' + i
  const shape = BASE + 'C' + i

  const shexFocus = ShExTerm.ld2RdfJsTerm(focus)
  suite.add(['shex.js', i], function () {
    shexValidator.validateNodeShapePair(shexFocus, shape)
  })

  const tshFocus = n3.DataFactory.namedNode(focus)
  suite.add(['tsh', i], function () {
    tshValidator.validateNode(tshFocus, shape)
  })
}

suite.on('cycle', function (event) {
  console.error(event.target.name)
})

const results = await suite.run()

console.log(JSON.stringify([...results], null, 2))

schema.shex

<C1> IRI CLOSED {
  <b1> LITERAL?
}

<C2> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?
}

<C3> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?
}

<C4> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?
}

<C5> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?
}

<C6> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?
}

<C7> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?
}

<C8> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?
}

<C9> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?
}

<C10> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?
}

<C11> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?
}

<C12> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?;
  <b12> LITERAL?
}

<C13> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?;
  <b12> LITERAL?;
  <b13> LITERAL?
}

<C14> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?;
  <b12> LITERAL?;
  <b13> LITERAL?;
  <b14> LITERAL?
}

<C15> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?;
  <b12> LITERAL?;
  <b13> LITERAL?;
  <b14> LITERAL?;
  <b15> LITERAL?
}

<C16> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?;
  <b12> LITERAL?;
  <b13> LITERAL?;
  <b14> LITERAL?;
  <b15> LITERAL?;
  <b16> LITERAL?
}

<C17> IRI CLOSED {
  <b1> LITERAL?;
  <b2> LITERAL?;
  <b3> LITERAL?;
  <b4> LITERAL?;
  <b5> LITERAL?;
  <b6> LITERAL?;
  <b7> LITERAL?;
  <b8> LITERAL?;
  <b9> LITERAL?;
  <b10> LITERAL?;
  <b11> LITERAL?;
  <b12> LITERAL?;
  <b13> LITERAL?;
  <b14> LITERAL?;
  <b15> LITERAL?;
  <b16> LITERAL?;
  <b17> LITERAL?
}

To be clear, with eval-simple-1err (as shex.js2):

┌─────────┬───────┬──────────────────────────────────────┬────────────────────────────────┬────────────────────────────────┐
│ (index) │ count │ shex.js                              │ shex.js2                       │ tsh                            │
├─────────┼───────┼──────────────────────────────────────┼────────────────────────────────┼────────────────────────────────┤
│ 0       │ '1'   │ '2603.06500 ± 0.00000 µs (n=1)'      │ '952.85900 ± 0.00000 µs (n=1)' │ '546.94200 ± 0.00000 µs (n=1)' │
│ 1       │ '2'   │ '5719.00700 ± 0.00000 µs (n=1)'      │ '413.09200 ± 0.00000 µs (n=1)' │ '141.04800 ± 0.00000 µs (n=1)' │
│ 2       │ '3'   │ '509.83900 ± 0.00000 µs (n=1)'       │ '336.15200 ± 0.00000 µs (n=1)' │ '97.58200 ± 0.00000 µs (n=1)'  │
│ 3       │ '4'   │ '490.91000 ± 0.00000 µs (n=1)'       │ '369.44200 ± 0.00000 µs (n=1)' │ '119.54300 ± 0.00000 µs (n=1)' │
│ 4       │ '5'   │ '497.77100 ± 0.00000 µs (n=1)'       │ '390.12600 ± 0.00000 µs (n=1)' │ '134.38000 ± 0.00000 µs (n=1)' │
│ 5       │ '6'   │ '772.49400 ± 0.00000 µs (n=1)'       │ '352.21000 ± 0.00000 µs (n=1)' │ '131.85500 ± 0.00000 µs (n=1)' │
│ 6       │ '7'   │ '1186.96400 ± 0.00000 µs (n=1)'      │ '250.49500 ± 0.00000 µs (n=1)' │ '220.05500 ± 0.00000 µs (n=1)' │
│ 7       │ '8'   │ '2303.56900 ± 0.00000 µs (n=1)'      │ '447.42400 ± 0.00000 µs (n=1)' │ '112.89900 ± 0.00000 µs (n=1)' │
│ 8       │ '9'   │ '5406.37000 ± 0.00000 µs (n=1)'      │ '346.93300 ± 0.00000 µs (n=1)' │ '135.94600 ± 0.00000 µs (n=1)' │
│ 9       │ '10'  │ '14973.13700 ± 0.00000 µs (n=1)'     │ '362.50400 ± 0.00000 µs (n=1)' │ '101.74600 ± 0.00000 µs (n=1)' │
│ 10      │ '11'  │ '33032.41800 ± 0.00000 µs (n=1)'     │ '356.99400 ± 0.00000 µs (n=1)' │ '97.34300 ± 0.00000 µs (n=1)'  │
│ 11      │ '12'  │ '101453.36500 ± 0.00000 µs (n=1)'    │ '328.11200 ± 0.00000 µs (n=1)' │ '129.06500 ± 0.00000 µs (n=1)' │
│ 12      │ '13'  │ '326234.79700 ± 0.00000 µs (n=1)'    │ '394.73400 ± 0.00000 µs (n=1)' │ '111.81300 ± 0.00000 µs (n=1)' │
│ 13      │ '14'  │ '1239083.92500 ± 0.00000 µs (n=1)'   │ '474.85200 ± 0.00000 µs (n=1)' │ '129.35600 ± 0.00000 µs (n=1)' │
│ 14      │ '15'  │ '7489446.66200 ± 0.00000 µs (n=1)'   │ '460.03400 ± 0.00000 µs (n=1)' │ '116.54900 ± 0.00000 µs (n=1)' │
│ 15      │ '16'  │ '35470230.76300 ± 0.00000 µs (n=1)'  │ '519.87900 ± 0.00000 µs (n=1)' │ '132.17000 ± 0.00000 µs (n=1)' │
│ 16      │ '17'  │ '150254474.67100 ± 0.00000 µs (n=1)' │ '836.59300 ± 0.00000 µs (n=1)' │ '247.73500 ± 0.00000 µs (n=1)' │
└─────────┴───────┴──────────────────────────────────────┴────────────────────────────────┴────────────────────────────────┘