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.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:49:57 UTC