Allow allocating container in memory pool

[baibaichen]

Allow allocating container in memory pool

[lemire]

As you point out, we support custom memory allocators, so you can provide your own. You definitively can then implement a memory pool. In fact, it is the most likely usage (e.g., an arena).

A per-bitmap dynamically chosen allocator is not something we are going to do. It is has much too great an overhead. It is not just the allocation, but also follow-up operations (deallocation) that need to be tracked and the bitmaps interact with each others, a container allocated in one bitmap, with one memory system could end up within another bitmap that uses another memory allocator. This implies that every container, and some of them can be just a few bytes, needs to track its source. It adds memory usage, computational overhead, complexity overhead, etc. Nothing in the issue you raise justifies the need to justify a distinct memory allocator per bitmap.

Please use the functionality we provide right now for custom memory management. If after using it, you find it insufficient, please report back. Describe your implementation... ideally, provide us with the custom memory manager you designed (e.g., your arena) and a benchmark that illustrates your problems. We might then look for solutions.

That is, before we may consider that the current solution we provide is insufficient, we need to look at the problem and see what solution you provided. We need to make sure that you are making full use of the capabilities we provide already, before we extend them. Let me be clear: We already provide the necessary functionality to provide a custom memory pool. Please make sure you are making complete use of this already existing functionality.

One thing we will not do is per-bitmap memory management. We considered this carefully, and we just won't do it. It is the wrong granularity.

[baibaichen]

Hi @lemire

​Would we reopen this issue, so that we can discuss it for some days? I totally understand a per-bitmap dynamically chosen allocator is the wrong way. Here are my cases, consider we have two vectors a and b, each has its own life time.

vector<roaring::Roaring> a, b;

​When a or b is at end of its' lifetime, every bitmap of vectors is freed by independent roaring_bitmap_clear calling, if there are millions of bitmaps, it becomes a performance bottleneck. I am trying to find a solution to define the vector as follows:

std::vector<Roaring, MyAllocator<Roaring>> a;

When a is at end of its' lifetime, MyAllocator<Roaring> can free all memory in one shot. This is indeed a special case where we know bitmaps of one vector can't interact with bitmaps of another vector, and the lifetime of bitmaps are same with their vectors, but CRoaing can't know this information.

[SalvatorePreviti]

To me this looks like a special case where you'd want to implement your own roaring64 container using the current implementation of roaring64 C api or roaring32 C api. If you look at the source code for the roaring c++ wrapper is not extremely complex or large, so it should be easy to write your own using the allocator of choice. Seems to me a very special case that goes beyond what the general roaring c++ APIs should support

[lemire]

I expect @SalvatorePreviti is correct. The new 64-bit roaring bitmaps are likely what @baibaichen.

We are still lacking a C++ wrapper, but that's not a very difficult job. Pull request invited !!!

[baibaichen]

@SalvatorePreviti

No, we can't simply wrap a roaring64_bitmap_t or roaring_bitmap_t, since most container operations will create new contaier. For example:

static inline container_t *container_or(const container_t *c1, uint8_t type1,
                                        const container_t *c2, uint8_t type2,
                                        uint8_t *result_type) {
    c1 = container_unwrap_shared(c1, &type1);
    c2 = container_unwrap_shared(c2, &type2);
    container_t *result = NULL;
    switch (PAIR_CONTAINER_TYPES(type1, type2)) {
        case CONTAINER_PAIR(BITSET, BITSET):
            result = bitset_container_create();  => /*create a new container via global memory hook */
....

There is no way to tell CRoaring creating a container in a different allocator. I guess @lemire needs a way to judge bitmap a and bitmap b are different bitmaps if they have different allcoator at compile time. I dot't know how to do based on current c code base.

[lemire]

@baibaichen You are certainly free to go out and implement it. If, after implementing it, you feel that it is good code and you want to contribute back, we will consider the pull request. If the contributors support your pull request, it is likely to be accepted. We will need serious testing and benchmarking, and you should clearly document the benefits. The benefits should exceed those that are possible right now with a custom allocator (as allowed by the library).

This issue is resolved. If you'd like to offer up a pull request, do so.