3

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 ?

1 Answer 1

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.

4
  • 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 stepping 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, 2023 at 14:39
  • Is z = x + y just a hack or does it produce suboptimal benchmarks? Aug 8, 2023 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, 2023 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, 2023 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.