I propose that we increase the performance (and at the same time decrease memory usage) of HLLDenseRegister by changing the implementation of the set() and getSumInversePow2() methods.

First, in HLLConstants, we add a:
public static final double[] inversePow2Data
array with 64 values

item 0 would be the constant 2^0
item 1 would be the constant 2^-1
item 2 would be the constant 2^-2
etc.

Then in HLLDenseRegister, we remove the member array:
private double[] invPow2Register;

In the set() method we remove:
invPow2Register[idx] = Math.pow(2, -value);

We change the implementation of getSumInversePow2() to:

  public double getSumInversePow2() {
    double sum = 0;
    for (byte b : register) {
      sum += HLLConstants.inversePow2Data[b];
    }
    return sum;
  }

The set method will be significantly faster for two reasons:

• It will not have the expensive Math.pow() call for every set call.
• There will only be random memory access to register, and not also to invPow2Register. With p=14, with just a register array, there will be random access to 16kiB of data, which fits in an Intel CPU's L1 cache. With the current code, one also needs the invPow2Register, and that is a total of 144kiB of data, which means random access to the L2 cache.

For the getSumInversePow2 method, the performance will probably be about the same, perhaps a bit faster, or perhaps slightly slower. The performance of the set() method is more important, because most applications will call set() orders-of-magnitude more times than the application will call HyperLogLog.count(). With the current getSumInversePow2() method, it's reading sequentially through an array that would fit in the L2 cache. With the proposed new code, it'd do a sequential read of the register array that would almost always be in the L1 cache, and a random read of the HLLConstants.inversePow2Data array that'd be in the L1 cache (it would be 512 bytes).

Installation fails with the following warning and error:
[WARNING] The POM for org.apache.hive:hive-standalone-metastore:jar:3.0.0-SNAPSHOT is missing, no dependency information available

[ERROR] Failed to execute goal on project hyperloglog: Could not resolve dependencies for project com.github.prasanthj:hyperloglog:jar:1.2-SNAPSHOT: Could not find artifact org.apache.hive:hive-standalone-metastore:jar:3.0.0-SNAPSHOT -> [Help 1]

I attach the detailed log as well. Please check.
Thanks in advance.
hll_installation_error.txt