   Compiling rabitq-rs v0.8.0 (/Users/qliu/workspace/rabitq-rs)
    Finished `release` profile [optimized] target(s) in 1m 05s
     Running `target/release/examples/bench_ivf_vs_mstg --epsilon 0.02`

========================================================
  IVF vs MSTG-mem vs MSTG-disk Benchmark
========================================================

Loading data ...
  loading dataset/cohere_100k_768d/train.parquet ...
  loading dataset/cohere_100k_768d/test.parquet ...
  loading dataset/cohere_100k_768d/neighbors.parquet ...
  loaded: 100000 train vectors, 1000 queries, 1000 ground truth, dim=768

  vectors  : 100000
  queries  : 1000
  dim      : 768
  k        : 100
  metric   : L2
  load time: 871 ms

--- IVF (nlist=316) ---
Training k-means on original data (316 clusters, 30 iterations)...
  K-means: 80896 points, 316 clusters, 30 iterations, 1 restarts
    Restart 1/1: objective = 3.94e6
K-means training complete
Huge pages: DISABLED (compile with --features huge_pages to enable)
Rotating data vectors...
Rotating centroids...
Quantizing vectors...
  Quantized 15/316 clusters (4.7%)
  Quantized 30/316 clusters (9.5%)
  Quantized 45/316 clusters (14.2%)
  Quantized 60/316 clusters (19.0%)
  Quantized 75/316 clusters (23.7%)
  Quantized 90/316 clusters (28.5%)
  Quantized 105/316 clusters (33.2%)
  Quantized 120/316 clusters (38.0%)
  Quantized 135/316 clusters (42.7%)
  Quantized 150/316 clusters (47.5%)
  Quantized 165/316 clusters (52.2%)
  Quantized 180/316 clusters (57.0%)
  Quantized 195/316 clusters (61.7%)
  Quantized 210/316 clusters (66.5%)
  Quantized 225/316 clusters (71.2%)
  Quantized 240/316 clusters (75.9%)
  Quantized 255/316 clusters (80.7%)
  Quantized 270/316 clusters (85.4%)
  Quantized 285/316 clusters (90.2%)
  Quantized 300/316 clusters (94.9%)
  Quantized 315/316 clusters (99.7%)
  Quantized 316/316 clusters (100.0%)
Quantization complete
Building clusters with unified memory layout...
Cluster construction complete
  build    : 7528 ms
  memory   : 71.3 MB

    nprobe    recall@K     latency         QPS
  --------  ----------  ----------  ----------
         1       35.1%       345 us        2899
         2       49.9%       466 us        2145
         4       63.3%       624 us        1602
         7       72.3%       883 us        1133
         8       74.1%       878 us        1140
        10       76.9%       996 us        1004
        15       81.1%      1263 us         792
        22       84.3%      1621 us         617
        33       86.5%      2153 us         465
        49       87.9%      2980 us         336
        73       88.8%      4042 us         247
       109       89.2%      5726 us         175
       163       89.4%      8056 us         124
       244       89.5%     11647 us          86
       316       89.5%     13680 us          73

--- MSTG-mem (epsilon=0.02) ---
Building MSTG index for 100000 vectors
Step 1: Hierarchical balanced clustering...
Starting hierarchical clustering: 100000 vectors, max_size=1000, branching=8
  Iteration 1: Splitting cluster of size 100000 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 4.80e6
  Iteration 2: Splitting cluster of size 25294 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.01e6
  Iteration 3: Splitting cluster of size 4184 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.58e5
  Iteration 4: Splitting cluster of size 2062 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 7.44e4
  Iteration 5: Splitting cluster of size 5307 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.90e5
  Iteration 6: Splitting cluster of size 4295 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.60e5
  Iteration 7: Splitting cluster of size 2641 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 9.59e4
  Iteration 8: Splitting cluster of size 2126 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 7.81e4
  Iteration 9: Splitting cluster of size 4678 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.60e5
  Iteration 10: Splitting cluster of size 7679 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 3.04e5
  Iteration 11: Splitting cluster of size 1162 into 8 subclusters
  K-means: 1162 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 3.98e4
  Iteration 12: Splitting cluster of size 1380 into 8 subclusters
  K-means: 1380 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 5.13e4
  Iteration 13: Splitting cluster of size 1470 into 8 subclusters
  K-means: 1470 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 5.02e4
  Iteration 14: Splitting cluster of size 11301 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 4.68e5
  Iteration 15: Splitting cluster of size 1568 into 8 subclusters
  K-means: 1568 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 6.62e4
  Iteration 16: Splitting cluster of size 1469 into 8 subclusters
  K-means: 1469 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 4.49e4
  Iteration 17: Splitting cluster of size 2071 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 7.79e4
  Iteration 18: Splitting cluster of size 1613 into 8 subclusters
  K-means: 1613 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 6.97e4
  Iteration 19: Splitting cluster of size 2163 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 5.75e4
  Iteration 20: Splitting cluster of size 10315 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 5.02e5
  Iteration 21: Splitting cluster of size 2075 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.60e4
  Iteration 22: Splitting cluster of size 1604 into 8 subclusters
  K-means: 1604 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 6.68e4
  Iteration 23: Splitting cluster of size 1955 into 8 subclusters
  K-means: 1955 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.62e4
  Iteration 24: Splitting cluster of size 2760 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.31e5
  Iteration 25: Splitting cluster of size 1003 into 8 subclusters
  K-means: 1003 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 4.22e4
  Iteration 26: Splitting cluster of size 12890 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 6.93e5
  Iteration 27: Splitting cluster of size 1395 into 8 subclusters
  K-means: 1395 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 7.83e4
  Iteration 28: Splitting cluster of size 1542 into 8 subclusters
  K-means: 1542 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.17e4
  Iteration 29: Splitting cluster of size 2049 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 9.92e4
  Iteration 30: Splitting cluster of size 2312 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.05e5
  Iteration 31: Splitting cluster of size 2186 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.10e5
  Iteration 32: Splitting cluster of size 3393 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.73e5
  Iteration 33: Splitting cluster of size 14881 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 6.94e5
  Iteration 34: Splitting cluster of size 1844 into 8 subclusters
  K-means: 1844 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.38e4
  Iteration 35: Splitting cluster of size 2323 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.87e4
  Iteration 36: Splitting cluster of size 1195 into 8 subclusters
  K-means: 1195 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 4.87e4
  Iteration 37: Splitting cluster of size 2310 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.09e5
  Iteration 38: Splitting cluster of size 3343 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.35e5
  Iteration 39: Splitting cluster of size 1928 into 8 subclusters
  K-means: 1928 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.04e4
  Iteration 40: Splitting cluster of size 1937 into 8 subclusters
  K-means: 1937 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 8.99e4
  Iteration 41: Splitting cluster of size 17628 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 7.44e5
  Iteration 42: Splitting cluster of size 2131 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 9.04e4
  Iteration 43: Splitting cluster of size 1854 into 8 subclusters
  K-means: 1854 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 7.41e4
  Iteration 44: Splitting cluster of size 2921 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.13e5
  Iteration 45: Splitting cluster of size 2893 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.26e5
  Iteration 46: Splitting cluster of size 2906 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.09e5
  Iteration 47: Splitting cluster of size 3149 into 8 subclusters
  K-means: 2048 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 1.12e5
  Iteration 48: Splitting cluster of size 1773 into 8 subclusters
  K-means: 1773 points, 8 clusters, 100 iterations, 1 restarts
    Restart 1/1: objective = 5.04e4
Hierarchical clustering complete: 337 final clusters
  Created 337 clusters
Step 2: Closure assignment with RNG rule...
  Average replication factor: 1.56
Step 3: Creating and quantizing posting lists...
  Created 337 posting lists with 156435 total vectors
Step 3.5: Building FastScan batch layouts...
Step 4: Building centroid index...
  Built centroid index with 337 centroids (BF16 precision)
MSTG index build complete
  Memory usage estimate: ~110.80 MB
  build    : 7359 ms
  repl     : 1.56x
  memory   : 110.8 MB

       profile    recall@K     latency         QPS      ef / eps
  ------------  ----------  ----------  ----------  ------------
   low-latency       83.2%       894 us        1119  ef=50  e=0.3
  balanced-low       86.9%      1700 us         588  ef=100 e=0.5
      balanced       87.2%      2551 us         392  ef=150 e=0.6
  balanced-high       87.4%      3508 us         285  ef=200 e=0.8
   high-recall       87.5%      4766 us         210  ef=300 e=1.0
    max-recall       87.5%      5332 us         188  ef=500 e=1.5

--- MSTG-disk (mmap, same index) ---
  save     : 130 ms
Loaded MSTG in disk mode: 337 centroids, posting lists on mmap
  mmap load: 98 ms
  memory   : 0.5 MB (centroid + directory only)

       profile    recall@K     latency         QPS      ef / eps
  ------------  ----------  ----------  ----------  ------------
   low-latency       83.2%      3049 us         328  ef=50  e=0.3
  balanced-low       86.9%      6781 us         147  ef=100 e=0.5
      balanced       87.2%     10195 us          98  ef=150 e=0.6
  balanced-high       87.4%     15554 us          64  ef=200 e=0.8
   high-recall       87.5%     21240 us          47  ef=300 e=1.0
    max-recall       87.5%     23208 us          43  ef=500 e=1.5

========================================================
  Head-to-head (matched recall)
========================================================

  MSTG-mem vs IVF:
    recall ~83%: MSTG-mem(mem-low-latency) 894us vs IVF(nprobe=22) 1621us => MSTG-mem 1.81x faster
    recall ~87%: MSTG-mem(mem-balanced-low) 1700us vs IVF(nprobe=33) 2153us => MSTG-mem 1.27x faster
    recall ~87%: MSTG-mem(mem-balanced) 2551us vs IVF(nprobe=49) 2980us => MSTG-mem 1.17x faster
    recall ~87%: MSTG-mem(mem-balanced-high) 3508us vs IVF(nprobe=49) 2980us => IVF 1.18x faster
    recall ~87%: MSTG-mem(mem-high-recall) 4766us vs IVF(nprobe=49) 2980us => IVF 1.60x faster
    recall ~88%: MSTG-mem(mem-max-recall) 5332us vs IVF(nprobe=49) 2980us => IVF 1.79x faster

  MSTG-disk vs MSTG-mem:
    recall ~83%: disk 3049us vs mem 894us => disk 3.4x slower
    recall ~87%: disk 6781us vs mem 1700us => disk 4.0x slower
    recall ~87%: disk 10195us vs mem 2551us => disk 4.0x slower
    recall ~87%: disk 15554us vs mem 3508us => disk 4.4x slower
    recall ~87%: disk 21240us vs mem 4766us => disk 4.5x slower
    recall ~88%: disk 23208us vs mem 5332us => disk 4.4x slower

========================================================
  Summary
========================================================

  MSTG config: epsilon=0.02, replication=1.56x
  MSTG-mem : build=7359ms, memory=110.8MB
  MSTG-disk: save=130ms, mmap_load=98ms, memory=0.5MB
  Build: IVF 7528ms vs MSTG 7359ms (MSTG 1.0x faster)
  Peak recall: IVF 89.5% (nprobe=316) vs MSTG-mem 87.5% (mem-max-recall)
  Peak recall: MSTG-mem 87.5% (mem-max-recall) vs MSTG-disk 87.5% (disk-max-recall)

Done.
