Benchmark of arrays vs linked lists.

README.md

Benchmark of Arrays vs Linked Lists

Running the benchmark:

go test -bench=.

This is the result that I got on my i7 2018 MacBook Pro.

goos: darwin
goarch: amd64
BenchmarkArray-8        73914960                15.7 ns/op
BenchmarkChain-8        24245868                61.6 ns/op
PASS
ok      _/tmp/benchmark 2.958s

main_test.go

package main

import "testing"

type Chain struct {
	value int
	next  *Chain
}

func (c *Chain) Insert(value int) Chain {
	tail := Chain{value, c}
	return tail
}

func noop(val int) {}

func BenchmarkArray(b *testing.B) {
	arr := make([]int, 0, 0)
	for n := 0; n < b.N; n++ {
		arr = append(arr, n)
	}

	for n := len(arr) - 1; n >= 0; n-- {
		noop(arr[n])
	}
}

func BenchmarkChain(b *testing.B) {
	var chain *Chain
	for n := 0; n < b.N; n++ {
		if chain == nil {
			chain = &Chain{n, nil}
		} else {
			chain = &Chain{n, chain}
		}
	}

	for chain != nil {
		noop(chain.value)
		chain = chain.next
	}
}