core/benchmarks/multi-hop-rule-bench.js

import { Arbiter } from '../src/core/Arbiter.js';

function parseArgs(argv) {
  const args = new Map();
  for (let i = 2; i < argv.length; i++) {
    const value = argv[i];
    if (!value.startsWith('--')) continue;
    const [key, inline] = value.slice(2).split('=');
    if (inline !== undefined) {
      args.set(key, inline);
      continue;
    }
    const next = argv[i + 1];
    if (next && !next.startsWith('--')) {
      args.set(key, next);
      i++;
    } else {
      args.set(key, true);
    }
  }
  return args;
}

function parseSizes(value) {
  if (!value) return null;
  return value.split(',').map(item => Number(item.trim())).filter(Number.isFinite);
}

function createRng(seed) {
  let state = seed >>> 0;
  return () => {
    state = (1664525 * state + 1013904223) >>> 0;
    return state / 0x100000000;
  };
}

function randInt(rng, max) {
  return Math.floor(rng() * max);
}

function buildNodes(arbiter, count, prefix) {
  for (let i = 0; i < count; i++) {
    arbiter.addNode(`${prefix}:${i}`, prefix);
  }
}

function buildScenario(arbiter, size, edgeFactor, rng) {
  const nodes = size;
  buildNodes(arbiter, nodes, 'user');
  buildNodes(arbiter, nodes, 'resource');

  for (let i = 0; i < nodes; i++) {
    arbiter.addRelation(`user:${i}`, 'link', `resource:${i}`, 1.0);
  }

  const extraEdges = Math.max(0, Math.floor(nodes * edgeFactor));
  for (let i = 0; i < extraEdges; i++) {
    const src = randInt(rng, nodes);
    const dst = randInt(rng, nodes);
    if (src === dst) continue;
    arbiter.addRelation(`user:${src}`, 'link', `resource:${dst}`, 1.0, { value: (src + dst) % 100 });
  }

  arbiter.setRelationConfig('link', { type: 'direct' });
  arbiter.setRelationConfig('multi_hop_link', {
    type: 'multi_hop',
    relation: 'link',
    maxDepth: 3,
    pathAggregation: 'max',
    collectValues: false,
    trackPaths: false
  });
}

function buildQueries(size, rng, samples) {
  const queries = [];
  for (let i = 0; i < samples; i++) {
    const userId = randInt(rng, size);
    const objectId = randInt(rng, size);
    queries.push({ userKey: `user:${userId}`, objectKey: `resource:${objectId}` });
  }
  return queries;
}

function measure(label, iterations, fn) {
  const start = process.hrtime.bigint();
  for (let i = 0; i < iterations; i++) fn();
  const elapsedMs = Number(process.hrtime.bigint() - start) / 1e6;
  return { label, elapsedMs, qps: elapsedMs > 0 ? Math.round((iterations / elapsedMs) * 1000) : 0 };
}

function measureMedian(label, iterations, fn, warmups, runs) {
  for (let w = 0; w < warmups; w++) {
    for (let i = 0; i < iterations; i++) fn();
  }

  const samples = [];
  for (let r = 0; r < runs; r++) {
    samples.push(measure(label, iterations, fn).qps);
  }

  samples.sort((a, b) => a - b);
  const mid = Math.floor(samples.length / 2);
  const median = samples.length % 2 === 0
    ? Math.round(((samples[mid - 1] + samples[mid]) / 2) * 100) / 100
    : samples[mid];
  return { label, elapsedMs: null, qps: median };
}

const args = parseArgs(process.argv);
const config = {
  sizes: parseSizes(args.get('sizes')) || [2000, 5000, 10000],
  samples: Number(args.get('samples') || 2000),
  seed: Number(args.get('seed') || 42),
  edgeFactor: Number(args.get('edge-factor') || 1.5),
  includeMeta: !args.has('no-meta'),
  collectValues: !args.has('no-values'),
  warmupRuns: Number(args.get('warmup-runs') || 2),
  medianRuns: Number(args.get('median-runs') || 5),
  relationGraph: args.has('relation-graph')
};

console.log('multi_hop_rule_bench');
console.log('size,samples,meta,values,relation_graph,metric,elapsed_ms,qps');

for (const size of config.sizes) {
  const rng = createRng(config.seed + size);
  const arbiter = new Arbiter({ useRelationGraphTraversal: config.relationGraph });
  buildScenario(arbiter, size, config.edgeFactor, rng);
  const queries = buildQueries(size, rng, config.samples);
  const baseOptions = { fastPath: true, includeMeta: config.includeMeta, collectValues: config.collectValues };

  const multiHop = measureMedian('multi_hop', queries.length, () => {
    const q = queries[randInt(rng, queries.length)];
    arbiter.check(q.userKey, 'multi_hop_link', q.objectKey, baseOptions);
  }, config.warmupRuns, config.medianRuns);

  console.log([
    size,
    queries.length,
    config.includeMeta ? 'on' : 'off',
    config.collectValues ? 'on' : 'off',
    config.relationGraph ? 'on' : 'off',
    multiHop.label,
    multiHop.elapsedMs === null ? 'median' : Math.round(multiHop.elapsedMs),
    multiHop.qps
  ].join(','));
}