Weight refunds for staking extrinsics potentially using SortedListProvider

[emostov]

paritytech/substrate#9507 introduced the SortedListProvider for keeping an ordered list of nominators. For extrinsics using the SortedListProvider this dramatically increased their worst case weight; in some cases though certain logic paths have dramatically less weight. Benchmarks should be updated to document less expensive code paths and give relevant refunds.

(rel: paritytech/polkadot#3872 (comment))

[kianenigma]

I came across this again while thinking about all of this. I think this is quite important, and we should do it before we deploy this on Polkadot.

[kianenigma]

cc @emostov something for you to consider on the side.

[emostov]

Might also be a good FRAME entry point for @rossbulat

[rossbulat]

I am happy to be assigned this and play with the benchmarking.

[emostov]

Looking closer, the only scenario for SortedListProvider::on_update where we should see a significant weight reduction is if the voter does not change bags. The current weight setup is

	/// - the node to be updated (r) is the head of a bag that has at least one other node. The bag
	///   itself will need to be read and written to update its head. The node pointed to by r.next
	///   will need to be read and written as it will need to have its prev pointer updated. Note
	///   that there are two other worst case scenarios for bag removal: 1) the node is a tail and
	///   2) the node is a middle node with prev and next; all scenarios end up with the same number
	///   of storage reads and writes.
	///
	/// - the destination bag has at least one node, which will need its next pointer updated.

As the above mentions, the other worst cases are that in the source bag the node is the tail or the node is a middle node with a prev and next pointer. This means that in any scenario where the node moves we will see the same count of read/writes for the operations related to the source bag. For the destination bag, the only cheaper scenario is that the bag does not already exist, which I hypothesize to be a relatively rare occurrence.

With this in mind, I propose that SortedListProvider::on_update return a bool or enum indicating if the node changed bags (this is an easy change, since do_rebag returns an option indicating this). We can then make the refund conditional on the returned value.

If this approach sounds ok, I see 3 parts to implementing this, (which could be broken into separate PRs)

1. change the signature of SortedListProvider::on_update to return a bool or enum indicating if the node changed bags
2. create new benchmarks for staking extrinsics that use SortedListProvider::on_update. The benchmarks would be a scenario where the node doesn't change bags
3. implement refund logic by return the weight from the new benchmarks if no refund happened

(Parts 1 and 2 are not dependent on each other)