Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > require some memory allocation advice ....

Reply
Thread Tools

require some memory allocation advice ....

 
 
abir
Guest
Posts: n/a
 
      07-17-2008
I have a big dynamic sparse directed graph implementation where new
nodes are added & old nodes are removed. Usually, at any moment of
time the number of nodes in the graph and the number of edges are
approximately constant. The nodes and associated data are stored in a
quasi-static dynamic memory (quasi_buffer) which reserves a minimum
memory, but on demand can grow upto an user defined maximum memory.
The no of nodes in the graph are approx (N = 6000000) , while the no
of edges per node are approx 40-45, connected to mostly recently
arrived nodes, and number of properties (name value pair stored in
map) per node approx 24.
Each node has its local data, a set of parameter maps (std::map with
name value pair) and a list of linked vertex (std::vector). Both of
them are small dynamic memory per vertex.
so the codes are like,
///This is position structure, to get position from quasi_buffer
struct pos{
std::size_t index;///the index to quasi_buffer including history.
quasi_buffer<node>* buffer;
pos(quasi_buffer<node>& b,std::size_t i) : buffer(&b),index(i){}
std::size_t relative_pos()const{ return index-
(*buffer).num_removed();}
};
struct node{
std::vector<pos> edges;///vector has dynamic memory
std::map<Name,Value> prop;///map has dynamic memory
///Name is enum, Value is a small struct(no dynamic memory)
///other local data (which doesn't have any dynamic memory)
int type;
int processState;
};
typedef quasi_buffer<node> graph;
The graph visualization is like, and most of the edges are
connected nearby nodes (in memory & in time) The numbers are node
numbers for connection.
add node<---------- graph nodes ---------> remove node (time line)
1 2 3 4 5 6 7 8 9 10 11 12 13
--- --- --- --- --- --- --- --- --- --- --- --- ---
|1 |1 |1 |3 |4 |5 |5 |6 |10 |11 |10 |13 |10
|2 |2 |5 |6 |6 |7 |12 |11 =>
connecting node list
|4 |7 |8 |9 |12
|9
in memory the nodes may be like
6 7 8 9 10 11 12 13 1 2 3 4 5 , i.e folded in a circular fashion.

Now my questions are,
1) can i have an allocator which allocates all these small vectors in
approximately FIFO way (there can be some holes in the FIFO list, as
some of the old nodes may be still referred) so that it can works
without too many allocation /deallocation calls?
At present i am not doing too much performance measure, but i want to
check if the concept works.
i think i need a statefull allocator, which can allocate multiple
vectors and maps from same pool (perhaps using some static data?).
2) as the number of nodes can rarely increase to a large extent or
shrink to a small, causing the nodes to be moved to a new memory (much
like vector). In this case as all the nodes are copied to a new memory
(N node struct), so the vectors & maps which ware stored in the node
are also copied (this is approx 40*N pos struct + N maps with approx
20 elements). However it can be done with only exchanging the internal
pointers for them like swap. Can the node's copy constructor be
implemented to facilitate this (i don't use at present the copy
ctors)?
This will be kind of proposed "move " ?

Thanks
abir
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
An idea for heap allocation at near stack allocation speed Bjarke Hammersholt Roune C++ 14 03-06-2011 08:07 AM
some question about memory allocation not enough miloody C Programming 8 05-13-2009 08:44 AM
static memory allocation versus dynamic memory allocation Ken C Programming 24 11-30-2006 12:37 AM
What is the difference between dynamic memory allocation,and stack allocation ? chris C++ 6 10-28-2005 05:27 AM
Dynamic memory allocation and memory leak... s.subbarayan C Programming 10 03-22-2005 02:48 PM



Advertisments