go_benchmark_map_vs_slice_random_memory_access.go

package main

import (
	"fmt"
	"time"
)

type s struct {
	s []*s
}

type m struct {
	m map[int]*m
}

const (
	testLevel = 1000000
	testTimes = 300
)

func buildS() *s {
	root := &s{}
	cur := root

	for i := 0; i < testLevel; i++ {
		cur.s = make([]*s, 1)

		cur.s[0] = &s{}

		cur = cur.s[0]
	}

	return root
}

func traverseS(t *s) int {
	levels := 0

	for {
		if t.s == nil {
			return levels
		}

		t = t.s[0]

		levels++
	}
}

func buildM() *m {
	root := &m{}
	cur := root

	for i := 0; i < testLevel; i++ {
		cur.m = make(map[int]*m, 1)

		cur.m[0] = &m{}

		cur = cur.m[0]
	}

	return root
}

func traverseM(t *m) int {
	levels := 0

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

		if !found {
			return levels
		}

		t = current
		levels++
	}
}

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

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

	fmt.Println("Traversing", sss, mmm)

	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)
	}
}

Building
Traversing &{[0xc00000a080]} &{map[0:0xc002695228]}
Traverse took: Slice 11.611514ms vs Map 71.026909ms
Traverse took: Slice 11.779278ms vs Map 81.304766ms
Traverse took: Slice 10.08076ms vs Map 80.382277ms
Traverse took: Slice 29.699107ms vs Map 84.432906ms
Traverse took: Slice 12.378533ms vs Map 78.549239ms
Traverse took: Slice 11.269701ms vs Map 75.566652ms
Traverse took: Slice 12.97716ms vs Map 76.422582ms
Traverse took: Slice 11.828796ms vs Map 74.299485ms
Traverse took: Slice 13.009427ms vs Map 99.980928ms
Traverse took: Slice 16.847106ms vs Map 66.568603ms
Traverse took: Slice 11.936984ms vs Map 56.68138ms
Traverse took: Slice 11.271657ms vs Map 53.75809ms
Traverse took: Slice 10.769693ms vs Map 58.242308ms
Traverse took: Slice 15.008761ms vs Map 56.861156ms
Traverse took: Slice 12.385727ms vs Map 66.41397ms
Traverse took: Slice 13.051474ms vs Map 58.50387ms
Traverse took: Slice 12.246181ms vs Map 51.181502ms
Traverse took: Slice 11.182188ms vs Map 54.498638ms
Traverse took: Slice 11.259923ms vs Map 57.504483ms
Traverse took: Slice 13.190182ms vs Map 64.140013ms
Traverse took: Slice 12.082677ms vs Map 64.051312ms
Traverse took: Slice 15.908692ms vs Map 59.54684ms
Traverse took: Slice 12.016745ms vs Map 68.141334ms
Traverse took: Slice 10.946258ms vs Map 60.030715ms
Traverse took: Slice 11.288279ms vs Map 60.315326ms
Traverse took: Slice 16.032524ms vs Map 60.162369ms
Traverse took: Slice 12.096785ms vs Map 63.861967ms
Traverse took: Slice 13.731467ms vs Map 70.499802ms
Traverse took: Slice 11.570237ms vs Map 51.497332ms
Traverse took: Slice 11.143215ms vs Map 53.051346ms
Traverse took: Slice 10.440242ms vs Map 59.294077ms
Traverse took: Slice 17.316452ms vs Map 54.430681ms
Traverse took: Slice 13.179147ms vs Map 66.972926ms
Traverse took: Slice 13.486876ms vs Map 62.795111ms
Traverse took: Slice 10.759636ms vs Map 55.115074ms
Traverse took: Slice 11.743867ms vs Map 59.496413ms
Traverse took: Slice 13.982693ms vs Map 65.886933ms
Traverse took: Slice 15.83403ms vs Map 62.522373ms
Traverse took: Slice 13.923466ms vs Map 60.486092ms
Traverse took: Slice 14.303204ms vs Map 55.169692ms
Traverse took: Slice 9.609387ms vs Map 63.131686ms
Traverse took: Slice 13.656665ms vs Map 54.184762ms
Traverse took: Slice 11.069531ms vs Map 56.546792ms
Traverse took: Slice 12.832724ms vs Map 60.873513ms
Traverse took: Slice 13.197725ms vs Map 54.011551ms
Traverse took: Slice 10.036618ms vs Map 56.33817ms
Traverse took: Slice 12.469818ms vs Map 55.862538ms
Traverse took: Slice 11.207052ms vs Map 55.821819ms
Traverse took: Slice 10.571687ms vs Map 70.296907ms
Traverse took: Slice 17.497975ms vs Map 67.13594ms
Traverse took: Slice 12.428611ms vs Map 66.795734ms
Traverse took: Slice 13.799565ms vs Map 62.620503ms
Traverse took: Slice 11.006322ms vs Map 55.650213ms
Traverse took: Slice 10.94514ms vs Map 54.211931ms
Traverse took: Slice 11.083709ms vs Map 56.314703ms
Traverse took: Slice 10.963438ms vs Map 55.003604ms
Traverse took: Slice 13.31108ms vs Map 62.862859ms
Traverse took: Slice 12.914999ms vs Map 57.117342ms
Traverse took: Slice 12.582406ms vs Map 53.243414ms
Traverse took: Slice 9.878214ms vs Map 56.741655ms
Traverse took: Slice 12.569765ms vs Map 57.201294ms
Traverse took: Slice 13.210018ms vs Map 60.974646ms
Traverse took: Slice 13.780497ms vs Map 65.663504ms
Traverse took: Slice 12.143301ms vs Map 70.805227ms
Traverse took: Slice 10.498003ms vs Map 54.093756ms
Traverse took: Slice 14.729388ms vs Map 62.510221ms
Traverse took: Slice 10.463011ms vs Map 67.836328ms
Traverse took: Slice 12.175359ms vs Map 57.393362ms
Traverse took: Slice 15.388639ms vs Map 66.852376ms
Traverse took: Slice 14.128666ms vs Map 69.498947ms
Traverse took: Slice 16.365536ms vs Map 62.194739ms
Traverse took: Slice 11.263695ms vs Map 52.672935ms
Traverse took: Slice 10.829758ms vs Map 55.034126ms
Traverse took: Slice 10.66409ms vs Map 58.108976ms
Traverse took: Slice 14.484238ms vs Map 63.478038ms
Traverse took: Slice 13.734401ms vs Map 58.202706ms
Traverse took: Slice 10.705507ms vs Map 55.554459ms
Traverse took: Slice 12.924917ms vs Map 60.213005ms
Traverse took: Slice 10.187829ms vs Map 60.512004ms
Traverse took: Slice 11.970788ms vs Map 63.959119ms
Traverse took: Slice 14.47453ms vs Map 63.549488ms
Traverse took: Slice 16.842077ms vs Map 100.524029ms
Traverse took: Slice 14.552894ms vs Map 86.108028ms
Traverse took: Slice 10.799935ms vs Map 56.266511ms
Traverse took: Slice 9.647452ms vs Map 61.24026ms
Traverse took: Slice 13.638436ms vs Map 62.193411ms
Traverse took: Slice 11.310071ms vs Map 56.417582ms
Traverse took: Slice 10.103389ms vs Map 55.517791ms
Traverse took: Slice 10.941159ms vs Map 53.947505ms
Traverse took: Slice 12.440623ms vs Map 51.533651ms
Traverse took: Slice 10.118684ms vs Map 82.514451ms
Traverse took: Slice 16.486715ms vs Map 64.898301ms
Traverse took: Slice 14.497089ms vs Map 75.521394ms
Traverse took: Slice 16.187157ms vs Map 55.668443ms
Traverse took: Slice 11.937264ms vs Map 53.101842ms
Traverse took: Slice 10.197886ms vs Map 53.516361ms
Traverse took: Slice 10.672262ms vs Map 58.54396ms
Traverse took: Slice 13.532274ms vs Map 62.143961ms
Traverse took: Slice 13.69005ms vs Map 52.776023ms
Traverse took: Slice 10.558766ms vs Map 53.945339ms
Traverse took: Slice 11.279549ms vs Map 59.740655ms
Traverse took: Slice 12.146584ms vs Map 57.239078ms
Traverse took: Slice 14.351466ms vs Map 71.876553ms
Traverse took: Slice 16.241076ms vs Map 62.589143ms
Traverse took: Slice 13.802707ms vs Map 56.482606ms
Traverse took: Slice 12.769306ms vs Map 53.585367ms
Traverse took: Slice 10.326678ms vs Map 60.748982ms
Traverse took: Slice 11.742401ms vs Map 56.673348ms
Traverse took: Slice 13.93513ms vs Map 66.114343ms
Traverse took: Slice 14.425081ms vs Map 63.41944ms
Traverse took: Slice 13.794955ms vs Map 54.24322ms
Traverse took: Slice 10.31229ms vs Map 68.403735ms
Traverse took: Slice 10.884935ms vs Map 53.602549ms
Traverse took: Slice 10.176933ms vs Map 64.924423ms
Traverse took: Slice 15.234565ms vs Map 65.635567ms
Traverse took: Slice 12.574234ms vs Map 88.110923ms
Traverse took: Slice 27.257177ms vs Map 100.140659ms
Traverse took: Slice 13.607914ms vs Map 81.424198ms
Traverse took: Slice 20.081338ms vs Map 61.237117ms
Traverse took: Slice 13.9176ms vs Map 76.280729ms
Traverse took: Slice 13.264705ms vs Map 61.90859ms
Traverse took: Slice 10.893805ms vs Map 53.128871ms
Traverse took: Slice 12.17082ms vs Map 53.542204ms
Traverse took: Slice 10.812158ms vs Map 53.208283ms
Traverse took: Slice 10.470554ms vs Map 59.666971ms
Traverse took: Slice 17.297316ms vs Map 65.858087ms
Traverse took: Slice 14.010701ms vs Map 60.601613ms
Traverse took: Slice 13.139755ms vs Map 56.64101ms
Traverse took: Slice 11.386619ms vs Map 54.159828ms
Traverse took: Slice 11.355748ms vs Map 65.283627ms
Traverse took: Slice 10.985439ms vs Map 55.239256ms
Traverse took: Slice 13.577673ms vs Map 64.828947ms
Traverse took: Slice 14.738397ms vs Map 62.647601ms
Traverse took: Slice 10.885843ms vs Map 63.229256ms
Traverse took: Slice 12.023241ms vs Map 53.35684ms
Traverse took: Slice 12.782506ms vs Map 57.039117ms
Traverse took: Slice 12.352063ms vs Map 74.148484ms
Traverse took: Slice 15.08943ms vs Map 67.986771ms
Traverse took: Slice 15.281219ms vs Map 58.832064ms
Traverse took: Slice 10.179169ms vs Map 59.684081ms
Traverse took: Slice 9.984724ms vs Map 61.808504ms
Traverse took: Slice 9.712756ms vs Map 64.745764ms
Traverse took: Slice 19.973431ms vs Map 58.794069ms
Traverse took: Slice 13.747322ms vs Map 69.811846ms
Traverse took: Slice 16.458358ms vs Map 63.009599ms
Traverse took: Slice 10.220795ms vs Map 54.535445ms
Traverse took: Slice 10.474396ms vs Map 54.529857ms
Traverse took: Slice 10.280092ms vs Map 56.212242ms
Traverse took: Slice 9.934648ms vs Map 57.975715ms
Traverse took: Slice 13.179915ms vs Map 62.451901ms
Traverse took: Slice 11.552148ms vs Map 53.671903ms
Traverse took: Slice 10.658014ms vs Map 51.67222ms
Traverse took: Slice 12.09469ms vs Map 57.728959ms
Traverse took: Slice 10.813834ms vs Map 60.83433ms
Traverse took: Slice 12.586666ms vs Map 63.901568ms
Traverse took: Slice 12.461717ms vs Map 65.4428ms
Traverse took: Slice 13.779939ms vs Map 77.156145ms
Traverse took: Slice 10.192229ms vs Map 55.627236ms
Traverse took: Slice 12.321751ms vs Map 59.416163ms
Traverse took: Slice 12.587435ms vs Map 56.273216ms
Traverse took: Slice 14.362152ms vs Map 59.766916ms
Traverse took: Slice 12.305617ms vs Map 78.621596ms
Traverse took: Slice 14.146965ms vs Map 55.601393ms
Traverse took: Slice 9.66135ms vs Map 53.934723ms
Traverse took: Slice 10.572386ms vs Map 55.827685ms
Traverse took: Slice 10.493184ms vs Map 56.934212ms
Traverse took: Slice 13.950775ms vs Map 65.894685ms
Traverse took: Slice 16.544196ms vs Map 63.955417ms
Traverse took: Slice 13.794466ms vs Map 55.256786ms
Traverse took: Slice 10.075521ms vs Map 54.007919ms
Traverse took: Slice 11.806866ms vs Map 64.088538ms
Traverse took: Slice 10.445481ms vs Map 64.975409ms
Traverse took: Slice 10.849664ms vs Map 59.806727ms
Traverse took: Slice 12.164533ms vs Map 62.400566ms
Traverse took: Slice 12.496149ms vs Map 63.342193ms
Traverse took: Slice 11.616473ms vs Map 50.911557ms
Traverse took: Slice 13.30675ms vs Map 56.032814ms
Traverse took: Slice 11.054234ms vs Map 53.693065ms
Traverse took: Slice 11.169895ms vs Map 51.656994ms
Traverse took: Slice 12.498594ms vs Map 61.526129ms
Traverse took: Slice 12.528137ms vs Map 60.779085ms
Traverse took: Slice 11.563811ms vs Map 59.558434ms
Traverse took: Slice 10.805663ms vs Map 54.681138ms
Traverse took: Slice 10.649493ms vs Map 54.815447ms
Traverse took: Slice 12.258193ms vs Map 74.013477ms
Traverse took: Slice 17.948884ms vs Map 76.776198ms
Traverse took: Slice 15.064915ms vs Map 64.656504ms
Traverse took: Slice 11.002341ms vs Map 55.716076ms
Traverse took: Slice 9.753683ms vs Map 56.172851ms
Traverse took: Slice 12.405912ms vs Map 53.926062ms
Traverse took: Slice 9.896931ms vs Map 67.310409ms
Traverse took: Slice 12.570672ms vs Map 67.601795ms
Traverse took: Slice 14.996329ms vs Map 60.339351ms
Traverse took: Slice 11.170943ms vs Map 54.485158ms
Traverse took: Slice 9.824644ms vs Map 60.585619ms
Traverse took: Slice 9.763392ms vs Map 58.733026ms
Traverse took: Slice 13.60533ms vs Map 65.333704ms
Traverse took: Slice 13.421084ms vs Map 78.928907ms
Traverse took: Slice 15.284433ms vs Map 61.898393ms
Traverse took: Slice 12.226344ms vs Map 54.175263ms
Traverse took: Slice 12.563688ms vs Map 60.33097ms
Traverse took: Slice 11.374606ms vs Map 62.046251ms
Traverse took: Slice 14.662688ms vs Map 60.738995ms
Traverse took: Slice 15.57938ms vs Map 63.331926ms
Traverse took: Slice 14.166311ms vs Map 56.812894ms
Traverse took: Slice 10.685602ms vs Map 60.421767ms
Traverse took: Slice 10.690561ms vs Map 54.344214ms
Traverse took: Slice 10.263888ms vs Map 65.587654ms
Traverse took: Slice 12.931761ms vs Map 58.81614ms
Traverse took: Slice 12.557541ms vs Map 65.686622ms
Traverse took: Slice 13.491206ms vs Map 62.182725ms
Traverse took: Slice 10.498352ms vs Map 62.456161ms
Traverse took: Slice 12.31791ms vs Map 53.137741ms
Traverse took: Slice 10.888147ms vs Map 54.382558ms
Traverse took: Slice 13.381553ms vs Map 59.900107ms
Traverse took: Slice 13.53863ms vs Map 63.703143ms
Traverse took: Slice 10.505686ms vs Map 72.320267ms
Traverse took: Slice 12.419671ms vs Map 55.225915ms
Traverse took: Slice 11.750642ms vs Map 57.461599ms
Traverse took: Slice 12.848438ms vs Map 51.922957ms
Traverse took: Slice 10.309357ms vs Map 64.389702ms
Traverse took: Slice 13.525918ms vs Map 66.683914ms
Traverse took: Slice 14.940873ms vs Map 60.130589ms
Traverse took: Slice 11.145031ms vs Map 55.574922ms
Traverse took: Slice 11.789964ms vs Map 54.111985ms
Traverse took: Slice 11.360847ms vs Map 71.849802ms
Traverse took: Slice 18.068245ms vs Map 68.391583ms
Traverse took: Slice 16.545872ms vs Map 66.844274ms
Traverse took: Slice 11.420493ms vs Map 53.918309ms
Traverse took: Slice 12.600844ms vs Map 54.80483ms
Traverse took: Slice 11.973722ms vs Map 53.649203ms
Traverse took: Slice 10.986766ms vs Map 64.290315ms
Traverse took: Slice 12.07709ms vs Map 58.856019ms
Traverse took: Slice 12.466396ms vs Map 68.90053ms
Traverse took: Slice 13.362136ms vs Map 56.470034ms
Traverse took: Slice 10.689932ms vs Map 60.199176ms
Traverse took: Slice 12.026104ms vs Map 53.630206ms
Traverse took: Slice 10.101083ms vs Map 55.864981ms
Traverse took: Slice 12.254841ms vs Map 61.513975ms
Traverse took: Slice 12.361212ms vs Map 60.126957ms
Traverse took: Slice 10.115402ms vs Map 58.555275ms
Traverse took: Slice 11.50207ms vs Map 56.419397ms
Traverse took: Slice 9.906011ms vs Map 53.823462ms
Traverse took: Slice 10.012871ms vs Map 63.052274ms
Traverse took: Slice 13.430373ms vs Map 55.524635ms
Traverse took: Slice 13.198004ms vs Map 66.628738ms
Traverse took: Slice 13.073963ms vs Map 56.576824ms
Traverse took: Slice 10.937736ms vs Map 56.978703ms
Traverse took: Slice 10.721013ms vs Map 53.041986ms
Traverse took: Slice 12.584152ms vs Map 59.21683ms
Traverse took: Slice 10.049609ms vs Map 53.475573ms
Traverse took: Slice 9.814168ms vs Map 61.863192ms
Traverse took: Slice 13.177959ms vs Map 61.466412ms
Traverse took: Slice 13.276299ms vs Map 59.870843ms
Traverse took: Slice 10.90917ms vs Map 56.953978ms
Traverse took: Slice 10.115191ms vs Map 62.824305ms
Traverse took: Slice 12.913323ms vs Map 54.610735ms
Traverse took: Slice 13.356689ms vs Map 63.266762ms
Traverse took: Slice 13.306122ms vs Map 61.959575ms
Traverse took: Slice 10.932498ms vs Map 52.472973ms
Traverse took: Slice 11.837387ms vs Map 57.876118ms
Traverse took: Slice 11.922038ms vs Map 56.130385ms
Traverse took: Slice 12.635068ms vs Map 56.562995ms
Traverse took: Slice 9.521874ms vs Map 62.19781ms
Traverse took: Slice 14.400287ms vs Map 62.985363ms
Traverse took: Slice 11.440259ms vs Map 53.918868ms
Traverse took: Slice 12.893767ms vs Map 59.685338ms
Traverse took: Slice 10.599206ms vs Map 62.909234ms
Traverse took: Slice 12.708962ms vs Map 64.496283ms
Traverse took: Slice 9.929478ms vs Map 69.604271ms
Traverse took: Slice 13.347888ms vs Map 63.335697ms
Traverse took: Slice 9.845876ms vs Map 55.857788ms
Traverse took: Slice 12.524436ms vs Map 56.087083ms
Traverse took: Slice 10.131256ms vs Map 54.357764ms
Traverse took: Slice 11.1678ms vs Map 66.465304ms
Traverse took: Slice 10.442058ms vs Map 64.467438ms
Traverse took: Slice 14.537249ms vs Map 69.282852ms
Traverse took: Slice 12.254352ms vs Map 58.68225ms
Traverse took: Slice 14.034587ms vs Map 56.521299ms
Traverse took: Slice 9.686284ms vs Map 59.931326ms
Traverse took: Slice 12.549788ms vs Map 52.778188ms
Traverse took: Slice 19.55039ms vs Map 78.468919ms
Traverse took: Slice 13.876811ms vs Map 62.623296ms
Traverse took: Slice 10.142571ms vs Map 53.526ms
Traverse took: Slice 11.324319ms vs Map 58.026072ms
Traverse took: Slice 12.314277ms vs Map 52.76422ms
Traverse took: Slice 10.060644ms vs Map 54.365446ms
Traverse took: Slice 12.067172ms vs Map 66.137321ms
Traverse took: Slice 14.499813ms vs Map 67.564219ms
Traverse took: Slice 14.007418ms vs Map 54.890248ms
Traverse took: Slice 11.189871ms vs Map 57.671268ms
Traverse took: Slice 11.402404ms vs Map 57.091569ms
Traverse took: Slice 11.692393ms vs Map 52.987298ms
Traverse took: Slice 10.876065ms vs Map 59.801279ms
Traverse took: Slice 13.737543ms vs Map 64.333548ms
Traverse took: Slice 13.353964ms vs Map 56.487285ms
Traverse took: Slice 11.068553ms vs Map 54.977133ms
Traverse took: Slice 12.126748ms vs Map 59.727454ms
Traverse took: Slice 10.613314ms vs Map 62.457348ms
Traverse took: Slice 13.295995ms vs Map 65.646742ms