[suggestion]: MerkleTree optimization

[s8sato]

Explore tradeoffs between time and space efficiency (skipping hash calculations v.s. having no wrappers).

Currently, a node is represented as Option<HashOf<T>>.
This can benefit from skipping empty (None) nodes in the hash calculation from the leaves to the root of the tree, while increases the memory footprint by the amount of the wrapper.

HashOf<T> may be an alternative for the node representation.
In that case, an empty node can be represented as Hash::zeroed().typed().
This is advantageous in terms of memory footprint, while increases the hash calculation cost since there is no distinction in types between empty and non-empty nodes

[appetrosyan]

There's a few points. This is a consequence of years of experience in optimising software, so I'd err on the side of caution.

This is advantageous in terms of memory footprint, while increases the hash calculation cost since there is no distinction in types between empty and non-empty nodes

Only at the language level. In reality most CPUs ignore the branch conditions execute the likely branch, and only backtrack to the condition once the branch misprediction takes place.

If we don't use monadics, and instead operate on zeroed, we might do what the compiler would have done anyway. Except now, it's explicit.

This can benefit from skipping empty (None) nodes in the hash calculation from the leaves to the root of the tree, while increases the memory footprint by the amount of the wrapper.

Also no.

I'd argue that if Hash::zeroed()::typed was made an invalid Hash, and we refactored everywhere to use Option<HashOf<T>>, we'd actually have the exact same assembly thanks to the niche optimisation. The internal representations of HashOf<T> where zeroed is valid and Option<HashOf<T>> where HashOf::<T>::zeroed() is invalid, is guaranteed by the compiler.

In other words we can have the cake and eat it too in terms of memory layout savings.

A similar thing is done to the built-in type NonZeroUsize which is used to represent pointers.

[appetrosyan]

I think that we should explore the approach of making HashOf be non-zero, marking that value as a niche, and refactoring every place where we produce HashOf::<T>::zeroed to accept Option<HashOf<T>>.

[Erigara]

i and @mversic recently have discussed that having niche value will be nice for ffi too (here).

[Erigara]

However i'm not sure how we can make HashOf non-zero, since it's backed by [u8;32].

[appetrosyan]

That’s the clever bit. if it were u8;16 you could just pack that into a single u128. That trick doesn’t quite work with u8: 32 but there must be a way.

[appetrosyan]

Actually, we could pack it into two u128s, and mark the less significant bits as nonzero. We then set the LSB to 1 for all valid hashes. If we want to be pedantic, this sacrifices one bit for all other hashes.

[Erigara]

We should be careful as u128/i128 is not fully supported in FFI (#2622)

[Erigara]

With merge of #3012 there is no need to remove Option since Option<Hash> is niche optimized.