Optimize suffix building in FileTest::ReadNext().
Updating HPKE to draft-irtf-cfrg-hpke-07 added a number of tests to
crypto/hpke/hpke_test_vectors.txt. The time to run HPKE crypto tests
increased from 0.09 to 0.56 seconds (averaged over 6 runs). The runtime
for the whole crypto_test suite increased from 86.44 to 88.19 (measured
once).
Profiling revealed an excessive amount of CPU time (~50% for HPKE tests)
spent on std::map lookups in ReadNext(). I found a slow loop that
computes the suffix for a repeated attribute by hammering a std::map
with incremental guesses.
This CL adds a std::map<std::string, size_t> for counting repeated
attributes, eliminating the need for the loop. This reduces the runtime
for HPKE tests from 0.56 to 0.12 seconds (averaged over 6 runs). For the
whole crypto_test suite, runtime is reduced from 88.19 to 86.71
seconds (measured once).
Change-Id: Ie87f4a7f3edc95d434226d2959dcf09974f0656f
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/44905
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/test/file_test.cc b/crypto/test/file_test.cc
index 963429d..47a6f4c 100644
--- a/crypto/test/file_test.cc
+++ b/crypto/test/file_test.cc
@@ -205,11 +205,10 @@
// Duplicate keys are rewritten to have “/2”, “/3”, … suffixes.
std::string mapped_key = key;
- for (unsigned i = 2; attributes_.count(mapped_key) != 0; i++) {
- char suffix[32];
- snprintf(suffix, sizeof(suffix), "/%u", i);
- suffix[sizeof(suffix)-1] = 0;
- mapped_key = key + suffix;
+ // If absent, the value will be zero-initialized.
+ const size_t num_occurrences = ++attribute_count_[key];
+ if (num_occurrences > 1) {
+ mapped_key += "/" + std::to_string(num_occurrences);
}
unused_attributes_.insert(mapped_key);
@@ -317,6 +316,7 @@
start_line_ = 0;
type_.clear();
parameter_.clear();
+ attribute_count_.clear();
attributes_.clear();
unused_attributes_.clear();
unused_instructions_.clear();
diff --git a/crypto/test/file_test.h b/crypto/test/file_test.h
index 87f306f..1502003 100644
--- a/crypto/test/file_test.h
+++ b/crypto/test/file_test.h
@@ -221,6 +221,9 @@
std::string type_;
// parameter_ is the value of the first attribute.
std::string parameter_;
+ // attribute_count_ maps unsuffixed attribute names to the number of times
+ // they have occurred so far.
+ std::map<std::string, size_t> attribute_count_;
// attributes_ contains all attributes in the test, including the first.
std::map<std::string, std::string> attributes_;
// instructions_ contains all instructions in scope for the test.