1. 13 Apr, 2014 2 commits
  2. 12 Apr, 2014 10 commits
  3. 11 Apr, 2014 4 commits
  4. 10 Apr, 2014 1 commit
    • antirez's avatar
      HyperLogLog sparse representation slightly modified. · 9c037ba8
      antirez authored
      After running a few simulations with different alternative encodings,
      it was found that the VAL opcode performs better using 5 bits for the
      value and 2 bits for the run length, at least for cardinalities in the
      range of interest.
      9c037ba8
  5. 09 Apr, 2014 1 commit
  6. 04 Apr, 2014 2 commits
    • antirez's avatar
      PFCOUNT: always unshare/decode the object. · d5be696d
      antirez authored
      This will be a non-op most of the times since the object will be
      unshared / decoded, however it is more technically correct to start this
      way since the object may be decoded even in the read-only code path.
      d5be696d
    • antirez's avatar
      Changed HyperLogLog hash seed to a non-zero value. · 433ce7f8
      antirez authored
      Using a seed of zero has the side effect of having the empty string
      hashing to what is a very special case in the context of HyperLogLog: a
      very long run of zeroes.
      
      This did not influenced the correctness of the result with 16k registers
      because of the harmonic mean, but still it is inconvenient that a so
      obvious value maps to a so special hash.
      
      The seed 0xadc83b19 is used instead, which is the first 64 bits of the
      SHA1 of the empty string.
      
      Reference: issue #1657.
      433ce7f8
  7. 03 Apr, 2014 6 commits
  8. 02 Apr, 2014 1 commit
    • antirez's avatar
      HyperLogLog: added magic / version. · 096b5e92
      antirez authored
      This will allow future changes like compressed representations.
      Currently the magic is not checked for performance reasons but this may
      change in the future, for example if we add new types encoded in strings
      that may have the same size of HyperLogLogs.
      096b5e92
  9. 01 Apr, 2014 3 commits
  10. 31 Mar, 2014 8 commits
  11. 30 Mar, 2014 2 commits
    • antirez's avatar
      HyperLogLog approximated cardinality caching. · 307a1899
      antirez authored
      The more we add elements to an HyperLogLog counter, the smaller is
      the probability that we actually update some register.
      
      From this observation it is easy to see how it is possible to use
      caching of a previously computed cardinality and reuse it to serve
      HLLCOUNT queries as long as no register was updated in the data
      structure.
      
      This commit does exactly this by using just additional 8 bytes for the
      data structure to store a 64 bit unsigned integer value cached
      cardinality. When the most significant bit of the 64 bit integer is set,
      it means that the value computed is no longer usable since at least a
      single register was modified and we need to recompute it at the next
      call of HLLCOUNT.
      
      The value is always stored in little endian format regardless of the
      actual CPU endianess.
      307a1899
    • antirez's avatar
      String value unsharing refactored into proper function. · 543ede03
      antirez authored
      All the Redis functions that need to modify the string value of a key in
      a destructive way (APPEND, SETBIT, SETRANGE, ...) require to make the
      object unshared (if refcount > 1) and encoded in raw format (if encoding
      is not already REDIS_ENCODING_RAW).
      
      This was cut & pasted many times in multiple places of the code. This
      commit puts the small logic needed into a function called
      dbUnshareStringValue().
      543ede03