1. 04 Apr, 2014 9 commits
  2. 03 Apr, 2014 8 commits
  3. 02 Apr, 2014 3 commits
  4. 01 Apr, 2014 3 commits
  5. 31 Mar, 2014 13 commits
  6. 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
  7. 29 Mar, 2014 2 commits
    • antirez's avatar
      Use endian neutral hash function for HyperLogLog. · aaf6db45
      antirez authored
      We need to be sure that you can save a dataset in a Redis instance,
      reload it in a different architecture, and continue to count in the same
      HyperLogLog structure.
      
      So 32 and 64 bit, little or bit endian, must all guarantee to output the
      same hash for the same element.
      aaf6db45
    • antirez's avatar
      HyperLogLog internal representation modified. · 4628ac00
      antirez authored
      The new representation is more obvious, starting from the LSB of the
      first byte and using bits going to MSB, and passing to next byte as
      needed.
      
      There was also a subtle error: first two bits were unused, everything
      was carried over on the right of two bits, even if it worked because of
      the code requirement of always having a byte more at the end.
      
      During the rewrite the code was made safer trying to avoid undefined
      behavior due to shifting an uint8_t for more than 8 bits.
      4628ac00