diff options
author | antirez <antirez@gmail.com> | 2014-04-17 17:53:20 +0200 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2014-04-18 16:16:20 +0200 |
commit | 3f5cd0c6605d71574b254fa4a6eb5964f8711f9b (patch) | |
tree | b85f8b81bc8eb7cbd3f6f3bb7e12beb9f5cd5fac | |
parent | f0eca148fffc265def5b5e07b679495d95e83f60 (diff) | |
download | redis-3f5cd0c6605d71574b254fa4a6eb5964f8711f9b.tar.gz |
Speedup SUM(2^-reg[m]) in HyperLogLog computation.
When the register is set to zero, we need to add 2^-0 to E, which is 1,
but it is faster to just add 'ez' at the end, which is the number of
registers set to zero, a value we need to compute anyway.
-rw-r--r-- | src/hyperloglog.c | 12 |
1 files changed, 8 insertions, 4 deletions
diff --git a/src/hyperloglog.c b/src/hyperloglog.c index a44df87c9..c951c09f7 100644 --- a/src/hyperloglog.c +++ b/src/hyperloglog.c @@ -546,11 +546,12 @@ double hllDenseSum(uint8_t *registers, double *PE, int *ezp) { HLL_DENSE_GET_REGISTER(reg,registers,j); if (reg == 0) { ez++; - E += 1; /* 2^(-reg[j]) is 1 when m is 0. */ + /* Increment E at the end of the loop. */ } else { E += PE[reg]; /* Precomputed 2^(-reg[j]). */ } } + E += ez; /* Add 2^0 'ez' times. */ } *ezp = ez; return E; @@ -894,13 +895,13 @@ double hllSparseSum(uint8_t *sparse, int sparselen, double *PE, int *ezp, int *i runlen = HLL_SPARSE_ZERO_LEN(p); idx += runlen; ez += runlen; - E += 1*runlen; /* 2^(-reg[j]) is 1 when m is 0. */ + /* Increment E at the end of the loop. */ p++; } else if (HLL_SPARSE_IS_XZERO(p)) { runlen = HLL_SPARSE_XZERO_LEN(p); idx += runlen; ez += runlen; - E += 1*runlen; /* 2^(-reg[j]) is 1 when m is 0. */ + /* Increment E at the end of the loop. */ p += 2; } else { runlen = HLL_SPARSE_VAL_LEN(p); @@ -911,6 +912,7 @@ double hllSparseSum(uint8_t *sparse, int sparselen, double *PE, int *ezp, int *i } } if (idx != HLL_REGISTERS && invalid) *invalid = 1; + E += ez; /* Add 2^0 'ez' times. */ *ezp = ez; return E; } @@ -932,11 +934,13 @@ double hllRawSum(uint8_t *registers, double *PE, int *ezp) { reg = registers[j]; if (reg == 0) { ez++; - E += 1; /* 2^(-reg[j]) is 1 when m is 0. */ + /* Increment E at the end of the loop. */ } else { E += PE[reg]; /* Precomputed 2^(-reg[j]). */ } } + E += ez; /* 2^(-reg[j]) is 1 when m is 0, add it 'ez' times for every + zero register in the HLL. */ *ezp = ez; return E; } |