I have no clue so might require a bit of to-fro in terms of questions - but I'd love to take this up!

Assigned, @chettriyuvraj thanks for picking this up, please let me know if you've any queries around this.

Hey @lucifercr07

So, I was looking into this issue so that I can also help @chettriyuvraj a bit, while reading the code I stumbled upon some things.

switch(hdr->encoding) {
    case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);
    case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);

So for the above code in Redis file the sparse and dense implementation can be chosen in the hllAdd function based on the encoding type and the other is inside the hllSparseAdd(o,ele,elesize); which is based on the threshold value, So here are we implementing both of these methods or we are going with the threshold based on the size.

One other thing is the way it calculates the string size, so in the Redis, they have sdslen() so do we also have to do something like that to get the size of strings in args?

Thanks

Sorry for no updates on this one - was down with H1N1 the past week. Will pick up and put out an update @lucifercr07 .

Hello @chettriyuvraj,

There has been no activity on this issue for the past 5 days.
It would be awesome if you keep posting updates to this issue so that we know you are actively working on it.

We are really eager to close this issue at the earliest, hence if we continue to see the inactivity, we will have to reassign the issue to someone else. We are doing this to ensure that the project maintains its momentum and others are not blocked on this work.

Just drop a comment with the current status of the work or share any issues you are facing. We can always chip in to help you out.

Thanks again.

Hi @arpitbbhayani!

Today was the first day I actively picked up the issue. I'll be posting an update daily from now on.

Status

I mentioned that I had no clue about what HyperLogLog was and my first step today was to pick up the paper.

• Went over the paper
• The idea of cardinality estimation structures was new to me but seemed very intuitive.
• The proofs/math zoomed over my head.
• After getting the overview wanted some more concreteness to my understanding - quickly ran over this video, this article.
• The top level comment in Redis's implementation for understanding sparse and dense representations

I'll hopefully have a bit more concrete updates + queries to ask tomorrow.

Apologies about the unreasonable delays and for slowing things down on this issue - I know how important keeping the momentum in this project is. Please bear with me - I'll get this over the line!

Hey @lucifercr07!

A little unsure if my understanding is correct here

My understanding

In Redis source, this seems to be handling the promotion from sparse to dense representations.

Promotion occurs in 2 cases:
Case 1. Using #define HLL_SPARSE_VAL_MAX_VALUE 32, where the value exceeds that which can be represented by a sparse register.
Case 2. A configurable threshold of bytes i.e. server.hll_sparse_max_bytes. If the storage consumed by sparse representation exceeds this - promotion occurs.

Queries

• Promotion in case 1 -> shouldn't this case already be handled by the library we are using? I had a peek (just a glimpse) on the library's source and it is promoting sparse to dense inside its Insert(..) function, need to take a closer look

• So the main objective of the issue is to determine the threshold for case 2?

• Analyse feasibility of switch between Sparse and Dense representations based on benchmark testing - can you elaborate on how benchmarking will help us decide this?

Hello @chettriyuvraj,

There has been no activity on this issue for the past 5 days.
It would be awesome if you keep posting updates to this issue so that we know you are actively working on it.

We are really eager to close this issue at the earliest, hence if we continue to see the inactivity, we will have to reassign the issue to someone else. We are doing this to ensure that the project maintains its momentum and others are not blocked on this work.

Just drop a comment with the current status of the work or share any issues you are facing. We can always chip in to help you out.

Thanks again.

Hi @arpitbbhayani - have unassigned myself from this issue. Free to assign it to someone else.

Hi @arpitbbhayani / @JyotinderSingh,
Can you assign this to me?

Hi @arpitbbhayani / @JyotinderSingh,

Can you assign this to me?

Assigned

I made some progress by working on top of suggestions by @evoxtorm and I am working on understanding it and implementing the Dense algorithm.

Hi @arpitbbhayani, @lucifercr07,
The benchmarks present a significant jump in the time taken per op, if the number of items in the list is greater than 1000.

Benchmarks with the current Sparse Representation in PFADD

goos: darwin
goarch: arm64
pkg: github.com/dicedb/dice/internal/eval
cpu: Apple M1 Pro
BenchmarkEvalPFADD/PFAddSize_0-8         	 3737166	       317.1 ns/op	      80 B/op	       3 allocs/op
BenchmarkEvalPFADD/PFAddSize_10-8        	  628004	      1892 ns/op	     665 B/op	      22 allocs/op
BenchmarkEvalPFADD/PFAddSize_100-8       	   64923	     18592 ns/op	    4850 B/op	     125 allocs/op
BenchmarkEvalPFADD/PFAddSize_1000-8      	    3874	    303253 ns/op	   68278 B/op	    1177 allocs/op
BenchmarkEvalPFADD/PFAddSize_10000-8     	    1576	    757984 ns/op	  160080 B/op	   10003 allocs/op
BenchmarkEvalPFADD/PFAddSize_100000-8    	     306	   3911595 ns/op	 1600081 B/op	  100003 allocs/op
PASS
ok  	github.com/dicedb/dice/internal/eval	8.562s