Merge pull request #4 from apache/fix-windows-build

Fix hyper build for Windows

Fix hyper build for win32

Merge pull request #3 from apache/use-matching-tags-for-triq-deps

Use exactly matching tags for triq dependencies

Use exactly matching tags for triq dependencies

Otherwise rebar thinks there is a conflict:

```
ERROR: Conflicting dependencies for triq: [{"From: hyper",
                                            {[],
                                             {git,
                                              "https://github.com/apache/couchdb-triq",
                                              {tag,"v1.2.0"}}}},
                                           {"From: asf2",
                                            {".*",
                                             {git,
                                              "https://github.com/apache/couchdb-triq.git",
                                              {tag,"v1.2.0"}}}}]
```

Merge pull request #2 from apache/fix-tests-to-run-with-triq

Fix tests to run with Triq

Comment out broken Makefile target

Disable failing test on R20

Fix tests to run with Triq

Used CouchDB's Triq port

Had to uncomment a bunch of bisect module checks. That made the diff kind of
ugly.

Merge pull request #1 from apache/remove-bisect

Remove bisect implementation

Remove bisect implementation

We're not using this backend, and it requires R17 (we are still
supporting R16 as of this writing).

Merge pull request #16 from elverkilde/fix/carray

Fix/carray - Merging the pull request from @elverkilde  as the permission has been given by all three contributors @elverkilde @chrisavl and @johannesh to change license to MIT

Switch to MIT license for carray

Removed use of tgmath.h for pow function (assuming C99 compiler)

Merge pull request #14 from savonarola/fix-deprecated-time-functions

Updated usage of time functions

Updated usage of time functions (removed usage of deprecated erlang:now())

Merge pull request #11 from knutin/master

Pull in hyper:is_hyper/1 from Knut

add note about `indent` to C source file

add contributors to C source file

Merge pull request #10 from GameAnalytics/fix_merge_leak

Release resource created for merge result

Remove unnecessary enif_make_resource.

Release resource created for merge result

Added hyper:is_hyper/1.

Merge pull request #9 from GameAnalytics/remove_alloc

Remove unecessary alloc from hyper c array.

run indent

Remove unecessary alloc from hyper c array.

The last commit allocated an array for pointers to the hyper c array
structure. This is not necessary for improved performance. This change
still leaves the union time at 0.01 to 0.02 ms.

Merge pull request #8 from GameAnalytics/faster_merge

Faster merging of hyper c arrays.

Faster merging of hyper c arrays.

I tried implementing 3 different approaches to merging the arrays. This was by
far the fastest at (0.01ms to 0.02ms for the union benchmark). It seems
when the ternary operator is inside the inner loop compiler does something that
is fast such as an operation with no branching.

The other approaches were,

* processing a 64-bit integer at a time and unpacking the bytes (0.16ms)
* branching rather than a ternary operator for the max value which is
  similar to the original code (0.10ms to 0.40ms)

Benchmark before,

module       P        card   fill      bytes  insert us   union ms    card ms    json ms
hyper_carray 15          1   0.00      32784       1.80       0.10       0.33       0.21
hyper_carray 15        100   0.00      32784       0.54       0.11       0.34       0.28
hyper_carray 15        500   0.02      32784       0.50       0.10       0.38       0.47
hyper_carray 15       1000   0.03      32784       0.51       0.11       0.38       0.74
hyper_carray 15       2500   0.07      32784       0.50       0.11       0.43       1.41
hyper_carray 15       5000   0.14      32784       0.51       0.12       0.51       2.38
hyper_carray 15      10000   0.26      32784       0.51       0.14       0.65       4.17
hyper_carray 15      15000   0.37      32784       0.51       0.16       0.82       5.32
hyper_carray 15      25000   0.53      32784       0.51       0.20       1.05       6.10
hyper_carray 15      50000   0.78      32784       0.51       0.26       1.31       5.77
hyper_carray 15     100000   0.95      32784       0.51       0.33       1.65       5.18
hyper_carray 15    1000000   1.00      32784       0.53       0.43       1.83       5.23

Benchmark after,

module       P        card   fill      bytes  insert us   union ms    card ms    json ms
hyper_carray 15          1   0.00      32784       2.30       0.02       0.32       0.22
hyper_carray 15        100   0.00      32784       0.53       0.02       0.33       0.22
hyper_carray 15        500   0.02      32784       0.51       0.02       0.35       0.43
hyper_carray 15       1000   0.03      32784       0.50       0.02       0.37       0.68
hyper_carray 15       2500   0.07      32784       0.51       0.02       0.42       1.34
hyper_carray 15       5000   0.14      32784       0.50       0.01       0.50       2.33
hyper_carray 15      10000   0.26      32784       0.52       0.01       0.65       4.10
hyper_carray 15      15000   0.37      32784       0.51       0.02       0.79       5.33
hyper_carray 15      25000   0.53      32784       0.51       0.02       1.01       6.11
hyper_carray 15      50000   0.78      32784       0.51       0.02       1.30       5.77
hyper_carray 15     100000   0.95      32784       0.51       0.02       1.63       5.23
hyper_carray 15    1000000   1.00      32784       0.53       0.02       1.82       5.32

Merge pull request #7 from GameAnalytics/carray_tests

Test hyper_carray backend

Fix hyper_carray register encoding

Don't include anything else than the registers in the returned binary

Support single hll input for hyper_carray:union/1

This function still creates a new hll, could be optimized to simply return
it's input.

Include hyper_carray in performance report

Add hyper_carray to test suite

Fixed bug in merging of filters with the hyper_bisect backend.

Optimization to hyper_binary backend for sequential changes to the same index.

Merge pull request #6 from martinrehfeld/folding

Support mixed-precision union

Demonstrate error rate of reduced-precision HLLs

Support mixed-precision union

... for the hyper_binary default backend only, sorry ;-)

Merge pull request #5 from martinrehfeld/master

Add hyper:precision/1

Add hyper:precision/1

Provide a getter for the precision of a HyperLogLog filter.

Merge pull request #4 from GameAnalytics/clang_compile

Make compile work with clang

Make compile work with clang

Merge pull request #3 from johannesh/hyper_carray

hyper_carray, a hyper_register implemented by a C-array

[hyper_carray] K&R and kernel style, added docs

hyper_carray, a hyper_register implemented by a C-array

Merge pull request #2 from johannesh/master

Typo in documentation of register_sum callback

Typo for @doc of register_sum callback

Added output from make perf_report.

Added the MIT license.

Cleanup of README.

Cleanup of estimate graphs.

Measure time of 5 unions.

Run parts of estimate report in parallel.

Don't force compaction before union to allow for more optimizations. Property of unions.

Clean up of README.

Roll v1.0

Cleaned up the estimate report.

Apply the same optimization to other merges.

Postpone actual merge if merging two buffers results in a small enough new buffer.

Disable native compilation of hyper_binary as it crashes when reloading.

Also merge buffers when merging dense binaries.

In hyper_binary, merge the buffers to allow for more efficient merges of small into big filters.

Run estimate report from Makefile.

Added more documentation to README.

Better tests.

Avoid useless conversion from list to tuple.

Updated behaviour and cleaned up backends.

More optimizations to hyper_binary. Use an explicit buffer to allow for fast inserts and fast unions for low fill rates.

Better quickcheck properties. Added first version of hyper_binary_rle backend.

Optimizations for buffering writes in hyper_binary.

Use (now bug-free) bisect:bulk_insert/2 for merging two bisects.

In case on extra 0 byte in old serialized filters, ignore it in hyper_bisect and hyper_binary.

Compact the binary structure when it makes sense.

Serialization tests.

Moved tests into separate folder. Added PropEr test of encoding. Moved more logic into backends to allow for more optimizations.

Moved more heavy lifting into the backend module to allow for more optimizations. Introduced hyper_binary, using a fixed size binary as an array.

Fixed incorrect merge.

Faster unions for bisect, repeated runs of timed tests.

More tests of backends.

Export from_json/2

Size in bytes.

Smarter union for dense and sparse bisect.

Measure card/1

Start of README.

Union test with bigger cardinality.

More cardinalities, use the same seed.

Switch to plain dense representation when it would use less memory.

Let backend decide on merge strategy.

perf report.

bisect backend.

make size_report

Array backend.

Pluggable register data structure.

Minor cleanup of tests.

Use tail recursive helper functions instead of lists:map + lists:seq

Registers using gb_trees.

Performance improvement to union: don't write back the same value.

When deserializing, zeroes should become the default value in the array to make sure it's sparse.

Use sparse folding for unions of two filters

Add function for the cardinality of the intersection of two filters

Implemented the bias correction from the google paper.