require some memory allocation advice ....

Discussion in 'C++' started by abir, Jul 17, 2008.

  1. abir

    abir Guest

    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
     
    abir, Jul 17, 2008
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. s.subbarayan

    Dynamic memory allocation and memory leak...

    s.subbarayan, Mar 18, 2005, in forum: C Programming
    Replies:
    10
    Views:
    720
    Eric Sosman
    Mar 22, 2005
  2. Ken
    Replies:
    24
    Views:
    3,896
    Ben Bacarisse
    Nov 30, 2006
  3. chris
    Replies:
    6
    Views:
    1,006
    chris
    Oct 28, 2005
  4. miloody
    Replies:
    8
    Views:
    325
    miloody
    May 13, 2009
  5. Bjarke Hammersholt Roune
    Replies:
    14
    Views:
    1,207
    Bjarke Hammersholt Roune
    Mar 6, 2011
Loading...

Share This Page