go_benchmark_map_vs_slice_access.go

package main

import (
	"fmt"
	"time"
)

type s struct {
	s []sData
}

type sData struct {
	NextIndex int
}

type m struct {
	m map[int]mData
}

type mData struct {
	NextKey int
}

const (
	testLevel = 1000000
	testTimes = 300
)

func buildS() *s {
	root := &s{
		s: make([]sData, testLevel),
	}
	half := testLevel / 2

	for k := range root.s {
		if k >= half {
			root.s[k] = sData{
				NextIndex: testLevel - k,
			}

			continue
		}

		root.s[k] = sData{
			NextIndex: testLevel - (k + 1),
		}
	}

	return root
}

func traverseS(t *s) int {
	levels := 0
	nextIndex := t.s[0].NextIndex

	for {
		if t.s[nextIndex].NextIndex == nextIndex {
			return levels
		}

		nextIndex = t.s[nextIndex].NextIndex
		levels++
	}
}

func buildM() *m {
	root := &m{
		m: make(map[int]mData, testLevel),
	}

	for i := 0; i < testLevel; i++ {
		root.m[i] = mData{
			NextKey: i + 1,
		}
	}

	return root
}

func traverseM(t *m) int {
	levels := 0
	nextKey := t.m[0].NextKey

	for {
		current, found := t.m[nextKey]

		if !found || current.NextKey == testLevel {
			return levels
		}

		nextKey = current.NextKey
		levels++
	}
}

func main() {
	fmt.Println("Building")

	sss := buildS()
	mmm := buildM()

	fmt.Println("Traversing")

	for i := 0; i < testTimes; i++ {
		start := time.Now()

		sCount := traverseS(sss)
		sEnd := time.Since(start)

		start = time.Now()
		mCount := traverseM(mmm)
		mEnd := time.Since(start)

		if sCount != mCount {
			panic("Count are different")
		}

		fmt.Printf("Traverse took: Slice %s vs Map %s\r\n", sEnd, mEnd)
	}
}

Result of updated code that require CPU to switch page:

Building
Traversing
Traverse took: Slice 3.516668ms vs Map 166.125143ms
Traverse took: Slice 3.292193ms vs Map 167.361995ms
Traverse took: Slice 3.331863ms vs Map 172.94476ms
Traverse took: Slice 3.611445ms vs Map 161.53855ms
Traverse took: Slice 3.294427ms vs Map 161.692624ms
Traverse took: Slice 3.267188ms vs Map 168.105195ms
Traverse took: Slice 3.367762ms vs Map 162.679576ms
Traverse took: Slice 3.294916ms vs Map 163.641106ms
Traverse took: Slice 3.625902ms vs Map 164.086495ms
Traverse took: Slice 3.294288ms vs Map 161.780626ms
Traverse took: Slice 3.554873ms vs Map 161.840412ms
Traverse took: Slice 3.319641ms vs Map 164.839054ms
Traverse took: Slice 3.22207ms vs Map 162.336367ms
Traverse took: Slice 3.303926ms vs Map 161.959355ms
Traverse took: Slice 3.71146ms vs Map 164.706003ms
Traverse took: Slice 3.70699ms vs Map 161.739559ms
Traverse took: Slice 3.442564ms vs Map 169.292178ms
Traverse took: Slice 3.698889ms vs Map 179.625459ms
Traverse took: Slice 3.275431ms vs Map 162.098273ms
Traverse took: Slice 3.567025ms vs Map 168.470195ms
Traverse took: Slice 3.402055ms vs Map 164.796031ms
Traverse took: Slice 3.348486ms vs Map 161.513058ms
Traverse took: Slice 3.552148ms vs Map 168.35719ms
Traverse took: Slice 3.26642ms vs Map 164.20446ms
Traverse took: Slice 3.372722ms vs Map 168.012933ms
Traverse took: Slice 3.355051ms vs Map 170.171503ms
Traverse took: Slice 3.344574ms vs Map 163.882624ms
Traverse took: Slice 3.638195ms vs Map 167.274692ms
Traverse took: Slice 3.576174ms vs Map 162.957971ms
Traverse took: Slice 3.277316ms vs Map 167.224894ms
Traverse took: Slice 3.700775ms vs Map 164.882637ms
Traverse took: Slice 3.20412ms vs Map 162.058254ms
Traverse took: Slice 3.745054ms vs Map 170.081545ms
Traverse took: Slice 3.331864ms vs Map 161.432879ms
Traverse took: Slice 3.823419ms vs Map 170.420983ms
Traverse took: Slice 3.985594ms vs Map 176.430908ms
Traverse took: Slice 3.553265ms vs Map 163.587189ms
Traverse took: Slice 3.408132ms vs Map 170.553336ms
Traverse took: Slice 3.243651ms vs Map 162.602332ms
Traverse took: Slice 3.571215ms vs Map 161.770011ms
Traverse took: Slice 3.261671ms vs Map 177.998467ms
Traverse took: Slice 3.320549ms vs Map 166.13199ms
Traverse took: Slice 3.479232ms vs Map 163.828148ms
Traverse took: Slice 3.451644ms vs Map 176.241704ms
Traverse took: Slice 3.802954ms vs Map 170.702521ms
Traverse took: Slice 3.673954ms vs Map 168.843438ms
Traverse took: Slice 3.303367ms vs Map 252.186816ms
Traverse took: Slice 14.710695ms vs Map 167.466832ms
Traverse took: Slice 3.37349ms vs Map 161.985408ms
Traverse took: Slice 6.086893ms vs Map 171.568645ms
Traverse took: Slice 3.466311ms vs Map 166.378049ms
Traverse took: Slice 3.473296ms vs Map 165.806453ms
Traverse took: Slice 3.375794ms vs Map 163.602485ms
Traverse took: Slice 3.241067ms vs Map 171.94922ms
Traverse took: Slice 4.890621ms vs Map 324.382683ms
Traverse took: Slice 4.084004ms vs Map 184.740348ms
Traverse took: Slice 3.477905ms vs Map 165.810923ms
Traverse took: Slice 3.714114ms vs Map 166.200997ms
Traverse took: Slice 3.832917ms vs Map 163.138448ms
Traverse took: Slice 3.313564ms vs Map 165.966045ms
Traverse took: Slice 3.481607ms vs Map 251.823982ms
Traverse took: Slice 4.128843ms vs Map 227.667711ms
Traverse took: Slice 3.645947ms vs Map 172.065789ms
Traverse took: Slice 3.656144ms vs Map 168.73197ms
Traverse took: Slice 3.394442ms vs Map 173.264575ms
Traverse took: Slice 3.325857ms vs Map 175.149221ms
Traverse took: Slice 4.143649ms vs Map 164.816288ms
Traverse took: Slice 3.381173ms vs Map 171.744721ms
Traverse took: Slice 4.670894ms vs Map 170.549497ms
Traverse took: Slice 3.847724ms vs Map 262.057947ms
Traverse took: Slice 4.524084ms vs Map 170.19623ms
Traverse took: Slice 3.296453ms vs Map 165.687861ms
Traverse took: Slice 3.527005ms vs Map 166.511031ms
Traverse took: Slice 3.264325ms vs Map 167.352081ms
Traverse took: Slice 3.407504ms vs Map 164.171219ms
Traverse took: Slice 3.262579ms vs Map 163.803914ms
Traverse took: Slice 3.242045ms vs Map 162.306759ms
Traverse took: Slice 3.582809ms vs Map 164.030416ms
Traverse took: Slice 3.261671ms vs Map 159.97826ms
Traverse took: Slice 3.389693ms vs Map 158.678131ms
Traverse took: Slice 3.514083ms vs Map 159.371045ms
Traverse took: Slice 3.416513ms vs Map 165.727113ms
Traverse took: Slice 3.384316ms vs Map 158.428723ms
Traverse took: Slice 3.259994ms vs Map 158.659694ms
Traverse took: Slice 3.235411ms vs Map 159.843953ms
Traverse took: Slice 3.22626ms vs Map 158.926913ms
Traverse took: Slice 3.35149ms vs Map 161.802142ms
Traverse took: Slice 3.81413ms vs Map 160.462483ms
Traverse took: Slice 3.926158ms vs Map 158.917275ms
Traverse took: Slice 3.298618ms vs Map 158.022655ms
Traverse took: Slice 3.325717ms vs Map 160.813165ms
Traverse took: Slice 3.452692ms vs Map 158.535374ms
Traverse took: Slice 3.273964ms vs Map 160.412964ms
Traverse took: Slice 3.37775ms vs Map 158.279259ms
Traverse took: Slice 3.282903ms vs Map 160.786624ms
Traverse took: Slice 3.294358ms vs Map 158.236864ms
Traverse took: Slice 3.400868ms vs Map 161.553223ms
Traverse took: Slice 3.415466ms vs Map 158.522801ms
Traverse took: Slice 3.296523ms vs Map 159.287165ms
Traverse took: Slice 3.972534ms vs Map 159.860995ms
Traverse took: Slice 3.328721ms vs Map 160.380768ms
Traverse took: Slice 3.461422ms vs Map 158.478521ms
Traverse took: Slice 3.404431ms vs Map 158.512536ms
Traverse took: Slice 3.392767ms vs Map 179.086346ms
Traverse took: Slice 3.316218ms vs Map 165.60412ms
Traverse took: Slice 3.237087ms vs Map 166.331466ms
Traverse took: Slice 3.628486ms vs Map 163.085999ms
Traverse took: Slice 3.237226ms vs Map 161.676496ms
Traverse took: Slice 3.539576ms vs Map 162.040518ms
Traverse took: Slice 3.294148ms vs Map 162.402095ms
Traverse took: Slice 3.527494ms vs Map 162.666731ms
Traverse took: Slice 3.286047ms vs Map 162.611136ms
Traverse took: Slice 3.35568ms vs Map 170.845424ms
Traverse took: Slice 3.27103ms vs Map 161.328539ms
Traverse took: Slice 3.32858ms vs Map 162.697113ms
Traverse took: Slice 3.57785ms vs Map 159.390253ms
Traverse took: Slice 3.381801ms vs Map 160.025477ms
Traverse took: Slice 3.345553ms vs Map 160.511933ms
Traverse took: Slice 3.335146ms vs Map 160.143232ms
Traverse took: Slice 3.450457ms vs Map 157.685385ms
Traverse took: Slice 3.434393ms vs Map 158.01679ms
Traverse took: Slice 3.527144ms vs Map 160.727679ms
Traverse took: Slice 3.201955ms vs Map 159.035172ms
Traverse took: Slice 3.312936ms vs Map 160.209303ms
Traverse took: Slice 3.349883ms vs Map 162.744327ms
Traverse took: Slice 3.210616ms vs Map 157.87452ms
Traverse took: Slice 3.249029ms vs Map 159.538461ms
Traverse took: Slice 3.256014ms vs Map 159.172065ms
Traverse took: Slice 3.223606ms vs Map 159.063947ms
Traverse took: Slice 3.483143ms vs Map 159.496346ms
Traverse took: Slice 3.444171ms vs Map 160.189609ms
Traverse took: Slice 3.210616ms vs Map 158.475729ms
Traverse took: Slice 3.236318ms vs Map 158.576862ms
Traverse took: Slice 3.212292ms vs Map 161.062647ms
Traverse took: Slice 3.23562ms vs Map 169.773613ms
Traverse took: Slice 3.631141ms vs Map 163.906727ms
Traverse took: Slice 3.950114ms vs Map 169.937046ms
Traverse took: Slice 3.605229ms vs Map 162.205629ms
Traverse took: Slice 3.32865ms vs Map 163.563099ms
Traverse took: Slice 4.066961ms vs Map 172.093241ms
Traverse took: Slice 3.323971ms vs Map 161.862559ms
Traverse took: Slice 3.575267ms vs Map 161.623208ms
Traverse took: Slice 3.392767ms vs Map 167.693129ms
Traverse took: Slice 3.881599ms vs Map 170.690165ms
Traverse took: Slice 3.526516ms vs Map 169.512959ms
Traverse took: Slice 3.259436ms vs Map 162.185793ms
Traverse took: Slice 3.582879ms vs Map 162.808794ms
Traverse took: Slice 3.348346ms vs Map 161.681527ms
Traverse took: Slice 3.687435ms vs Map 165.527087ms
Traverse took: Slice 3.585463ms vs Map 161.943718ms
Traverse took: Slice 3.235271ms vs Map 161.371214ms
Traverse took: Slice 3.334238ms vs Map 162.956442ms
Traverse took: Slice 3.955632ms vs Map 166.880925ms
Traverse took: Slice 3.261741ms vs Map 161.757237ms
Traverse took: Slice 3.228566ms vs Map 165.891248ms
Traverse took: Slice 3.298897ms vs Map 162.536267ms
Traverse took: Slice 3.329699ms vs Map 162.200881ms
Traverse took: Slice 3.308326ms vs Map 161.865634ms
Traverse took: Slice 3.592239ms vs Map 161.368631ms
Traverse took: Slice 3.291005ms vs Map 161.43135ms
Traverse took: Slice 3.207752ms vs Map 165.233397ms
Traverse took: Slice 3.279761ms vs Map 163.929496ms
Traverse took: Slice 3.598245ms vs Map 161.463547ms
Traverse took: Slice 3.237017ms vs Map 162.073138ms
Traverse took: Slice 3.624087ms vs Map 163.609476ms
Traverse took: Slice 3.330815ms vs Map 161.466201ms
Traverse took: Slice 3.620874ms vs Map 165.903472ms
Traverse took: Slice 3.251544ms vs Map 162.062521ms
Traverse took: Slice 3.634074ms vs Map 161.36451ms
Traverse took: Slice 3.46212ms vs Map 161.80089ms
Traverse took: Slice 3.545024ms vs Map 165.703232ms
Traverse took: Slice 3.314542ms vs Map 161.178868ms
Traverse took: Slice 3.303856ms vs Map 166.105528ms
Traverse took: Slice 3.307349ms vs Map 167.21275ms
Traverse took: Slice 3.396468ms vs Map 162.220927ms
Traverse took: Slice 3.485099ms vs Map 162.34378ms
Traverse took: Slice 3.265792ms vs Map 163.270179ms
Traverse took: Slice 3.25315ms vs Map 161.628937ms
Traverse took: Slice 3.237017ms vs Map 166.356824ms
Traverse took: Slice 3.317057ms vs Map 163.765646ms
Traverse took: Slice 3.656005ms vs Map 161.150582ms
Traverse took: Slice 3.341432ms vs Map 163.206971ms
Traverse took: Slice 3.387319ms vs Map 162.847489ms
Traverse took: Slice 3.637147ms vs Map 161.973823ms
Traverse took: Slice 3.36015ms vs Map 165.852626ms
Traverse took: Slice 3.313565ms vs Map 161.213162ms
Traverse took: Slice 3.270262ms vs Map 162.172526ms
Traverse took: Slice 3.603134ms vs Map 162.258713ms
Traverse took: Slice 3.239391ms vs Map 163.893948ms
Traverse took: Slice 4.18325ms vs Map 174.838636ms
Traverse took: Slice 4.007455ms vs Map 171.2362ms
Traverse took: Slice 3.558644ms vs Map 161.659389ms
Traverse took: Slice 3.295894ms vs Map 163.661581ms
Traverse took: Slice 3.815108ms vs Map 163.023633ms
Traverse took: Slice 3.265163ms vs Map 163.191257ms
Traverse took: Slice 3.588257ms vs Map 162.066644ms
Traverse took: Slice 3.616893ms vs Map 165.284384ms
Traverse took: Slice 3.30665ms vs Map 161.753817ms
Traverse took: Slice 3.625833ms vs Map 164.694071ms
Traverse took: Slice 3.668367ms vs Map 161.879605ms
Traverse took: Slice 3.345552ms vs Map 162.617427ms
Traverse took: Slice 3.27585ms vs Map 161.575647ms
Traverse took: Slice 3.580016ms vs Map 164.582532ms
Traverse took: Slice 3.599502ms vs Map 169.276125ms
Traverse took: Slice 3.508567ms vs Map 162.397701ms
Traverse took: Slice 3.309584ms vs Map 161.762199ms
Traverse took: Slice 3.484121ms vs Map 162.839319ms
Traverse took: Slice 3.295894ms vs Map 165.618793ms
Traverse took: Slice 3.589654ms vs Map 164.456116ms
Traverse took: Slice 3.595661ms vs Map 164.332424ms
Traverse took: Slice 3.310142ms vs Map 166.463196ms
Traverse took: Slice 3.903249ms vs Map 177.434494ms
Traverse took: Slice 3.393605ms vs Map 162.994581ms
Traverse took: Slice 3.635402ms vs Map 162.937728ms
Traverse took: Slice 3.32914ms vs Map 164.80135ms
Traverse took: Slice 3.31531ms vs Map 164.556551ms
Traverse took: Slice 3.636379ms vs Map 166.118381ms
Traverse took: Slice 3.61382ms vs Map 162.618965ms
Traverse took: Slice 3.289329ms vs Map 162.423055ms
Traverse took: Slice 3.586022ms vs Map 161.306614ms
Traverse took: Slice 3.238623ms vs Map 163.557376ms
Traverse took: Slice 3.287863ms vs Map 163.845689ms
Traverse took: Slice 3.563114ms vs Map 162.258784ms
Traverse took: Slice 3.291424ms vs Map 161.192629ms
Traverse took: Slice 3.569888ms vs Map 162.657518ms
Traverse took: Slice 3.205028ms vs Map 165.630319ms
Traverse took: Slice 3.230032ms vs Map 163.212701ms
Traverse took: Slice 3.59601ms vs Map 163.55123ms
Traverse took: Slice 3.266141ms vs Map 162.334703ms
Traverse took: Slice 3.589585ms vs Map 161.17901ms
Traverse took: Slice 3.303717ms vs Map 161.902446ms
Traverse took: Slice 3.270332ms vs Map 161.133263ms
Traverse took: Slice 3.58735ms vs Map 163.672758ms
Traverse took: Slice 3.596848ms vs Map 168.640206ms
Traverse took: Slice 3.24428ms vs Map 164.186733ms
Traverse took: Slice 3.597546ms vs Map 161.797261ms
Traverse took: Slice 3.313844ms vs Map 161.892458ms
Traverse took: Slice 3.243233ms vs Map 160.518854ms
Traverse took: Slice 3.734648ms vs Map 163.65383ms
Traverse took: Slice 3.208031ms vs Map 163.855956ms
Traverse took: Slice 3.263557ms vs Map 161.951196ms
Traverse took: Slice 3.75162ms vs Map 161.82946ms
Traverse took: Slice 3.346251ms vs Map 161.879328ms
Traverse took: Slice 3.633725ms vs Map 161.386096ms
Traverse took: Slice 3.22221ms vs Map 168.177426ms
Traverse took: Slice 3.329419ms vs Map 168.808877ms
Traverse took: Slice 3.446546ms vs Map 163.822292ms
Traverse took: Slice 3.490687ms vs Map 165.288438ms
Traverse took: Slice 3.336822ms vs Map 164.225287ms
Traverse took: Slice 3.202724ms vs Map 165.987497ms
Traverse took: Slice 3.578899ms vs Map 178.235457ms
Traverse took: Slice 3.638684ms vs Map 164.991885ms
Traverse took: Slice 3.304554ms vs Map 164.738144ms
Traverse took: Slice 3.615007ms vs Map 164.727878ms
Traverse took: Slice 3.567793ms vs Map 163.317257ms
Traverse took: Slice 3.35128ms vs Map 170.705118ms
Traverse took: Slice 4.162786ms vs Map 168.435846ms
Traverse took: Slice 3.665574ms vs Map 164.337735ms
Traverse took: Slice 3.285348ms vs Map 163.33828ms
Traverse took: Slice 3.263836ms vs Map 161.686213ms
Traverse took: Slice 3.555641ms vs Map 162.433603ms
Traverse took: Slice 3.621852ms vs Map 169.638334ms
Traverse took: Slice 3.862392ms vs Map 167.079145ms
Traverse took: Slice 3.270332ms vs Map 165.54127ms
Traverse took: Slice 9.051382ms vs Map 164.074217ms
Traverse took: Slice 3.406456ms vs Map 162.632726ms
Traverse took: Slice 3.602854ms vs Map 162.15898ms
Traverse took: Slice 3.230731ms vs Map 164.534623ms
Traverse took: Slice 3.501373ms vs Map 163.738202ms
Traverse took: Slice 3.237296ms vs Map 168.516167ms
Traverse took: Slice 3.495157ms vs Map 168.519728ms
Traverse took: Slice 3.262439ms vs Map 164.66062ms
Traverse took: Slice 3.342829ms vs Map 166.50329ms
Traverse took: Slice 3.640011ms vs Map 165.298985ms
Traverse took: Slice 3.337102ms vs Map 162.259625ms
Traverse took: Slice 3.322016ms vs Map 164.137425ms
Traverse took: Slice 3.31992ms vs Map 163.517149ms
Traverse took: Slice 3.352118ms vs Map 163.257054ms
Traverse took: Slice 3.565838ms vs Map 162.022787ms
Traverse took: Slice 3.279202ms vs Map 164.839698ms
Traverse took: Slice 3.384526ms vs Map 163.848695ms
Traverse took: Slice 3.654748ms vs Map 162.998984ms
Traverse took: Slice 3.434323ms vs Map 164.000883ms
Traverse took: Slice 3.418749ms vs Map 162.775625ms
Traverse took: Slice 3.261042ms vs Map 162.807684ms
Traverse took: Slice 3.310771ms vs Map 163.977835ms
Traverse took: Slice 3.292612ms vs Map 164.167319ms
Traverse took: Slice 3.500884ms vs Map 163.006877ms
Traverse took: Slice 3.569819ms vs Map 169.602786ms
Traverse took: Slice 3.888792ms vs Map 174.014424ms
Traverse took: Slice 3.737442ms vs Map 178.263047ms
Traverse took: Slice 4.037837ms vs Map 171.16769ms
Traverse took: Slice 3.598594ms vs Map 161.460062ms
Traverse took: Slice 3.273475ms vs Map 163.635953ms
Traverse took: Slice 10.183399ms vs Map 161.778617ms
Traverse took: Slice 3.300924ms vs Map 175.660485ms
Traverse took: Slice 3.414976ms vs Map 166.513768ms
Traverse took: Slice 3.398424ms vs Map 167.520206ms
Traverse took: Slice 3.30637ms vs Map 167.7143ms
Traverse took: Slice 3.332143ms vs Map 167.15353ms