c++ - 在 C++ 中迭代链表比在具有类似内存访问的 Go 中慢

Question

在各种情况下，我观​​察到 C++ 中的链表迭代始终比 Go 慢 10-15%。我第一次尝试在 Stack Overflow 上解决这个谜团是 here .我编写的示例有问题，因为:

1) 由于堆分配，内存访问不可预测，并且

2) 因为没有做任何实际工作，一些人的编译器正在优化主循环。

为了解决这些问题，我有一个用 C++ 和 Go 实现的新程序。 C++ 版本需要 1.75 秒，而 Go 版本需要 1.48 秒。这一次，我在计时开始之前做了一个大堆分配，并用它来操作一个对象池，我从中释放和获取链表的节点。这样，两个实现之间的内存访问应该完全类似。

希望这能让谜团更加重现!

C++:

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <boost/timer.hpp>

using namespace std;

struct Node {
    Node *next; // 8 bytes
    int age;   // 4 bytes
};

// Object pool, where every free slot points to the previous free slot
template<typename T, int n>
struct ObjPool
{
    typedef T*       pointer;
    typedef pointer* metapointer;

    ObjPool() :
        _top(NULL),
        _size(0)
    {
        pointer chunks = new T[n];
        for (int i=0; i < n; i++) {
            release(&chunks[i]);
        }
    }

    // Giver an available pointer to the object pool
    void release(pointer ptr)
    {
        // Store the current pointer at the given address
        *(reinterpret_cast<metapointer>(ptr)) = _top;

        // Advance the pointer
        _top = ptr;

        // Increment the size
        ++_size;
    }

    // Pop an available pointer off the object pool for program use
    pointer acquire(void)
    {
        if(_size == 0){throw std::out_of_range("");}

        // Pop the top of the stack
        pointer retval = _top;

        // Step back to the previous address
        _top = *(reinterpret_cast<metapointer>(_top));

        // Decrement the size
        --_size;

        // Return the next free address
        return retval;
    }

    unsigned int size(void) const {return _size;}

protected:
    pointer _top;

    // Number of free slots available
    unsigned int _size;
};

Node *nodes = nullptr;
ObjPool<Node, 1000> p;

void processAge(int age) {
    // If the object pool is full, pop off the head of the linked list and release
    // it from the pool
    if (p.size() == 0) {
        Node *head = nodes;
        nodes = nodes->next;
        p.release(head);
    }

    // Insert the new Node with given age in global linked list. The linked list is sorted by age, so this requires iterating through the nodes.
    Node *node = nodes;
    Node *prev = nullptr;
    while (true) {
        if (node == nullptr || age < node->age) {
            Node *newNode = p.acquire();
            newNode->age = age;
            newNode->next = node;

            if (prev == nullptr) {
                nodes = newNode;
            } else {
                prev->next = newNode;
            }

            return;
        }

        prev = node;
        node = node->next;
    }
}

int main() {
    Node x = {};
    std::cout << "Size of struct: " << sizeof(x) << "\n"; // 16 bytes

    boost::timer t;
    for (int i=0; i<1000000; i++) {
        processAge(i);
    }

    std::cout << t.elapsed() << "\n";
}

Go:

package main

import (
    "time"
    "fmt"
    "unsafe"
)

type Node struct {
    next *Node // 8 bytes
    age int32 // 4 bytes
}

// Every free slot points to the previous free slot
type NodePool struct {
    top *Node
    size int
}

func NewPool(n int) NodePool {
    p := NodePool{nil, 0}
    slots := make([]Node, n, n)
    for i := 0; i < n; i++ {
        p.Release(&slots[i])
    }

    return p
}

func (p *NodePool) Release(l *Node) {
    // Store the current top at the given address
    *((**Node)(unsafe.Pointer(l))) = p.top
    p.top = l
    p.size++
}

func (p *NodePool) Acquire() *Node {
    if p.size == 0 {
        fmt.Printf("Attempting to pop from empty pool!\n")
    }
    retval := p.top

    // Step back to the previous address in stack of addresses
    p.top = *((**Node)(unsafe.Pointer(p.top)))
    p.size--
    return retval
}

func processAge(age int32) {
    // If the object pool is full, pop off the head of the linked list and release
    // it from the pool
    if p.size == 0 {
        head := nodes
        nodes = nodes.next
        p.Release(head)
    }

    // Insert the new Node with given age in global linked list. The linked list is sorted by age, so this requires iterating through the nodes.
    node := nodes
    var prev *Node = nil
    for true {
        if node == nil || age < node.age {
            newNode := p.Acquire()
            newNode.age = age
            newNode.next = node

            if prev == nil {
                nodes = newNode
            } else {
                prev.next = newNode
            }
            return
        }

        prev = node
        node = node.next
    }
}

// Linked list of nodes, in ascending order by age
var nodes *Node = nil
var p NodePool = NewPool(1000)

func main() {
    x := Node{};
    fmt.Printf("Size of struct: %d\n", unsafe.Sizeof(x)) // 16 bytes

    start := time.Now()
    for i := 0; i < 1000000; i++ {
        processAge(int32(i))
    }

    fmt.Printf("Time elapsed: %s\n", time.Since(start))
}

输出:

clang++ -std=c++11 -stdlib=libc++ minimalPool.cpp -O3; ./a.out
Size of struct: 16
1.7548

go run minimalPool.go
Size of struct: 16
Time elapsed: 1.487930629s

Answer 1

您的两个程序之间的最大区别在于您的 Go 代码会忽略错误(如果幸运的话，如果您清空池，则会出现 panic 或段错误)，而您的 C++ 代码通过异常传播错误。比较:

if p.size == 0 {
    fmt.Printf("Attempting to pop from empty pool!\n")
}

对比

if(_size == 0){throw std::out_of_range("");}

---

至少有三种方法¹可以使比较公平:

1. 可以更改 C++ 代码以忽略错误，就像在 Go 中所做的那样，
2. 将两个版本都更改为 panic/abort on error。
3. 更改 Go 版本以惯用地处理错误，² 就像在 C++ 中一样。

那么，让我们全部做一遍，比较结果³:

• C++ 忽略错误:1.059329s 墙，1.050000s 用户 + 0.000000s 系统 = 1.050000s CPU (99.1%)
• C++ 因错误中止:1.081585s 墙，1.060000s 用户 + 0.000000s 系统 = 1.060000s CPU (98.0%)
• 因错误而 panic :耗时:1.152942427s
• 忽略错误:耗时:1.196426068s
• Go 惯用错误处理:耗时:1.322005119s
• C++ 异常:1.373458s 墙，1.360000s 用户 + 0.000000s 系统 = 1.360000s CPU (99.0%)

---

所以:

• 没有错误处理，C++ 比 Go 更快。
• 由于 panic ，Go 变得更快，⁴但仍然没有 C++ 快。
• 使用惯用的错误处理，C++ 比 Go 慢得多。

为什么？这个异常在您的测试运行中实际上从未发生过，因此实际的错误处理代码永远不会以任何一种语言运行。但是 clang 不能证明它没有发生。而且，由于您永远不会在任何地方 catch 异常，这意味着它必须为每个未省略的帧一直发出异常处理程序和堆栈展开器。所以它在每个函数调用和返回上做了更多的工作——不是很多更多的工作，但是你的函数做的实际工作太少了，以至于不必要的额外工作加起来了。

---

<子>1。您还可以更改 C++ 版本以进行 C 风格的错误处理，或使用 Option 类型，可能还有其他可能性。

<子>2。这当然需要更多的改动:需要导入errors，将Acquire的返回类型改为(*Node, error)，把processAge的返回类型改成error，把你所有的return语句都改一下，加上至少两个if err != nil { ... } 检查。但这应该是 Go 的一件好事，对吧？

<子>3。当我这样做的时候，我用 boost::auto_cpu_timer 替换了你的旧版 boost::timer，所以我们现在也可以看到挂钟时间(与 Go 一样)作为 CPU 时间。

_{4.我不会试图解释为什么，因为我不明白。快速浏览一下程序集，它明显优化了一些检查，但我不明白为什么没有 panic 就无法优化这些检查。}