Quadratic complexity in Benchmarking

Question

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 ?

Answer 1

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.