onflow / atree

Atree provides scalable arrays and scalable ordered maps.
https://onflow.org
Apache License 2.0
39 stars 13 forks source link

Omit empty next slab ID in encoded array data slab #339

Closed fxamacker closed 10 months ago

fxamacker commented 10 months ago

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

Changes:

Currently, we omit empty next slab ID in encoded root data slabs because next slab ID is always empty in root data slabs.

However, next slab ID is also empty for non-root data slabs if the non-root data slab is the last data slab.

This commit sets hasNextSlabID flag during encoding and only encodes non-empty next slab ID for array data slab.

This change saves 16 bytes for the last non-root data slabs. Also, we don't special case the omission of next slab ID in root slabs.

NOTE: omission of empty next slab ID doesn't affect slab size computation which is used for slab operations, such as splitting and merging. This commit is a size optimization during slab encoding.