lib/pluck/src/profiling/internal/weighted.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

 1 const std = @import("std");
 2 
 3 const pluck = @import("pluck");
 4 const bdd = pluck.bdd;
 5 const Manager = bdd.Manager;
 6 const Bdd = bdd.Bdd;
 7 const WmcParams = bdd.WmcParams;
 8 const WeightedSampler = bdd.WeightedSampler;
 9 const bench_util = @import("util.zig");
10 
11 fn buildOrChain(manager: *Manager, params: *WmcParams, num_vars: usize) !Bdd {
12     var formula = Bdd.FALSE;
13     var idx: usize = 0;
14     while (idx < num_vars) : (idx += 1) {
15         try params.setWeight(@intCast(idx), 0.45, 0.55);
16         const var_bdd = try manager.newVar(true);
17         formula = if (formula.isFalse()) var_bdd else try manager.bddOr(formula, var_bdd);
18     }
19     return formula;
20 }
21 
22 test "BENCHMARK: weighted sampling cache reuse" {
23     const benchmark_latency = bench_util.benchmarkScope("weighted sampling cache reuse");
24     defer benchmark_latency.end();
25     const allocator = bench_util.allocator();
26     const bench = bench_util.BenchConfig.init();
27     var manager = try Manager.init(allocator);
28     defer manager.deinit();
29 
30     var params = WmcParams.init(allocator);
31     defer params.deinit();
32 
33     const num_vars: usize = 24;
34     const num_samples: usize = bench.value(10_000, 1_000);
35     const formula = try buildOrChain(&manager, &params, num_vars);
36 
37     bench_util.stdout("benchmark,weighted_sample,num_vars,num_samples,baseline_ns,sampler_ns,speedup\n", .{});
38 
39     var prng_baseline = std.Random.DefaultPrng.init(2026);
40     const rng_baseline = prng_baseline.random();
41     var baseline_acc: f64 = 0.0;
42     const baseline_start = bench_util.nowNs();
43     for (0..num_samples) |_| {
44         const result = try bdd.weightedSample(&manager, formula, &params, rng_baseline);
45         baseline_acc += result.probability;
46     }
47     const baseline_ns: u64 = bench_util.elapsedNs(baseline_start);
48     std.mem.doNotOptimizeAway(baseline_acc);
49 
50     var sampler = try WeightedSampler.init(allocator, &manager, formula, &params);
51     defer sampler.deinit();
52 
53     var prng_sampler = std.Random.DefaultPrng.init(2026);
54     const rng_sampler = prng_sampler.random();
55     var sampler_acc: f64 = 0.0;
56     const sampler_start = bench_util.nowNs();
57     for (0..num_samples) |_| {
58         const result = try sampler.sample(rng_sampler);
59         sampler_acc += result.probability;
60     }
61     const sampler_ns: u64 = bench_util.elapsedNs(sampler_start);
62     std.mem.doNotOptimizeAway(sampler_acc);
63 
64     const speedup = @as(f64, @floatFromInt(baseline_ns)) / @as(f64, @floatFromInt(@max(sampler_ns, 1)));
65     bench_util.stdout("weighted_sample,{d},{d},{d},{d},{d:.2}\n", .{
66         num_vars,
67         num_samples,
68         baseline_ns,
69         sampler_ns,
70         speedup,
71     });
72 }