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

x/tools/containers/intsets: use the Sparse root block #21311

Closed
RaduBerinde opened this issue Aug 4, 2017 · 6 comments
Closed

x/tools/containers/intsets: use the Sparse root block #21311

RaduBerinde opened this issue Aug 4, 2017 · 6 comments

Comments

@RaduBerinde
Copy link
Contributor

Sparse has a root block but that block doesn't store any element information. So even very small sets (e.g. single element) will need to allocate another block on the heap. So (on a 64-bit arch) we have 56 bytes in the structure and another 56 bytes on the heap, just to represent a single value.

There is no reason to not use the root block itself to store bits. It could be always the block with the smallest offset.

@josharian josharian changed the title tools/containers/intsets: use the Sparse root block x/tools/containers/intsets: use the Sparse root block Aug 4, 2017
@gopherbot gopherbot added this to the Unreleased milestone Aug 4, 2017
@josharian
Copy link
Contributor

@alandonovan

@RaduBerinde
Copy link
Contributor Author

I can try to find some time to take a stab at this if folks agree it's a good idea.

@alandonovan
Copy link
Contributor

Please do; it would certainly be a worthwhile optimization. I tried this at some point in the past but the logic got rather messy so I abandoned it.

@dongweigogo
Copy link

what about bitsets, a high performance pkg.

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/53431 mentions this issue: x/tools/container/intsets: use root block

@RaduBerinde
Copy link
Contributor Author

@dongweigogo - the usecase is different: Sparse supports arbitrary integers, bitsets looks like it allocates X bits if it contains value X.

@golang golang locked and limited conversation to collaborators Aug 21, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants