summaryrefslogtreecommitdiff
path: root/src/hyperloglog.c
Commit message (Collapse)AuthorAgeFilesLines
* RDMF: More consistent define names.antirez2015-07-271-3/+3
|
* RDMF: REDIS_OK REDIS_ERR -> C_OK C_ERR.antirez2015-07-261-24/+24
|
* RDMF: redisAssert -> serverAssert.antirez2015-07-261-2/+2
|
* RDMF: OBJ_ macros for object related stuff.antirez2015-07-261-2/+2
|
* RDMF: use client instead of redisClient, like Disque.antirez2015-07-261-6/+6
|
* RDMF (Redis/Disque merge friendlyness) refactoring WIP 1.antirez2015-07-261-1/+1
|
* Better read-only behavior for expired keys in slaves.antirez2014-12-101-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Slaves key expire is orchestrated by the master. Sometimes the master will send the synthesized DEL to expire keys on the slave with a non trivial delay (when the key is not accessed, only the incremental expiry algorithm will expire it in background). During that time, a key is logically expired, but slaves still return the key if you GET (or whatever) it. This is a bad behavior. However we can't simply trust the slave view of the key, since we need the master to be able to send write commands to update the slave data set, and DELs should only happen when the key is expired in the master in order to ensure consistency. However 99.99% of the issues with this behavior is when a client which is not a master sends a read only command. In this case we are safe and can consider the key as non existing. This commit does a few changes in order to make this sane: 1. lookupKeyRead() is modified in order to return NULL if the above conditions are met. 2. Calls to lookupKeyRead() in commands actually writing to the data set are repliaced with calls to lookupKeyWrite(). There are redundand checks, so for example, if in "2" something was overlooked, we should be still safe, since anyway, when the master writes the behavior is to don't care about what expireIfneeded() returns. This commit is related to #1768, #1770, #2131.
* Over 80 chars comment trimmed in pfcountCommand().antirez2014-12-021-1/+1
|
* Remove warnings and improve integer sign correctness.antirez2014-08-131-2/+2
|
* PFSELFTEST: less false positives.antirez2014-07-231-2/+10
| | | | | | | This is just a quickfix, for the nature of the test the right way to fix it is to average the error of N runs, since otherwise it is always possible to get a false positive with a bad run, or to minimize too much this possibility we may end testing with too much "large" error ranges.
* Correct the HyperLogLog stale cache flag to prevent unnecessary computations.Mike Trinkala2014-05-181-4/+4
| | | | Set the MSB as documented.
* Speedup hllRawSum() processing 8 bytes per iteration.antirez2014-04-171-7/+15
| | | | | | | | | | The internal HLL raw encoding used by PFCOUNT when merging multiple keys is aligned to 8 bits (1 byte per register) so we can exploit this to improve performances by processing multiple bytes per iteration. In benchmarks the new code was several times faster with HLLs with many registers set to zero, while no slowdown was observed with populated HLLs.
* Speedup SUM(2^-reg[m]) in HyperLogLog computation.antirez2014-04-171-4/+8
| | | | | | 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.
* PFCOUNT support for multi-key union.antirez2014-04-171-5/+72
|
* HyperLogLog low level merge extracted from PFMERGE.antirez2014-04-171-39/+54
|
* HyperLogLog invalid representation error code set to INVALIDOBJ.antirez2014-04-161-7/+7
|
* PFDEBUG TODENSE added.antirez2014-04-161-0/+15
| | | | Converts HyperLogLogs from sparse to dense. Used for testing.
* User-defined switch point between sparse-dense HLL encodings.antirez2014-04-151-6/+5
|
* PFSELFTEST improved with sparse encoding checks.antirez2014-04-151-4/+29
|
* PFDEBUG ENCODING added.antirez2014-04-141-0/+7
|
* Set HLL_SPARSE_MAX to 3000.antirez2014-04-141-1/+1
| | | | | | | | | | | | | | | After running a few benchmarks, 3000 looks like a reasonable value to keep HLLs with a few thousand elements small while the CPU cost is still not huge. This covers all the cases where the dense representation would use N orders of magnitude more space, like in the case of many HLLs with carinality of a few tens or hundreds. It is not impossible that in the future this gets user configurable, however it is easy to pick an unreasoable value just looking at savings in the space dimension without checking what happens in the time dimension.
* Error message for invalid HLL objects unified.antirez2014-04-141-5/+7
|
* PFMERGE fixed to work with sparse encoding.antirez2014-04-141-8/+45
|
* Correctly replicate PFDEBUG GETREG.antirez2014-04-141-3/+6
| | | | | Even if it is a debugging command, make sure that when it forces a change in encoding, the command is propagated.
* Added assertion in hllSparseAdd() when promotion to dense occurs.antirez2014-04-141-1/+11
| | | | | If we converted to dense, a register must be updated in the dense representation.
* hllSparseAdd(): speed optimization.antirez2014-04-141-12/+15
| | | | | Mostly by reordering opcodes check conditional by frequency of opcodes in larger sparse-encoded HLLs.
* Detect corrupted sparse HLLs in hllSparseSum().antirez2014-04-141-11/+18
|
* hllSparseAdd(): faster code removing conditional.antirez2014-04-141-5/+14
| | | | | Bottleneck found profiling. Big run time improvement found when testing after the change.
* Comment typo in hllSparseAdd(). first -> fits.antirez2014-04-141-1/+1
|
* Merge adjacent VAL opcodes in hllSparseAdd().antirez2014-04-141-5/+36
| | | | | As more values are added splitting ZERO or XZERO opcodes, try to merge adjacent VAL opcodes if they have the same value.
* More robust HLL_SPARSE macros protecting 'p' with parens.antirez2014-04-141-8/+8
| | | | Now the macros will work with arguments such as "ptr+1".
* hllSparseAdd() opcode seek stop condition fixed.antirez2014-04-141-1/+1
|
* Fixed error message generation in PFDEBUG GETREG.antirez2014-04-141-1/+2
| | | | | | Bulk length for registers was emitted too early, so if there was a bug the reply looked like a long array with just one element, blocking the client as result.
* Fixed memmove() count in hllSparseAdd().antirez2014-04-141-1/+1
|
* hllSparseAdd(): more correct dense conversion conditional.antirez2014-04-141-1/+1
| | | | | We want to promote if the total string size exceeds the resulting size after the upgrade.
* hllSparseToDense(): sanity check added.antirez2014-04-141-5/+20
| | | | | | | | | | The function checks if all the HLL_REGISTERS were processed during the convertion from sparse to dense encoding, returning REDIS_OK or REDIS_ERR to signal a corruption problem. A bug in PFDEBUG GETREG was fixed: when the object is converted to the dense representation we need to reassign the new pointer to the header structure pointer.
* PFDEBUG DECODE added.antirez2014-04-141-0/+35
| | | | | | Provides a human readable description of the opcodes composing a run-length encoded HLL (sparse encoding). The command is only useful for debugging / development tasks.
* PFDEBUG added, PFGETREG removed.antirez2014-04-131-7/+23
| | | | | PFDEBUG will be the interface to do debugging tasks with a key containing an HLL object.
* hllSparseToDense API changed to take ref to object.antirez2014-04-131-6/+10
| | | | | | The new API takes directly the object doing everything needed to turn it into a dense representation, including setting the new representation as object->ptr.
* hllSparseAdd() sanity check for span != 0 added.antirez2014-04-131-0/+3
|
* Fix hllSparseAdd() new sequence replacement when next is NULL.antirez2014-04-121-4/+2
| | | | | sdsIncrLen() must be called anyway even if we are replacing the last oppcode of the sparse representation.
* Fix seqlen computation in hllSparseAdd().antirez2014-04-121-1/+1
|
* Abstract hllSparseAdd() / hllDenseAdd() via hllAdd().antirez2014-04-121-4/+19
|
* hllSparseSum(): multiply 1 * runlen for zero entries.antirez2014-04-121-2/+2
|
* Macro HLL_SPARSE_XZERO_LEN fixed.antirez2014-04-121-1/+1
|
* Fix HLL sparse object creation #2.antirez2014-04-121-2/+2
| | | | Two vars initialized to wrong values in createHLLObject().
* Increment pointer while iterating sparse HLL object.antirez2014-04-121-0/+6
|
* Fix HLL sparse object creation.antirez2014-04-121-2/+2
| | | | | The function didn't considered the fact that each XZERO opcode is two bytes.
* Create HyperLogLog objects with sparse encoding.antirez2014-04-121-10/+28
|
* HyperLogLog sparse to dense conversion function.antirez2014-04-121-3/+44
|
View Lorry Controller Status