Optimize max map value size to reduce number of registers

onflow / atree

Atree provides scalable arrays and scalable ordered maps.

https://onflow.org

Apache License 2.0

39 stars 16 forks source link

Optimize max map value size to reduce number of registers #314

Closed fxamacker closed 1 year ago

fxamacker commented 1 year ago

Closes #313 Updates #296 #292 https://github.com/onflow/flow-go/issues/1744

Description

Previously, both max map key size and max map value size were the same (about half of max map element size). However, key size can be much smaller than max limit and max value size didn't benefit from smaller key.

Optimize this by computing max map value size to subtract encoded key size from max map element size. So large value can be stored along with small key to reduce number of registers.

While at it, also replace exported settings with exported functions.

[x] Targeted PR against main branch
[x] Linked to Github issue with discussion and accepted design OR link to spec that describes this work
[x] Code follows the standards mentioned here
[x] Updated relevant documentation
[x] Re-reviewed Files changed in the Github PR explorer
[x] Added appropriate labels

codecov-commenter commented 1 year ago

Codecov Report

Merging #314 (3c855fb) into main (bc0184e) will decrease coverage by 0.02%. The diff coverage is 71.42%.

@@            Coverage Diff             @@
##             main     #314      +/-   ##
==========================================
- Coverage   64.61%   64.59%   -0.02%     
==========================================
  Files          14       14              
  Lines        7991     7997       +6     
==========================================
+ Hits         5163     5166       +3     
- Misses       2152     2156       +4     
+ Partials      676      675       -1

Impacted Files	Coverage Δ
array_debug.go	`51.65% <0.00%> (ø)`
settings.go	`81.25% <60.00%> (-11.06%)`	:arrow_down:
array.go	`69.86% <100.00%> (ø)`
basicarray.go	`49.78% <100.00%> (ø)`
map.go	`66.79% <100.00%> (+0.09%)`	:arrow_up:

... and 1 file with indirect coverage changes

turbolent commented 1 year ago

Nice! Does this need a state migration?

fxamacker commented 1 year ago

Nice! Does this need a state migration?

@turbolent Yes, this is part of prep work for Atree Register Inlining (#292) which requires migration anyway.