重标号前置算法性能优化：迭代移元素至队首的最优数据结构

问题背景 #

在实现最大流的重标号前置算法时遭遇性能瓶颈，当前图存储结构与主循环逻辑如下：

当前图存储结构 #

struct edge{
    int destination;
    int capacity;
};

struct vertex{
    int e_flow;
    int h;
    vector<edge> edges;
};

主循环实现 #

//nodes are 0..nodeCount-1 with source=0 and sink=nodeCount-1
vector<int> toDischarge(nodeCount-2,0);
for(int i=1;i<sink;i++){
    toDischarge[i-1]=i;
}//skip over source and sink
//custom pointer to the entry of toDischarge we are currently accessing
int point = 0;
while(point != nodeCount-2){
    int val = toDischarge[point];
    int oldHeight = graph[val].h;
    discharge(val, graph, graph[val].e_flow);
    if(graph[val].h != oldHeight){
        rotate(toDischarge.begin(), toDischarge.begin()+point, toDischarge.begin()+point+1);
        //if the value of the vertex has changed move it to the front and reset pointer
        point = 0;
    }
    point++;
}

已尝试优化及问题：

• 使用std::list因缓存命中率过低，性能反而更差；
• 改用vector后，valgrind分析显示向量元素访问占比超30%；
• 尝试复制顶点到局部变量，但因复制边列表导致性能恶化。

数据结构优化（针对toDischarge遍历列表） #

1. 改用std::deque+无效标记 #

避免rotate操作的O(n)内存移动开销：当顶点高度变化时，直接将其推入队列头部，同时标记原位置元素无效，遍历过程中跳过无效项。示例逻辑：

deque<int> toDischarge;
vector<bool> isValid(nodeCount, true);
for(int i=1;i<sink;i++){
    toDischarge.push_back(i);
}
while(!toDischarge.empty()){
    int val = toDischarge.front();
    toDischarge.pop_front();
    if(!isValid[val]) continue;
    int oldHeight = graph[val].h;
    discharge(val, graph, graph[val].e_flow);
    if(graph[val].h != oldHeight){
        isValid[val] = false;
        isValid[val] = true;
        toDischarge.push_front(val);
    }
}

优势：push_front/pop_front为O(1)操作，无大规模内存移动，缓存友好性优于list。

2. 手动实现基于数组的循环队列 #

若std::deque缓存表现仍不理想，可手动实现循环队列：

• 用head/tail指针管理队列数组，配合布尔数组标记元素有效性；
• 顶点高度变化时，直接将其加入队列头部，原位置标记无效；
• 遍历到无效元素直接跳过，完全避免内存移动操作。

3. 优化遍历逻辑，避免重置point #

当前代码修改顶点后重置point=0，导致重复遍历大量已处理节点。可改为：

• 将修改后的顶点插入到当前point的前一位置，而非列表头部，无需重置point，减少重复遍历次数。

图存储结构优化 #

1. 紧凑化邻接表存储 #

将所有边存入全局连续数组，顶点仅存储边的起始索引与数量，避免多个小vector<edge>的内存碎片化：

struct edge{
    int destination;
    int capacity;
};

struct vertex{
    int e_flow;
    int h;
    int edge_start; //全局边数组中的起始索引
    int edge_count; //边的数量
};

vector<edge> all_edges;
vector<vertex> graph;

优势：全局边数组为连续内存，访问时缓存命中率更高，降低内存开销。

2. 拆分顶点高频字段 #

将e_flow、h这两个高频访问字段从vertex结构体中拆分，存入独立的连续数组：

vector<int> e_flow(nodeCount);
vector<int> height(nodeCount);
vector<vector<edge>> edges(nodeCount); //或使用上述紧凑存储方案

优势：访问e_flow和h时为连续内存访问，缓存命中率大幅提升。

3. 边结构的内存对齐优化 #

确保edge结构体大小符合缓存行对齐要求，减少缓存行拆分：

struct edge{
    int destination;
    int capacity;
    alignas(16) int padding; //强制16字节对齐，根据CPU缓存行调整
};

4. 显式存储反向边索引 #

重标号前置算法需频繁操作反向边，在edge结构体中添加反向边索引，避免遍历查找开销：

struct edge{
    int destination;
    int capacity;
    int rev_edge_idx; //反向边在全局边数组中的索引
};

其他优化建议 #

• 预分配内存：所有vector初始化时预分配足够空间，避免动态扩容开销；
• 内联核心函数：将discharge标记为inline，减少函数调用的栈帧开销；
• 编译优化：使用-O2/-O3级别编译，禁用调试符号；
• 循环展开：对discharge内的循环适当展开，提升CPU流水线效率。

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