NethermindEth / Paprika

A custom storage engine of Nethermind, benefiting from the alignment of the underlying data structure with the layout of State & Storage trees of Ethereum.
GNU Lesser General Public License v3.0
91 stars 14 forks source link

Addressable 8kb #378

Closed Scooletz closed 3 months ago

Scooletz commented 3 months ago

This PR reintroduces the ability for the SlottedArray to address 8kb. Also, removes the masking of the hash which could make the Prepare / Unprepare a bit faster. This is an enabler for #375 to make pages bigger and allow to amortize more.

To make it work, this PR splits the cases of keys:

  1. 0-length - encoded as 0b00 in preamble
  2. 1,2,3 - nibbles - length encoded as one nibble in the hash, marker set in preamble 0b01
  3. 4 nibbles - 0b10 in preamble to represent 4
  4. 5+ nibbles - 0b11 in preamble to represent 5+ as some key parts will be in the array

As the values above take 2 bits, 1 bit is used to mark Odd/Deleted. This leaves 13 out of 16 to address 8k

Benchmarks

Before

Method sliceFrom length Mean Error StdDev Code Size
EnumerateAll ? ? 761.759 ns 10.7755 ns 10.0795 ns 2,145 B
Prepare_Key 0 0 2.507 ns 0.0601 ns 0.0562 ns 763 B
Prepare_Key 0 1 2.342 ns 0.0365 ns 0.0324 ns 727 B
Prepare_Key 0 2 2.224 ns 0.0492 ns 0.0460 ns 727 B
Prepare_Key 0 3 2.371 ns 0.0299 ns 0.0280 ns 726 B
Prepare_Key 0 4 2.242 ns 0.0341 ns 0.0302 ns 725 B
Prepare_Key 0 6 3.768 ns 0.0337 ns 0.0281 ns 763 B
Prepare_Key 0 32 3.834 ns 0.0460 ns 0.0430 ns 763 B
Prepare_Key 1 1 2.249 ns 0.0296 ns 0.0277 ns 727 B
Prepare_Key 1 2 2.551 ns 0.0419 ns 0.0371 ns 726 B
Prepare_Key 1 3 2.413 ns 0.0492 ns 0.0411 ns 725 B
Prepare_Key 1 4 2.323 ns 0.0336 ns 0.0314 ns 726 B
Prepare_Key 1 6 3.466 ns 0.0400 ns 0.0374 ns 723 B
Prepare_Key 1 30 3.502 ns 0.0447 ns 0.0374 ns 723 B
Prepare_Key 1 31 3.547 ns 0.0619 ns 0.0579 ns 723 B

After

Method sliceFrom length Mean Error StdDev Code Size
EnumerateAll ? ? 777.297 ns 10.9494 ns 9.7063 ns 1,913 B
Prepare_Key 0 0 2.087 ns 0.0282 ns 0.0263 ns 718 B
Prepare_Key 0 1 1.683 ns 0.0366 ns 0.0343 ns 715 B
Prepare_Key 0 2 1.627 ns 0.0365 ns 0.0341 ns 715 B
Prepare_Key 0 3 1.707 ns 0.0326 ns 0.0305 ns 715 B
Prepare_Key 0 4 1.688 ns 0.0244 ns 0.0228 ns 715 B
Prepare_Key 0 6 3.314 ns 0.0316 ns 0.0296 ns 742 B
Prepare_Key 0 32 3.351 ns 0.0350 ns 0.0327 ns 742 B
Prepare_Key 1 1 1.691 ns 0.0365 ns 0.0341 ns 715 B
Prepare_Key 1 2 1.739 ns 0.0392 ns 0.0366 ns 712 B
Prepare_Key 1 3 1.689 ns 0.0347 ns 0.0324 ns 715 B
Prepare_Key 1 4 1.898 ns 0.0357 ns 0.0334 ns 719 B
Prepare_Key 1 6 2.995 ns 0.0436 ns 0.0408 ns 694 B
Prepare_Key 1 30 3.003 ns 0.0508 ns 0.0451 ns 694 B
Prepare_Key 1 31 3.077 ns 0.0251 ns 0.0235 ns 694 B
github-actions[bot] commented 3 months ago

Code Coverage

Package Line Rate Branch Rate Health
Paprika 84% 78%
Summary 84% (4241 / 5019) 78% (1340 / 1709)

Minimum allowed line rate is 75%