I am trying to understand if quadratic complexity is bad (gives inaccurate results) when used for benchmarking:

I have a pallet whose weight would ideally depend on `x * y` where x and y are lengths of two vectors. Just for context this is how the vector looks like `Vec<_, Vec<_>>`. To replicate this, during benchmarking, the first thought that comes to mind is to make the benchmark a nested for loop :

``````fn benchmark(x: Linear<1, 5000> , y : Linear<1, 5000>) {
for i in 0 .. x {
for j in 0 .. y {
// setup input parameter
}
}
#[extrinsic_call]
}
``````

Given that this input parameter is now depends on two variables that are kind of nested implying a complexity of `O(i * j)`, is it okay for getting an accurate benchmark? Additional question: is this how you would set up a non-linear benchmark ?

Currently the benchmarking backend logic only supports linear components, which is why the type is called `Linear`. The assumption is that the output weight relates linearly to the input parameters.

Now this is not given in your case. If you are sure that it is linear to `x * y` then you can instead use another component `z` which is just defined as `x * y`. Then you can make your benchmark linear again.
Otherwise a work-around can be done where two benchmarks are written. One which fixes `x` to 5000 and one where `y` is fixed to 5000 and then take the `.min` of both in your call weight.
It is not ideal since it will still over-estimate one of them, but at least not both.

Additional question: is this how you would set up a non-linear benchmark ?

You can do anything in the setup phase. Only the complexity of the `extrinsic_call` (or `block`) is important. Looks fine.

• Thanks for your response. There's definitely some thinking to do when you say `let z = x * y`. Just to clarify, do I really need a loop as I showcase in the question about or can I just leave it as `Linear<...>` and make use of it in the call input parameter, and the framework takes care of `step`ping through it? I know it's kind of a silly question, but for all purposes I am using this value as just the size of vec as `size` in `vec![.. ; size]`. Aug 8 at 14:39
• Is `z = x + y` just a hack or does it produce suboptimal benchmarks? Aug 8 at 14:44
• You def. dont "need" a loop. The `Linear` just becomes a normal `u32` in the end. You can do anything you want in the setup phase; loop or not. You can also do `vec![.. ; x as usize]` or whatever. About hack: I think it should be fine, but it implies that `x` and `y` are interchangeable since only the product is used. Although i have not tested it myself yet. Please post here again if you have problems with it. Aug 8 at 18:57
• Thanks for clearing it up. About `z = x * y` unfortunately that is a hack indeed as there's no way with we can vary both `x` and `y` and expect `z` to fit a line. Thanks for your input! Aug 9 at 4:35