Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

compress countmin state to 64bits #16

Open
lmb opened this issue Sep 21, 2020 · 0 comments
Open

compress countmin state to 64bits #16

lmb opened this issue Sep 21, 2020 · 0 comments
Labels
enhancement New feature or request

Comments

@lmb
Copy link
Contributor

lmb commented Sep 21, 2020

The value we store in a count-min sketch is currently 128bit:

struct cm_value {
        fpoint value;
        __u64 ts;
};

I think we can compress this to 64 bits total: a __u32 for the estimated rate in pps and a __u32 for the timestamp. This means the timestamp would wrap every 4.2s but given our current WINDOW that isn't a problem. It just needs code to deal with it.

Doing this will halve the memory we need, plus on 64bit arches we can (probably) use a single load and store for struct cm_value which reduces the likelihood of observing a race condition.

@lmb lmb added the enhancement New feature or request label Sep 21, 2020
lmb added a commit that referenced this issue Jan 19, 2021
We don't really need 64 bit to represent a rate, 2^32 packets per
second should be enough for everyone. Once we manage to shrink the
timestamp to 32 bit we'll save a bunch of memory.

Updates #16
lmb added a commit that referenced this issue Feb 3, 2021
We don't really need 64 bit to represent a rate, 2^32 packets per
second should be enough for everyone. Once we manage to shrink the
timestamp to 32 bit we'll save a bunch of memory.

Updates #16
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant