Update submit finality proof weight formula

[svyatonik]

on top of #979 => draft
the only new commit is 6ed0641

Final results (weighs) are on the "common prefix" sheet of this document. There are 4 weight-related parameters in this document - p and v + c and f. The f parameter represents the number of forks in the precommits ancestry and the c is the number of shared (among all forks) ancestors. In the end, I've dropped these parameters from the weight formula - we may try to re-add them later, but for now I haven't found a way to use them (spent 1.5 days on that) + seems that they are not affecting total weight that much.

From results, you may see that the largest (in percents) error (computed vs actual weight) is 11.5% for the case (p=2, v=16). The larger are parameters (p and v), the less is error. On real chains, we'll be seeing justifications that are near to (p=512, v=2) and (p=1024, v=2) where error is ~1.4%.

I've computed approximate cost of submit_finality_proof on the Kusama chain where (I hope) we'll see ~1024*2/3+1 precommits and near to 2 ancestors - the cost is near to 0.37 KSM, given weights that I've computed on my laptop. Initially I've got ~0.2, but I haven't considered forks back then. Hopefully, after updating weights on reference machine, we'll have better results.

I've also left JustificationGeneratorParams::common_ancestors field to show what the c parameter represents in the document above. Could remove it if required, but I feel that we may use it later for optimizing the formula (to refund submitter if some forks had duplicate headers => AncestryChain::is_descendant was executed faster).

[HCastano]

Final results (weighs) are on the "common prefix" sheet of this document.

So something that's still unclear to me is how you're calculating the "actual" column here

I've dropped these parameters from the weight formula - we may try to re-add them later, but for now I haven't found a way to use them (spent 1.5 days on that) + seems that they are not affecting total weight that much.

Yeah, that's fine imo

I've computed approximate cost of submit_finality_proof on the Kusama chain where (I hope) we'll see ~1024*2/3+1 precommits and near to 2 ancestors - the cost is near to 0.37 KSM, given weights that I've computed on my laptop. Initially I've got ~0.2, but I haven't considered forks back then. Hopefully, after updating weights on reference machine, we'll have better results.

If you're running these on a laptop then yeah, this should probably go down by at least half

I've also left JustificationGeneratorParams::common_ancestors field to show what the c parameter represents in the document above. Could remove it if required, but I feel that we may use it later for optimizing the formula (to refund submitter if some forks had duplicate headers => AncestryChain::is_descendant was executed faster).

I think we should drop in. If later on we want to do optimizations we can add it back then

[HCastano]

Why are you holding this fixed at v = 1 instead of holding it at MAX_VALIDATOR_SET_SIZE, or even sweeping through the range? Each of these choices will give us different weights for each additional item

[svyatonik]

Because there's another benchmark which is responsible for that. This benchmark must build weight(p). And while building weight(p) I don't care about number of headers in the votes ancestry. So here I'm interested in additional weight that comes with additional signature verification + some of the loop checks. With that new custom justification validation there's a guarantee that every header in the ancestry will be only visited once (this doesn't include one additional visit per precommit, weight for which is added here). So we may use formula like that a*A + b*B. Benchmarks are responsible for computing A/B.

[HCastano]

So wasn't part of the initial problem here that different values of p/v would have different impacts depending on the size of the other variable?

E.g with v=1 every additional p increases the weights by X, while with v=1000 every additional p increases the weights by X + C?

[svyatonik]

Yes. Take a look at the new verification code, please - all that happens with ancestry is: (1) every header is hashed and inserted into btree (this is accounted y the weight_per_additional_unique_ancestor) (2) zero or one header is accessed for every precommit (accounted by weight_per_additional_precommit) (3) every header in the valid justification is accessed at most one time (accounted by weight_per_additional_unique_ancestor). So while both parameters are still used inside one loop, it doesn't mean anymore that the weight formula should look something like p*v*W. Look at the attached doc - if what you're saying was the true, then the formula wouldn't fit that good for both small and large values of (p, v).

[HCastano]

I agree with you, the formula shouldn't look like p*v*W. What it should look like is A*p + B*v.

What I'm trying to say here is that the values of A and B will be different depending on the values of p and v used when running the benchmarks. Depending on if we fix v=1 or v=1000 the corresponding constants will be different - so what should we choose?

[svyatonik]

So something that's still unclear to me is how you're calculating the "actual" column here

By executing benchmark with (p, v, c, f) pinned to given values :) You could try yourself.

[HCastano]

So something that's still unclear to me is how you're calculating the "actual" column here

By executing benchmark with (p, v, c, f) pinned to given values :) You could try yourself.

Okay so basically what you're doing here is running the benchmarks with

submit_finality_proof {
	let v in 1..8192;
	let p = 1..8192;
	let caller: T::AccountId = whitelisted_caller();
	let (header, justification) = prepare_benchmark_data::<T, I>(p, v);
}: _(RawOrigin::Signed(caller), header, justification)

With --steps 12 and --repeat 1?

If that's the case, given that the actual and computed weights are almost the same, why not just use the actual weight directly?

[svyatonik]

weight_per_additional_unique_ancestor

No, I'm not doing that. I'm running benchmarks from this file

With --steps 12 and --repeat 1?

No

If that's the case, given that the actual and computed weights are almost the same, why not just use the actual weight directly?

That's not the case. If I would use benchmarks which iterates both p and v in the range 1..8192, it would mean that the benchmark engine will be building weight(p) using v=8192. It would mean that the cost of single precommit would always include cost of hashing + iterating 8192 headers. The opposite is also true - the cost of adding one more header will include the cost of verifying 8192 signatures.

So what must be remembered is that you can only build weight(p1, p2) in single benchmark only when p1 and p2 are fully uncorrelated. I.e. they're used like that:

fn call(origin, p1: u64, p2: u64) {
  for _ in 0..p1 {
    // do something totally unrelated to the next loop 
  }
  for _ in 0..p2 {
    // do something totally unrelated to the previous loop
  }

If they're used in a single loop, or if they may affect what's happen in the other loop, then single benchmark isn't a good idea.

UPD: actually I'm not sure how benchmarking would work in this example ^^^ above. Probably I've made a mistake and actually weight(p1) would always include weight(max(p2)), as we have seen in original benchmark.

[HCastano]

weight_per_additional_unique_ancestor

No, I'm not doing that. I'm running benchmarks from this file

With --steps 12 and --repeat 1?

No

So I know the benchmarks you included weren't run as I said, but the "actual" benches look like what I proposed (imo anyways).

That's not the case. If I would use benchmarks which iterates both p and v in the range 1..8192, it would mean that the benchmark engine will be building weight(p) using v=8192. It would mean that the cost of single precommit would always include cost of hashing + iterating 8192 headers. The opposite is also true - the cost of adding one more header will include the cost of verifying 8192 signatures.

Yeah, that's intentional. The benchmarking framework is trying to compute the weight based off the worst-case scenario, which in our case would be max(p) or max(v) depending on the benchmark.

So what must be remembered is that you can only build weight(p1, p2) in single benchmark only when p1 and p2 are fully uncorrelated. I.e. they're used like that:

fn call(origin, p1: u64, p2: u64) {
  for _ in 0..p1 {
    // do something totally unrelated to the next loop 
  }
  for _ in 0..p2 {
    // do something totally unrelated to the previous loop
  }

If they're used in a single loop, or if they may affect what's happen in the other loop, then single benchmark isn't a good idea.

UPD: actually I'm not sure how benchmarking would work in this example ^^^ above. Probably I've made a mistake and actually weight(p1) would always include weight(max(p2)), as we have seen in original benchmark.

I don't think you're totally off here. As I said, the bench framework will use max(p | v) depending on the bench. That being said, it's trying to construct a formula in the form of W = A*p + B*v, so if they are correlated the model doesn't quite work (which is what's happening in our case).

[HCastano]

So I ran the following benchmarks. They're a combination your "actual" benchmarks, the benchmarks you're using for calculations, and my proposed weight calculation.

Using the resulting weight.rs output I then plugged them into a spreadsheet as you've done.

p	v		submit_finality_proof	Calculated (Slava)	Actual (Slava)
4	4		218129000	410445000	251110000
8	8		408017000	600041000	436597000
16	16		787793000	979233000	812402000
32	32		1547345000	1737617000	1569048000
64	64		3066449000	3254385000	3074437000
128	128		6104657000	6287921000	6094292000
256	256		12181073000	12354993000	12154561000
512	512		24333905000	24489137000	24266001000
1024	1024		48639569000	48757425000	48593006000
2048	2048		97250897000	97294001000	97266311000
4096	4096		194473553000	194367153000	194707441000
8192	8192		388918865000	388513457000	390276707000

So I don't think we need to go through the trouble of deriving some calculated benchmark result if we can use the actual results directly.

[svyatonik]

Ok, I've changed to single benchmark. Your results, however, show that the computed result would always be less than actual, which I wanted to avoid. But if you feels that's the correct way - here you are

[HCastano]

Ok, I've changed to single benchmark. Your results, however, show that the computed result would always be less than actual, which I wanted to avoid.

Why were you trying to avoid that? The differences, especially at higher values of p and v are quite small, so I don't see the problem here

But if you feels that's the correct way - here you are

I'm not trying to impose my will on you here, I'm just trying to understand the different approaches and presenting what I think is simpler and equally accurate. If you disagree that's fine - let's work through it. We're both trying to work towards the same goal 😄

[svyatonik]

I wanted to avoid that because weight represents computation time. If weight formula returns weight that is less than actual, it would mean that block production may take a longer-than-expected time. In worst case, iiuc, it means missing the slot and slashing.

I agree that the single benchmark shows quite accurate results - honestly, I was assuming that it'll behave much worse. Simply because this base weight (a in a + b*x) will be computed incorrectly. But apparently it is ok - in mine version I've been adding extra precommit, the same may be done here to achieve the same (upper weight limit).

[svyatonik]

(I forgot it is a draft :/ )

[HCastano]

👍

[tomusdrw]

Looks good! Let me just re-run the benchmarks on standardized hardware.

[HCastano]

@tomusdrw any updates with the benches?