Перебор связанного списка в C ++ медленнее, чем в Go с аналогичным доступом к памяти

Question

В различных контекстах я наблюдал, что итерация связанного списка в C ++ всегда медленнее, чем в Go, на 10-15%. Моя первая попытка раскрыть эту загадку при переполнении стека - здесь . Пример, который я кодировал, был проблематичным, потому что:

1) доступ к памяти был непредсказуемым из-за выделения кучи, и

2) из-за того, что фактически не было сделано никакой работы, некоторые компиляторы оптимизировали основной цикл.

Для решения этих проблем у меня есть новая программа с реализациями на C ++ и Go. Версия C ++ занимает 1,75 с по сравнению с 1,48 с для версии Go. На этот раз я делаю одно большое выделение кучи до начала синхронизации и использую его для управления пулом объектов, из которого я освобождаю и получаю узлы для связанного списка. Таким образом, доступ к памяти должен быть полностью аналогичным между двумя реализациями.

Надеюсь, это сделает тайну более воспроизводимой!

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";
}

Перейти:

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 игнорирует ошибки (и будет паниковать или вызывать ошибку, если вам повезет, если вы очистите пул), в то время как ваш код 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 при ошибке.
3. Измените версию Go для обработки ошибок идиоматически, ² , как вы делаете в C ++.

Итак, давайте сделаем их все и сравним результаты ³ :

• Ошибка игнорирования C ++: стена 1.059329s, пользователь 1.050000s + система 0.000000s = 1.050000s ЦП (99,1%)
• C ++ прерывание при ошибке: стена 1.081585s, пользователь 1.060000s + система 0.000000s = 1.060000s ЦП (98.0%)
• Паникуйте по ошибке: истекшее время: 1.152942427s
• Ошибка игнорирования: истекшее время: 1,196426068s
• Go идиоматическая обработка ошибок: прошедшее время: 1.322005119s
• C ++ исключение: стена 1.373458s, пользователь 1.360000s + система 0.000000s = 1.360000s ЦП (99.0%)

---

Итак:

• Без обработки ошибок C ++ работает быстрее, чем Go.
• С паникой Go становится быстрее, ⁴ , но все же не так быстро, как C ++.
• С идиоматической обработкой ошибок C ++ тормозит намного больше, чем Go.

Почему? Это исключение на самом деле никогда не происходит в вашем тестовом прогоне, поэтому фактический код обработки ошибок никогда не выполняется ни на одном языке. Но clang не может доказать, что этого не происходит. И, поскольку вы никогда не catch исключение где-либо, это означает, что он должен генерировать обработчики исключений и разматывать стеки для каждого неопределяемого кадра на всем протяжении стека. Таким образом, он выполняет больше работы над каждым вызовом и возвратом функции - не много больше работы, но тогда ваша функция выполняет так мало реальной работы, что ненужная дополнительная работа складывается.

---

_{1. Вы также можете изменить версию C ++ для обработки ошибок в стиле C или для использования типа Option и, возможно, других возможностей.}

_{2. Это, конечно, требует гораздо больше изменений: вам нужно импортировать errors, изменить тип возврата Acquire на (*Node, error), изменить тип возврата processAge на error, изменить все ваши return заявления, и добавить как минимум две if err != nil { … } проверки. Но это должно быть хорошо в Go, верно?}

_{3. Пока я занимался этим, я заменил ваше прежнее boost::timer на boost::auto_cpu_timer, так что теперь мы видим время на настенных часах (как в Go), а также время процессора.}

_{4. Я не буду пытаться объяснить почему, потому что я не понимаю этого. С первого взгляда на сборку, он явно оптимизировал некоторые проверки, но я не понимаю, почему он не мог оптимизировать те же проверки без panic.}