Базовые знания
Концепция карты
Интуитивно понятное значение карты — отображение, представляющее собой абстрактную структуру, состоящую из пар , причем ключ не будет повторяться, и все операции также являются ключом/значением. Обычно существуют две основные реализации map:
- Дерево поиска, естественно упорядоченное, средняя/наихудшая сложность записи/поиска составляет O(logN)
- Хеш-таблица, неупорядоченное хранилище, средняя сложность записи/поиска — O(1), наихудшая — O(N)
В языке go базовой реализацией map является хеш-таблица. В этой статье также в основном будет рассказано, как улучшить/оптимизировать хеш-таблицу в ходу.
Для простейшей хеш-таблицы она состоит из массива + хеш-функции + разрешения коллизий хэшей. Проще говоря, хеш-функция преобразует ключи (различных типов) в индексы массива, чтобы достичь эффективности поиска O (1) с помощью массива [хэш [ключ]]. Существует множество реализаций хэш-функции, цель которых состоит в том, чтобы результат хеширования был как можно более равномерно распределен между 0~length(массивом). Совершенная хеш-функция сопоставляет ключи с индексами один к одному, а плохая хэш-функция сопоставляет все ключи с индексом.
Когда разные ключи сопоставляются с одним и тем же индексом, возникает так называемый конфликт хэшей. Есть также два распространенных решения хеш-конфликтов, а именно:
- Открытая адресация. Также называется повторным хэшированием, что означает, что в случае конфликта хэшей хешируйте его снова, пока конфликт не исчезнет, и поместите его в соответствующее хранилище.
Открытый метод адресации, который оказывает наибольшее влияние на производительность, этокоэффициент загрузки, который является отношением количества элементов в массиве к размеру массива. По мере увеличения коэффициента загрузки среднее время линейного обнаружения будет постепенно увеличиваться, что повлияет на производительность чтения и записи хеш-таблицы. Когда скорость загрузки превышает 70%, производительность хеш-таблицы резко падает, а когда скорость загрузки достигает 100%, вся хэш-таблица полностью выходит из строя, в это время временная сложность поиска и вставки любого элемента составляет 𝑂 ( 𝑛), то вам нужно обойти все элементы в массиве, поэтому вы должны обратить внимание на изменение коэффициента загрузки при реализации хеш-таблицы.
- Метод цепного адреса. Это означает, что ключи с одинаковым хеш-адресом связаны вместе в виде связанного списка. Также необходимо пройти по этой цепочке, чтобы найти настоящий ключ при поиске вверх. И это также решение для разрешения конфликтов для карты на языке го.
Основные операции карты go
Есть следующие операции на карте в языке го
1. Заявление
var m map[T]T
Обратите внимание, что карта в это время равна нулю, и читать/удалять карту nil безопасно, но это вызовет панику при записи в карту nil.
package main
func main() {
var a map[int64]bool
delete(a, 10)
_ = a
a[10] = false
}
go run main.go
panic: assignment to entry in nil map//具体原因详见源码解析部分
2. Инициализация
var m = make(map[T]T,len)
var m = map[T]T{..}
3. Добавить/обновить, просто назначив значение напрямую
m[key]=value
4. Запрос
Карта golang имеет две операции получения, с запятой и без нее, как показано ниже.
v := m[key]
v, ok := m[key]
Для первого метода заданное значение ключа получит нулевое значение, для второго метода неустановленное значение ket будет ok=false.
5. удалить
delete(m,key)
Один и тот же ключ можно удалить несколько раз без ошибки
Сравнение с другой картой/хеш-таблицей
1. Нижний слой карты Java представляет собой хеш-таблицу + связанный список (метод застежки-молнии).
Его характеристика заключается в том, что когда длина связанного списка превышает пороговое значение (8), он будет преобразован в красно-черное дерево, избегая обхода O(n).
2. Карта C++ — это реализация красно-черного дерева.
Его unordered_map реализуется с помощью хеш-таблицы.
3. Массив в php5 также является базовой хеш-таблицей
В версии 7 он оптимизирован как хеш-таблица, непрерывная в памяти.
4. Хэш redis — это обычная хеш-таблица, для которой характерно использование высокого порядка итераций при обходе, чтобы избежать дублирования элементов при сканировании. Однако при уменьшении масштаба все еще могут быть повторяющиеся элементы.
Углубитесь в исходный код
На основе golang 1.15.3 исходный код, связанный с картой, находится в runtime/map{xxx}.go.
Онлайн доступ: golang/go at go1.15.3 (github.com)
модель памяти
runtime.hmap — это информация заголовка карты, структура данных следующая
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin) map中kv的个数
flags uint8 //标记位
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) bucket的个数为2^B个
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details 现在正在使用的溢出桶的个数
hash0 uint32 // hash seed hash种子，随机数，在make map时进行设置，会参与到key 的hash值计算中来，这样做可以使hash结果更离散一些
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.指向当前正在使用的bucket数组
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing golang map的扩容方式是渐进式扩容，oldbuckets指向的是老的bucket数组
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) 同上，在渐进式扩容中会用到，标识扩容进度
extra *mapextra // optional fields 可选字段
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// If both key and elem do not contain pointers and are inline, then we mark bucket
// type as containing no pointers. This avoids scanning such maps.
// However, bmap.overflow is a pointer. In order to keep overflow buckets
// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
// overflow and oldoverflow are only used if key and elem do not contain pointers.
// 翻译一下，当k/v都不是指针的情况下，在gc时可以避免扫描整个map，但是bmap的最后一个字段是uintptr类型，为了保证gc效率同时对溢出桶进行保活，所以将overflow写入到下边这俩个数组里。
// overflow contains overflow buckets for hmap.buckets.
// oldoverflow contains overflow buckets for hmap.oldbuckets.
// The indirection allows to store a pointer to the slice in hiter.
overflow *[]*bmap //当前桶所用到的溢出桶，map在初始化时会分配一定的溢出桶，在地址上与常规桶连续
oldoverflow *[]*bmap //老桶所用到的溢出桶
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap //下一个可用的溢出桶
}
- hmap.count Количество kvs в текущей карте будет увеличиваться при вставке и уменьшаться при удалении.
- hmap.B = log2 (количество сегментов). Тип hmap.B — uint8, максимальное значение — 255, но максимальный предел ведра в golang — pow(2,64) — 1. Конкретный исходный код выглядит следующим образом, а 64-битная обработка против переполнения будет выполняться на b, когда он используется.
// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
// Masking the shift amount allows overflow checks to be elided.
return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}
//在写入/读取等操作时都会用bucketMask获取bucket的数量
// bucketMask returns 1<<b - 1, optimized for code generation.
func bucketMask(b uint8) uintptr {
return bucketShift(b) - 1
}
Расположение ключа на карте сначала будет использовать хеш-функцию для получения хэш-значения, записи индекса позиции = хэш%N и получения реальной позиции записи. Тем не менее, есть небольшая оптимизация позиционирования индекса в golang.Golang использует битовую операцию AND для позиционирования корзины:
index = hash & (N-1) Чтобы обеспечить достаточное хеширование ключа, необходимо убедиться, что N является целочисленной степенью числа 2, поэтому в приведенной выше структуре hmap hmap.B относится к этой целочисленной степени.
По сравнению с операцией побитового И, операция по модулю имеет более высокие накладные расходы ЦП, что можно легко проверить.Код перехода выглядит следующим образом.
package main
import "fmt"
func main() {
T(1000, 0b11)
}
func T(a, b int) (int, int) {
c := a & b
d := a % b
fmt.Println(c,d)
return c, d
}
Скомпилируйте приведенный выше код go в ассемблерный код plan9, используя команду go tool compile -S, как показано ниже.
См. рисунок ниже, main.go:10 — это битовая операция И, а main.go:11 — операция по модулю, вы можете видеть, что битовая операция И требует меньше инструкций по сборке.
- hmap.flags — это текущее состояние карты, а также это классическое бинарное хранилище битов.Значения перечисления соответствующих битов следующие:
// flags
iterator = 1 // there may be an iterator using buckets 有迭代器正在使用bucket
oldIterator = 2 // there may be an iterator using oldbuckets 有迭代器正在使用old bucket
hashWriting = 4 // a goroutine is writing to the map map正在被写入，并发读写导致的panic就是去check这个标记位
sameSizeGrow = 8 // the current map growth is to a new map of the same size 当前map正在进行等量扩容
- hmap.bucket и hmap.oldbucket на самом деле указывают на слайс сегмента []bmap, где хранится kv.
Структура данных bmap во время выполнения выглядит следующим образом.
// A bucket for a Go map.
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
const (
// Maximum number of key/elem pairs a bucket can hold.
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
)
//其中bucketCnt在源码中是常量8，也就是每个bucket中有8个kv
Но при компиляции компилятор добавит еще несколько полей в runtime.bmap, настоящий bmap такой
type bmap struct {
topbits [8]uint8
keys [8]keytype
elems [8]valuetype
// pad uintptr
overflow uintptr //每个bmap最多存储8个kv对，为了减少因bmap满了而导致的扩容操作，如果这时有第9个kv，则需要使用溢出桶，溢出桶通过overflow字段进行连接，所以常规桶和溢出桶间是单链表结构，溢出桶数据结构与常规桶一致。
}
заruntime.bmapИсходный код для добавления полей:cmd/compile/internal/gc/reflect.go, фрагмент ядра выглядит так
// bmap makes the map bucket type given the type of the map.
func bmap(t *types.Type) *types.Type {
//some init code...
field := make([]*types.Field, 0, 5)
// The first field is: uint8 topbits[BUCKETSIZE].
arr := types.NewArray(types.Types[TUINT8], BUCKETSIZE)
field = append(field, makefield("topbits", arr))
arr = types.NewArray(keytype, BUCKETSIZE)
arr.SetNoalg(true)
keys := makefield("keys", arr)
field = append(field, keys)
arr = types.NewArray(elemtype, BUCKETSIZE)
arr.SetNoalg(true)
elems := makefield("elems", arr)
field = append(field, elems)
// If keys and elems have no pointers, the map implementation
// can keep a list of overflow pointers on the side so that
// buckets can be marked as having no pointers.
// Arrange for the bucket to have no pointers by changing
// the type of the overflow field to uintptr in this case.
// See comment on hmap.overflow in runtime/map.go.
otyp := types.NewPtr(bucket)
if !elemtype.HasPointers() && !keytype.HasPointers() {
otyp = types.Types[TUINTPTR]
}
overflow := makefield("overflow", otyp)
field = append(field, overflow)
// link up fields
bucket.SetNoalg(true)
bucket.SetFields(field[:])
dowidth(bucket)
// some check code...
}
Давайте посмотрим на схему
схема памяти карты
схема памяти bmap
Что особенного в bmap так это хранение kv.bmap хранит 8 ключей вместе и 8 значений вместе, то есть ключ/ключ/....значение/значение... Такой вид хранения, по сравнению с ключ/значение В схеме хранения /key/value отдельное хранение ключа и значения может сделать макет памяти bmap более компактным, и потребуется только увеличить выравнивание заполнения в конце.
Вы можете рассчитать размер пространства, занимаемого каждым bmap в двух приведенных выше схемах хранения для карты этого типа map[int64]int8.
Если kv существует вместе, 7 байтов заполнения необходимо заполнить после каждой требуемой пары kv, а общее заполнение составляет 7 * 8 = 56 байтов.
Но если kv хранится отдельно, 8 ключей выравниваются, а 8 значений выравниваются, и никакого дополнительного заполнения не требуется.
bmap.tophash идентифицирует первые 8 бит хеш-значения каждого ключа, поэтому сначала можно сравнить tophash, что может уменьшить некоторые накладные расходы на сравнение. В то же время tophash также будет хранить бит метки соответствующего ключа. значения перечисления
const (
emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.//当前cell为空，且后续cell都为空，在遍历时会用到，加快map遍历速度
emptyOne = 1 // this cell is empty //当前cell为空
evacuatedX = 2 // key/elem is valid. Entry has been evacuated to first half of larger table.翻倍扩容时会用到，指示cell迁移到新bucket的前半部分
evacuatedY = 3 // same as above, but evacuated to second half of larger table. 翻倍扩容时会用到，指示cell迁移到新bucket的后半部分
evacuatedEmpty = 4 // cell is empty, bucket is evacuated.//扩容时会用到。表示当前cell为空，且bucket已经迁移完成
minTopHash = 5 // minimum tophash for a normal filled cell.正常的tophash的最小值
)
//👇为了不与正常的top hash冲突，在计算tophash时如果小于minTopHash也会加上对应的值
// tophash calculates the tophash value for hash.
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
return top
}
//判断某个bucket是否迁移完成，也是较简单的，只需要check tophash[0]的值即可
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > emptyOne && h < minTopHash
}
Относительная bmap-позиция bmap.keys — это константа dataOffset в исходном коде:
// data offset should be the size of the bmap struct, but needs to be
// aligned correctly. For amd64p32 this means 64-bit alignment
// even though pointers are 32 bit.
dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)
//获取v相对于struct的偏移量，也就是获取bmap的keys相对于bmap的偏移量
func (b *bmap) keys() unsafe.Pointer {
return add(unsafe.Pointer(b), dataOffset)
}
хэш
Прототип хэш-функции выглядит следующим образом: при инициализации она получает два параметра — наш ключ и начальное значение хеш-функции, а возвращаемое значение — соответствующее значение хеш-функции.
func(unsafe.Pointer, uintptr) uintptr
Для рассчитанного хеш-значения
- Первые 8 бит хранятся в соответствующей позиции bmap как tophash. При поиске вы можете сначала сравнить tophash. Если он непротиворечив, то сравнить ключ. Если он несовместим, пропустить его напрямую. Это имеет преимущество в сокращении некоторые накладные расходы на сравнение.
- Последние B битов хранятся в соответствующей корзине как индекс корзины.
Как использовать хэш-значение
Что касается реализации хеш-функции, то для каждого типа будет своя реализация хеш-функции.Например, хэш-функция строкового типа выглядит следующим образом, что является функцией O(N).Более подробная реализация находится в src/ runtime/alg.go Заинтересовано Вы можете проверить это сами~
// Testing adapters for hash quality tests (see hash_test.go)
func stringHash(s string, seed uintptr) uintptr {
return strhash(noescape(unsafe.Pointer(&s)), seed)
}
инициализация
Операция make на карте — это синтаксический сахар, предоставляемый go, который будет преобразован в runtime.makemap во время компиляции.
// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If h.buckets != nil, bucket pointed to can be used as the first bucket.
//hint就是我们make时的第二个参数，代表预分配的空间大小
//maptype 是golang类型系统涉及的数据结构，感觉可以再来一次类型系统的学习😸
func makemap(t *maptype, hint int, h *hmap) *hmap {
//防溢出检测，如果有溢出，则将hint清0
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()
//fashrand获取随机数 内部实现与调度器相关，感觉可以来一次调度器的学习😁
// Find the size parameter B which will hold the requested # of elements.
// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
B := uint8(0)
for overLoadFactor(hint, B) { //根据
B++
}
h.B = B
// allocate initial hash table
// if B == 0, the buckets field is allocated lazily later (in mapassign)
// If hint is large zeroing this memory could take a while.
if h.B != 0 {
var nextOverflow *bmap
// 调用makeBucketArray函数生成常规桶和溢出桶，在map初始化时常规桶和溢出桶在内存上是连续的一块空间，只不过常规桶用了前边，溢出桶则用了后边
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
// 如果初始化时生成了溢出桶,会放置到map的extra字段里去
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
// 根据传入的 B 计算出的需要创建的桶数量，并在内存中分配一片连续的空间用于常规桶和溢出桶
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
// For small b, overflow buckets are unlikely.Avoid the overhead of the calculation.
if b >= 4 { // bmap的数量大于了2^4，在初始化的时候才会生成溢出桶。溢出桶的大小为2^(b-4)，b为常规桶的大小
nbuckets += bucketShift(b - 4)
sz := t.bucket.size * nbuckets
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
}
if dirtyalloc == nil {
buckets = newarray(t.bucket, int(nbuckets))
} else {
...
}
// preallocated some overflow buckets.
if base != nbuckets {
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
читать
Есть две формы чтения, то есть возвращаемое значение имеет две формы, но в языке Go нет концепции перегрузки функций.Это динамическое возвращаемое значение, очевидно, является синтаксическим сахаром, предоставляемым go, и оно будет скомпилировано в соответствии с возвращаемое значение, используемое пользователем во время компиляции. Число преобразуется в соответствующую функцию среды выполнения. Позиция исходного кода все еще находится в runtime/map.go. Соответствующие функции
-
runtime.mapaccess1, соответствующий форме возвращаемого значения
-
runtime.mapaccess2, соответствующий форме двух возвращаемых значений
-
runtime.mapaccessk, соответствующий форме возврата kv при этом, будет использоваться при обходе карты
Логика этих трех функций в основном одинаковая.В качестве примера возьмем runtime.mapccess1 для анализа карты.
процесс чтения.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//这还有一些gc相关的代码块，我们暂时可以忽略
// mapaccess1 我们拆成两部分来看
//1. 参数校验，数据准备
//2. 数据查找
}
- Проверка параметров, подготовка данных
if h == nil || h.count == 0 { //这就是上文中提到的，对nil的map做读取操作是安全的，会返回0值
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
if h.flags&hashWriting != 0 { //并发读写标记位check，如果已设置写标记位，则打印错误信息，并退出进程
throw("concurrent map read and map write")
}
// 通过hash函数计算当前key的哈希值，不同类型的key会有不同的hash函数
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B) // 计算出当前桶的个数，即(1<<B)-1
//t.bucketsize为bmap的大小，通过对哈希值和buckets起始地址进行运算，获取哈希值对应的bmap地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
//当map的oldbuckets存在时，证明map正在处于扩容中，会先去check旧桶中的数据
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// 如果oldbuckets不为nil且未设置sameSize标记位，证明map的扩容为翻倍扩容(具体在扩容一章会介绍到)，老的bucket的数量为m>>1
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) { //判断旧桶是否已被迁移
b = oldb // 因为旧桶尚未迁移，所以需要在旧桶中查找数据
}
}
// 获取当前key的哈希的高8位，和bmap中的topbits作比较，可以减轻直接比较key带来的开销
top := tophash(hash)
Среди них несколько функций инструментов, использованных выше, следующие:
//因为unsafe.Pointer是不支持加法运算的，所以需要将unsafe.Pointer进行强转
func add(p unsafe.Pointer, x uintptr) unsafe.Pointer {
return unsafe.Pointer(uintptr(p) + x)
}
// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
// Masking the shift amount allows overflow checks to be elided.
return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}
// bucketMask returns 1<<b - 1, optimized for code generation.
func bucketMask(b uint8) uintptr {
return bucketShift(b) - 1
}
//判断入参bmap是否已完成迁移
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > emptyOne && h < minTopHash
}
// sameSizeGrow reports whether the current growth is to a map of the same size.
func (h *hmap) sameSizeGrow() bool {
return h.flags&sameSizeGrow != 0
}
// tophash calculates the tophash value for hash.
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
//上文中已提到，避免标记位与正常的hashvalue冲突，需要加上minTopHash
top += minTopHash
}
return top
}
- поиск данных
Он делится на два слоя кровообращения, а именно:
-
Первый слой пересекает все ведра, соответствующие хэш
-
Второй слой пересекает 8 ячеек ведра.
bucketloop:
// 遍历当前hash的常规桶及全部溢出桶
for ; b != nil; b = b.overflow(t) {
// 遍历每一个桶的8个cell
for i := uintptr(0); i < bucketCnt; i++ {
// 对比tophash
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
// emptyRest 标志位：表示当前cell及当前cell后续的cell及bucket都为空，可以退出整个大循环，查找失败
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
//上述运算定位到当前bucket的第i个key的地址
//如果key的类型是指针，则需要进行解引用再进行下边的equal对比
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
//对比key是否一致，因为tophash也会存在冲突的情况，所以需要再次对比两个key是否一致
if t.key.equal(key, k) {
//key是一致，则获取对应索引位置的值
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
//如果value是指针，则需要对value进行解引用，拿到value真正的值
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
return unsafe.Pointer(&zeroVal[0])
Стоит отметить, что в приведенном выше процессе вы можете видеть, что перед сравнением есть t.indirectkey().Мы также можем увидеть большое количество t.indirectkey() и t.indirectelem() в следующих абзацах. Давайте сделаем один здесь Объясните, функция этой функции состоит в том, чтобы судить, есть ли оптимизация указателя для типа, и если да, то его нужно разыменовать, чтобы получить реальное значение соответствующего ключа/значения. Карта оптимизирует ключ и элемент больше 128B.В bmap соответствующие данные не будут храниться напрямую, но будет храниться указатель.Преимущество этого в том, что при инициализации карты она не может применяться слишком Большой объем памяти за один раз Вместо этого для каждой операции записи выделяется большой объем памяти.
написать
//通过函数原型可以看到，对map的写入操作其实是会返回对应value的地址，再通过返回的地址进行简介写入
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 赋值操作，map不能为nil，这也是上述对nil的map进行写操作会panic的源码
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
...
//暂时忽略gc和race操作
// 检测是否写标记位已被设置，若已设置则进程直接crash
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0))
// Set hashWriting after calling t.hasher, since t.hasher may panic, in which case we have not actually done a write.
h.flags ^= hashWriting // 设置写标记位
// 如果当前正在使用的桶为nil，则新建一个
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// 找到key对应的桶
bucket := hash & bucketMask(h.B)
// 如果map在扩容，则会触发一次搬迁操作
if h.growing() {
growWork(t, h, bucket)
}
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
var inserti *uint8 //tophash的地址
var insertk unsafe.Pointer //key的地址
var elem unsafe.Pointer //elem的地址
bucketloop:
for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
// 写入时会写入到第一个空cell
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
}
//emptyRest 标志位：表示当前cell及当前cell后续的cell及bucket都为空，
//可以退出整个大循环，查找失败
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !t.key.equal(key, k) {
continue
}
// already have a mapping for key. Update it.
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
goto done
}
ovf := b.overflow(t) // 当前bucket未找到，继续便利下一个溢出桶
if ovf == nil {
break
}
b = ovf
}
// 插入新元素前，先判断Map是否需要扩容，扩容相关的细节我们在扩容一章再介绍
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
// all current buckets are full, allocate a new one.
// 桶链上已无空cell，需要申请新的溢出桶
if inserti == nil {
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0] // 新桶的第一个位置
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// store new key/elem at insert position
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectelem() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.key, insertk, key)
// 通过 runtime.typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址 val
*inserti = top
h.count++
done:
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting // 写入操作已结束，清除写标记位
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem
}
Вот некоторые из использованных выше служебных функций:
// growing reports whether h is growing. The growth may be to the same size or bigger.判断map是否处于扩容中，方法也很简单，hmap.oldbucket不为nil则正在扩容
func (h *hmap) growing() bool {
return h.oldbuckets != nil
}
удалять
В логике удаления особенностью является то, что флаг emptyOne будет установлен на пустую позицию, а флаг emptyRest будет установлен на следующие пустые позиции. Этот флаг также используется для продолжения и прерывания поиска.
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
...
if h.flags&hashWriting != 0 { // 删除key也属于写操作，禁止并发
throw("concurrent map writes")
}
h.flags ^= hashWriting
if h.growing() { // 触发扩容
growWork(t, h, bucket)
}
hash := t.hasher(key, uintptr(h.hash0))
bucket := hash & bucketMask(h.B)
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break search
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
if !t.key.equal(key, k2) {
continue
}
// Only clear key if there are pointers in it.
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.ptrdata != 0 {
memclrHasPointers(k, t.key.size)
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
*(*unsafe.Pointer)(e) = nil
} else if t.elem.ptrdata != 0 {
memclrHasPointers(e, t.elem.size)
} else {
memclrNoHeapPointers(e, t.elem.size)
}
b.tophash[i] = emptyOne
// If the bucket now ends in a bunch of emptyOne states,
// change those to emptyRest states.
// It would be nice to make this a separate function, but
// for loops are not currently inlineable.
// 如果发现当前元素的下一个元素的tophash值不是emptyRest，则直接退出
if i == bucketCnt-1 {
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
// 否则，将当前元素的tophash设置为emptyRest，且向前check并设置emptyRest标识
for {
b.tophash[i] = emptyRest
if i == 0 {
if b == bOrig {
break // beginning of initial bucket, we're done.
}
// Find previous bucket, continue at its last entry.
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne {
break
}
}
notLast:
h.count--
break search
}
}
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
}
Расширение
карта golang не сжимается. Если эффективный контент на карте не скопирован на карту с небольшой емкостью, можно освободить много места, занимаемого старой картой (то же самое верно для фрагмента ps: golang)
- Есть два способа расширить карту, а именно: двойное расширение и равное расширение.
Удвойте емкость
Коэффициент загрузки представляет собой степень использования bmap.Когда количество элементов на карте превышает 8, а размер коэффициента загрузки превышает 6,5 (81,25%), срабатывает двойное расширение, и количество сегментов удваивается. Поскольку емкость каждого bmap равна 8, когда loadFactor слишком велик, производительность поиска быстро падает.В golang порог loadfactor установлен на 13/2 = 6,5.
const (
loadFactorNum = 13
loadFactorDen = 2
)
// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
Что касается того, почему коэффициент загрузки равен 6,5, то ниже приведен тест различных коэффициентов загрузки в исходном коде go, среди которых есть четыре важных показателя.
-
%overflow: количество сегментов с переполнением в hmap.
-
байт/запись: средний объем памяти, используемый каждой парой ключ/элемент
-
hitprobe: количество проверок kv, необходимых для поиска существующего ключа
-
missprobe: Количество kvs для проверки, чтобы найти несуществующий ключ
Видно, что когда коэффициент загрузки слишком велик, производительность поиска быстро падает, но если коэффициент загрузки слишком мал, много памяти будет потрачено впустую, поэтому команда go наконец выбрала коэффициент загрузки 6,5.
// Picking loadFactor: too large and we have lots of overflow
// buckets, too small and we waste a lot of space. I wrote
// a simple program to check some stats for different loads:
// (64-bit, 8 byte keys and elems)
// loadFactor %overflow bytes/entry hitprobe missprobe
// 4.00 2.13 20.77 3.00 4.00
// 4.50 4.05 17.30 3.25 4.50
// 5.00 6.85 14.77 3.50 5.00
// 5.50 10.55 12.94 3.75 5.50
// 6.00 15.27 11.67 4.00 6.00
// 6.50 20.90 10.79 4.25 6.50
// 7.00 27.14 10.15 4.50 7.00
// 7.50 34.03 9.73 4.75 7.50
// 8.00 41.10 9.40 5.00 8.00
//
// %overflow = percentage of buckets which have an overflow bucket
// bytes/entry = overhead bytes used per key/elem pair
// hitprobe = # of entries to check when looking up a present key
// missprobe = # of entries to check when looking up an absent key
Эквивалентное расширение
Дифференциация будет производиться в соответствии с размером карты.Если переполненных сегментов слишком много, будет запущено равное расширение, а количество сегментов останется неизменным. Потому что, если количество переполненных сегментов слишком велико, эффективность поиска карты также снизится. Таким образом, инициируйте равное расширение, но это может уменьшить использование переполнения и сделать расположение bmap более плотным (GitHub.com/gowaves/go/from…
Есть 2 триггерных условия для равного расширения
-
Если hmap.B
-
Если hmap.B>15, пока количество сегментов переполнения превышает pow(2,15), будет запущено равное расширение.
// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
// If the threshold is too low, we do extraneous work.
// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
// "too many" means (approximately) as many overflow buckets as regular buckets.
// See incrnoverflow for more details.
if B > 15 {
B = 15
}
// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
return noverflow >= uint16(1)<<(B&15)
}
- Подготовка перед расширением
Условие расширения будет оцениваться перед записью данных.Если текущий статус hmap соответствует вышеупомянутому двойному расширению или равному расширению, будет запущена операция расширения.Обратите внимание, что расширение карты golang не является атомарным процессом, он является инкрементным и будет увеличивать операцию расширения для каждой операции записи,runtime.hashGrowЭто подготовительная операция перед расширением, которая помечает карту как состояние расширения.
Прогрессивное расширение также является идеей «разделяй и властвуй», что означает, что golang не завершит миграцию всей карты за один раз, а будет дискретным для каждой операции записи.Что касается того, почему golang выбирает инкрементное расширение, преимущества также очевидно. Инкрементальное расширение может уменьшить мгновенные накладные расходы на вычисления/хранение, вызванные полным расширением, но есть и некоторые недостатки. Поскольку инкрементное расширение должно поддерживать промежуточное состояние, оно также приведет к определенным дополнительным затратам при использовании, которые мы обсудим ниже.
func hashGrow(t *maptype, h *hmap) {
// If we've hit the load factor, get bigger. Otherwise, there are too many overflow buckets,
// so keep the same number of buckets and "grow" laterally.
bigger := uint8(1) //优先走翻倍扩容操作，如果未满足翻倍扩容条件，则走等量扩容
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow // 设置等量扩容标记位
}
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
flags := h.flags &^ (iterator | oldIterator) //清楚iterator标记位
//这里指的一提的是 &^操作，这个操作符的意思是按位置0,通常用于标记位的清楚操作
//x=01011001
//y=01010111
//z = x &^ y = 00001000
//如果y对应的位为1，则z对应的位置0，z的其余位与x一致
//这里的意思是如果hmap存在iterator标记位，因为已经触发了扩容，所以需要转移到oldIterator标志位
if h.flags&iterator != 0 {
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets // 旧桶会存储到oldbuckets字段
h.buckets = newbuckets // buckets赋值为新桶
// 转移溢出桶
h.nevacuate = 0
h.noverflow = 0
if h.extra != nil && h.extra.overflow != nil {
// Promote current overflow buckets to the old generation.
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
}
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
}
- перемещение ковша
Данные из старого сегмента не переносятся в новый сегмент при расширении. Передача данных осуществляется по правилу копирования при записи. Когда фактическое назначение выполнено, будет выбрано, требуется ли передача данных. Даже в сегменте кода «if h.growing() {growWork(t, h, Bucket)}» на момент написания также можно обнаружить, что будет передан только старый сегмент, который в настоящее время должен работать.
Сначала несколько изображений
- hash
Поскольку наше B является положительной целой степенью числа 2, эффект удвоения расширения хеш-значения заключается в том, что нам нужно всего лишь перенести еще один бит вперед.
- bigSizeGrow (двойное расширение)
- sameSizeGrow (равное расширение)
Давайте посмотрим на конкретный исходный код
//执行桶的迁移，每次迁移桶的数量为1或2
func growWork(t *maptype, h *hmap, bucket uintptr) {
// make sure we evacuate the oldbucket corresponding
// to the bucket we're about to use
// 迁移当前正在访问的旧桶
evacuate(t, h, bucket&h.oldbucketmask())
// evacuate one more oldbucket to make progress on growing
// 为了加快搬迁进度，如果依旧处于扩容中，则再迁移一个桶
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
// evacDst is an evacuation destination.
type evacDst struct {
b *bmap // current destination bucket
i int // key/elem index into b
k unsafe.Pointer // pointer to current key storage
e unsafe.Pointer // pointer to current elem storage
}
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()//旧桶的个数
if !evacuated(b) {
// TODO: reuse overflow buckets instead of using new ones, if there
// is no iterator using the old buckets. (If !oldIterator.)
//如果是翻倍扩容，一个旧桶会被迁移到两个新桶，分别位于新buckets的前半部分和后半部分。xy[0]指向前半部分，xy[1]指向后半部分
// xy contains the x and y (low and high) evacuation destinations.
var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.e = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() { // 如果是f是翻倍扩容，也需要用到ypart，计算ypart地址
// y 代表的 bucket 序号增加了 2^oldB
y := &xy[1]
y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
y.k = add(unsafe.Pointer(y.b), dataOffset)
y.e = add(y.k, bucketCnt*uintptr(t.keysize))
}
//以bucket index维度进行迁移，每一次迁移需要迁移对应index的常规桶和全部溢出桶
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
e := add(k, bucketCnt*uintptr(t.keysize))
// 遍历 bucket 中的所有 cell
for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
top := b.tophash[i]
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
var useY uint8 //如果是等量扩容则迁移到xpart。如果是翻倍扩容，则会根据高1位来决定迁移到xpart还是ypart
if !h.sameSizeGrow() {
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
//这里的if条件只有key是math.NAN会进入，因为math.NAN!=math.NAN，我们暂时先忽略这里的特殊逻辑处理，后续详细介绍一下math.NAN
useY = top & 1
top = tophash(hash)
} else {
// 取决于新哈希值的 oldB+1 位是 0 还是 1
if hash&newbit != 0 {
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
dst := &xy[useY] // evacuation destination
// 如果新桶已满，则需要使用溢出桶
if dst.i == bucketCnt {
dst.b = h.newoverflow(t, dst.b) // 新建一个 bucket
dst.i = 0 // xi 从 0 开始计数
dst.k = add(unsafe.Pointer(dst.b), dataOffset)
dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
}
dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
if t.indirectkey() { // key 是指针
*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
} else { // 将原 key（是值）复制到新位置
typedmemmove(t.key, dst.k, k) // copy elem
}
if t.indirectelem() { // value 是指针，操作同 key
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
// 使用下一个 cell
dst.i++
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// Unlink the overflow buckets & clear key/elem to help GC.
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
// Preserve b.tophash because the evacuation
// state is maintained there.
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
memclrHasPointers(ptr, n)
}
}
// bucket迁移并不是按序迁移的，map在写入时会优先迁移当前正在写入的bucket，如果当前迁移的bucket是hmap中记录的待迁移的下一个bmap，则更新迁移进度。
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
//记录迁移进度
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
h.nevacuate++
// Experiments suggest that 1024 is overkill by at least an order of magnitude.
// Put it in there as a safeguard anyway, to ensure O(1) behavior.
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
h.nevacuate++
}
//全部迁移完成，需要将hmap.flags，hmap.oldbuckets，hmap.extra.oldoverflow清除掉
if h.nevacuate == newbit { // newbit == # of oldbuckets
// Growing is all done. Free old main bucket array.
h.oldbuckets = nil
// Can discard old overflow buckets as well.
// If they are still referenced by an iterator,
// then the iterator holds a pointers to the slice.
if h.extra != nil {
h.extra.oldoverflow = nil
}
h.flags &^= sameSizeGrow
}
}
траверс
Давайте сначала поговорим о выводе: процесс обхода карты будет случайным образом брать начальные корзины и ячейки, а затем проходить все корзины и ячейки по очереди. не был перенесен, он будет проходить через ячейки, которые будут перенесены в текущую корзину из старой корзины.
Примечание. При вставке/удалении пары kv в процессе обхода результат не определен, что вызовет исключение в пройденном наборе результатов.
Соответствует стороне пользователя использовать диапазон для обхода карты.Диапазон также ориентирован на пользователя.Давайте сначала посмотрим, какие функции будет вызывать диапазон во время выполнения.
перейти исходный код:
package main
func main() {
//a := map[int]int{1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}
//for k, v := range a {
// fmt.Println(k, v)
//delete(a, 3)
//a[k+10] = v + 10
//a[k+2_000000] = v + 2_000000
//}
}
func Range(mp map[int64]int64) {
var k, v int64
for k, v = range mp {
_, _ = k, v
}
}
Используйте команду go tool compile -N -S -l, чтобы скомпилировать приведенный выше код в ассемблерный код, как показано ниже, основные функции отмечены зеленым цветом.
...
0x002f 00047 (main.go:15) MOVQ $0, "".k+32(SP)
0x0038 00056 (main.go:15) MOVQ $0, "".v+24(SP)
0x0041 00065 (main.go:16) MOVQ "".mp+160(SP), AX
0x0049 00073 (main.go:16) MOVQ AX, ""..autotmp_3+40(SP)
0x004e 00078 (main.go:16) LEAQ ""..autotmp_4+48(SP), DI
0x0053 00083 (main.go:16) XORPS X0, X0
0x0056 00086 (main.go:16) PCDATA $0, $-2
0x0056 00086 (main.go:16) LEAQ -32(DI), DI
0x005a 00090 (main.go:16) NOP
0x0060 00096 (main.go:16) DUFFZERO $273
0x0073 00115 (main.go:16) PCDATA $0, $-1
0x0073 00115 (main.go:16) MOVQ ""..autotmp_3+40(SP), AX
0x0078 00120 (main.go:16) LEAQ type.map[int64]int64(SB), CX
0x007f 00127 (main.go:16) MOVQ CX, (SP)
0x0083 00131 (main.go:16) MOVQ AX, 8(SP)
0x0088 00136 (main.go:16) LEAQ ""..autotmp_4+48(SP), AX
0x008d 00141 (main.go:16) MOVQ AX, 16(SP)
0x0092 00146 (main.go:16) PCDATA $1, $1
0x0092 00146 (main.go:16) CALL runtime.mapiterinit(SB)
0x0097 00151 (main.go:16) JMP 153
0x0099 00153 (main.go:16) CMPQ ""..autotmp_4+48(SP), $0 //sp+48是我们当前遍历到的key的地址
0x009f 00159 (main.go:16) NOP
0x00a0 00160 (main.go:16) JNE 164
0x00a2 00162 (main.go:16) JMP 212
0x00a4 00164 (main.go:16) MOVQ ""..autotmp_4+48(SP), AX
0x00a9 00169 (main.go:16) TESTB AL, (AX)
0x00ab 00171 (main.go:16) MOVQ (AX), AX
0x00ae 00174 (main.go:16) MOVQ AX, "".k+32(SP)
0x00b3 00179 (main.go:16) MOVQ ""..autotmp_4+56(SP), AX
0x00b8 00184 (main.go:16) TESTB AL, (AX)
0x00ba 00186 (main.go:16) MOVQ (AX), AX
0x00bd 00189 (main.go:16) MOVQ AX, "".v+24(SP)
0x00c2 00194 (main.go:17) JMP 196
0x00c4 00196 (main.go:16) LEAQ ""..autotmp_4+48(SP), AX
0x00c9 00201 (main.go:16) MOVQ AX, (SP)
0x00cd 00205 (main.go:16) CALL runtime.mapiternext(SB)
0x00d2 00210 (main.go:16) JMP 153
0x00d4 00212 (main.go:16) PCDATA $1, $-1
0x00d4 00212 (main.go:16) MOVQ 144(SP), BP
0x00dc 00220 (main.go:16) ADDQ $152, SP
0x00e3 00227 (main.go:16) RET
0x00e4 00228 (main.go:16) NOP
Общая схема обхода выглядит следующим образом:
Traversal будет использовать структуру runtime.hiter в качестве итератора, использовать runtime.mapiterinit для инициализации итератора и использовать runtime.mapiternext для итерации по карте.
Если процесс расширения является атомарным, то обход может быть очень простым, достаточно пройти по корзине и ячейке по порядку. Однако, так как расширение карты в golang является поэтапной операцией, также будет состояние, в котором карта расширяется.В этом случае некоторые данные старого ведра не были перенесены в ведро.Чтобы гарантировать, что все ключи траверсируются, при траверсе нужно прыгать туда-сюда между олдбаксами и ковшами. Взгляните на схему обхода:
Предположим, что текущая структура памяти карты выглядит следующим образом, текущая карта находится в процессе расширения, а миграция корзины завершена, что соответствует красному значению oldbuckets[0] на рисунке ниже, которое было перенесено в корзины. [0] и ведра[2].
Предположим, наш startBucket = 2 и offset = 1.
Таким образом, порядок обхода bmap и ключа следующий:
| bmap | 2 | 3 | 0 | 1 |
|---|---|---|---|---|
| key | 3->7->11 | 10-> | 1->2-> | 9 |
bmap: 2 ----> 3----->0------>1
key: 3 -> 7 -> 10 -> 1 -> 2 --> 9
Далее разберем исходный код обхода
type hiter struct {
key unsafe.Pointer // 当前遍历到的key
elem unsafe.Pointer // 当前遍历到的value
t *maptype // map 类型，包含如 key size 大小等
h *hmap // 迭代器初始化时设置，指向当前hmap
buckets unsafe.Pointer // 初始化时指向的 buckets
bptr *bmap // 当前遍历到的 bmap
overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive
oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive
startBucket uintptr // 起始遍历的 bucket 编号
offset uint8 // 迭代过程，从每一个桶的开始cell编号
wrapped bool // already wrapped around from end of bucket array to beginning 是否已经遍历到[]bmap结尾，需要从头开始遍历，用于结束条件的判断
B uint8 // hmap.B
i uint8 // 当前 相对offset的cell序号，真正遍历到的cell序号其实是(i+offset) & (bucketCnt - 1)
bucket uintptr // 指向当前的 bucket
checkBucket uintptr // 因为map在迭代时也可能发生扩容，所以在扩容也需要检查bucket是否已经迁移
}
func mapiterinit(t *maptype, h *hmap, it *hiter) {
//忽略race相关的操作
...
if h == nil || h.count == 0 {
return
}
if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go
}
it.t = t
it.h = h
it.B = h.B // grab snapshot of bucket state 保存桶的当前状态
it.buckets = h.buckets
if t.bucket.ptrdata == 0 {
// Allocate the current slice and remember pointers to both current and old.
// This preserves all relevant overflow buckets alive even if
// the table grows and/or overflow buckets are added to the table
// while we are iterating.
h.createOverflow()
it.overflow = h.extra.overflow
it.oldoverflow = h.extra.oldoverflow
}
// 生成随机数 r
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B) // 从哪个 bucket 开始遍历
it.offset = uint8(r >> h.B & (bucketCnt - 1)) // 从 bucket 的哪个 cell 开始遍历
// iterator state
it.bucket = it.startBucket
// Remember we have an iterator.
// Can run concurrently with another mapiterinit().
//将map标记为正在迭代中
if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
atomic.Or8(&h.flags, iterator|oldIterator)
}
mapiternext(it)
}
func mapiternext(it *hiter) {
// 检测当前是不是有 groutine 在进行写入，有的话直接抛出错误
if h.flags&hashWriting != 0 {
throw("concurrent map iteration and map write")
}
h := it.h
t := it.t
bucket := it.bucket
b := it.bptr
i := it.i
checkBucket := it.checkBucket
next:
// 当前遍历到的bmap为 nil，需要继续遍历下一个bmap
if b == nil {
// 当前遍历到的bmap是开始的bmap 并且已经遍历过尾部了，则标识key为nil，
// 在汇编中会用key==nil作为遍历结束条件
if bucket == it.startBucket && it.wrapped {
it.key = nil
it.elem = nil
return
}
//开始迭代时，hmap已经在扩容中，并且扩容尚未结束
if h.growing() && it.B == h.B {
// Iterator was started in the middle of a grow, and the grow isn't done yet.
// If the bucket we're looking at hasn't been filled in yet (i.e. the old
// bucket hasn't been evacuated) then we need to iterate through the old
// bucket and only return the ones that will be migrated to this bucket.
oldbucket := bucket & it.h.oldbucketmask() //当前bucket对应的old bucket
b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) //对应的old bmap
if !evacuated(b) { // 如果old bmap尚未完成迁移，则需要去遍历oldbucket
checkBucket = bucket //标记，当前bucket需要检查，因为当前bucket对应的oldbucket尚未完成迁移
} else { //old bucket已经完成了迁移，则正常遍历当前bucket即可
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
} else {
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
bucket++ // 下一个桶
if bucket == bucketShift(it.B) { // 已经遍历到尾部了，需要继续从头部开始
bucket = 0
it.wrapped = true //标识已经遍历过尾部了，在退出条件时会用到
}
i = 0
}
// 遍历当前 bucket 的 cell
for ; i < bucketCnt; i++ {
offi := (i + it.offset) & (bucketCnt - 1)
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
// TODO: emptyRest is hard to use here, as we start iterating
// in the middle of a bucket. It's feasible, just tricky.
continue
}
// key/value 地址
k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
//如果map处于翻倍扩容的场景，
if checkBucket != noCheck && !h.sameSizeGrow() {
// Special case: iterator was started during a grow to a larger size
// and the grow is not done yet. We're working on a bucket whose
// oldbucket has not been evacuated yet. Or at least, it wasn't
// evacuated when we started the bucket. So we're iterating
// through the oldbucket, skipping any keys that will go
// to the other new bucket (each oldbucket expands to two
// buckets during a grow).
if t.reflexivekey() || t.key.equal(k, k) {
// If the item in the oldbucket is not destined for
// the current new bucket in the iteration, skip it.
// 因为迭代时在迭代新桶，但是旧桶中的数据可以迁移到2个新桶，
// 如果检查旧桶中的数据不是迁移到当前这个新桶，则跳过，会在另一个新桶遍历到
hash := t.hasher(k, uintptr(h.hash0))
if hash&bucketMask(it.B) != checkBucket {
continue
}
} else {
// math.NAN的特殊逻辑，暂时忽略
if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
continue
}
}
}
if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
!(t.reflexivekey() || t.key.equal(k, k)) {
// This is the golden data, we can return it.
// OR
// key!=key, so the entry can't be deleted or updated, so we can just return it.
// That's lucky for us because when key!=key we can't look it up successfully.
it.key = k
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
it.elem = e
} else {
// The hash table has grown since the iterator was started.
// The golden data for this key is now somewhere else.
// Check the current hash table for the data.
// This code handles the case where the key
// has been deleted, updated, or deleted and reinserted.
// NOTE: we need to regrab the key as it has potentially been
// updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
rk, re := mapaccessK(t, h, k)
if rk == nil {
continue // key has been deleted
}
it.key = rk
it.elem = re
}
it.bucket = bucket
if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
it.bptr = b
}
it.i = i + 1
it.checkBucket = checkBucket
return
}
b = b.overflow(t)
i = 0
goto next
}
общая яма
1. Чтобы разработчики не полагались на порядок карты, для каждого обхода карты (диапазона) порядок получения результатов разный, потому что над startBucket и startCell выполняются случайные операции, когда итератор (runtime. mapiterinit) инициализируется.
func mapiterinit(t *maptype, h *hmap, it *hiter) {
//some code ...
// decide where to start
r := uintptr(fastrand()) //fastrand 是一个快速生成随机数的函数
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
//bucketMask返回bucket的个数-1，也就是全1，将r和bucketMask做与操作，获得开始的桶编号
it.offset = uint8(r >> h.B & (bucketCnt - 1))
//bucketCnt是常量8代表一个桶内的cell数，将r右移B位后与7做与运算，可以获得开始的cell编号
//some code ...
}
2. Несопоставимые типы нельзя использовать в качестве ключей
Для сравнения на языке Go обратитесь к официальной документации.gowave.org/hotwind/spec#co…
- Логические значения сопоставимы
- Целочисленные значения сопоставимы
- Значения с плавающей запятой сравнимы (из которых более специальными являются math.NAN, math.NAN != math.NAN)
- Комплексные значения сопоставимы
- Строковые значения сопоставимы
- Значения указателя сопоставимы. Два значения указателя равны, если они указывают на одну и ту же переменную, или если оба значения указателя равны нулю.
- каналы сопоставимы. Два значения канала равны, если они были созданы одним и тем же вызовом make, или если оба значения равны нулю.
- Значения интерфейса сопоставимы. Два значения интерфейса равны, если они имеют одинаковый динамический тип и одинаковые динамические значения, или если оба значения интерфейса равны нулю.
- Если все поля структуры сравнимы, их значения сравнимы.
- Значения массива сравнимы, если сравнимы значения типов элементов массива. Два массива равны, если равны их соответствующие элементы.
- срез, значение функции, карта несопоставимы (но все три типа можно сравнить с nil)
3. Значение карты не адресуется, то есть адрес значения карты не может быть получен.
Распространенные случаи: когда значение имеет тип struct, его значение нельзя изменить (самое простое решение — сохранить значение как тип *T); при выборке адреса map[key] сообщается об ошибке.
package main
type T struct {
Id int64
}
func main() {
var a = map[int64]T{}
a[10].Id = 20
var m map[int]int{1:1}
b := &m[1]
}
./main.go:9:11: cannot assign to struct field a[10].Id in map
./main.go:11:11: cannot take the address of
Он спроектирован так, чтобы быть неадресуемым, потому что место хранения внутри карты не обязательно фиксировано. При вставке, если места для данных не хватает, его нужно расширить, а расширение нужно перехэшировать, в это время ключ перехэшируется в другую корзину.
4. Карта не поддерживает одновременное чтение и запись, только одновременное чтение
package main
func main() {
mp := make(map[int]int)
go func() {
for i := 0; i < 10_0000; i++ {
_ = mp[i]
}
}()
go func() {
for i := 0; i < 10_0000; i++ {
mp[i] = i
}
}()
select {}
}
В Интернете говорят, что параллельная карта чтения и записи вызовет панику, но это неправда, она не вызовет панику, а напечатает ошибку и соответствующую информацию и вызовет ее напрямую.runtime.exit(2)Функция выходит. Выполнение приведенного выше кода будет иметь
throw：fatal error: concurrent map read and map write。
Стоит отметить, что бросок, вызванный одновременным чтением и записью на карту,unrecoverable, он не может быть захвачен встроенной функцией восстановления, процесс сразу завершится с ошибкой, а код выхода будет равен 2.
Вы можете добавить обнаружение гонки во время выполнения для обнаружения параллельных конкурирующих операций, но накладные расходы на гонку велики, поэтому не включайте ее в производственной среде.
go run -race main.go
Существенной причиной также является то, что адрес памяти ключа/значения является переменным. Если адрес изменяется во время записи, одновременные потоки, читающие и записывающие старый адрес, вызовут повреждение/небезопасность памяти.
Конкретный метод кода заключается в установке и проверке бита флага записи:
// 写时：
h.flags ^= hashWriting
// 在读/写map时会check标记位，如果发现了并发读写，会抛出错误信息
if h.flags & hashWriting != 0 {
throw("concurrent map read and map write")
}
//输出错误信息
//go:nosplit
func throw(s string) {
// Everything throw does should be recursively nosplit so it
// can be called even when it's unsafe to grow the stack.
systemstack(func() {
print("fatal error: ", s, "\n")
})
gp := getg()
if gp.m.throwing == 0 {
gp.m.throwing = 1
}
fatalthrow()
*(*int)(nil) = 0 // not reached
}
// fatalthrow implements an unrecoverable runtime throw. It freezes the
// system, prints stack traces starting from its caller, and terminates the
// process.
//（输出函数堆栈信息，并退出进程）
//go:nosplit
func fatalthrow() {
pc := getcallerpc()
sp := getcallersp()
gp := getg()
// Switch to the system stack to avoid any stack growth, which
// may make things worse if the runtime is in a bad state.
systemstack(func() {
startpanic_m()
if dopanic_m(gp, pc, sp) {
// crash uses a decent amount of nosplit stack and we're already
// low on stack in throw, so crash on the system stack (unlike
// fatalpanic).
crash()
}
exit(2)
})
*(*int)(nil) = 0 // not reached
}
Для сценариев, требующих одновременного чтения и записи карт, распространенными решениями являются следующие:
- map + sync.RWMutex
- Используя sync.map, реализация представляет собой мелкозернистую блокировку + разделение чтения-записи + атомарную операцию.
5. len(map) возвращает количество элементов на карте, а не емкость карты
package main
import "fmt"
func main() {
mp := make(map[int64]int64,10)
fmt.Println(len(mp))
}
//上面这段程序会输出0
6. Карту из новой использовать нельзя, т.к. новая просто выделяет 8 байт памяти (новая возвращает указатель).
Напротив, make — это синтаксический сахар, который в конечном итоге транслируется компилятором в вызов функции runtime.makemap, которая будет выполнять операции по развитию памяти и инициализации объекта.
7. При печати карты через fmt результат пустой карты и нулевой карты одинаков, оба являются map[]. Поэтому в настоящее время не судите, является ли карта пустой или нулевой, но судите по карте == nil.
8. Емкость будет автоматически увеличена при превышении емкости, но постарайтесь указать разумное начальное значение.
9. Когда карта используется в качестве выходного параметра функции, ее не нужно передавать как указатель, потому что сама карта является указателем.Также вы можете видеть, что runtime.makemap возвращает *runtime.hmap в секции инициализации карты над.
10. Удалить толком не освободит память карты.Чтобы перепрошить карту, ее все равно нужно обнулить
var intMap map[int]int
func main() {
printMemStats("初始化")
// 添加1w个map值
intMap = make(map[int]int, 10000)
for i := 0; i < 10000; i++ {
intMap[i] = i
}
// 手动进行gc操作
runtime.GC()
// 再次查看数据
printMemStats("增加map数据后")
log.Println("删除前数组长度：", len(intMap))
for i := 0; i < 10000; i++ {
delete(intMap, i)
}
log.Println("删除后数组长度：", len(intMap))
// 再次进行手动GC回收
runtime.GC()
printMemStats("删除map数据后")
// 设置为nil进行回收
intMap = nil
runtime.GC()
printMemStats("设置为nil后")
}
func printMemStats(mag string) {
var m runtime.MemStats
runtime.ReadMemStats(&m)
log.Printf("%v：分配的内存 = %vKB, GC的次数 = %v\n", mag, m.Alloc/1024, m.NumGC)
}
Суммировать
В этой статье мы впервые представили базовую концепцию карты, узнали, что карта golang реализована на основе хэш-таблицы, а метод разрешения конфликтов использует метод цепных адресов, а также кратко представили основные операции карты.
Далее мы углубились в исходный код и изучили модель памяти, хеш-функцию, инициализацию, чтение, запись, удаление, расширение и процесс обхода карты соответственно. Самой основной концепцией карты является сегмент. Сегмент — это основная единица поиска и хранения данных карты. В каждом сегменте 8 ячеек. Младший бит хеш-значения ключа определяет, в какой сегмент он попадает, а старший бит определяет, в какую ячейку он попадает.Для корзин с более чем 8 элементами ведро переполнения будет использоваться для дополнительного хранения на задней цепочке, и если ведер переполнения слишком много или свободная емкость карты мала, расширение карта будет запущена.Дрожание памяти и накладные расходы задержки, вызванные расширением, расширение карты происходит постепенно, и процесс расширения будет дискретным в каждой операции записи данных.
Наконец, в сочетании с некоторыми справочными материалами в Интернете и нашей обычной практикой, мы вводим некоторые общие ямки карты в повседневном использовании.