New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Shrink table_mutable #490
Comments
492: Increase lsm_batch_multiple to 64. r=jamii a=jamii This is roughly the value we plan to use in production, so we should be benchmarking this configuration as early as possible. This increases memory usage and increase the latency spike from the final phase of compaction, but we need to deal with both regardless. #491 and #490 can help with memory usage. #269 will reduce the latency spike, as will any optimization that improves compaction performance in general. ## Pre-merge checklist Performance: * [x] Compare `zig benchmark` on linux before and after this pr. ``` lbm=4 1643655168 allocated 1223 batches in 116.60 s load offered = 1000000 tx/s load accepted = 85766 tx/s batch latency p00 = 5 ms batch latency p10 = 26 ms batch latency p20 = 27 ms batch latency p30 = 32 ms batch latency p40 = 36 ms batch latency p50 = 42 ms batch latency p60 = 112 ms batch latency p70 = 142 ms batch latency p80 = 172 ms batch latency p90 = 217 ms batch latency p100 = 411 ms lbm=64 2989330432 bytes allocated 1223 batches in 93.51 s load offered = 1000000 tx/s load accepted = 106942 tx/s batch latency p00 = 5 ms batch latency p10 = 26 ms batch latency p20 = 26 ms batch latency p30 = 27 ms batch latency p40 = 31 ms batch latency p50 = 31 ms batch latency p60 = 32 ms batch latency p70 = 36 ms batch latency p80 = 37 ms batch latency p90 = 42 ms batch latency p100 = 3624 ms ``` OR * [ ] I am very sure this PR could not affect performance. Co-authored-by: Jamie Brandon <jamie@scattered-thoughts.net>
492: Increase lsm_batch_multiple to 64. r=jamii a=jamii This is roughly the value we plan to use in production, so we should be benchmarking this configuration as early as possible. This increases memory usage and increase the latency spike from the final phase of compaction, but we need to deal with both regardless. #491 and #490 can help with memory usage. #269 will reduce the latency spike, as will any optimization that improves compaction performance in general. ## Pre-merge checklist Performance: * [x] Compare `zig benchmark` on linux before and after this pr. ``` lbm=4 1643655168 allocated 1223 batches in 116.60 s load offered = 1000000 tx/s load accepted = 85766 tx/s batch latency p00 = 5 ms batch latency p10 = 26 ms batch latency p20 = 27 ms batch latency p30 = 32 ms batch latency p40 = 36 ms batch latency p50 = 42 ms batch latency p60 = 112 ms batch latency p70 = 142 ms batch latency p80 = 172 ms batch latency p90 = 217 ms batch latency p100 = 411 ms lbm=64 2989330432 bytes allocated 1223 batches in 93.51 s load offered = 1000000 tx/s load accepted = 106942 tx/s batch latency p00 = 5 ms batch latency p10 = 26 ms batch latency p20 = 26 ms batch latency p30 = 27 ms batch latency p40 = 31 ms batch latency p50 = 31 ms batch latency p60 = 32 ms batch latency p70 = 36 ms batch latency p80 = 37 ms batch latency p90 = 42 ms batch latency p100 = 3624 ms ``` OR * [ ] I am very sure this PR could not affect performance. Co-authored-by: Jamie Brandon <jamie@scattered-thoughts.net>
For hash tables that do linear probing, a load factor of 50% is important to avoid excessive collisions, clustering and probing. We could do 60% or perhaps 70% I think, given that Zig's implementation is pretty good, but then it's risking clustering and more CPU-intensive probing, so we should then also verify that these load factors don't cause excessive probing. |
For object trees only: If we're willing to pay an extra indirection cost + complexity, the hash map could be |
Which we could then sort in-place and swap with the immutable table's arraylist when we transition mutable → immutable to avoid copying all of the values out. |
This is a neat trick—and a "super idea" for both reasons. |
Currently the load factor is set to 50%, which is fairly wasteful. Unfortunately
value_count_max
is just below a power of two, so even load factors up to 99% result in https://github.com/ziglang/zig/blob/6d44a6222d6eba600deb7f16c124bfa30628fb60//lib/std/hash_map.zig#L876 rounding up the allocation size to an effective load factor of just under 50%.The text was updated successfully, but these errors were encountered: