为何Boost并行图的Edge内存占用远高于Vertex？

问题背景 #

为何Boost并行图中Edge的内存占用远高于Vertex？

测试代码 #

if (world_.rank() == 0)
    std::cout << "test the memory requirements of edges only using own graph" << std::endl;
world_.barrier(); 
// std::cout << getpid() << std::endl;
auto mems1 = MemoryMonitor::instance().get_all_proc_memory();
if (world_.rank() == 0) {
    std::cout << "before create graph" << std::endl;
    std::cout << mems1 << std::endl;
}
size_type vertex_size = 5000;
size_type per_batch_size = vertex_size / world_.size();

typedef boost::adjacency_list<boost::vecS, boost::distributedS<ProcessGroup, boost::vecS>, boost::bidirectionalS> Graph;

ProcessGroup pg;
Graph g(vertex_size, pg);


Timer t;
for (size_type i = world_.rank() * per_batch_size; i < (world_.rank() + 1) * per_batch_size; i++) {
    for (size_type j = 0; j < vertex_size; j++) {
        Graph::vertex_descriptor from = boost::vertex(i, g);
        Graph::vertex_descriptor to = boost::vertex(j, g);
        boost::add_edge(from, to, g);
    }
}
synchronize(g);
t.stop();
t.print();

world_.barrier();
auto mems2 = MemoryMonitor::instance().get_all_proc_memory();
if (world_.rank() == 0) {
    std::cout << "after create graph" << std::endl;
// std::cout << getpid() "has" << std::endl;
    std::cout << mems2 << std::endl;
}
auto total_edge_size = vertex_size * vertex_size;
auto edge_size_per_proc = total_edge_size / world_.size();
std::cout << "edge_size_per_proc:" << edge_size_per_proc << std::endl;
if (world_.rank() == 0) {
    for (auto i = 0; i < world_.size(); i++) {
        std::cout << "mem increase total:" << mems2[i] - mems1[i];
        std::cout << "\tper edge:"
                  << (mems2[i] - mems1[i]) * 1024 * 1024 / edge_size_per_proc
                  << std::endl;
    }
}

测试结果 #

edge_size_per_proc:6250000
mem increase total:1020.52      per edge:171.215
mem increase total:1016.33      per edge:170.512
mem increase total:1029.33      per edge:172.693
mem increase total:1018.72      per edge:170.913

测试显示每条Edge占用约170字节，而测试Vertex时仅为4字节。查看Boost源码发现，每个顶点维护in_edge和out_edge两个vector，定义如下：

std::vector< boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, MyVertexDescriptor, MyEdgeDescriptor>>

但使用sizeof计算其大小仅为32字节，疑惑剩余140+字节的内存消耗去向。

内存消耗分析 #

• 分布式图的元数据开销：你使用的boost::distributedS是分布式顶点容器，每条边需要存储跨进程的路由信息（比如目标顶点所属进程ID、分布式边标识），以及支持进程间同步、通信的辅助数据，这些是单机图没有的额外开销，占比很大。
• 双向图的存储冗余：因为指定了boost::bidirectionalS，每条边会被存储两次——一次在源顶点的out_edges列表，一次在目标顶点的in_edges列表。在分布式场景下，每份边实例都要附带分布式元数据，进一步放大了内存占用。
• vector的实际存储与分配开销：sizeof计算的只是vector对象本身的大小（64位系统下通常是3个指针加对齐，对应你看到的32字节），但vector中存储的边对象本身包含了分布式描述符、顶点引用等数据，远大于空结构的大小。另外，内存分配器的块分配策略会产生对齐和碎片开销，这部分也会被计入总内存增长。
• 同步后的辅助结构：调用synchronize(g)后，分布式图会构建全局边索引、进程间映射表等辅助结构，这些内存占用也被统计到了总增长里。

验证建议 #

• 替换distributedS为vecS（单机图）重新测试，对比内存占用，直观看到分布式特性带来的额外开销。
• 改用directedS代替bidirectionalS，验证双向存储的冗余对内存的影响。
• 用boost::edge_size(g)确认实际边数，排除统计误差。

内容的提问来源于stack exchange，提问作者Michael