Comments (8)
Let me know what you think @lemire !
from roaring.
@lemire Pinging again if you have a chance to look.
from roaring.
Yes... this is a reasonable use case, but please review my comments on the PR. I think we want a non-invasive solution. That is, we want something that does not fatten the structures and code for everyone, just to handle this one case.
You are probably limited by the memory allocation/garbage collection. And thus you try to create polls of arrays to get around the problem. That is fine, but it is also not a general-purpose solution. So we want to push the complexity, the potential bugs and all such things away from what most people use.
See my sketch of a counterproposal.
from roaring.
Thanks for taking a look, I really appreciate it!
I think you're right that basically what I wanted was a custom allocator, so I responded with an alternative proposal that basically makes this explicit. Its slightly more invasive than your proposal, but much more generic and will lend itself to a much wider variety of incremental optimizations I think.
from roaring.
There's another approach which I have been thinking of implementing in Java which should be easy to implement so long as the integers added to the bitmaps are sorted: avoid allocating memory in the first place since the bitmaps being built are themselves temporary. A serialized bitmap has two sections: the header and the containers.
The structure of the header doesn't lend itself to streaming:
field | size (bytes) | purpose |
---|---|---|
cookie | 4 | identification of a roaringbitmap |
runcontainer bitset | numContainers | identifies when to interpret a cardinality as a number of runs |
repeated container key - cardinality pairs | 4 * numContainers | reconstructing/mapping the index |
repeated container offsets | 4 * numContainers | finding container bits |
These quantities need to be known in their entirety before writing the header.
Though the header can't be streamed, the containers can: they're just written out contiguously and indexed by the offsets in the header. This lends itself to a lot of object reuse while streaming integers straight to an output: it requires a resuable bitset of runcontainer locations, lists of key/cardinality pairs and container offsets, a number of containers, and a reusable container to accumulate added integers into, or even just another reusable set to buffer values in the same container into.
As values are consumed, the high bits of the values need to be tracked, and whenever there is a new value in the high bits:
- the current key and cardinality is saved to the list of key/cardinality pairs to build the header from
- the current offset into the destination for the containers is appended to the list of offsets
- the current container is written to the destination
- if the current container is a run container, mark the header bitset
At the end, the header needs to be written into another destination, with the size of the header (which is calculable by this point) added to each container offset. If the destination is a file, it may be possible to move the serialized containers to the file containing the header without performing a copy (this is possible in Java but I don't know how to do it in Go).
This has another rather nice advantage of avoiding a binary search in the container index for each input value. The Java implementation has the concept of a RoaringBitmapWriter
which can speed up construction from sorted inputs a lot because of this, though streaming straight to disk along these lines hasn't been implemented yet.
from roaring.
It does seem that what is needed is a bitmap writer. Of course, it would work much better if the input is sorted but if not, you could still partially sort it in a buffer before serialization. A bitmap writer for already sorted data could beat anything else in performance and keep allocations very scarce.
from roaring.
A bitmap writer would be excellent for this particular use-case yeah, although it would still be nice to reduce allocations when reading many short-lived bitmaps. I think the frozen implementation is supposed to help with this, but I'd prefer if we could avoid that.
from roaring.
I recommend working on a bitmap writer. It is a well-defined problem, it is relatively easy to implement it safely and efficiently, the API won't be confusing and it will not be a significant burden on the code base. Furthermore, the Java implementation has already a powerful and fast bitmap writer (although not specialized for serialization..), so we have validation. If well implemented, it can be faster and simpler than anything else for this task which motivates you.
It is still not trivial to do: if you look at what Richard did in Java, it still requires handling efficiently different densities and data distribution so that the right container is picked. But, at least, if you assume that the input data is sorted, it is a tractable problem.
It does not preclude further work in other directions later.
from roaring.
Related Issues (20)
- upper bound memory estimate HOT 3
- question: what is Freeze? HOT 2
- Failed to read runtime container content: unexpected EOF HOT 1
- External-memory roaring data structure HOT 2
- Add Bitmap.NextAbsentValue HOT 5
- error in roaringArray.readFrom: could not read initial cookie: unexpected EOF HOT 7
- [roaring64] Why Or function modify bitmap "a" in this example? HOT 7
- Regarding memory use of maximum size and removal of bit number HOT 2
- UnmarshalBinary has containers with needCopyOnWrite set to true HOT 1
- Implement roaring_bitmap_internal_validate HOT 2
- error in roaringArray.readFrom: did not find expected serialCookie in header HOT 2
- "error in roaringArray.readFrom: did not find expected serialCookie in header" HOT 4
- make qa fails for release 1.6.0
- incorrect GetSizeInBytes() value HOT 1
- "error in roaringArray.readFrom: did not find expected serialCookie in header" when reading a bitmap written by roaring64 HOT 5
- "Could not deserialize bitmap for key #0: error in roaringArray.readFrom: did not find expected serialCookie in header" on v1.8.0 when reading a bitmap written by roaring64 HOT 1
- Go get error HOT 2
- Feature request : mmap roaring bitmap for use in multi threaded inter-process/separate program HOT 1
- Feature request for 128bit for ipv6 usage. HOT 3
- possible to do an mmap version of roaring bitmap for golang? HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from roaring.