Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Apr 15, 2014

  1. Salvatore Sanfilippo

    User-defined switch point between sparse-dense HLL encodings.

    antirez authored
  2. Salvatore Sanfilippo

    PFSELFTEST improved with sparse encoding checks.

    antirez authored

Apr 14, 2014

  1. Salvatore Sanfilippo

    PFDEBUG ENCODING added.

    antirez authored
  2. Salvatore Sanfilippo

    Set HLL_SPARSE_MAX to 3000.

    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.
    antirez authored
  3. Salvatore Sanfilippo

    Error message for invalid HLL objects unified.

    antirez authored
  4. Salvatore Sanfilippo

    PFMERGE fixed to work with sparse encoding.

    antirez authored
  5. Salvatore Sanfilippo

    Mark PFDEBUG as write command in the commands table.

    It is safer since it is able to have side effects.
    antirez authored
  6. Salvatore Sanfilippo

    Correctly replicate PFDEBUG GETREG.

    Even if it is a debugging command, make sure that when it forces a
    change in encoding, the command is propagated.
    antirez authored
  7. Salvatore Sanfilippo

    Added assertion in hllSparseAdd() when promotion to dense occurs.

    If we converted to dense, a register must be updated in the dense
    representation.
    antirez authored
  8. Salvatore Sanfilippo

    hllSparseAdd(): speed optimization.

    Mostly by reordering opcodes check conditional by frequency of opcodes
    in larger sparse-encoded HLLs.
    antirez authored
  9. Salvatore Sanfilippo

    Detect corrupted sparse HLLs in hllSparseSum().

    antirez authored
  10. Salvatore Sanfilippo

    hllSparseAdd(): faster code removing conditional.

    Bottleneck found profiling. Big run time improvement found when testing
    after the change.
    antirez authored
  11. Salvatore Sanfilippo

    Comment typo in hllSparseAdd(). first -> fits.

    antirez authored
  12. Salvatore Sanfilippo

    Merge adjacent VAL opcodes in hllSparseAdd().

    As more values are added splitting ZERO or XZERO opcodes, try to merge
    adjacent VAL opcodes if they have the same value.
    antirez authored
  13. Salvatore Sanfilippo

    More robust HLL_SPARSE macros protecting 'p' with parens.

    Now the macros will work with arguments such as "ptr+1".
    antirez authored
  14. Salvatore Sanfilippo

    hllSparseAdd() opcode seek stop condition fixed.

    antirez authored
  15. Salvatore Sanfilippo

    Fixed error message generation in PFDEBUG GETREG.

    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.
    antirez authored
  16. Salvatore Sanfilippo

    Fixed memmove() count in hllSparseAdd().

    antirez authored
  17. Salvatore Sanfilippo

    hllSparseAdd(): more correct dense conversion conditional.

    We want to promote if the total string size exceeds the resulting size
    after the upgrade.
    antirez authored
  18. Salvatore Sanfilippo

    hllSparseToDense(): sanity check added.

    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.
    antirez authored
  19. Salvatore Sanfilippo

    PFDEBUG DECODE added.

    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.
    antirez authored

Apr 13, 2014

  1. Salvatore Sanfilippo

    PFDEBUG added, PFGETREG removed.

    PFDEBUG will be the interface to do debugging tasks with a key
    containing an HLL object.
    antirez authored
  2. Salvatore Sanfilippo

    hllSparseToDense API changed to take ref to object.

    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.
    antirez authored
  3. Salvatore Sanfilippo

    hllSparseAdd() sanity check for span != 0 added.

    antirez authored

Apr 12, 2014

  1. Salvatore Sanfilippo

    Fix hllSparseAdd() new sequence replacement when next is NULL.

    sdsIncrLen() must be called anyway even if we are replacing the last
    oppcode of the sparse representation.
    antirez authored
  2. Salvatore Sanfilippo

    Fix seqlen computation in hllSparseAdd().

    antirez authored
  3. Salvatore Sanfilippo

    Abstract hllSparseAdd() / hllDenseAdd() via hllAdd().

    antirez authored
  4. Salvatore Sanfilippo

    hllSparseSum(): multiply 1 * runlen for zero entries.

    antirez authored
  5. Salvatore Sanfilippo

    Macro HLL_SPARSE_XZERO_LEN fixed.

    antirez authored
  6. Salvatore Sanfilippo

    Fix HLL sparse object creation #2.

    Two vars initialized to wrong values in createHLLObject().
    antirez authored
  7. Salvatore Sanfilippo

    Increment pointer while iterating sparse HLL object.

    antirez authored
  8. Salvatore Sanfilippo

    Fix HLL sparse object creation.

    The function didn't considered the fact that each XZERO opcode is
    two bytes.
    antirez authored
  9. Salvatore Sanfilippo

    Create HyperLogLog objects with sparse encoding.

    antirez authored
  10. Salvatore Sanfilippo

    HyperLogLog sparse to dense conversion function.

    antirez authored

Apr 11, 2014

  1. Salvatore Sanfilippo

    HyperLogLog sparse representation initial implementation.

    Code never tested, but the basic layout is shaped in this commit.
    Also missing:
    
    1) Sparse -> Dense conversion function.
    2) New HLL object creation using the sparse representation.
    3) Implementation of PFMERGE for the sparse representation.
    antirez authored
Something went wrong with that request. Please try again.