385 lines
12 KiB
JavaScript
385 lines
12 KiB
JavaScript
|
/**
|
||
|
|
* Reachability Optimization Benchmark
|
||
|
|
*
|
||
|
|
* This benchmark tests the performance improvements from implementing
|
||
|
|
* 2-hop labeling and tree-cover indexing based on the reachability papers.
|
||
|
|
*/
|
||
|
|
|
||
|
|
import { Arbiter } from '../src/core/Arbiter.js';
|
||
|
|
|
||
|
|
class ReachabilityOptimizationBenchmark {
|
||
|
|
constructor() {
|
||
|
|
this.arbiter = new Arbiter({
|
||
|
|
fastConstructionMode: true,
|
||
|
|
lazyStaleMarking: true
|
||
|
|
});
|
||
|
|
|
||
|
|
this.results = {
|
||
|
|
traditional: {},
|
||
|
|
twoHop: {},
|
||
|
|
treeCover: {},
|
||
|
|
hybrid: {}
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Setup test data with various graph structures
|
||
|
|
*/
|
||
|
|
setupTestData() {
|
||
|
|
console.log('🏗️ Setting up test data...');
|
||
|
|
|
||
|
|
// Create nodes
|
||
|
|
const users = [];
|
||
|
|
const groups = [];
|
||
|
|
const projects = [];
|
||
|
|
const documents = [];
|
||
|
|
|
||
|
|
// Create users
|
||
|
|
for (let i = 0; i < 1000; i++) {
|
||
|
|
const userKey = `user_${i}`;
|
||
|
|
this.arbiter.addNode(userKey, 'user', { name: `User ${i}` });
|
||
|
|
users.push(userKey);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create groups
|
||
|
|
for (let i = 0; i < 100; i++) {
|
||
|
|
const groupKey = `group_${i}`;
|
||
|
|
this.arbiter.addNode(groupKey, 'group', { name: `Group ${i}` });
|
||
|
|
groups.push(groupKey);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create projects
|
||
|
|
for (let i = 0; i < 50; i++) {
|
||
|
|
const projectKey = `project_${i}`;
|
||
|
|
this.arbiter.addNode(projectKey, 'project', { name: `Project ${i}` });
|
||
|
|
projects.push(projectKey);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create documents
|
||
|
|
for (let i = 0; i < 200; i++) {
|
||
|
|
const docKey = `doc_${i}`;
|
||
|
|
this.arbiter.addNode(docKey, 'document', { name: `Document ${i}` });
|
||
|
|
documents.push(docKey);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create hierarchical relationships
|
||
|
|
this._createHierarchicalRelations(users, groups, projects, documents);
|
||
|
|
|
||
|
|
// Create cross-cutting relationships
|
||
|
|
this._createCrossCuttingRelations(users, groups, projects, documents);
|
||
|
|
|
||
|
|
console.log(`✅ Created ${this.arbiter.nodes.size} nodes and ${this.arbiter.relations.length} relations`);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Create hierarchical relationships (users -> groups -> projects -> documents)
|
||
|
|
*/
|
||
|
|
_createHierarchicalRelations(users, groups, projects, documents) {
|
||
|
|
// Users join groups
|
||
|
|
for (let i = 0; i < users.length; i++) {
|
||
|
|
const user = users[i];
|
||
|
|
const groupIndex = Math.floor(Math.random() * groups.length);
|
||
|
|
const group = groups[groupIndex];
|
||
|
|
this.arbiter.addRelation(user, 'member_of', group, { possibility: 1.0 });
|
||
|
|
}
|
||
|
|
|
||
|
|
// Groups own projects
|
||
|
|
for (let i = 0; i < groups.length; i++) {
|
||
|
|
const group = groups[i];
|
||
|
|
const projectCount = Math.floor(Math.random() * 3) + 1; // 1-3 projects per group
|
||
|
|
for (let j = 0; j < projectCount; j++) {
|
||
|
|
const projectIndex = Math.floor(Math.random() * projects.length);
|
||
|
|
const project = projects[projectIndex];
|
||
|
|
this.arbiter.addRelation(group, 'owns', project, { possibility: 1.0 });
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Projects contain documents
|
||
|
|
for (let i = 0; i < projects.length; i++) {
|
||
|
|
const project = projects[i];
|
||
|
|
const docCount = Math.floor(Math.random() * 5) + 1; // 1-5 docs per project
|
||
|
|
for (let j = 0; j < docCount; j++) {
|
||
|
|
const docIndex = Math.floor(Math.random() * documents.length);
|
||
|
|
const doc = documents[docIndex];
|
||
|
|
this.arbiter.addRelation(project, 'contains', doc, { possibility: 1.0 });
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Create cross-cutting relationships
|
||
|
|
*/
|
||
|
|
_createCrossCuttingRelations(users, groups, projects, documents) {
|
||
|
|
// Some users have direct access to projects
|
||
|
|
for (let i = 0; i < 50; i++) {
|
||
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
||
|
|
const project = projects[Math.floor(Math.random() * projects.length)];
|
||
|
|
this.arbiter.addRelation(user, 'direct_access', project, { possibility: 1.0 });
|
||
|
|
}
|
||
|
|
|
||
|
|
// Some groups have cross-project access
|
||
|
|
for (let i = 0; i < 20; i++) {
|
||
|
|
const group = groups[Math.floor(Math.random() * groups.length)];
|
||
|
|
const project = projects[Math.floor(Math.random() * projects.length)];
|
||
|
|
this.arbiter.addRelation(group, 'cross_access', project, { possibility: 1.0 });
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Benchmark traditional reachability (basic traversal)
|
||
|
|
*/
|
||
|
|
async benchmarkTraditional() {
|
||
|
|
console.log('🔍 Benchmarking traditional reachability...');
|
||
|
|
|
||
|
|
const queries = this._generateTestQueries(1000);
|
||
|
|
const startTime = Date.now();
|
||
|
|
|
||
|
|
let results = 0;
|
||
|
|
for (const query of queries) {
|
||
|
|
const isReachable = this._traditionalReachability(query.source, query.target);
|
||
|
|
if (isReachable) results++;
|
||
|
|
}
|
||
|
|
|
||
|
|
const endTime = Date.now();
|
||
|
|
const duration = endTime - startTime;
|
||
|
|
|
||
|
|
this.results.traditional = {
|
||
|
|
duration,
|
||
|
|
queries: queries.length,
|
||
|
|
results,
|
||
|
|
qps: Math.round((queries.length / duration) * 1000),
|
||
|
|
averageTime: duration / queries.length
|
||
|
|
};
|
||
|
|
|
||
|
|
console.log(`✅ Traditional: ${this.results.traditional.qps} QPS, ${this.results.traditional.averageTime.toFixed(3)}ms avg`);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Benchmark 2-hop indexing
|
||
|
|
*/
|
||
|
|
async benchmarkTwoHop() {
|
||
|
|
console.log('🔍 Benchmarking 2-hop indexing...');
|
||
|
|
|
||
|
|
// Initialize 2-hop index
|
||
|
|
const initStart = Date.now();
|
||
|
|
await this.arbiter.initializeReachabilityChecker({ strategy: 'twohop' });
|
||
|
|
const initTime = Date.now() - initStart;
|
||
|
|
|
||
|
|
const queries = this._generateTestQueries(1000);
|
||
|
|
const startTime = Date.now();
|
||
|
|
|
||
|
|
let results = 0;
|
||
|
|
for (const query of queries) {
|
||
|
|
const isReachable = this.arbiter.isReachable(query.source, query.target);
|
||
|
|
if (isReachable) results++;
|
||
|
|
}
|
||
|
|
|
||
|
|
const endTime = Date.now();
|
||
|
|
const duration = endTime - startTime;
|
||
|
|
|
||
|
|
this.results.twoHop = {
|
||
|
|
initTime,
|
||
|
|
duration,
|
||
|
|
queries: queries.length,
|
||
|
|
results,
|
||
|
|
qps: Math.round((queries.length / duration) * 1000),
|
||
|
|
averageTime: duration / queries.length,
|
||
|
|
stats: this.arbiter.getReachabilityStats()
|
||
|
|
};
|
||
|
|
|
||
|
|
console.log(`✅ 2-hop: ${this.results.twoHop.qps} QPS, ${this.results.twoHop.averageTime.toFixed(3)}ms avg, init: ${initTime}ms`);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Benchmark tree-cover indexing
|
||
|
|
*/
|
||
|
|
async benchmarkTreeCover() {
|
||
|
|
console.log('🔍 Benchmarking tree-cover indexing...');
|
||
|
|
|
||
|
|
// Initialize tree-cover index
|
||
|
|
const initStart = Date.now();
|
||
|
|
await this.arbiter.initializeReachabilityChecker({ strategy: 'treecover' });
|
||
|
|
const initTime = Date.now() - initStart;
|
||
|
|
|
||
|
|
const queries = this._generateTestQueries(1000);
|
||
|
|
const startTime = Date.now();
|
||
|
|
|
||
|
|
let results = 0;
|
||
|
|
for (const query of queries) {
|
||
|
|
const isReachable = this.arbiter.isReachable(query.source, query.target);
|
||
|
|
if (isReachable) results++;
|
||
|
|
}
|
||
|
|
|
||
|
|
const endTime = Date.now();
|
||
|
|
const duration = endTime - startTime;
|
||
|
|
|
||
|
|
this.results.treeCover = {
|
||
|
|
initTime,
|
||
|
|
duration,
|
||
|
|
queries: queries.length,
|
||
|
|
results,
|
||
|
|
qps: Math.round((queries.length / duration) * 1000),
|
||
|
|
averageTime: duration / queries.length,
|
||
|
|
stats: this.arbiter.getReachabilityStats()
|
||
|
|
};
|
||
|
|
|
||
|
|
console.log(`✅ Tree-cover: ${this.results.treeCover.qps} QPS, ${this.results.treeCover.averageTime.toFixed(3)}ms avg, init: ${initTime}ms`);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Benchmark hybrid approach
|
||
|
|
*/
|
||
|
|
async benchmarkHybrid() {
|
||
|
|
console.log('🔍 Benchmarking hybrid approach...');
|
||
|
|
|
||
|
|
// Initialize hybrid index
|
||
|
|
const initStart = Date.now();
|
||
|
|
await this.arbiter.initializeReachabilityChecker({ strategy: 'hybrid' });
|
||
|
|
const initTime = Date.now() - initStart;
|
||
|
|
|
||
|
|
const queries = this._generateTestQueries(1000);
|
||
|
|
const startTime = Date.now();
|
||
|
|
|
||
|
|
let results = 0;
|
||
|
|
for (const query of queries) {
|
||
|
|
const isReachable = this.arbiter.isReachable(query.source, query.target);
|
||
|
|
if (isReachable) results++;
|
||
|
|
}
|
||
|
|
|
||
|
|
const endTime = Date.now();
|
||
|
|
const duration = endTime - startTime;
|
||
|
|
|
||
|
|
this.results.hybrid = {
|
||
|
|
initTime,
|
||
|
|
duration,
|
||
|
|
queries: queries.length,
|
||
|
|
results,
|
||
|
|
qps: Math.round((queries.length / duration) * 1000),
|
||
|
|
averageTime: duration / queries.length,
|
||
|
|
stats: this.arbiter.getReachabilityStats()
|
||
|
|
};
|
||
|
|
|
||
|
|
console.log(`✅ Hybrid: ${this.results.hybrid.qps} QPS, ${this.results.hybrid.averageTime.toFixed(3)}ms avg, init: ${initTime}ms`);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Traditional reachability using basic BFS
|
||
|
|
*/
|
||
|
|
_traditionalReachability(sourceKey, targetKey) {
|
||
|
|
if (sourceKey === targetKey) return true;
|
||
|
|
|
||
|
|
const visited = new Set();
|
||
|
|
const queue = [sourceKey];
|
||
|
|
visited.add(sourceKey);
|
||
|
|
|
||
|
|
while (queue.length > 0) {
|
||
|
|
const current = queue.shift();
|
||
|
|
|
||
|
|
// Find outgoing relations
|
||
|
|
const outgoing = this.arbiter.relations.filter(r => {
|
||
|
|
const srcKey = this.arbiter.keyByNodeId.get(r.src);
|
||
|
|
return srcKey === current;
|
||
|
|
});
|
||
|
|
|
||
|
|
for (const relation of outgoing) {
|
||
|
|
const nextKey = this.arbiter.keyByNodeId.get(relation.dst);
|
||
|
|
if (nextKey === targetKey) return true;
|
||
|
|
if (!visited.has(nextKey)) {
|
||
|
|
visited.add(nextKey);
|
||
|
|
queue.push(nextKey);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Generate test queries
|
||
|
|
*/
|
||
|
|
_generateTestQueries(count) {
|
||
|
|
const queries = [];
|
||
|
|
const allKeys = Array.from(this.arbiter.nodes.keys());
|
||
|
|
|
||
|
|
for (let i = 0; i < count; i++) {
|
||
|
|
const source = allKeys[Math.floor(Math.random() * allKeys.length)];
|
||
|
|
const target = allKeys[Math.floor(Math.random() * allKeys.length)];
|
||
|
|
queries.push({ source, target });
|
||
|
|
}
|
||
|
|
|
||
|
|
return queries;
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Run all benchmarks
|
||
|
|
*/
|
||
|
|
async runBenchmarks() {
|
||
|
|
console.log('🚀 Starting Reachability Optimization Benchmarks\n');
|
||
|
|
|
||
|
|
// Setup test data
|
||
|
|
this.setupTestData();
|
||
|
|
|
||
|
|
// Run benchmarks
|
||
|
|
await this.benchmarkTraditional();
|
||
|
|
await this.benchmarkTwoHop();
|
||
|
|
await this.benchmarkTreeCover();
|
||
|
|
await this.benchmarkHybrid();
|
||
|
|
|
||
|
|
// Print results
|
||
|
|
this.printResults();
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Print benchmark results
|
||
|
|
*/
|
||
|
|
printResults() {
|
||
|
|
console.log('\n📊 Reachability Optimization Results\n');
|
||
|
|
|
||
|
|
const methods = ['traditional', 'twoHop', 'treeCover', 'hybrid'];
|
||
|
|
const methodNames = ['Traditional', '2-Hop', 'Tree-Cover', 'Hybrid'];
|
||
|
|
|
||
|
|
console.log('Method | QPS | Avg Time | Init Time | Speedup');
|
||
|
|
console.log('----------------------|----------|----------|-----------|--------');
|
||
|
|
|
||
|
|
const baselineQps = this.results.traditional.qps;
|
||
|
|
|
||
|
|
for (let i = 0; i < methods.length; i++) {
|
||
|
|
const method = methods[i];
|
||
|
|
const result = this.results[method];
|
||
|
|
const speedup = result.qps / baselineQps;
|
||
|
|
const initTime = result.initTime ? `${result.initTime}ms` : 'N/A';
|
||
|
|
|
||
|
|
console.log(
|
||
|
|
`${methodNames[i].padEnd(20)} | ${result.qps.toString().padStart(8)} | ${result.averageTime.toFixed(3)}ms`.padEnd(8) +
|
||
|
|
` | ${initTime.padStart(9)} | ${speedup.toFixed(2)}x`
|
||
|
|
);
|
||
|
|
}
|
||
|
|
|
||
|
|
console.log('\n🎯 Key Insights:');
|
||
|
|
|
||
|
|
// Find best performer
|
||
|
|
const bestMethod = methods.reduce((best, method) =>
|
||
|
|
this.results[method].qps > this.results[best].qps ? method : best
|
||
|
|
);
|
||
|
|
|
||
|
|
const bestSpeedup = this.results[bestMethod].qps / baselineQps;
|
||
|
|
console.log(`• Best performer: ${methodNames[methods.indexOf(bestMethod)]} (${bestSpeedup.toFixed(2)}x speedup)`);
|
||
|
|
|
||
|
|
// Memory usage insights
|
||
|
|
if (this.results.twoHop.stats) {
|
||
|
|
console.log(`• 2-hop index size: ${this.results.twoHop.stats.twoHopStats?.labelSize || 'N/A'} labels`);
|
||
|
|
}
|
||
|
|
|
||
|
|
if (this.results.treeCover.stats) {
|
||
|
|
console.log(`• Tree-cover trees: ${this.results.treeCover.stats.treeCoverStats?.treeCount || 'N/A'}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
console.log(`• Total queries: ${this.results.traditional.queries}`);
|
||
|
|
console.log(`• Graph size: ${this.arbiter.nodes.size} nodes, ${this.arbiter.relations.length} edges`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Run the benchmark
|
||
|
|
const benchmark = new ReachabilityOptimizationBenchmark();
|
||
|
|
benchmark.runBenchmarks().catch(console.error);
|