From 20de516cd303b3c1e4b61272988a9a4ac054f2fa Mon Sep 17 00:00:00 2001 From: Pauli Date: Mon, 28 Mar 2022 12:14:22 +1100 Subject: [PATCH] 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 Reviewed-by: Tomas Mraz (Merged from https://github.com/openssl/openssl/pull/17973) (cherry picked from commit 514bd51a8cb901a7351ecdc45a680d6aba720b5a) --- crypto/sparse_array.c | 23 +++++++++-------------- 1 file 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 -- 2.34.1