referrerpolicy=no-referrer-when-downgrade

pallet_elections_phragmen/
benchmarking.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Elections-Phragmen pallet benchmarking.
19
20#![cfg(feature = "runtime-benchmarks")]
21
22use frame_benchmarking::v2::*;
23use frame_support::{dispatch::DispatchResultWithPostInfo, traits::OnInitialize};
24use frame_system::RawOrigin;
25
26#[cfg(test)]
27use crate::tests::MEMBERS;
28use crate::*;
29
30const BALANCE_FACTOR: u32 = 250;
31
32// grab new account with infinite balance.
33fn endowed_account<T: Config>(name: &'static str, index: u32) -> T::AccountId {
34	let account: T::AccountId = account(name, index, 0);
35	// Fund each account with at-least their stake but still a sane amount as to not mess up
36	// the vote calculation.
37	let amount = default_stake::<T>(T::MaxVoters::get()) * BalanceOf::<T>::from(BALANCE_FACTOR);
38	let _ = T::Currency::make_free_balance_be(&account, amount);
39	// Important to increase the total issuance since `T::CurrencyToVote` will need it to be sane
40	// for phragmen to work.
41	let _ = T::Currency::issue(amount);
42
43	account
44}
45
46// Account to lookup type of system trait.
47fn as_lookup<T: Config>(account: T::AccountId) -> AccountIdLookupOf<T> {
48	T::Lookup::unlookup(account)
49}
50
51// Get a reasonable amount of stake based on the execution trait's configuration.
52fn default_stake<T: Config>(num_votes: u32) -> BalanceOf<T> {
53	let min = T::Currency::minimum_balance();
54	Pallet::<T>::deposit_of(num_votes as usize).max(min)
55}
56
57// Get the current number of candidates.
58fn candidate_count<T: Config>() -> u32 {
59	Candidates::<T>::decode_len().unwrap_or(0usize) as u32
60}
61
62// Add `c` new candidates.
63fn submit_candidates<T: Config>(
64	c: u32,
65	prefix: &'static str,
66) -> Result<Vec<T::AccountId>, &'static str> {
67	(0..c)
68		.map(|i| {
69			let account = endowed_account::<T>(prefix, i);
70			Pallet::<T>::submit_candidacy(
71				RawOrigin::Signed(account.clone()).into(),
72				candidate_count::<T>(),
73			)
74			.map_err(|_| "failed to submit candidacy")?;
75			Ok(account)
76		})
77		.collect::<Result<_, _>>()
78}
79
80// Add `c` new candidates with self vote.
81fn submit_candidates_with_self_vote<T: Config>(
82	c: u32,
83	prefix: &'static str,
84) -> Result<Vec<T::AccountId>, &'static str> {
85	let candidates = submit_candidates::<T>(c, prefix)?;
86	let stake = default_stake::<T>(c);
87	candidates
88		.iter()
89		.try_for_each(|c| submit_voter::<T>(c.clone(), vec![c.clone()], stake).map(|_| ()))?;
90	Ok(candidates)
91}
92
93// Submit one voter.
94fn submit_voter<T: Config>(
95	caller: T::AccountId,
96	votes: Vec<T::AccountId>,
97	stake: BalanceOf<T>,
98) -> DispatchResultWithPostInfo {
99	Pallet::<T>::vote(RawOrigin::Signed(caller).into(), votes, stake)
100}
101
102// Create `num_voter` voters who randomly vote for at most `votes` of `all_candidates` if
103// available.
104fn distribute_voters<T: Config>(
105	mut all_candidates: Vec<T::AccountId>,
106	num_voters: u32,
107	votes: usize,
108) -> Result<(), &'static str> {
109	let stake = default_stake::<T>(num_voters);
110	for i in 0..num_voters {
111		// to ensure that votes are different
112		all_candidates.rotate_left(1);
113		let votes = all_candidates.iter().cloned().take(votes).collect::<Vec<_>>();
114		let voter = endowed_account::<T>("voter", i);
115		submit_voter::<T>(voter, votes, stake)?;
116	}
117	Ok(())
118}
119
120// Fill the seats of members and runners-up up until `m`. Note that this might include either only
121// members, or members and runners-up.
122fn fill_seats_up_to<T: Config>(m: u32) -> Result<Vec<T::AccountId>, &'static str> {
123	submit_candidates_with_self_vote::<T>(m, "fill_seats_up_to")?;
124	assert_eq!(Candidates::<T>::get().len() as u32, m, "wrong number of candidates.");
125	Pallet::<T>::do_phragmen();
126	assert_eq!(Candidates::<T>::get().len(), 0, "some candidates remaining.");
127	assert_eq!(
128		Members::<T>::get().len() + RunnersUp::<T>::get().len(),
129		m as usize,
130		"wrong number of members and runners-up",
131	);
132	Ok(Members::<T>::get()
133		.into_iter()
134		.map(|m| m.who)
135		.chain(RunnersUp::<T>::get().into_iter().map(|r| r.who))
136		.collect())
137}
138
139// Removes all the storage items to reverse any genesis state.
140fn clean<T: Config>() {
141	Members::<T>::kill();
142	Candidates::<T>::kill();
143	RunnersUp::<T>::kill();
144	#[allow(deprecated)]
145	Voting::<T>::remove_all(None);
146}
147
148#[benchmarks]
149mod benchmarks {
150	use super::*;
151
152	// -- Signed ones
153	#[benchmark]
154	fn vote_equal(v: Linear<1, { T::MaxVotesPerVoter::get() }>) -> Result<(), BenchmarkError> {
155		clean::<T>();
156
157		// create a bunch of candidates.
158		let all_candidates = submit_candidates::<T>(v, "candidates")?;
159
160		let caller = endowed_account::<T>("caller", 0);
161		let stake = default_stake::<T>(v);
162
163		// Original votes.
164		let mut votes = all_candidates;
165		submit_voter::<T>(caller.clone(), votes.clone(), stake)?;
166
167		// New votes.
168		votes.rotate_left(1);
169
170		whitelist!(caller);
171
172		#[extrinsic_call]
173		vote(RawOrigin::Signed(caller), votes, stake);
174
175		Ok(())
176	}
177
178	#[benchmark]
179	fn vote_more(v: Linear<2, { T::MaxVotesPerVoter::get() }>) -> Result<(), BenchmarkError> {
180		clean::<T>();
181
182		// Create a bunch of candidates.
183		let all_candidates = submit_candidates::<T>(v, "candidates")?;
184
185		let caller = endowed_account::<T>("caller", 0);
186		// Multiply the stake with 10 since we want to be able to divide it by 10 again.
187		let stake = default_stake::<T>(v) * BalanceOf::<T>::from(10_u32);
188
189		// Original votes.
190		let mut votes = all_candidates.iter().skip(1).cloned().collect::<Vec<_>>();
191		submit_voter::<T>(caller.clone(), votes.clone(), stake / BalanceOf::<T>::from(10_u32))?;
192
193		// New votes.
194		votes = all_candidates;
195		assert!(votes.len() > Voting::<T>::get(caller.clone()).votes.len());
196
197		whitelist!(caller);
198
199		#[extrinsic_call]
200		vote(RawOrigin::Signed(caller), votes, stake / BalanceOf::<T>::from(10_u32));
201
202		Ok(())
203	}
204
205	#[benchmark]
206	fn vote_less(v: Linear<2, { T::MaxVotesPerVoter::get() }>) -> Result<(), BenchmarkError> {
207		clean::<T>();
208
209		// Create a bunch of candidates.
210		let all_candidates = submit_candidates::<T>(v, "candidates")?;
211
212		let caller = endowed_account::<T>("caller", 0);
213		let stake = default_stake::<T>(v);
214
215		// Original votes.
216		let mut votes = all_candidates;
217		submit_voter::<T>(caller.clone(), votes.clone(), stake)?;
218
219		// New votes.
220		votes = votes.into_iter().skip(1).collect::<Vec<_>>();
221		assert!(votes.len() < Voting::<T>::get(caller.clone()).votes.len());
222
223		whitelist!(caller);
224
225		#[extrinsic_call]
226		vote(RawOrigin::Signed(caller), votes, stake);
227
228		Ok(())
229	}
230
231	#[benchmark]
232	fn remove_voter() -> Result<(), BenchmarkError> {
233		// We fix the number of voted candidates to max.
234		let v = T::MaxVotesPerVoter::get();
235		clean::<T>();
236
237		// Create a bunch of candidates.
238		let all_candidates = submit_candidates::<T>(v, "candidates")?;
239
240		let caller = endowed_account::<T>("caller", 0);
241
242		let stake = default_stake::<T>(v);
243		submit_voter::<T>(caller.clone(), all_candidates, stake)?;
244
245		whitelist!(caller);
246
247		#[extrinsic_call]
248		_(RawOrigin::Signed(caller));
249
250		Ok(())
251	}
252
253	#[benchmark]
254	fn submit_candidacy(
255		// Number of already existing candidates.
256		c: Linear<1, { T::MaxCandidates::get() }>,
257	) -> Result<(), BenchmarkError> {
258		// We fix the number of members to the number of desired members and runners-up.
259		// We'll be in this state almost always.
260		let m = T::DesiredMembers::get() + T::DesiredRunnersUp::get();
261
262		clean::<T>();
263
264		// Create `m` members and runners combined.
265		fill_seats_up_to::<T>(m)?;
266
267		// Create previous candidates.
268		submit_candidates::<T>(c, "candidates")?;
269
270		// We assume worse case that: extrinsic is successful and candidate is not duplicate.
271		let candidate_account = endowed_account::<T>("caller", 0);
272		whitelist!(candidate_account);
273
274		#[extrinsic_call]
275		_(RawOrigin::Signed(candidate_account), candidate_count::<T>());
276
277		// Reset members in between benchmark tests.
278		#[cfg(test)]
279		MEMBERS.with(|m| *m.borrow_mut() = vec![]);
280
281		Ok(())
282	}
283
284	#[benchmark]
285	fn renounce_candidacy_candidate(
286		// This will check members, runners-up and candidate for removal.
287		// Members and runners-up are limited by the runtime bound, nonetheless we fill them by
288		// `m`.
289		// Number of already existing candidates.
290		c: Linear<1, { T::MaxCandidates::get() }>,
291	) -> Result<(), BenchmarkError> {
292		// We fix the number of members to the number of desired members and runners-up.
293		// We'll be in this state almost always.
294		let m = T::DesiredMembers::get() + T::DesiredRunnersUp::get();
295
296		clean::<T>();
297
298		// Create `m` members and runners combined.
299		fill_seats_up_to::<T>(m)?;
300		let all_candidates = submit_candidates::<T>(c, "caller")?;
301
302		let bailing = all_candidates[0].clone(); // Should be ("caller", 0)
303		let count = candidate_count::<T>();
304		whitelist!(bailing);
305
306		#[extrinsic_call]
307		renounce_candidacy(RawOrigin::Signed(bailing), Renouncing::Candidate(count));
308
309		// Reset members in between benchmark tests.
310		#[cfg(test)]
311		MEMBERS.with(|m| *m.borrow_mut() = vec![]);
312
313		Ok(())
314	}
315
316	#[benchmark]
317	fn renounce_candidacy_members() -> Result<(), BenchmarkError> {
318		// Removing members and runners will be cheaper than a candidate.
319		// We fix the number of members to when members and runners-up to the desired.
320		// We'll be in this state almost always.
321		let m = T::DesiredMembers::get() + T::DesiredRunnersUp::get();
322		clean::<T>();
323
324		// Create `m` members and runners combined.
325		let members_and_runners_up = fill_seats_up_to::<T>(m)?;
326
327		let bailing = members_and_runners_up[0].clone();
328		assert!(Pallet::<T>::is_member(&bailing));
329
330		whitelist!(bailing);
331
332		#[extrinsic_call]
333		renounce_candidacy(RawOrigin::Signed(bailing.clone()), Renouncing::Member);
334
335		// Reset members in between benchmark tests.
336		#[cfg(test)]
337		MEMBERS.with(|m| *m.borrow_mut() = vec![]);
338
339		Ok(())
340	}
341
342	#[benchmark]
343	fn renounce_candidacy_runners_up() -> Result<(), BenchmarkError> {
344		// Removing members and runners will be cheaper than a candidate.
345		// We fix the number of members to when members and runners-up to the desired.
346		// We'll be in this state almost always.
347		let m = T::DesiredMembers::get() + T::DesiredRunnersUp::get();
348		clean::<T>();
349
350		// Create `m` members and runners combined.
351		let members_and_runners_up = fill_seats_up_to::<T>(m)?;
352
353		let bailing = members_and_runners_up[T::DesiredMembers::get() as usize + 1].clone();
354		assert!(Pallet::<T>::is_runner_up(&bailing));
355
356		whitelist!(bailing);
357
358		#[extrinsic_call]
359		renounce_candidacy(RawOrigin::Signed(bailing.clone()), Renouncing::RunnerUp);
360
361		// Reset members in between benchmark tests.
362		#[cfg(test)]
363		MEMBERS.with(|m| *m.borrow_mut() = vec![]);
364
365		Ok(())
366	}
367
368	// We use the max block weight for this extrinsic for now. See below.
369	#[benchmark]
370	fn remove_member_without_replacement() -> Result<(), BenchmarkError> {
371		#[block]
372		{
373			Err(BenchmarkError::Override(BenchmarkResult::from_weight(
374				T::BlockWeights::get().max_block,
375			)))?;
376		}
377
378		Ok(())
379	}
380
381	#[benchmark]
382	fn remove_member_with_replacement() -> Result<(), BenchmarkError> {
383		// Easy case.
384		// We have a runner up.
385		// Nothing will have that much of an impact.
386		// `m` will be number of members and runners.
387		// There is always at least one runner.
388		let m = T::DesiredMembers::get() + T::DesiredRunnersUp::get();
389		clean::<T>();
390
391		fill_seats_up_to::<T>(m)?;
392		let removing = as_lookup::<T>(Pallet::<T>::members_ids()[0].clone());
393
394		#[extrinsic_call]
395		remove_member(RawOrigin::Root, removing, true, false);
396
397		// Must still have enough members.
398		assert_eq!(Members::<T>::get().len() as u32, T::DesiredMembers::get());
399
400		// Reset members in between benchmark tests.
401		#[cfg(test)]
402		MEMBERS.with(|m| *m.borrow_mut() = vec![]);
403
404		Ok(())
405	}
406
407	#[benchmark]
408	fn clean_defunct_voters(
409		// Total number of voters.
410		v: Linear<{ T::MaxVoters::get() / 2 }, { T::MaxVoters::get() }>,
411		// Those that are defunct and need removal.
412		d: Linear<0, { T::MaxVoters::get() / 2 }>,
413	) -> Result<(), BenchmarkError> {
414		// Remove any previous stuff.
415		clean::<T>();
416
417		let all_candidates = submit_candidates::<T>(T::MaxCandidates::get(), "candidates")?;
418		distribute_voters::<T>(all_candidates, v, T::MaxVotesPerVoter::get() as usize)?;
419
420		// All candidates leave.
421		Candidates::<T>::kill();
422
423		// Now everyone is defunct.
424		assert!(Voting::<T>::iter().all(|(_, v)| Pallet::<T>::is_defunct_voter(&v.votes)));
425		assert_eq!(Voting::<T>::iter().count() as u32, v);
426
427		#[extrinsic_call]
428		_(RawOrigin::Root, v, d);
429
430		assert_eq!(Voting::<T>::iter().count() as u32, v - d);
431
432		Ok(())
433	}
434
435	#[benchmark]
436	fn election_phragmen(
437		// This is just to focus on phragmen in the context of this module.
438		// We always select 20 members, this is hard-coded in the runtime and cannot be trivially
439		// changed at this stage. Yet, change the number of voters, candidates and edge per voter
440		// to see the impact. Note that we give all candidates a self vote to make sure they are
441		// all considered.
442		c: Linear<1, { T::MaxCandidates::get() }>,
443		v: Linear<1, { T::MaxVoters::get() }>,
444		e: Linear<{ T::MaxVoters::get() }, { T::MaxVoters::get() * T::MaxVotesPerVoter::get() }>,
445	) -> Result<(), BenchmarkError> {
446		clean::<T>();
447
448		// So we have a situation with `v` and `e`.
449		// We want `e` to basically always be in the range of
450		// `e -> e * T::MaxVotesPerVoter::get()`, but we cannot express that now with the
451		// benchmarks. So what we do is: when `c` is being iterated, `v`, and `e` are max and
452		// fine. When `v` is being iterated, `e` is being set to max and this is a problem.
453		// In these cases, we cap `e` to a lower value, namely `v * T::MaxVotesPerVoter::get()`.
454		// When `e` is being iterated, `v` is at max, and again fine.
455		// All in all, `votes_per_voter` can never be more than `T::MaxVotesPerVoter::get()`.
456		// Note that this might cause `v` to be an overestimate.
457		let votes_per_voter = (e / v).min(T::MaxVotesPerVoter::get());
458
459		let all_candidates = submit_candidates_with_self_vote::<T>(c, "candidates")?;
460		distribute_voters::<T>(all_candidates, v.saturating_sub(c), votes_per_voter as usize)?;
461
462		#[block]
463		{
464			Pallet::<T>::on_initialize(T::TermDuration::get());
465		}
466
467		assert_eq!(Members::<T>::get().len() as u32, T::DesiredMembers::get().min(c));
468		assert_eq!(
469			RunnersUp::<T>::get().len() as u32,
470			T::DesiredRunnersUp::get().min(c.saturating_sub(T::DesiredMembers::get())),
471		);
472
473		// reset members in between benchmark tests.
474		#[cfg(test)]
475		MEMBERS.with(|m| *m.borrow_mut() = vec![]);
476
477		Ok(())
478	}
479
480	impl_benchmark_test_suite! {
481		Pallet,
482		tests::ExtBuilder::default().desired_members(13).desired_runners_up(7),
483		tests::Test,
484		exec_name = build_and_execute,
485	}
486}