openpgp: De-duplicate cert components before checking signatures.

  - Before we do anything, we'll order and deduplicate the components.
    If two components are the same, they will be merged, and their
    signatures will also be deduplicated.  This improves the
    performance considerably when we update a certificate, because the
    certificates will be most likely almost identical, and we avoid
    about half of the signature verifications.

  - And indeed, benchmarking shows a 45% performance improvement on a
    typical cert.

  - Fixes #644.

2 files changed, 24 insertions, 1 deletions

diff --git a/openpgp/benches/merge_cert.rs b/openpgp/benches/merge_cert.rs
new file mode 100644
index 00000000..a628e60a
--- /dev/null
+++ b/openpgp/benches/merge_cert.rs
@@ -0,0 +1,20 @@
+use criterion::{
+    criterion_group, Criterion,
+};
+
+use sequoia_openpgp as openpgp;
+use openpgp::cert::Cert;
+use openpgp::parse::Parse;
+
+/// Benchmark merging a typical cert with itself.
+fn bench_merge_certs(c: &mut Criterion) {
+    let mut group = c.benchmark_group("merge cert with itself");
+    let neal = Cert::from_bytes(include_bytes!("../tests/data/keys/neal.pgp"))
+        .unwrap();
+    group.bench_function("neal.pgp", |b| b.iter(|| {
+        neal.clone().merge_public(neal.clone()).unwrap();
+    }));
+    group.finish();
+}
+
+criterion_group!(benches, bench_merge_certs);
diff --git a/openpgp/benches/run_benchmarks.rs b/openpgp/benches/run_benchmarks.rs
index fc872af7..f5210747 100644
--- a/openpgp/benches/run_benchmarks.rs
+++ b/openpgp/benches/run_benchmarks.rs
@@ -18,6 +18,8 @@ mod generate_cert;
 use generate_cert::benches as generate_cert;
 mod parse_cert;
 use parse_cert::benches as parse_cert;
+mod merge_cert;
+use merge_cert::benches as merge_cert;
 
 // Add all benchmark functions here
 criterion_main!(
@@ -28,5 +30,6 @@ criterion_main!(
     encrypt,
     decrypt,
     generate_cert,
-    parse_cert
+    parse_cert,
+    merge_cert,
 );