swift-crypto
swift-crypto copied to clipboard
apple
Reduce the number of heap allocations when computing hash digests
This PR reduces the number of heap allocations needed to compute a hash digest from 7 to 1.
Checklist
- [x] I've run tests to see all new and existing tests pass
- [x] I've followed the code style of the rest of the project
- [x] I've read the Contribution Guidelines
- [x] I've updated the documentation if necessary
Motivation:
Currently, computing a hash digest requires 7 heap allocations:
- A first
DigestContextobject is created during init. - Its
EVP_MD_CTXstruct is allocated byEVP_MD_CTX_new. md_datais allocated when initializing the context usingEVP_DigestInit.- A second
DigestContextobject is created during finalize - Its
EVP_MD_CTXstruct is allocated byEVP_MD_CTX_new. md_datais allocated when copying the context usingEVP_MD_CTX_copy.- A temporary array is created to store the result of
EVP_DigestFinalize.
This means that for small messages the HashFunction.hash method spends most of its time allocating and deallocating memory.
Generally, users will only compute a few hash digests and aren't really concerned by the performance. But sometimes, it may be necessary to compute a lot of hash digests as fast as possible. Possible use cases include:
- Implementing the PBKDF2 key derivation function, which isn't implemented in Swift Crypto yet.
- Implementing some other key derivation function that definitively won't be implemented in Swift Crypto.
Modifications:
- The temporary array is replaced by a temporary stack-allocated buffer.
- The specialized
MD5_*/SHA*_*APIs are used instead of the genericEVP_MD_*APIs. - The
MD5_CTX/SHA*_CTXdigest context is stored inline in theDigestContextobject. - When calling
finalize, the temporary digest context copy is allocated on the stack as a temporary variable. - The context and digest buffers are zeroized after use.
Result:
On its own, this change makes hashing about 2x faster and computing HMAC authentication codes about 1.5x faster.
On my machine (MacBook Pro 14-inch 2021) with suggested changes (@exclusivity(unchecked) between parentheses)
MD5: 19.1 → 10.5 seconds (9.0 seconds) SHA1: 15.8 → 7.5 seconds (6.2 seconds) SHA256: 16.1 → 7.7 seconds (6.3 seconds) SHA384: 20.4 → 10.6 seconds (9.2 seconds) SHA512: 19.8 → 10.6 seconds (9.1 seconds) HMAC-MD5: 50.4 → 31.0 seconds (28.6 seconds) HMAC-SHA1: 42.9 → 25.1 seconds (22.9 seconds) HMAC-SHA256: 43.5 → 25.7 seconds (23.1 seconds) HMAC-SHA384: 52.0 → 31.4 seconds (29.2 seconds) HMAC-SHA512: 50.5 → 32.0 seconds (29.3 seconds)
Test code
import Crypto
import Foundation
func testDigest<H: HashFunction>(_ type: H.Type) {
let start = Date()
let iterations = 50_000_000
var hasher = H()
let original = hasher
var digest = hasher.finalize()
for _ in 1 ..< iterations {
hasher = original
digest.withUnsafeBytes { bytes in
hasher.update(data: bytes)
}
digest = hasher.finalize()
}
let duration = -start.timeIntervalSinceNow
print("\(H.self): \(String(format: "%.1f", duration)) seconds")
}
func testHMAC<H: HashFunction>(_ type: H.Type) {
let start = Date()
let iterations = 50_000_000
let key = SymmetricKey(data: Data())
var hmac = HMAC<H>(key: key)
let original = hmac
var digest = hmac.finalize()
for _ in 1 ..< iterations {
hmac = original
digest.withUnsafeBytes { bytes in
hmac.update(data: bytes)
}
digest = hmac.finalize()
}
let duration = -start.timeIntervalSinceNow
print("HMAC-\(H.self): \(String(format: "%.1f", duration)) seconds")
}
testDigest(Crypto.Insecure.MD5.self)
testDigest(Crypto.Insecure.SHA1.self)
testDigest(Crypto.SHA256.self)
testDigest(Crypto.SHA384.self)
testDigest(Crypto.SHA512.self)
testHMAC(Crypto.Insecure.MD5.self)
testHMAC(Crypto.Insecure.SHA1.self)
testHMAC(Crypto.SHA256.self)
testHMAC(Crypto.SHA384.self)
testHMAC(Crypto.SHA512.self)
