A
abir
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
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