search

IntersectMBO / lsm-tree

A Haskell library for on-disk tables based on LSM-trees
Apache License 2.0
24 stars 7 forks source link

Micro-benchmark `IndexCompact` with non-uniform UTXO keys #295

Closed jorisdral closed 1 month ago

jorisdral commented 1 month ago

Construction becomes ~5x slower and has ~3.5x more allocated bytes. Search becomes 35x slower, and has 4876x allocations

❯ cabal run lsm-tree-micro-bench -- -m pattern non-uniformity --regress allocated:iters
benchmarking Bench.Database.LSMTree.Internal.IndexCompact/non-uniformity/construct appsWithNearDups
time                 191.5 μs   (189.7 μs .. 193.8 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 190.2 μs   (189.5 μs .. 191.7 μs)
std dev              3.189 μs   (2.175 μs .. 4.562 μs)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              907512.241 (907511.284 .. 907513.119)
  y                  3005.069   (2605.877 .. 3408.336)

benchmarking Bench.Database.LSMTree.Internal.IndexCompact/non-uniformity/construct appsWithoutNearDups
time                 38.53 μs   (38.14 μs .. 39.16 μs)
                     0.999 R²   (0.997 R² .. 1.000 R²)
mean                 38.40 μs   (38.19 μs .. 38.81 μs)
std dev              925.4 ns   (506.1 ns .. 1.615 μs)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              247160.024 (247159.828 .. 247160.240)
  y                  2968.467   (2614.805 .. 3347.596)
variance introduced by outliers: 22% (moderately inflated)

benchmarking Bench.Database.LSMTree.Internal.IndexCompact/non-uniformity/search appsWithNearDups
time                 941.7 μs   (938.8 μs .. 945.3 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 941.9 μs   (940.5 μs .. 943.9 μs)
std dev              5.432 μs   (3.845 μs .. 7.557 μs)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              156033.353 (156027.533 .. 156039.668)
  y                  3006.892   (2500.693 .. 3610.068)

benchmarking Bench.Database.LSMTree.Internal.IndexCompact/non-uniformity/search appsWithoutNearDups
time                 26.52 μs   (26.34 μs .. 26.71 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 26.54 μs   (26.39 μs .. 26.74 μs)
std dev              549.2 ns   (423.0 ns .. 719.2 ns)
allocated:           0.999 R²   (0.999 R² .. 1.000 R²)
  iters              31.971     (31.868 .. 32.104)
  y                  3084.545   (2792.265 .. 3396.580)
variance introduced by outliers: 18% (moderately inflated)

This is because in a worst-case appsWithNearDups scenario, there is a clash for every page. This means we'll construct a full tie-breaker map, and we'll consult it on every search.