311 lines
11 KiB
Rust
311 lines
11 KiB
Rust
#![allow(
|
|
clippy::unwrap_used,
|
|
clippy::cast_precision_loss,
|
|
clippy::cast_possible_truncation
|
|
)]
|
|
|
|
//! Criterion benchmarks for social graph filter and co-engagement operations.
|
|
//!
|
|
//! Validates the spec performance target: `social_graph` filter at depth=2
|
|
//! with 20 users / 10 followed creators completes in < 50ms.
|
|
//!
|
|
//! Also measures:
|
|
//! - `CoEngagementIndex::record_positive` at capacity (eviction path)
|
|
//! - `CoEngagementIndex::score` on a populated index
|
|
|
|
use criterion::{BenchmarkId, Criterion, black_box, criterion_group, criterion_main};
|
|
use tidaldb::entities::{CoEngagementIndex, CreatorItemsBitmap, PreferenceVectors, UserStateIndex};
|
|
use tidaldb::query::executor::social_filter::{resolve_social_subgraph_users, social_graph_bitmap};
|
|
use tidaldb::schema::EntityId;
|
|
|
|
// ── Social graph bitmap benchmark ─────────────────────────────────────────────
|
|
|
|
/// Build a social graph with `num_creators` followed creators, each having
|
|
/// `followers_per_creator` followers, and `items_per_creator` items.
|
|
fn build_social_state(
|
|
num_creators: usize,
|
|
followers_per_creator: usize,
|
|
items_per_creator: usize,
|
|
) -> (UserStateIndex, CreatorItemsBitmap) {
|
|
let user_state = UserStateIndex::new();
|
|
let creator_items = CreatorItemsBitmap::new();
|
|
|
|
let user_id = 1u64;
|
|
|
|
for c in 0..num_creators {
|
|
let creator_id = (100 + c) as u64;
|
|
|
|
// User 1 follows this creator.
|
|
user_state.add_follow(user_id, creator_id);
|
|
user_state.add_creator_follower(creator_id, user_id);
|
|
|
|
// Other followers for this creator.
|
|
for f in 0..followers_per_creator {
|
|
let follower_id = (1000 + c * followers_per_creator + f) as u64;
|
|
user_state.add_creator_follower(creator_id, follower_id);
|
|
// Each co-follower has seen some items (for depth-2 expansion).
|
|
for i in 0..5u32 {
|
|
user_state.mark_seen(follower_id, (follower_id as u32) * 100 + i);
|
|
}
|
|
}
|
|
|
|
// Items from this creator.
|
|
for i in 0..items_per_creator {
|
|
let item_id = ((c * items_per_creator + i) as u32) + 1;
|
|
creator_items.add_item(creator_id, item_id);
|
|
}
|
|
}
|
|
|
|
(user_state, creator_items)
|
|
}
|
|
|
|
fn bench_social_graph_bitmap(c: &mut Criterion) {
|
|
let mut group = c.benchmark_group("social_graph_bitmap");
|
|
|
|
// Spec scenario: 10 followed creators, 20 co-followers per creator, 50 items per creator.
|
|
let (user_state, creator_items) = build_social_state(10, 20, 50);
|
|
|
|
group.bench_function("depth1_10creators_50items", |b| {
|
|
b.iter(|| social_graph_bitmap(black_box(1), black_box(1), &user_state, &creator_items));
|
|
});
|
|
|
|
group.bench_function("depth2_10creators_20followers_50items", |b| {
|
|
b.iter(|| social_graph_bitmap(black_box(1), black_box(2), &user_state, &creator_items));
|
|
});
|
|
|
|
// Larger scenario: stress test fan-out cap.
|
|
let (user_state_large, creator_items_large) = build_social_state(10, 100, 100);
|
|
|
|
group.bench_function("depth2_10creators_100followers_100items", |b| {
|
|
b.iter(|| {
|
|
social_graph_bitmap(
|
|
black_box(1),
|
|
black_box(2),
|
|
&user_state_large,
|
|
&creator_items_large,
|
|
)
|
|
});
|
|
});
|
|
|
|
group.finish();
|
|
}
|
|
|
|
fn bench_resolve_social_subgraph(c: &mut Criterion) {
|
|
let mut group = c.benchmark_group("resolve_social_subgraph_users");
|
|
|
|
let (user_state, _) = build_social_state(10, 20, 50);
|
|
|
|
group.bench_function("depth1_10creators_20followers", |b| {
|
|
b.iter(|| resolve_social_subgraph_users(black_box(1), black_box(1), &user_state));
|
|
});
|
|
|
|
group.bench_function("depth2_10creators_20followers", |b| {
|
|
b.iter(|| resolve_social_subgraph_users(black_box(1), black_box(2), &user_state));
|
|
});
|
|
|
|
group.finish();
|
|
}
|
|
|
|
// ── CoEngagementIndex benchmarks ─────────────────────────────────────────────
|
|
|
|
fn bench_co_engagement(c: &mut Criterion) {
|
|
let mut group = c.benchmark_group("co_engagement");
|
|
|
|
// Benchmark score lookup on a populated index.
|
|
let index = CoEngagementIndex::new();
|
|
for user in 1..=50u64 {
|
|
for item in 1..=20u64 {
|
|
index.record_positive(user, EntityId::new(item));
|
|
}
|
|
}
|
|
|
|
group.bench_function("score_populated", |b| {
|
|
b.iter(|| index.score(black_box(EntityId::new(10)), black_box(EntityId::new(5))));
|
|
});
|
|
|
|
// Benchmark record_positive at capacity (eviction fires).
|
|
group.bench_function("record_positive_at_capacity_1k", |b| {
|
|
let cap_index = CoEngagementIndex::with_capacity(1_000);
|
|
// Pre-fill to capacity.
|
|
for user in 1..=40u64 {
|
|
for item in 1..=25u64 {
|
|
cap_index.record_positive(user, EntityId::new(item));
|
|
}
|
|
}
|
|
// Now benchmark a single record_positive that triggers eviction.
|
|
b.iter(|| {
|
|
cap_index.record_positive(black_box(999), black_box(EntityId::new(42)));
|
|
});
|
|
});
|
|
|
|
// Benchmark record_positive at default 50K capacity.
|
|
group.bench_function("record_positive_at_capacity_50k", |b| {
|
|
let cap_index = CoEngagementIndex::with_capacity(50_000);
|
|
// Pre-fill close to capacity.
|
|
for user in 1..=200u64 {
|
|
for item in 1..=50u64 {
|
|
cap_index.record_positive(user, EntityId::new(item));
|
|
}
|
|
}
|
|
b.iter(|| {
|
|
cap_index.record_positive(black_box(9999), black_box(EntityId::new(77)));
|
|
});
|
|
});
|
|
|
|
group.finish();
|
|
}
|
|
|
|
// ── Social graph at 1M items ──────────────────────────────────────────────────
|
|
|
|
/// Build a social graph at production scale: 100 followed creators,
|
|
/// 500 followers/creator, 10K items/creator = 1M items total.
|
|
fn build_1m_social_state() -> (UserStateIndex, CreatorItemsBitmap) {
|
|
let user_state = UserStateIndex::new();
|
|
let creator_items = CreatorItemsBitmap::new();
|
|
let user_id = 1u64;
|
|
|
|
for c in 0..100usize {
|
|
let creator_id = (100 + c) as u64;
|
|
user_state.add_follow(user_id, creator_id);
|
|
user_state.add_creator_follower(creator_id, user_id);
|
|
|
|
// 500 other followers per creator.
|
|
for f in 0..500usize {
|
|
let follower_id = (10_000 + c * 500 + f) as u64;
|
|
user_state.add_creator_follower(creator_id, follower_id);
|
|
}
|
|
|
|
// 10K items per creator = 1M total.
|
|
for i in 0..10_000usize {
|
|
let item_id = ((c * 10_000 + i) as u32) + 1;
|
|
creator_items.add_item(creator_id, item_id);
|
|
}
|
|
}
|
|
|
|
(user_state, creator_items)
|
|
}
|
|
|
|
fn bench_social_graph_1m_items(c: &mut Criterion) {
|
|
let (user_state, creator_items) = build_1m_social_state();
|
|
let mut group = c.benchmark_group("social_graph_1m");
|
|
|
|
group.bench_function("depth1_100creators_1m_items", |b| {
|
|
b.iter(|| social_graph_bitmap(black_box(1), black_box(1), &user_state, &creator_items));
|
|
});
|
|
|
|
group.bench_function("depth2_100creators_500followers_1m_items", |b| {
|
|
b.iter(|| social_graph_bitmap(black_box(1), black_box(2), &user_state, &creator_items));
|
|
});
|
|
|
|
group.finish();
|
|
}
|
|
|
|
// ── Cross-session preference merge ───────────────────────────────────────────
|
|
|
|
/// Benchmark `PreferenceVectors::update_with_custom_rate()` for 128D EMA update.
|
|
///
|
|
/// Targets: single merge < 1ms, 10-session batch < 10ms.
|
|
fn bench_preference_merge(c: &mut Criterion) {
|
|
const DIM: usize = 128;
|
|
let prefs = PreferenceVectors::new(DIM);
|
|
|
|
// Pre-populate 100K users.
|
|
for user_id in 0u64..100_000 {
|
|
let mut emb: Vec<f32> = (0..DIM)
|
|
.map(|i| ((user_id + i as u64) % 7) as f32)
|
|
.collect();
|
|
let norm: f32 = emb.iter().map(|x| x * x).sum::<f32>().sqrt();
|
|
if norm > f32::EPSILON {
|
|
for x in &mut emb {
|
|
*x /= norm;
|
|
}
|
|
}
|
|
prefs.update_with_custom_rate(user_id, &emb, 0.1);
|
|
}
|
|
|
|
let interaction: Vec<f32> = {
|
|
let mut v: Vec<f32> = (0..DIM).map(|i| (i % 5) as f32).collect();
|
|
let norm: f32 = v.iter().map(|x| x * x).sum::<f32>().sqrt();
|
|
if norm > f32::EPSILON {
|
|
for x in &mut v {
|
|
*x /= norm;
|
|
}
|
|
}
|
|
v
|
|
};
|
|
|
|
let mut group = c.benchmark_group("preference_merge");
|
|
|
|
group.bench_function("single_128d_ema_100k_users", |b| {
|
|
let mut user_id = 0u64;
|
|
b.iter(|| {
|
|
prefs.update_with_custom_rate(
|
|
black_box(user_id % 100_000),
|
|
black_box(&interaction),
|
|
0.1,
|
|
);
|
|
user_id += 1;
|
|
});
|
|
});
|
|
|
|
group.bench_function("10_session_batch_128d_100k_users", |b| {
|
|
let mut user_id = 0u64;
|
|
b.iter(|| {
|
|
for _ in 0..10 {
|
|
prefs.update_with_custom_rate(
|
|
black_box(user_id % 100_000),
|
|
black_box(&interaction),
|
|
0.1,
|
|
);
|
|
user_id += 1;
|
|
}
|
|
});
|
|
});
|
|
|
|
group.finish();
|
|
}
|
|
|
|
// ── CoEngagementIndex eviction at scale ──────────────────────────────────────
|
|
|
|
/// Benchmark eviction latency at various capacities.
|
|
///
|
|
/// Eviction is O(N log N) — verify acceptable latency at 10K, 50K, 100K edges.
|
|
fn bench_co_engagement_eviction_at_scale(c: &mut Criterion) {
|
|
let mut group = c.benchmark_group("co_engagement_eviction");
|
|
|
|
for &capacity in &[10_000usize, 50_000, 100_000] {
|
|
let index = CoEngagementIndex::with_capacity(capacity);
|
|
// Pre-fill to capacity.
|
|
let users = (capacity / 50).max(1);
|
|
for user_id in 1..=users as u64 {
|
|
for item_id in 1..=50u64 {
|
|
index.record_positive(user_id, EntityId::new(item_id));
|
|
}
|
|
}
|
|
|
|
group.bench_with_input(
|
|
BenchmarkId::from_parameter(capacity),
|
|
&capacity,
|
|
|b, _cap| {
|
|
// Each iteration adds an edge for user 9999 (new user, forces eviction).
|
|
b.iter(|| {
|
|
index.record_positive(black_box(99_999), black_box(EntityId::new(42)));
|
|
});
|
|
},
|
|
);
|
|
}
|
|
|
|
group.finish();
|
|
}
|
|
|
|
criterion_group!(
|
|
benches,
|
|
bench_social_graph_bitmap,
|
|
bench_resolve_social_subgraph,
|
|
bench_co_engagement,
|
|
bench_social_graph_1m_items,
|
|
bench_preference_merge,
|
|
bench_co_engagement_eviction_at_scale,
|
|
);
|
|
criterion_main!(benches);
|