EDIT: After getting some feedback, I created a new example which should be more reproducible.
I've been writing a project in C++ that involves lots of linked list iteration. To get a benchmark, I rewrote the code in Go. Surprisingly I've found that the Go implementation runs consistently faster by ~10%, even after passing the -O flag to clang++. Probably I'm just missing some obvious optimization in C++ but I've been banging my head against a wall for a while with various tweaks.
Here's a simplified version, with identical implementations in C++ and Go where the Go program runs faster. All it does is create a linked list with 3000 nodes, and then time how long it takes to iterate over this list 1,000,000 times (7.5 secs in C++, 6.8 in 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) << "
"; // 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
", 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
", time.Since(start))
}
Output from my 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 version:
$ clang++ --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin15.6.0
Thread model: posix
EDIT: UKMonkey brought up the fact that the nodes may be contiguously allocated in Go but not C++. To test this, I allocated contiguously in C++ with a vector, and this did not change the runtime:
// 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;
}
I checked that the resulting linked list is indeed contiguous:
std::cout << &nodes << " " << &nodes->next << " " << &nodes->next->next << " " << &nodes->next->next->next << "
";
0x1032de0e0 0x7fb934001000 0x7fb934001010 0x7fb934001020
