Permalink
Commits on Apr 4, 2014
  1. PFCOUNT: always unshare/decode the object.

    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.
    committed Apr 4, 2014
  2. Transparent LZF compression initial implementation.

    This commit shapes the main ideas for the implementation but doesn't
    fix all the command implementations, nor handles loading of LZF
    compressed objects in a way able to perserve the compression.
    committed Apr 4, 2014
  3. tryObjectEncoding() refactoring.

    We also avoid to re-create an object that is already in EMBSTR encoding.
    committed Apr 4, 2014
  4. Changed HyperLogLog hash seed to a non-zero value.

    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.
    committed Apr 4, 2014
Commits on Apr 3, 2014
  1. Initial HyperLogLog tests.

    committed Apr 3, 2014
  2. Fix PFADD infinite loop.

    We need to guarantee that the last bit is 1, otherwise an element may
    hash to just zeroes with probability 1/(2^64) and trigger an infinite
    loop.
    
    See issue #1657.
    committed Apr 3, 2014
  3. PFGETREG added for testing purposes.

    The new command allows to get a dump of the registers stored
    into an HyperLogLog data structure for testing / debugging purposes.
    committed Apr 3, 2014
Commits on Apr 2, 2014
  1. hll-gnuplot-graph.rb improved with new filter.

    The function to generate graphs is also more flexible as now includes
    step and max value. The step of the samples generation function is no
    longer limited to min step of 1000.
    committed Apr 2, 2014
  2. HyperLogLog: added magic / version.

    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.
    committed Apr 2, 2014
  3. Merge pull request #1646 from raydog/unstable

    Change HLL* to PF* in a few spots
    committed Apr 2, 2014
Commits on Apr 1, 2014
  1. Change HLL* to PF* in error messages

    Raymond Myers committed Apr 1, 2014
  2. Include redis.h before other stuff in hyperloglog.c.

    Otherwise fmacros.h is included later and this may break compilation on
    different systems.
    committed Apr 1, 2014
Commits on Mar 31, 2014
  1. HyperLogLog API prefix modified from "P" to "PF".

    Using both the initials of Philippe Flajolet instead of just "P".
    committed Mar 31, 2014
  2. HyperLogLog apply bias correction using a polynomial.

    Better results can be achieved by compensating for the bias of the raw
    approximation just after 2.5m (when LINEARCOUNTING is no longer used) by
    using a polynomial that approximates the bias at a given cardinality.
    
    The curve used was found using this web page:
    
        http://www.xuru.org/rt/PR.asp
    
    That performs polynomial regression given a set of values.
    committed Mar 31, 2014
  3. HLLMERGE implemented.

    Merge N HLL data structures by selecting the max value for every
    M[i] register among the set of HLLs.
    committed Mar 31, 2014
  4. HLLCOUNT is technically a write command

    When we update the cached value, we need to propagate the command and
    signal the key as modified for WATCH.
    committed Mar 31, 2014
  5. HLLADD: propagate write when only variable name is given.

    The following form is given:
    
        HLLADD myhll
    
    No element is provided in the above case so if 'myhll' var does not
    exist the result is to just create an empty HLL structure, and no update
    will be performed on the registers.
    
    In this case, the DB should still be set dirty and the command
    propagated.
    committed Mar 31, 2014