feat: batch hash tree root

[matthewkeil]

Motivation

Created on behalf of @twoeths. Keeping in draft for now but using to store some metrics from different iterations of the changes.

Update system to allow for batch hashing of trees. SIMD instruction set allows for parallel processing of hashes when running on a single core. Add the idea of levels to the hashing process to allow deeper sections of a tree to be processed before higher levels and then computes the hashes according to depth of the tree.

Description

• New hashtree hasher for batch hash

• Minimal memory allocation:

  • use same memory allocated in type to hash all objects of the same type
  • use same memory allocated in ListValidatorViewDU to hash all validators in batch

• For type.hashTreeRoot():

  • Preallocate memory at type level, a type.hashTreeRoot() almost does not need to allocate any temporary Uint8Arrays
    • Child fields are hashed into a preallocated memory of parent
  • Implement merkleizeInto() in hasher, this also does not allocate memory, and it uses batch hash

• For ViewDU:

  • Model HashComputation = {left: Node; right: Node; dest: Node}
  • Compute HashComputations at different level from the merkle tree
  • Execute the HashComputations using batch hash, order is bottom up

• For BeaconState, it contains validators as ContainerNodeStructViewDUs

  • Overwrite ListValidatorViewDU
  • We already track viewsChanged there, when commit() we compute validator roots in batch using preallocated Uint8Array
  • Save a lot of memory by avoid tree creation for validator type

Benchmark result on Mac M1

• 3x faster on a BeaconBlock.hashTreeRoot() call, data comes from a typical mainnet block with 200 transactions
• 7x faster on a BeaconState of 200k validators, 100k are modified

TODOs

• [ ] resolve TODO - batch
• [ ] polish the branch
• [ ] create smaller PRs for as-sha256, persistent-merkle-tree and ssz

part of #355 closes #78