More efficient ModifierId alternative

Problem

ModifierId is used extensively all over the code base (around 273 usages). However in most cases ModifierId is used as equality safe replacement of the original Array[Byte] 32-bytes hash which is stored in blockchain.

The reason for this is that the default implementation of hashCode and equals in Array class doesn't allow to use arrays in Map (as keys) and in Set collections. Other methods like distinct also become broken. ModifierId is tagged String, and String have correct equality implementation.

However the price we pay:

1. 5x memory footprint, since every byte -> 4 byte = 2 char * 2 byte/char, plus original Array[Byte]
2. 3x number of allocations, since every string require 2 allocations (header and char[])
3. 2x more operations to compute hashCode
4. 3x less efficent memory access (original Array[Byte] hash fits into 1 cache line (64 byte on Intel) where as ModifierId has (128 bytes long array of chars) + header, so 3 cache lines.

Solution

There is a way to avoid the above mentioned problems and in addition to outperform even Array[Byte] while guaranteeing the correctness of equality sensitive operations with collections.

The idea is to exploit the fact that ModifierId is backed by cryptographic hash, we know this for sure, so it is not general Array[Byte]. Thus instead of defining ModifierId as tagged type

  object ModifierId extends TaggedType[String]
  type ModifierId = ModifierId.Type

We can define it as

class ModifierId(hashBytes: Array[Byte]) {
  // This is much more efficient than hashing whole array or String. 
  // We can use the first 4 bytes and convert them into Int.
  override def hashCode = Ints.fromByteArray(hashBytes)
  override def equals(other: Any) = ...
}

Thus we can implement ModifierId as a new wrapper class around hash bytes and implement hashCode and equals.

The implementation of hashCode() shown above is much more efficient than hashing the whole 32 bytes of hashBytes array and actually provide better hashCode randomness, which will further improve performance of Map and Set operations.

Despite wide usage of ModifierId over the code, I don't expect much changes, and static type checking should play well here as well catching all the places where ModifierId is used as String implicitly.

See also

https://github.com/ScorexFoundation/sigmastate-interpreter/issues/197