1 of 40

Inside the Map Implementation

Keith Randall

@GopherCon, 2016/07/12

2 of 40

Can’t cover it all in ½ hour!

3 of 40

What are maps?

Associative containers mapping keys to values.

  • Construct: m := map[key]value{}
  • Insert: m[k] = v
  • Lookup: v = m[k]
  • Delete: delete(m, k)
  • Iterate: for k, v := range m
  • Size: len(m)

Key type must have an == operation (no maps, slices, or funcs as keys).

Operations run in constant expected time.

4 of 40

Use Go

maps

5 of 40

Use Go

maps

Stock Trading

6 of 40

High-frequency trading bot

var nasdaq chan struct {

symbol string

price float64

}

m := map[string]float64{}

for x := range nasdaq {

last := m[x.symbol]

if x.price > last {

fmt.Printf(“buy %s!\n”, x.symbol)

}

if x.price < last {

fmt.Printf(“sell %s!\n”, x.symbol)

}

m[x.symbol] = x.price

}

NASDAQ stock prices

MSFT 50.81�AAPL 94.56�GOOG 706.63�CSCO 26.72�ORCL 39.47�INTC 29.99�VOD 34.13�QCOM 52.79�AMZN 697.45�AMGN 150.83�…

​

7 of 40

High-frequency trading bot

var nasdaq chan struct {

symbol string

price float64

}

m := map[string]float64{}

for x := range nasdaq {

last := m[x.symbol]

if x.price > last {

fmt.Printf(“buy %s!\n”, x.symbol)

}

if x.price < last {

fmt.Printf(“sell %s!\n”, x.symbol)

}

m[x.symbol] = x.price

}

NASDAQ stock prices

MSFT 50.81�AAPL 94.56�GOOG 706.63�CSCO 26.72�ORCL 39.47�INTC 29.99�VOD 34.13�QCOM 52.79�AMZN 697.45�AMGN 150.83�…

​

8 of 40

High-frequency trading bot

var nasdaq chan struct {

symbol string

price float64

}

m := map[string]float64{}

for x := range nasdaq {

last := m[x.symbol]

if x.price > last {

fmt.Printf(“buy %s!\n”, x.symbol)

}

if x.price < last {

fmt.Printf(“sell %s!\n”, x.symbol)

}

m[x.symbol] = x.price

}

NASDAQ stock prices

MSFT 50.81�AAPL 94.56�GOOG 706.63�CSCO 26.72�ORCL 39.47�INTC 29.99�VOD 34.13�QCOM 52.79�AMZN 697.45�AMGN 150.83�…

​

9 of 40

High-frequency trading bot

var nasdaq chan struct {

symbol string

price float64

}

m := map[string]float64{}

for x := range nasdaq {

last := m[x.symbol]

if x.price > last {

fmt.Printf(“buy %s!\n”, x.symbol)

}

if x.price < last {

fmt.Printf(“sell %s!\n”, x.symbol)

}

m[x.symbol] = x.price

}

NASDAQ stock prices

MSFT 50.81�AAPL 94.56�GOOG 706.63�CSCO 26.72�ORCL 39.47�INTC 29.99�VOD 34.13�QCOM 52.79�AMZN 697.45�AMGN 150.83�…

​

10 of 40

High-frequency trading bot

var nasdaq chan struct {

symbol string

price float64

}

m := map[string]float64{}

for x := range nasdaq {

last := m[x.symbol]

if x.price > last {

fmt.Printf(“buy %s!\n”, x.symbol)

}

if x.price < last {

fmt.Printf(“sell %s!\n”, x.symbol)

}

m[x.symbol] = x.price

}

NASDAQ stock prices

MSFT 50.81�AAPL 94.56�GOOG 706.63�CSCO 26.72�ORCL 39.47�INTC 29.99�VOD 34.13�QCOM 52.79�AMZN 697.45�AMGN 150.83�…

​

11 of 40

Simple implementation

type entry struct {

k string

v float64�}

type map []entry

func lookup(m map, k string) float64 {

for _, e := range m {

if e.k == k {

return e.v

}

}

return 0

}

12 of 40

Simple implementation

type entry struct {

k string

v float64�}

type map []entry

func lookup(m map, k string) float64 {

for _, e := range m {

if e.k == k {

return e.v

}

}

return 0

}

Speed Fail!

13 of 40

Idea

14 of 40

Idea: split data up into buckets!

​

AAPL 94.56�CSCO 26.72�AMZN 697.45�AMGN 150.83�

MSFT 50.81�GOOG 706.63�INTC 29.99�

ORCL 39.47�QCOM 52.79�

VOD 34.13�

bucket = (symbol[0]-’A’)*4/(‘Z’-’A’)

A-F

G-M

N-S

T-Z

15 of 40

Idea: split data up into buckets!

​

AAPL 94.56�CSCO 26.72�AMZN 697.45�AMGN 150.83�

MSFT 50.81�GOOG 706.63�INTC 29.99�

ORCL 39.47�QCOM 52.79�

VOD 34.13�

bucket = (symbol[0]-’A’)*4/(‘Z’-’A’)

A-F

G-M

N-S

T-Z

Speed Fixed!

16 of 40

URLDAQ

​

http://google.com�http://intel.com

http://cisco.com

http://apple.com

http://amazon.com

http://amgen.com

http://microsoft.com

http://oracle.com

http://qualcomm.com

http://vodafone.com

​

A-F

G-M

N-S

T-Z

17 of 40

URLDAQ

​

http://google.com�http://intel.com

http://cisco.com

http://apple.com

http://amazon.com

http://amgen.com

http://microsoft.com

http://oracle.com

http://qualcomm.com

http://vodafone.com

​

A-F

G-M

N-S

T-Z

Bucketing by first letter isn’t very good.

Is there a way to reliably split the data into buckets?

Speed Fail!

18 of 40

Hash function

Choose a bucket for each key so that entries are distributed as evenly as possible.

​

bucket = h(key)

​

Required for correctness:

  • Deterministic: k1 == k2 → h(k1) == h(k2)

Want for performance:

  • Uniform: Probability[h(k) == b] ~= 1/#buckets
  • Fast: h(k) can be computed quickly
  • Adversary safe: hard for attacker to find lots of k with h(k) == b

Good news: Such hash functions exist.

Bad news: Hard to get right.

Go gets it right for you. → no user-defined hash functions.

19 of 40

Map bucket in Go

ei = 8-bit slots for extra hash bits

e0 e1 e2 e3 e4 e5 e6 e7

MSFT 50.81�CSCO 26.72�ORCL 39.47�INTC 29.99�QCOM 52.79�AMZN 697.45�--- ---

--- ---

overflow

overflow points to another bucket if we need more than 8 slots.

8 slots for data

20 of 40

Map in Go

m

len

lg(#buckets)

bucket array

hash seed

...

bucket 0

​

​

​

​

bucket 1

​

​

​

​

bucket 2

​

​

​

​

bucket 3

map header

bucket 2

overflow

bucket array

var m map[string]float64

21 of 40

Lookup

v = m[k]

v = runtime.lookup(m, k)

​

compiles to

22 of 40

Lookup

v = m[k]

v = runtime.lookup(m, k)

​

compiles to

where the runtime has the function

func<K,V> lookup(m map[K]V, k K) V

23 of 40

Lookup

v = m[k]

v = runtime.lookup(m, k)

​

compiles to

where the runtime has the function

func<K,V> lookup(m map[K]V, k K) V

Generics Fail!

24 of 40

Faking generics

  • All operations are done using unsafe.Pointers pointing to values of generic type.
  • Type information for each value is handled by a type descriptor.
  • Type descriptors provide operations like ==, hash, copy.

type _type struct {

size uintptr

equal func(unsafe.Pointer, unsafe.Pointer) bool

hash func(unsafe.Pointer, uintptr) uintptr

...

}

type mapType struct {

key *_type

value *_type

...

}

25 of 40

Lookup

v = m[k]

compiles to

where the runtime has the function

func lookup(t *mapType,

m *mapHeader,

k unsafe.Pointer) unsafe.Pointer

pk := unsafe.Pointer(&k)

pv := runtime.lookup(typeOf(m), m, pk)

v = *(*V)pv

26 of 40

Lookup implementation, page 1 of 2

// lookup looks up a key in a map and returns a pointer to the associated value.�// t = type of the map�// m = map�// key = pointer to key�func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {� if m == nil || m.count == 0 {� return zero� }� � hash := t.key.hash(key, m.seed) // hash := hashfn(key)� bucket := hash & (1<<m.logB-1) // bucket := hash % nbuckets� extra := byte(hash >> 56) // extra := top 8 bits of hash� b := (*bucket)(add(m.buckets, bucket*t.bucketsize)) // b := &m.buckets[bucket]�

27 of 40

Lookup implementation, page 2 of 2

for {� for i := 0; i < 8; i++ {� if b.extra[i] != extra { // check 8 extra hash bits� continue� }� k := add(b, dataOffset+i*t.key.size) // pointer to ki in bucket� if t.key.equal(key, k) {� // return pointer to vi� return add(b, dataOffset+8*t.key.size+i*t.value.size)� }� }� b = b.overflow� if b == nil {� return zero� }� }�}�

​

28 of 40

Growing the map

When buckets get too full, we need to grow the map.

“too full” = average of 6.5 entries per bucket

  • Allocate a new array of buckets of twice the size
  • Copy entries over from the old buckets to the new buckets
  • Use the new buckets

The process of copying is done incrementally, a little bit during each insert or delete. During copying, operations on the map are a bit more expensive.

29 of 40

Maps in other languages

​

c++

Java

Python

Go

&m[k] allowed

yes

no

no

no

Modify during iteration

no

no

no

yes

Provide your own ==, hash

yes

yes

yes

no

Adversary safe

no

yes*

no+

yes

30 of 40

Speed

31 of 40

Space

map[int64]int64

16 bytes/entry

32 of 40

Conclusions

Use maps!

  • A versatile data structure for the 21st century
  • 2x space overhead compared to the raw data
  • Access times on the order of ~100 cycles

​

33 of 40

Conclusions

Use maps!

  • A versatile data structure for the 21st century
  • 2x space overhead compared to the raw data
  • Access times on the order of ~100 cycles

​

34 of 40

Conclusions

Use maps!

  • A versatile data structure for the 21st century
  • 2x space overhead compared to the raw data
  • Access times on the order of ~100 cycles

​

35 of 40

Conclusions

Use maps!

  • A versatile data structure for the 21st century
  • 2x space overhead compared to the raw data
  • Access times on the order of ~100 cycles

​

36 of 40

Conclusions

Use maps!

  • A versatile data structure for the 21st century
  • 2x space overhead compared to the raw data
  • Access times on the order of ~100 cycles

​

37 of 40

Properties

  • Lookups typically do
    • 1 key hash
    • touch 1-3 consecutive cache lines
    • 1 key ==
  • Keeping 8 items in a bucket
    • Reduces space overhead of overflow pointer
    • Can pack data without padding (e.g. map[int8]int64)
    • Touching a cache line anyway, might as well use all of it

38 of 40

Iterators

Unlike most languages, Go provides definite semantics of iterators in the presence of inserts and deletes.

39 of 40

Still to do

  • m[k] += …
    • Currently requires 2 map operations, could do it with 1.
  • Map shrinking
    • Has tricky interactions with iteration
  • Do incremental grow work during reads
    • Currently a built but then static map has a chance of being forever in a growing state
    • Requires tricky synchronization
  • Hash function implementation improvements
  • Smaller overflow buckets

​

40 of 40

Insider tips

  • Preallocate buckets if size known: make(map[int]int, 1000)
  • There are special fast paths for int32, int64, and string keys.
  • Clear a map: for k := range m { delete(m, k) }
  • No allocation for var b []byte; v := m[string(b)]
  • No pointers in key and value -> faster GC scanning