hyperloglog

a concurrent, super fast, pretty-well-tested and fully safe hyperloglog for rust with no dependencies.

on my m1 macbook pro, there is no overhead to concurrency (only uses relaxed ordering), so it is not configurable feature.

you know, concurrency that just works. its pretty magic.

performance:

+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| b  | num_threads | elements_per_thread | duration           | est. cardinality   | error                   | z score              |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 12 | 1           | 80000000            | 0.783505583        | 81407162.3289801   | 0.017589529112251288    | 1.0824325607539254   |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 12 | 2           | 40000000            | 0.392236           | 81407162.3289801   | 0.017589529112251288    | 1.0824325607539254   |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 12 | 8           | 10000000            | 0.115582916        | 81407162.3289801   | 0.017589529112251288    | 1.0824325607539254   |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 12 | 8           | 200000000           | 2.054057208        | 1585805566.3940902 | -0.00887152100369364    | -0.5459397540734547  |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 12 | 16          | 200000000           | 3.7321913330000003 | 3227717320.617457  | 0.008661662692955286    | 0.533025396489556    |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 16 | 16          | 200000000           | 3.728134916        | 3198889302.695715  | -0.00034709290758907796 | -0.08543825417577304 |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 8  | 16          | 200000000           | 3.6748197080000002 | 2962602353.834109  | -0.074186764426841      | -1.1413348373360153  |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 4  | 16          | 200000000           | 3.756755708        | 4388265829.463295  | 0.3713330717072797      | 1.4282041219510757   |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 4  | 8           | 10000000            | 0.100113625        | 85015087.94729412  | 0.06268859934117645     | 0.24110999746606324  |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 4  | 2           | 40000000            | 0.390384833        | 85015087.94729412  | 0.06268859934117645     | 0.24110999746606324  |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 4  | 1           | 80000000            | 0.779172958        | 85015087.94729412  | 0.06268859934117645     | 0.24110999746606324  |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+
| 4  | 2           | 80000000            | 0.785492541        | 208090923.9294848  | 0.3005682745592801      | 1.1560318252280004   |
+----+-------------+---------------------+--------------------+--------------------+-------------------------+----------------------+

memory usage:

the number of registers is configurable by b: m = 2^b

5 registers are stored in 32 bits.

2^b / 5 * 4 gives the bytes of memory used