diff options
| author | Pauli <pauli@openssl.org> | 2022-03-28 12:14:22 +1100 |
|---|---|---|
| committer | Pauli <ppzgs1@gmail.com> | 2022-03-30 16:57:45 +1100 |
| commit | 514bd51a8cb901a7351ecdc45a680d6aba720b5a (patch) | |
| tree | 149990192a2ad6ec2ff0a7062ca21c817f24e871 /crypto | |
| parent | 87639c6bdfa976f673d37c067e28fc89c1dfaa5e (diff) | |
sparse array: reduces the block size
This becomes a performance improvement in the ossl_sa_doall_arg function which
has started appearing on profile output. The other ossl_sa_ functions don't
contribute significantly to profile output.
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/17973)
Diffstat (limited to 'crypto')
| -rw-r--r-- | crypto/sparse_array.c | 23 |
1 files changed, 9 insertions, 14 deletions
diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c index ac823d569e..2b143e4b7c 100644 --- a/crypto/sparse_array.c +++ b/crypto/sparse_array.c @@ -19,24 +19,19 @@ * depth of the tree but potentially wastes more memory. That is, this is a * direct space versus time tradeoff. * - * The large memory model uses twelve bits which means that the are 4096 - * pointers in each tree node. This is more than sufficient to hold the - * largest defined NID (as of Feb 2019). This means that using a NID to - * index a sparse array becomes a constant time single array look up. - * - * The small memory model uses four bits which means the tree nodes contain - * sixteen pointers. This reduces the amount of unused space significantly - * at a cost in time. + * The default is to use four bits which means that the are 16 + * pointers in each tree node. * * The library builder is also permitted to define other sizes in the closed - * interval [2, sizeof(ossl_uintmax_t) * 8]. + * interval [2, sizeof(ossl_uintmax_t) * 8]. Space use generally scales + * exponentially with the block size, although the implementation only + * creates enough blocks to support the largest used index. The depth is: + * ceil(log_2(largest index) / 2^{block size}) + * E.g. with a block size of 4, and a largest index of 1000, the depth + * will be three. */ #ifndef OPENSSL_SA_BLOCK_BITS -# ifdef OPENSSL_SMALL_FOOTPRINT -# define OPENSSL_SA_BLOCK_BITS 4 -# else -# define OPENSSL_SA_BLOCK_BITS 12 -# endif +# define OPENSSL_SA_BLOCK_BITS 4 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1) # error OPENSSL_SA_BLOCK_BITS is out of range #endif |