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

Arena setup #258

Closed phadej closed 1 month ago

phadej commented 2 months ago

This is ready. I run micro benchmarks

Benchmark                                                                                                    main      arena            
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 negative lookups/Bloomfilter query             0.779e-5  0.778e-5   -0.09%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 negative lookups/Compact index search          2.940e-7  9.549e-7 +224.73%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 negative lookups/Lookup preparation in memory  0.813e-5  0.876e-5   +7.76%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 negative lookups/Lookups in IO                 2.907e-5  3.258e-5  +12.08%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 negative lookups/Perform intra-page lookups    1.253e-6  1.320e-6   +5.37%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 negative lookups/Submit IOOps                  1.638e-5  2.204e-5  +34.56%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 positive lookups/Bloomfilter query             1.601e-5  1.590e-5   -0.66%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 positive lookups/Compact index search          0.504e-4  1.395e-4 +176.80%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 positive lookups/Lookup preparation in memory  0.673e-4  1.746e-4 +159.55%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 positive lookups/Lookups in IO                 0.540e-3  0.654e-3  +21.08%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 positive lookups/Perform intra-page lookups    0.398e-4  0.458e-4  +14.98%
Bench.Database.LSMTree.Internal.Lookup/2_000_000 entries, 256 positive lookups/Submit IOOps                  0.393e-3  0.432e-3   +9.86%
Geometric mean                                                                                               2.037e-5  2.868e-5  +40.79%

It's not unexpected that indexSearches "Compact index search" is slower, as a) it is quick function b) the fresh allocation with (not-yet cached) page allocation will have some overhead. It (hopefully) will be faster asymptotically.

TL;DR in micro benchmark this optimisation may look worse. And especially at this stage, where it's only a setup.