Create an efficient drop-in Data replacement for AssocMap.Map

[ana-pantilie]

From @zliu41 :

AsData doc: #5729

The goal is to create a Map for Plutus Tx that is encoded in BuiltinData. In contrast, PlutusTx.AssocMap wraps a regular list encoded in SOP.

Using AsData on PlutusTx.AssocMap won’t be effective, because it is backed by a regular (SOP-encoded) list, not a data-encoded list. If we simply wrap the PlutusTx.AssocMap.Map definition in AsData, it would become less, not more efficient, because two frequent operations, wrapping and unwrapping (via toList and fromList ) will be linear (converting an SOP list to or from Data).

Instead, we should implement all operations for the new Map type such that they do not involve regular lists.

I have an initial implementation but didn’t finish addressing all the comments: #5701 Please take it from there.

Once we are done with Map, we will be ready to wrap the ScriptContext types (for V1, V2 and V3) in AsData, which will significantly speed up scripts that only access a small portion of the script context.

[uhbif19]

Cannot asData encode "regular" lists with built-in lists as well? It seems like it should be always more performant this way.

[ana-pantilie]

@uhbif19 The SOP list type is encoded as a builtin list in its data representation:

plutus/plutus-tx/src/PlutusTx/IsData/Class.hs

Line 97 in 7b70ab0

instance ToData a => ToData [a] where

Does this answer your question or did I misunderstand?

[uhbif19]

@ana-pantilie

You right, I formulate my question incorrectly.

This issue implements AssocMap encoded in BuiltinData. That way one can use AssocMap in asData datatypes. For same reason one needs List encoded in BuiltinData, to use lists in asData datatypes. Is that not correct?

I think that asData translation could change regular SOP-encoded lists to such BuiltinData-backed lists. But may be I am wrong.