Overuse of resources when comparing for equality of VALUES (==)

Question

I found an strange consumption of mem and CPU when comparting VALUES on-chain.

If I do the same comparison with my own writing functions I found is more efficient. How could it be?

Everything is detailed here: https://github.com/input-output-hk/plutus/issues/5135

Basically, I run some test evaluations over two different minting policies. One using the (==) operator between VALUES and other using my own function called valueEqualsValue. The results where overwhelming.

With zero tokens my own functions use 12% less of resources and with 19 different tokens they use 32% less than the officials one.

It could be I'm missing some functionality in the comparison, that is implemented in the official one with the (==) operator. I found also benefits like this writing my own version of flattenValue.

How do you compare VALUES online?

Did you notice this unexpected inefficiency in some of other core functionalities of Plutus On Chain Code?

Considering the limited amount of memory that we have to write our smart contracts its very strange for me to realize that even the most basic functionalities they look very inefficient.

Thank you

Answer 1

Copying my answer from the Github issue here as well:

We have hit the same issue lately. It is due to how the == function in the Eq Value instance is implemented.

A value is logically a Map CurrencySymbol (Map TokenName Quantity), but on-chain there are no maps. Instead associative lists are used instead. As a Haskell type, a Value would be something like [(CurrencySymbol, [(TokenName, Quantity)]].

This means that given two values with the same contents, they may not be exactly the same if you compare them element by element. (I assume) the implementation of Eq Value was intended to mitigate this by implementing a Map-like equality. While correct, it turns out, this is quite an expensive implementation.

What we have opted for is an "exact equality" check for Value in the Hydra code base: https://github.com/input-output-hk/hydra/pull/709 (We investigated and indeed serializing to bytes and comparing the results was most efficient for us with complexity of about O(2n) or so)

I think we should discuss the need for such an exact equality function and maybe guide users more towards that if just want to ensure values are exactly the same / unchanged? From my experience this is often good enough and could be implemented cheaper.