perf: 检索图链接别名解析逐边扫描全部节点，导致 O(N×E) 同步耗时

node benchmark-link-resolution.mjs > results.json
# 可选：核对本地源码与固定基线完全相同，再运行
node benchmark-link-resolution.mjs --repo /path/to/llm_wiki > results.json

#!/usr/bin/env node
/**
 * Baseline: e8082119649e6a8e1cf85eaf289adcabfdf39d4e
 * Source: src/lib/graph-relevance.ts:124-138
 * Runs only the original resolver, with generated alias and exact-ID inputs.
 * Synchronous CPU microbenchmark; excludes I/O, LLM calls and UI rendering.
 */
import assert from 'node:assert/strict';
import fs from 'node:fs';
import os from 'node:os';
import path from 'node:path';
import { performance } from 'node:perf_hooks';

const COMMIT = 'e8082119649e6a8e1cf85eaf289adcabfdf39d4e';
const embeddedSource = `function resolveTarget(
  raw: string,
  nodeIds: ReadonlySet<string>,
): string | null {
  if (nodeIds.has(raw)) return raw

  const normalized = raw.toLowerCase().replace(/\\s+/g, "-")
  for (const id of nodeIds) {
    const idLower = id.toLowerCase()
    if (idLower === normalized) return id
    if (idLower === raw.toLowerCase()) return id
    if (idLower.replace(/\\s+/g, "-") === normalized) return id
  }
  return null
}`;

let source = embeddedSource;
const repoArg = process.argv.indexOf('--repo');
if (repoArg !== -1) {
  const root = process.argv[repoArg + 1];
  if (!root) throw new Error('--repo requires a repository directory');
  const text = fs.readFileSync(path.join(root, 'src/lib/graph-relevance.ts'), 'utf8');
  const match = text.match(/function resolveTarget\([\s\S]*?\n\}/);
  if (!match) throw new Error('resolveTarget function not found');
  source = match[0].replace(/\r\n/g, '\n');
  assert.equal(source, embeddedSource, 'Source differs from pinned baseline; review benchmark before use.');
}
const jsSource = source.replace('raw: string', 'raw')
  .replace('nodeIds: ReadonlySet<string>', 'nodeIds')
  .replace('): string | null {', ') {');
const originalResolve = new Function(`return (${jsSource});`)();

function makeFixture(n, mode = 'alias') {
  const ids = Array.from({ length: n }, (_, i) => `page-${String(i).padStart(5, '0')}`);
  const nodeIds = new Set(ids);
  const targets = [], expected = [];
  const offsets = [1, 7, 17, 31, 53, 97, 193, 389];
  for (let i = 0; i < n; i++) {
    for (const offset of offsets) {
      const j = (i + offset) % n;
      targets.push(mode === 'exact' ? ids[j] : `Page ${String(j).padStart(5, '0')}`);
      expected.push(ids[j]);
    }
  }
  return { nodeIds, targets, expected };
}

function runOriginal({ nodeIds, targets }) {
  const output = new Array(targets.length);
  for (let i = 0; i < targets.length; i++) output[i] = originalResolve(targets[i], nodeIds);
  return output;
}

const median = values => [...values].sort((a, b) => a - b)[Math.floor(values.length / 2)];
let sink;
function timed(fixture) {
  const start = performance.now();
  sink = runOriginal(fixture);
  return performance.now() - start;
}

function measure(n, mode = 'alias') {
  const fixture = makeFixture(n, mode);
  assert.deepEqual(runOriginal(fixture), fixture.expected);
  for (let i = 0; i < 2; i++) timed(fixture);
  const samples = Array.from({ length: 5 }, () => timed(fixture));
  return {
    pages: n,
    links: fixture.targets.length,
    mode,
    // Derived from uniform target coverage, not measured with instrumentation.
    baselineCandidateVisits: mode === 'alias' ? 8 * n * (n + 1) / 2 : 0,
    baselineMedianMs: median(samples),
    baselineSamplesMs: samples,
  };
}

const rows = [1000, 2000, 3000].map(n => measure(n));
const exactMatchControl = measure(3000, 'exact');
console.log(JSON.stringify({
  baselineCommit: COMMIT,
  baselinePath: 'src/lib/graph-relevance.ts:124-138',
  environment: {
    node: process.version,
    platform: process.platform,
    architecture: process.arch,
    cpu: os.cpus()[0]?.model,
  },
  method: {
    linksPerPage: 8,
    alias: 'Page 00042 -> page-00042',
    warmupPasses: 2,
    measuredPasses: 5,
    reportedStatistic: 'median',
    userDataUsed: false,
    scope: 'synchronous link resolution only; excludes I/O, LLM, UI rendering',
  },
  rows,
  exactMatchControl,
  sinkLength: sink.length,
}, null, 2));