Глубокое понимание Карты Go: Элементы инициализации и доступа

Автор оригинала: David Wong.

Начиная с этой статьи, давайте исследуем тайну карты Go, посмотрим, как она построена, и на какие моменты стоит обратить внимание?

В главе 1 будут обсуждаться Элементы инициализации и доступа В соответствующих разделах давайте рассмотрим такие вопросы, как:

Будет ли память выделена сразу же после инициализации?
Как хранятся базовые данные?
Как базовый ключ используется для поиска данных?
Каков способ разрешения конфликта хэшей внизу?
С таким количеством типов данных, как работает базовый процесс?

…

Исходный адрес: Глубокое понимание Карты Go: Элементы инициализации и доступа

структура данных

Во-первых, давайте рассмотрим базовую структуру данных карты Go. Во-первых, давайте составим общее впечатление.

карта

type hmap struct {
    count     int 
    flags     uint8
    B         uint8
    noverflow uint16
    hash0     uint32
    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr 
    extra *mapextra
}

type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

Количество: Размер карты, который является значением len (). Относится к числу пар ключ-значение в карте
Флаги: идентификация состояния, главным образом контроль состояния механизма записи и расширения goroutine. Одним из критериев одновременного чтения и записи является значение.
B: Ковш, максимальное количество элементов, которые могут быть размещены, значение Коэффициент загрузки (по умолчанию 6,5)* 2 ^ B Это показатель, равный двум.
Переполнение: количество переполненных ведер
Хэш 0: коэффициент хэширования
Сегменты: адрес указателя, содержащий текущие данные в сегменте (указывает на адрес непрерывной памяти, в котором в основном хранятся пары ключ-значение данных)
Старые ведра, сохраните адрес указателя старого ведра
Эвакуация: прогресс миграции
Дополнительно: Когда исходные ведра будут полностью загружены, произойдет действие расширения. Инкрементное расширение используется в механизме Go следующим образом:
- переполнение по map.buckets (Текущий) адрес указателя переполненного ведра
- старое переполнение по карте.старые ведра (старый) адрес указателя переполненного ведра
- следующее переполнение Адрес указателя для ведра переполнения холостого хода

Здесь мы должны обратить внимание на несколько моментов, а именно::

Если ключи и значения не содержат указателей и допускают вставку. Сегменты идентифицируются как не содержащие указателей. Использование дополнительных ведер переполнения хранилища позволяет избежать сканирования всей карты GC и сэкономить ненужные накладные расходы.
Как упоминалось ранее, Go использует постепенное расширение мощностей. и ведра и старые ведра Это также перевозчик, связанный с расширением пропускной способности, который обычно используется только. ведра , старые ведра Там пусто. Но если расширение идет полным ходом, старые ведра Он не пустой. ведра Размер также меняется.
Когда подсказка Когда она больше 8, она будет использоваться *дополнительная карта Сделайте переполнение ведра. Если меньше 8, он хранится в ведрах

bmap

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits
...
type bmap struct {
    tophash [bucketCnt]uint8
}

Верхний хэш: значение хэша ключа на 8 бит выше
Ключи: 8 ключей
Значения: 8 значений
Переполнение: адрес указателя следующего блока переполнения (при возникновении конфликта хэшей)

Фактическая КАРТА-это ведро в ведрах. В корзине может храниться до восьми пар ключ-значение.

топхаш

Tophash-это массив из 8 длин, что означает, что максимальное количество пар ключей, которые может содержать ведро, равно 8.

Сохраните значение хэша каждого элемента на высоком 8-разрядном уровне, если tophash [0] Затем tophash [0] Представлен как ход миграции

Ключи и значения

Здесь мы замечаем, что носители, в которых хранятся K и V, не используются. k/v/k/v/k/v/k/v Шаблоны, но k/k/k/k/v/v/v |/Форма для хранения. Это почему?

map[int64]int8

В этом случае, если вы выполните k/v/k/v/k/v/k |v/| При хранении в форме значение каждой пары ключ-значение занимает только один байт. Но для заполнения пространства памяти требуется семь байтов заполнения. В конечном счете, много памяти тратится впустую.

Но если k/k/k/k/v/v/v/v Формальное хранилище может решить проблему “траты” пространства памяти из-за выравнивания.

Поэтому эта часть разделения в основном учитывает проблему выравнивания памяти, хотя и относительно сложную, но все же стоящую разработки.

переполнение

Некоторые студенты могут задаться вопросом, почему существует переполненное ведро. Фактически, при отсутствии конфликта хэшей блок переполнения удаляется, то есть требуется только блок, фактор хэша и алгоритм хэширования. Также может быть реализована простая хэш-таблица. Но конфликт с хэшем неизбежен.

В Go map map.buckets При заполнении переполненное ведро используется для хранения. В сочетании с анализом мы можем подтвердить, что Go использует метод адреса массива + цепочки для решения конфликта хэшей.

Инициализация

использование

m := make(map[int32]int32)

Прототип функции

Чтение исходного кода показывает, что существует несколько методов инициализации. Прототип функции выглядит следующим образом:

func makemap_small() *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap

Makemap_small: подсказка Когда он меньше 8, он будет вызван makemap_small Для инициализации карты. Основное различие заключается в том, будет ли хэш-таблица инициализирована немедленно.
Makemap64: подсказка Специальная обработка преобразования и проверки типа In64, Последующий основной вызов makemap
Makemap: реализует стандартные действия по инициализации карты

Исходный код

func makemap(t *maptype, hint int, h *hmap) *hmap {
    if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
        hint = 0
    }

    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()

    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

В соответствии с типом входящего ведра получите максимальную емкость, на которую может претендовать его тип. И его длина make(карта[k]v, подсказка) Тестирование граничных значений
Инициализировать карту
Хеш-фактор инициализации
В соответствии с входящей подсказкой Рассчитайте ту, которую можно проставить подсказка Бочка элементов B Минимальное значение
Назначьте и инициализируйте хэш-таблицу. Если B Ведро распределения для 0 будет выделено в последующей лени, и если оно больше 0, оно будет выделено немедленно.
Возвращает инициализированную карту

Здесь можно заметить, что (когда ___________ подсказка Больше или равно 8) При первой инициализации карты вы называете ее makeBucketArray Распределите ведра. Поэтому мы часто говорим, что указываем соответствующий размер емкости для инициализации. Может повысить производительность.

Если емкость слишком мала, появляется много новых пар ключей. Это приведет к частому распределению сегментов, миграции расширения и другим действиям по повторной обработке. Конечным результатом является прямое снижение производительности (постукивание по доске).

И когда подсказка Проблема меньше 8:00 Относительная Это не будет слишком очевидно, как следует:

func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

Икона

Посещать

использование

v := m[i]
v, ok := m[i]

Прототип функции

Существует несколько способов доступа к элементам карты, в основном включая специальную обработку для 32/64 бит и строкового типа. Прототип общей функции выглядит следующим образом:

mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)

mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer
mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool)

mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)
mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
...

mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
...

Mapaccess1: Возвращает h[ключ] Адрес указателя, если ключ отсутствует карта В
Mapaccess2: Возвращает h[ключ] Адрес указателя, если ключ отсутствует карта В этом методе для суждения возвращаются нулевые и логические значения.

Исходный код

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    alg := t.key.alg
    hash := alg.hash(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // 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
        }
    }
    top := tophash(hash)
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            if alg.equal(key, k) {
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

Определите, равна ли карта нулю, а длина равна 0. Если это так, верните ноль
Определите, выполняется ли в настоящее время одновременное чтение и запись карты, и если да, то создайте исключение
Значение хэша вычисляется путем вызова различных методов хэширования в соответствии с различными типами ключей
Определите, в каком блоке находится ключ, и определите его местоположение
Определите, происходит ли расширение (h.старые пакеты равны нулю), и если расширение происходит, посмотрите в старых корзинах (потому что корзины могут не стоить того, и перемещение не завершено), если ведро было перемещено. Продолжайте поиск в корзинах
Вычислите максимальное значение хэша хэша (высокий октет)
В соответствии с рассчитанным топхешем поочередно сравниваются верхние хэш-значения сегментов (быстрый метод проб и ошибок).
Если верхний хэш успешно совпадает, вычисляется местоположение ключа и проводится формальное и полное сравнение между двумя ключами.
Если поиск завершится успешно и вернется, если он не существует, он вернет ноль.

На шаге 3 выше упоминается, что хэш-значение может быть рассчитано в соответствии с различными типами. Кроме того, высокие и низкие восемь битов хэш-значения могут быть вычислены с помощью бухгалтерского учета. Нижние восемь битов используются в качестве индекса ячейки, чтобы найти ячейку, в которой находится ключ. Старшие восемь бит хранятся в верхнем хэше BMAP

Его основная функция заключается в итеративном поиске на шаге 7 выше. Это повышает производительность, а не использует ключи для сравнения согласованности непосредственно с самого начала.

Икона

резюме

В этой главе мы представим следующие точки знаний типа карты:

Базовая структура данных карты
Инициализировать карту
Карта посещения

Из чтения исходного кода вы можете видеть, что сам Go Определенные методы написаны для некоторых свойств разных размеров и типов, включая методы хэширования Go для запуска. Вообще говоря, дизайн этого блока содержит больше идей, и есть много моментов, достойных тщательной дегустации:)

Примечание: Эта статья основана на Go 1.11.5

структура данных

карта

bmap

топхаш

Ключи и значения

переполнение

Инициализация

использование

Прототип функции

Исходный код

Икона

Посещать

использование

Прототип функции

Исходный код

Икона

резюме

Читайте ещё по теме: