Parcels? Subparcels? Not just for STV hand counts! – OpenTally dev log

Single transferable vote rules designed for hand-counting often contain references to ‘parcels’ (or ‘bundles’ or ‘batches’), ‘further parcels’ and sometimes even ‘subparcels’.

For example, consider the 4th stage of the ERS97 model election. 107 of Glazier's and Wright's ballot papers are aggregated according to value, and sorted into parcels according to next available preference, as shown on the exclusion form.

The papers with a next available preference for Abbott comprise 2 parcels: a parcel of 1 ballot paper at full value, and a parcel of 6 ballot papers at value 0.21. Under the ERS97 rules, the total value of the second parcel is 6 × 0.21 = 1.26.

To summarise the approach, rules for hand-count STV segregate ballot papers into ‘parcels’, such that each parcel contains ballot papers of only one value. This allows the total value of the parcel to be easily calculated by multiplying the number of ballot papers (easily counted) by the value of each.

In contrast, consider the OpenTally WIGM rules, which are unashamedly computer-count-only. The OpenTally WIGM rules make no mention of parcels or segregating ballot papers – they deal with each ballot paper and track the value of each individually:

ballot paper means a record of a voter's preferences, with an associated value; …

progress total: a candidate's progress total means the sum of the values of all ballot papers allocated to the candidate.

The parcel-less approach makes for significantly simpler provisions. One might think, then, that the notion of ‘parcels’ is an unnecessary anachronism in the computer age. If, however, we blindly follow these provisions in the translation to implementation, this can have adverse implications for performance.

Consider the following benchmarks:

use rug::Rational;
use std::{str::FromStr, time::Instant};

fn main() {
	let fract =
		Rational::from_str("457895675326723623").unwrap() /
		Rational::from_str("3257893783827146791234").unwrap();
	
	let one = Rational::from(1);
	
	// Add 1s
	
	let instant = Instant::now();
	let result = (0..10_000_000).fold(Rational::new(), |acc, _| acc + &one);
	let result = result * &fract;
	println!("Add 1s: {} ms - {}", instant.elapsed().as_millis(), result);
	
	// Add fractions
	
	let instant = Instant::now();
	let result = (0..10_000_000).fold(Rational::new(), |acc, _| acc + &fract);
	println!("Add fractions: {} ms - {}", instant.elapsed().as_millis(), result);
}

The 2 implementations clearly give equivalent results, but the first, equivalent to the parcel-based approach, has a mean execution time (±95%CI) of 444 (±2) milliseconds. The second, equivalent to the naive parcel-less approach, runs in 2810 (±30) milliseconds, over 6 times as slow!

The reason is simple to see. In the first example, the inner body of the loop is computationally very simple, merely adding integers. In the second example, the inner body of the loop is more complicated – by adding fractions, the result must be canonicalised (reduced to lowest terms) after each operation.

OpenTally has always segregated votes into parcels, even for systems that do not make the distinction. However, previously, all sums were implemented using the naive parcel-less approach, where vote values were tracked at the level of individual ballot papers.¹ OpenTally has now been revised to use the parcel-based summation approach in all methods, with vote values tracked at the level of parcels.

Under Rust, a count of the 351,988-vote 2019 Tasmanian Senate election using the old implementation ran in a mean execution time (±95%CI) of 0.901 (±0.006) seconds, whereas the new implementation runs in 0.657 (±0.007) seconds, a nearly 40% improvement in performance.