为何给std::list元素添加iterator字段会大幅减慢pop_back操作？

我在C++项目里用std::list<TestElement*>存储动态分配对象的指针，给每个TestElement加了个std::list<TestElement*>::iterator类型的listIterator字段，用来记录自身在列表中的位置。初始化时往列表里插入了200万个TestElement对象，每个对象都设置好对应的迭代器值。

测试时发现性能差异悬殊：

• 包含listIterator字段：pop_back()+delete操作平均耗时289.316ms
• 不含该字段：相同操作仅耗时0.0043ms

按道理std::list::pop_back()是常数时间操作，这种性能衰减完全不符合预期，测试代码如下：

#include <iostream>
#include <list>
#include <chrono>

class TestElement {
public:
    int value;
    std::list<TestElement*>::iterator listIterator;
};

int main() {
    const int numElements = 2000000;
    const int testIterations = 10;

    std::list<TestElement*> testList;

    for (int i = 0; i < numElements; ++i) {
        testList.push_front(new TestElement());
        testList.front()->listIterator = testList.begin();
    }

    double totalDuration = 0.0;

    for (int t = 0; t < testIterations; ++t) {
        auto start = std::chrono::high_resolution_clock::now();

        delete testList.back();
        testList.pop_back();

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> duration = end - start;
        totalDuration += duration.count();
    }

    std::cout << "Average time for pop_back and delete operations: "
              << (totalDuration / testIterations) << " ms" << std::endl;

    return 0;
}

性能暴跌的核心原因 #

问题根本不在pop_back()本身，而是CPU缓存命中率暴跌导致delete操作的内存访问开销剧增：

1. 对象内存占用大幅增加：不带listIterator时，TestElement只有一个int字段，加上内存对齐，64位系统下每个对象约占8字节；添加迭代器字段后，迭代器本质是一个指向链表节点的指针（8字节），加上int的4字节，对齐后每个对象占16字节。200万个对象的总内存占用从16MB飙升到32MB，远超多数CPU的L2缓存容量（通常几MB到十几MB），甚至可能超出L3缓存的承载上限。
2. 缓存未命中的高昂代价：执行delete testList.back()时，操作的是最早分配的那个TestElement对象。前面200万次new操作已经把缓存占满，替换掉了早期对象的缓存页；大对象场景下，这个对象的内存肯定不在CPU缓存里，每次delete都要从主存读取相关数据，而主存访问速度比缓存慢几百倍。
3. 内存管理器的额外开销：更大的对象会让内存分配器的管理块更分散，释放内存时的链表遍历、空闲块合并操作也会因为缓存未命中变得更慢。

而不带迭代器字段时，对象体积小，总内存占用低，早期对象的缓存页可能还留在L3缓存中，delete操作几乎都是缓存命中，因此耗时极低。

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