[Clarity] need a `.costs-3` contract for Stacks 2.1 and associated benchmarking

[jcnelson]

Stacks 2.1 adds new Clarity functions, which will need their own cost functions, which in turn necessitates a .costs-3 contract and associated benchmarks.

[jcnelson]

Making a list:

• to-consensus-buff: O(n) in the size of the value
• from-consensus-buff: O(n log n) in the number of atoms in the type signature (caused by tuple key/value pairs needing to be in sorted order).

[saralab]

@jcnelson : @pavitthrap can pick this up once she's back next week, she has prior experience with the costs contract benchmarking and can help with this.
Let me know if I can mark her as the assignee here .

[obycode]

Adding a note to mention that we may want to add a new, separate cost function for parsing with the v2 parser, as it is significantly cheaper than the original parser.

[a3slade]

Making a list:

• to-consensus-buff: O(n) in the size of the value
• from-consensus-buff: O(n log n) in the number of atoms in the type signature (caused by tuple key/value pairs needing to be in sorted order).

I'm not seeing where any sorts are occurring. And perhaps I'm misunderstanding what's happening here, but wouldn't that occur in the serialization?

I don't see runtime_cost called at all from to-consensus-buff. Is it supposed to be or does that n get passed in from somewhere else? In from-consensus-buff it's called with n=the len of the input bytes in the buffer but from Jude's comment that doesn't sound like the n we want (if there is a sort somewhere).

[jcnelson]

`from_consensus_buff` can parse a tuple, and tuple key/value pairs are stored in an ordered map (a `BTreeMap`), which means loading a Clarity value can take as long as O(n log n) for n bytes.

…

On Fri, Oct 14, 2022, 5:45 PM a3slade ***@***.***> wrote: Making a list: - to-consensus-buff: *O(n)* in the size of the value - from-consensus-buff: *O(n log n)* in the number of atoms in the type signature (caused by tuple key/value pairs needing to be in sorted order). I'm not seeing where any sorts are occurring. And perhaps I'm misunderstanding what's happening here, but wouldn't that occur in the serialization? I don't see runtime_cost called at all from to-consensus-buff. Is it supposed to be or does that n get passed in from somewhere else? In from-consensus-buff it's called with n=the len of the input bytes in the buffer but from Jude's comment that doesn't sound like the n we want (if there is a sort somewhere). — Reply to this email directly, view it on GitHub <#3115 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADQJK5EDVWXDAYHYPUWR2LWDHIBFANCNFSM5UP5H6UQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[a3slade]

okay, if you're happy then I'm happy.

[a3slade]

did you see my other question (re: slices and whether they should be O(n) wrt right_position - left_position? Because if you're okay with that being O(1) then I'm ready to lgtm.