In a variety of contexts I've observed that linked list iteration is consistently slower in C++ than in Go by 10-15%. My first attempt at resolving this mystery on Stack Overflow is here. The example I coded up was problematic because:
1) memory access was unpredictable because of heap allocations, and
2) because there was no actual work being done, some people's compilers were optimizing away the main loop.
To resolve these issues I have a new program with implementations in C++ and Go. The C++ version takes 1.75 secs compared to 1.48 secs for the Go version. This time, I do one large heap allocation before timing begins and use it to operate an object pool from which I release and acquire nodes for the linked list. This way the memory access should be completely analogous between the two implementations.
Hopefully this makes the mystery more reproducible!
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) << "
"; // 16 bytes
boost::timer t;
for (int i=0; i<1000000; i++) {
processAge(i);
}
std::cout << t.elapsed() << "
";
}
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!
")
}
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
", unsafe.Sizeof(x)) // 16 bytes
start := time.Now()
for i := 0; i < 1000000; i++ {
processAge(int32(i))
}
fmt.Printf("Time elapsed: %s
", time.Since(start))
}
Output:
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
