a problem on fixed length allocator and data structures

[rosun82]

Recently I am trying to develop a C++ program dealing with large scale DAGs (about 6,000,000 nodes and 50,000,000 edges), and I find a very serious problem here.

In the program, the node and edges are frequently added and deleted, so the key point is to avoid memory fragmentation, in other word, all the nodes and edges must be allocated from a chunk-based fix length allocator, so the deleted entries can be managed and re-used without any fragmentation.

Here is the question, where can I find high efficient C++ libraries providing basic manipulation of binary trees and graphs, at the same time allow the user to customize the allocation of objects. In other word, the lib works in a in-place pattern.

I have already tried STL, but the STL allocator seems not useful at all since it must provide allocation of different types. For instance, you can not pass an allocator designed for a specific type, since the allocator would be 'rebind' anyway.

The lib I want is in this form:

template <typename _Key, typename _T, typename _AllocForT, typename _AllocForOthers >
struct map;

and for example:
typedef map<int, mytype, alloc_type, default_alloc> map_type;

and the alloc_type is something like FixedLengthAllo cator<typename map_type::_Node Type>, so the allocation and deletion of the underlying binary tree node type can be managed specifically.

I do not want to implement everything myself, so please help me if you got any information. my email is <email address removed as per Posting Guidelines>

[AdrianH]

The STL allows you to bind an allocator to a STL container. Have you attempted to use this mechinism? See here for more information.

If you have other questions, please feel free to post them.


Adrian

[rosun82]

The problem is: the allocator you passed to STL container is an allocator for ALL types, not only for the specific type you need. For example

when use
std::list<T, alloc>, the alloc has to be able to allocate T, rebind<T>, ...

One possible solution is to override the default allocator with a two layer allocator, on the first layer, we check the size of memory required, and map specific memory requirement (say sizeof(T)+2*siz eof(void*) ) to our private allocator, which is designed to work with that type only. But this method is not very elegant, and it depends on specific implementation of different STL. What I want to know is that are there any libraries which support such allocation behavior explicitly? In other word, we have to assign allocation of PRIMARY type in a container (For example, in list, the PRIMARY type is T with two pointers, in set, the PRIMARY type is T with 3 pointers) with one allocator, and assign other allocations with default allocator.

Thank you very much

[AdrianH]

The problem is: the allocator you passed to STL container is an allocator for ALL types, not only for the specific type you need. For example

when use
std::list<T, alloc>, the alloc has to be able to allocate T, rebind<T>, ...

One possible solution is to override the default allocator with a two layer allocator, on the first layer, we check the size of memory required, and map specific memory requirement (say sizeof(T)+2*siz eof(void*) ) to our private allocator, which is designed to work with that type only. But this method is not very elegant, and it depends on specific implementation of different STL. What I want to know is that are there any libraries which support such allocation behaviour explicitly? In other word, we have to assign allocation of PRIMARY type in a container (For example, in list, the PRIMARY type is T with two pointers, in set, the PRIMARY type is T with 3 pointers) with one allocator, and assign other allocations with default allocator.

Thank you very much

Because what you are asking is unnecessary.

You could do something like you were considering: When allocate() is called, it will check to see if it is a particular size (sizeof(yourCla ss)) and if it is, put it in your allocation container and if not, use the default allocator. That would of course require that you check to see if the allocator was used when you delete it. But all this can be unnecessary as you will see in a moment.

If you are only putting a single type into the container, then you will not have a problem. The allocator is meant only to be used for that list type you specified (the template parameters are part of the type remember) and so you will not have the problem you were describing.

If you have a hierarchy of types you wish to put into the list, then you can do this instead: override the new and delete operators for the class you wish to have special allocation/deallocation semantics. This is much simpler as it is overridden on a class by class basis. The default allocator/deallocator is just a call to the new and delete operators.

Hope this helps.


Adrian