Once I set my cardinality to 100k using hll++, the error rate becomes massive:

approx:  10506
actual:  100000
delta:   89494

My sample code is pretty much cribbed from your test/bench code. Set the truth variable to 1000 and you get exact result. Things look good in the 10k range too. But at 100k... boom.

Complete repro code:

package main

import (
    "github.com/clarkduvall/hyperloglog"
    "fmt"
    "hash/fnv"
    "hash"
)

func hash64(s string) hash.Hash64 {
    h := fnv.New64()
    h.Write([]byte(s))
    return h
}

func main() {
    truth := 100000

    h, err := hyperloglog.NewPlus(16);
    if err != nil {
        fmt.Println(err)
        return
    }

    for i := 0; i < truth; i++ {
            istr := fmt.Sprintf("%s", i)
            h.Add(hash64(istr))
    }
    epp := h.Count()

    fmt.Println("approx: ", epp)
    fmt.Println("actual: ", truth)
    fmt.Println("delta:  ", int64(truth)-int64(h.Count()))
}

This is an alternative PR which build around io writers/readers rather than a []byte.

It uses gob, but things are complicated a bit because:

1. hll and hllp structs don't export their members
2. there possible nil pointers at times

I added the complication handling in marshal/unmarshal rather than make a more invasive package-wide change to play nice with gob.

One other benefit over the other PR... this maintains the sparse state for hllp when applicable.

Similar to #18 I have another case where the Count method returns an insanely large value for a very specific set of inputs.

Here is the input data: hll.txt

And here is the script to test it:

package main

import (
	"fmt"
	"hash/fnv"
	"io"
	"log"

	"github.com/clarkduvall/hyperloglog"
)

func main() {
	a, _ := hyperloglog.NewPlus(12)

	for {
		var l string
		if _, err := fmt.Scanln(&l); err == io.EOF {
			break
		} else if err != nil {
			panic(err)
		}
		h := fnv.New64a()
		h.Write([]byte(l))
		a.Add(h)
		//log.Printf("added val %q to hll, count is now: %d", l, a.Count())
	}

	log.Printf("a.Count: %d", a.Count())
}

Like in #18 I narrowed down the dataset so that omitting the last line causes the large number to not be output:

 /tmp ▻ cat hll.txt | ./hlltest                                                   
2017/05/22 14:49:54 a.Count: 18446744073709551604                                 
 /tmp ▻ cat hll.txt | head -n-1| ./hlltest                                        
2017/05/22 14:50:04 a.Count: 20478

Let me know if there's anything I can do to help debug more, thanks!

Our app, for various reasons, always calls Count after adding a bunch of items. This has the unfortunate side effect that toNormal never gets called - because Count calls mergeSparse and this resets the size of tmpSet to zero. Thus the size of tmpSet is never big enough for maybeToNormal to trigger toNormal.

The end result is we have a sparseList of millions of items, and Count is very slow (hundreds of milliseconds).

This patch fixes this by checking if the threshold is reached during Count.

I know hll's aren't supposed to be accurate, so if this is simply a case of finding a limitation in the accuracy then that's cool, I just wanted to double check. I have the following code:

func main() {
	add := func(hll *hyperloglog.HyperLogLogPlus, i int) {
		h := fnv.New64a()
		h.Write([]byte(strconv.Itoa(i)))
		hll.Add(h)
	}

	a, _ := hyperloglog.NewPlus(12)
	for i := 0; i < 10000; i++ {
		add(a, i%100)
	}
	fmt.Printf("a: %d\n", a.Count())

	b, _ := hyperloglog.NewPlus(12)
	for i := 0; i < 10000; i++ {
		add(b, (i%100)+5)
	}
	fmt.Printf("b: %d\n", b.Count())

	a.Merge(b)
	fmt.Printf("a+b: %d\n", a.Count())
}

I get the output:

a: 100
b: 100
a+b: 6

So the Counts for a and b individually look good, but post-merge it seems to get borked. Again, just wanted to check if this is a bug vs a limitation in what hll's can actually do. Thanks!

So this is a super specific test case, and unfortunately I haven't had much luck in boiling it down farther. But for a very specific input we're seeing extremely high Count() values after Merge'ing a populated HLL+ into an empty one.

Attached is the input data: hll.txt

This is the test code:

package main

import (
	"fmt"
	"hash/fnv"
	"io"
	"log"

	"github.com/clarkduvall/hyperloglog"
)

func main() {
	a, _ := hyperloglog.NewPlus(12)

	for {
		var l string
		if _, err := fmt.Scanln(&l); err == io.EOF {
			break
		} else if err != nil {
			panic(err)
		}
		h := fnv.New64a()
		h.Write([]byte(l))
		a.Add(h)
		log.Printf("added val %q to hll, count is now: %d", l, a.Count())
	}

	b, _ := hyperloglog.NewPlus(12)
	b.Merge(a)
	log.Printf("b.Count: %d", b.Count())
}

To run:

cat hll.txt | ./hlltest

The output should end with something like:

2016/12/12 14:20:06 b.Count: 18446744073709551615

If you omit the last line like this:

cat hll.txt | head -n-1 | ./hlltest

You get a much more reasonable output:

2016/12/12 14:26:46 b.Count: 3099

Let me know if there's any other information you need to help debug this, thanks!

every time I merge 2 hll++ with precision = 18. I find that the count result is totally wrong

func HashFnv1(str string) hash.Hash64 {
    hashed := fnv.New64a()
    hashed.Write([]byte(str))
    return hashed
}

func BenchmarkHLLPP(b *testing.B) {
    hll1,_ := hyperloglog.NewPlus(18)
    hll2,_ := hyperloglog.NewPlus(18)

    for i := 0; i < 1000; i++ {
        hll1.Add(HashFnv1("entry_1_"+strconv.Itoa(i)))
        hll2.Add(HashFnv1("entry_2_"+strconv.Itoa(i)))
    }

    b.Log("count hll1 = ", hll1.Count())
    b.Log("count hll2 = ", hll2.Count())

    for i := 0; i < b.N; i++ {
        hll1.Merge(hll2)
    }
    b.Log("count hll1 | hll2 =", hll1.Count())
}

gives me this

BenchmarkHLLPP-4       50000         36267 ns/op
--- BENCH: BenchmarkHLLPP-4
    operation_test.go:160: count hll1 =  1000
    operation_test.go:161: count hll2 =  1000
    operation_test.go:166: count hll1 | hll2 = 244
    operation_test.go:160: count hll1 =  1000
    operation_test.go:161: count hll2 =  1000
    operation_test.go:166: count hll1 | hll2 = 244
    operation_test.go:160: count hll1 =  1000
    operation_test.go:161: count hll2 =  1000
    operation_test.go:166: count hll1 | hll2 = 244
    operation_test.go:160: count hll1 =  1000

This improves the avalanche characteristic and avoids the issue found in: https://github.com/clarkduvall/hyperloglog/issues/10

I ran the benchmark. Code compiles fine; outputs look reasonable.

When adding items to sets, it's often impractical to use structs that implement full hash.Hash32/hash.Hash64 method set. Most of my implementations contain a bunch of empty methods, pretty much what you have done in your tests with fakeHash32/fakeHash64.

The existing gob encoder is easy to use but really slow. I'm using protobuf for my project which is much faster, but depends on serializing to/from generated data structures. Rather than introduce a dependency to the library, I've added this interface to translate from hll's internal data to the external struct with as little extra copying and allocation as possible. I think this is sufficiently generic to be used with a variety of communication libraries.

I see that other efforts to add serialization/deserialization to HLL are not merged yet, so let me offer another one, because I find it critical to be able to save HLL counter and restore it if app is restarted.

Basically, I've added gob-compatible interfaces, so HLL and HLLP inside custom structs can be saved/restored seamlessly.

Every exported function in a program should have a doc comment. The first sentence should be a summary that starts with the name being declared. From effective go.

I generated this with CodeLingo and I'm keen to get some feedback, but this is automated so feel free to close it and just say "opt out" to opt out of future CodeLingo outreach PRs.

What this does

• Adds a load function so we can make a new hyperloglog directly from the bytes instead of needing the gob format.

Why is this needed?

I needed to deserialize HLLs that were serialized from another language.

#14 also tried to address this issue, but lacked tests and seemed to be abandoned.

Instead of setting a state, this returns a new HLL, which I think is cleaner.