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

Question

РЕДАКТИРОВАТЬ: После получения обратной связи я создал новый пример , который должен быть более воспроизводимым.

Я писал проект на C ++, который включает в себя много итераций связанного списка.Чтобы получить эталонный тест, я переписал код на Go.Удивительно, но я обнаружил, что реализация Go работает стабильно быстрее на ~ 10%, даже после передачи флага -O в clang ++.Возможно, мне просто не хватает какой-то очевидной оптимизации в C ++, но я какое-то время бился головой о стену с различными ухищрениями.

Вот упрощенная версия с идентичными реализациями в C ++ и Go, где GoПрограмма работает быстрее.Все, что он делает, это создает связанный список с 3000 узлами, а затем время, необходимое для перебора этого списка 1 000 000 раз (7,5 с в C ++, 6,8 в Go).

C ++:

#include <iostream>
#include <chrono>

using namespace std;
using ms = chrono::milliseconds;

struct Node {
    Node *next;
    double age;
};

// Global linked list of nodes
Node *nodes = nullptr;

void iterateAndPlace(double age) {
    Node *node = nodes;
    Node *prev = nullptr;

    while (node != nullptr) {
        // Just to make sure that age field is accessed
        if (node->age > 99999) {
            break;
        }

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

    // Arbitrary action to make sure the compiler
    // doesn't optimize away this function
    prev->age = age;
}

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

    // Fill in global linked list with 3000 dummy nodes
    for (int i=0; i<3000; i++) {
        Node* newNode = new Node;
        newNode->age = 0.0;
        newNode->next = nodes;
        nodes = newNode;
    }

    auto start = chrono::steady_clock::now();
    for (int i=0; i<1000000; i++) {
        iterateAndPlace(100.1);
    }

    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    std::cout << "Elapsed time is :  "<< chrono::duration_cast<ms>(diff).count()<<" ms "<<endl;
}

Go:

package main
import (
    "time"
    "fmt"
    "unsafe"
)

type Node struct {
    next *Node
    age float64
}

var nodes *Node = nil

func iterateAndPlace(age float64) {
    node := nodes
    var prev *Node = nil

    for node != nil {
        if node.age > 99999 {
            break
        }
        prev = node
        node = node.next
    }

    prev.age = age
}

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

    for i := 0; i < 3000; i++ {
        newNode := new(Node)
        newNode.next = nodes
        nodes = newNode
    }

    start := time.Now()
    for i := 0; i < 1000000; i++ {
        iterateAndPlace(100.1)
    }
    fmt.Printf("Time elapsed: %s\n", time.Since(start))
}

Вывод с моего Mac:

$ go run minimal.go
Size of struct: 16
Time elapsed: 6.865176895s

$ clang++ -std=c++11 -stdlib=libc++ minimal.cpp -O3; ./a.out
Size of struct: 16
Elapsed time is :  7524 ms

Версия Clang:

$ clang++ --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin15.6.0
Thread model: posix

РЕДАКТИРОВАТЬ: UKMonkey поднял тот факт, чтоузлы могут быть расположены последовательно в Go, но не в C ++.Чтобы проверить это, я выделил в C ++ смежный вектор, и это не изменило время выполнения:

// Fill in global linked list with 3000 contiguous dummy nodes
vector<Node> vec;
vec.reserve(3000);
for (int i=0; i<3000; i++) {
    vec.push_back(Node());
}

nodes = &vec[0];
Node *curr = &vec[0];
for (int i=1; i<3000; i++) {
    curr->next = &vec[i];
    curr = curr->next;
    curr->age = 0.0;
}

Я проверил, что результирующий связанный список действительно смежный:

std::cout << &nodes << " " << &nodes->next << " " << &nodes->next->next << " " << &nodes->next->next->next << "\n";
0x1032de0e0 0x7fb934001000 0x7fb934001010 0x7fb934001020

Answer 1

Мне кажется, проблема в коде, созданном с помощью clang. Мой результат:
6097мс с лязгом
5106мс с gcc
5219мс с ходу
поэтому я разобрал и вижу, что генерируемый код без доступа к полю возраста одинаков как в clang, так и в gcc, но при доступе к полю возраста код, генерируемый из clang, немного хуже, чем код, генерируемый из gcc.
Это код, сгенерированный из Clang:

из gcc:

и последняя версия go:

Как вы можете видеть, код практически одинаков для всех, но в версии clang первые два шага в начале увеличивают количество команд в версии gcc, поэтому они немного замедляют производительность, и я думаю, что наибольшее влияние на производительность оказывает инструкция uncomisd для версии clang, поскольку происходит перенаправление памяти. Извините за мой плохой английский, я надеюсь, что это понятно

Answer 2

Предисловие: Я не эксперт по C ++ или ассемблер. Но я знаю немного о них, возможно, достаточно опасно.

Итак, я был взволнован и решил взглянуть на ассемблер, сгенерированный для Go, и проверил его на соответствие выводу для clang ++.

Краткий обзор высокого уровня

Позже здесь я рассмотрю вывод ассемблера для обоих языков в ассемблере x86-64. Фундаментальная «критическая секция» кода в этом примере представляет собой очень узкий цикл. По этой причине, это самый большой вклад в время, проведенное в программе.

Почему узкие циклы имеют значение, потому что современные процессоры могут выполнять инструкции, как правило, быстрее, чем соответствующие значения для кода, на который можно ссылаться (например, для сравнения) из памяти. Чтобы достичь невероятно высоких скоростей, которые они достигают, процессоры выполняют ряд приемов, включая конвейерную обработку, прогнозирование ветвлений и многое другое. Плотные циклы часто являются препятствием для конвейерной обработки, и реалистичное предсказание ветвления может быть лишь незначительно полезным, если между значениями существует зависимость.

По сути, цикл обхода состоит из четырех основных частей:

1. If `node` is null, exit the loop.
2. If `node.age` > 999999, exit the loop.
3a. set prev = node
3b. set node = node.next

Каждая из них представлена ​​несколькими инструкциями на ассемблере, но порции, выводимые Go и C ++, упорядочены по-разному. C ++ эффективно делает это в порядке 3a, 1, 2, 3b. Версия Go делает это в порядке 3, 2, 1. (он запускает первый цикл в сегменте 2, чтобы избежать присвоения до проверки на ноль)

На самом деле, clang ++ выводит на пару меньше инструкций, чем Go, и должен делать меньше обращений к ОЗУ (за счет еще одного регистра с плавающей запятой). Можно предположить, что выполнение почти одних и тех же инструкций только в разных порядках должно привести к тому же затрачиваемому времени, но это не учитывает конвейерную обработку и прогноз ветвления.

Выводы Можно было бы испытать искушение вручную оптимизировать этот код и написать сборку, если это был критический, но небольшой цикл. Игнорируя очевидные причины (это более рискованно / более сложно / более подвержено ошибкам), следует также учитывать, что хотя сгенерированный Go код был быстрее для двух процессоров Intel x86-64, на которых я его тестировал, вполне возможно, что с AMD процессор вы бы получили противоположные результаты. Также возможно, что с Intel N + 1-го поколения вы получите другие результаты.

Мое полное расследование следует ниже:

---

Расследование

ПРИМЕЧАНИЕ Я постарался привести как можно более короткие примеры, включая усечение имен файлов и удаление лишнего пуха из списка сборки, так что ваши результаты могут немного отличаться от моих. Но в любом случае я продолжаю.

Итак, я запустил go build -gcflags -S main.go, чтобы получить этот список сборок, и я только смотрю на iterateAndPlace.

"".iterateAndPlace STEXT nosplit size=56 args=0x8 locals=0x0
    00000 (main.go:16)   TEXT    "".iterateAndPlace(SB), NOSPLIT, $0-8
    00000 (main.go:16)   FUNCDATA    $0, gclocals·2a5305abe05176240e61b8620e19a815(SB)
    00000 (main.go:16)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    00000 (main.go:17)   MOVQ    "".nodes(SB), AX
    00007 (main.go:17)   MOVL    $0, CX
    00009 (main.go:20)   JMP 20
    00011 (main.go:25)   MOVQ    (AX), DX
    00014 (main.go:25)   MOVQ    AX, CX
    00017 (main.go:25)   MOVQ    DX, AX
    00020 (main.go:20)   TESTQ   AX, AX
    00023 (main.go:20)   JEQ 44
    00025 (main.go:21)   MOVSD   8(AX), X0
    00030 (main.go:21)   MOVSD   $f64.40f869f000000000(SB), X1
    00038 (main.go:21)   UCOMISD X1, X0
    00042 (main.go:21)   JLS 11
    00044 (main.go:21)   MOVSD   "".age+8(SP), X0
    00050 (main.go:28)   MOVSD   X0, 8(CX)
    00055 (main.go:29)   RET

В случае, если вы потеряли контекст, я вставлю исходный список с номерами строк:

16  func iterateAndPlace(age float64) {
17      node := nodes
18      var prev *Node = nil
19
20      for node != nil {
21          if node.age > 99999 {
22              break
23          }
24          prev = node
25          node = node.next
26      }
27
28      prev.age = age
29  }

Несколько интересных вещей, которые я сразу заметил:

1. Он не генерирует никакого кода для строки 24, prev = node. Это потому, что стало понятно, что присвоение может быть обмануто: при обходе для получения node.next он использует регистр CX, который является значением prev. Вероятно, это хорошая оптимизация, которую компилятор SSA может понять, является избыточной.
2. Оператор if для node.age изменен на после материала node = node.next, который пропускается на первой итерации. В этом случае вы можете думать об этом как о цикле do.. while. В целом незначительный, поскольку он действительно меняет только первую итерацию. Но, может быть, этого достаточно?

Итак, давайте перейдем к сборке C ++, которую вы получаете из clang++ -S -mllvm --x86-asm-syntax=intel -O3 minimal.cpp.

.quad   4681608292164698112     ## double 99999
# note I snipped some stuff here
__Z15iterateAndPlaced:                  ## @_Z15iterateAndPlaced
## BB#0:
    push    rbp
Lcfi0:
    .cfi_def_cfa_offset 16
Lcfi1:
    .cfi_offset rbp, -16
    mov rbp, rsp
Lcfi2:
    .cfi_def_cfa_register rbp
    mov rcx, qword ptr [rip + _nodes]
    xor eax, eax
    movsd   xmm1, qword ptr [rip + LCPI0_0] ## xmm1 = mem[0],zero
    .p2align    4, 0x90
LBB0_2:                                 ## =>This Inner Loop Header: Depth=1
    mov rdx, rax
    mov rax, rcx
    movsd   xmm2, qword ptr [rax + 8] ## xmm2 = mem[0],zero
    ucomisd xmm2, xmm1
    ja  LBB0_3
## BB#1:                                ##   in Loop: Header=BB0_2 Depth=1
    mov rcx, qword ptr [rax]
    test    rcx, rcx
    mov rdx, rax
    jne LBB0_2
LBB0_3:
    movsd   qword ptr [rdx + 8], xmm0
    pop rbp
    ret

Это действительно интересно. Сгенерированная сборка в целом довольно схожа (игнорируя незначительные различия в том, как ассемблеры перечисляют синтаксис). Она произвела аналогичную оптимизацию, не назначая prev. Более того, C ++, похоже, избавляет от необходимости загружать 99999 каждый раз, когда выполняется сравнение (версия Go загружает его прямо перед сравнением каждый раз).

---

Для целей репликации, версии вещей, которые я использовал (на x86-64 darwin mac на OSX High Sierra)

$ go version
go version go1.9.3 darwin/amd64

$ clang++ --version
Apple LLVM version 9.0.0 (clang-900.0.39.2)
Target: x86_64-apple-darwin17.4.0