[Boost-bugs] [Boost C++ Libraries] #1980: [Boost Graph library] functionality to reserve memory

Subject: [Boost-bugs] [Boost C++ Libraries] #1980: [Boost Graph library] functionality to reserve memory
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-06-01 18:14:26

#1980: [Boost Graph library] functionality to reserve memory
--------------------------------------------------------------+-------------
 Reporter:  marc.albers_at_[hidden]                          |       Owner:  dgregor     
     Type:  Feature Requests                                  |      Status:  new         
Milestone:  To Be Determined                                  |   Component:  graph       
  Version:  Boost 1.35.0                                      |    Severity:  Optimization
 Keywords:  Boost Graph library, std::vector, reserve memory  |  
--------------------------------------------------------------+-------------
 Hi,

 I would like to propose a feature for the Boost Graph library.

 Summary:

 For large std::vector containers reserving memory in advance can improve
 performance significantly if many objects are added. I'd like to have this
 option for the boost::adjacency_list when using selector type vecS for
 storage of vertices and edges. This option would help to avoid frequent
 reallocations when using add_vertex() and add_edge().

 My Problem:

 I am using the Boost Graph library for a large-scale railway crew
 scheduling problem.  The graph is defined as boost::adjecency_list with
 vecS as storage selection for vertices and edges, i.e., std::vector is
 used. For some problem instances, the graph can have 35,000 vertices and
 4,000,000 edges. The vertex descriptors have a size of up to 40 bytes and
 edge descriptors have a size of up to 100 bytes. The graph is created
 using the add_vertex() and add_edge() methods. Creating this graph
 requires several hours on my Pentium M 1.7 GHz which seems too long.

 My Solution:

 The file \boost\graph\detail\adjecency_list.hpp is modified as follows.
 Class vec_adj_list_impl gets 3 new methods:

 inline void v_reserve(const vertices_size_type& nv) {
   m_vertices.reserve(nv);
 }

 inline void oe_reserve(vertex_descriptor& v, const edges_size_type& ne) {
   m_vertices[v].m_out_edges.reserve(ne);
 }

 inline void ie_reserve(vertex_descriptor& v, const edges_size_type& ne) {
   m_vertices[v].m_in_edges.reserve(ne);
 }

 Using these methods, the time to create a large-scale graph drops to
 minutes (factor >10). I also modified the method copy_impl to speed-up
 copying.

 I attached my modification in a file.

 Comment:

 These methods are only a workaround. Since the documentation of
 add_vertex() and add_edge() mentions the problem of reallocations, I
 suspect that the authors have already thought about reserving memory, but
 for some reasons did not implement it. As my example shows, there are
 situations where reserving memory is very useful. This feature is
 desirable for any user working with large-scale graphs that require an
 implementation with std::vector.

 Marc

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/1980>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.