Память эффективная реализация Go Map? - PullRequest
Новая
       11

Память эффективная реализация Go Map?

0 голосов
/ 20 ноября 2018

Мой вариант использования - передача группы членов (целых чисел) по сети, поэтому мы используем дельта-кодирование, а на принимающей стороне декодируем и помещаем весь список в виде карты, карта [строка] структура {} для O (1) сложность для проверки членства.

Проблема, с которой я сталкиваюсь, состоит в том, что фактический размер членов составляет всего 15 МБ для 2 миллионов целых чисел, но размер карты в куче составляет 100 + МБ. Похоже, фактическая реализация карты Go не подходит для больших карт. Поскольку это SDK на стороне клиента, я не хочу сильно влиять на используемую память, и может быть несколько таких групп, которые необходимо хранить в памяти в течение длительного периода времени - около 1 недели.

Есть ли лучший альтернативный DS в Go для этого? 

type void struct{}
func ToMap(v []int64) map[string]void {
 out := map[string]void{}
 for _, i := range v {
   out[strconv.Itoa(int(i))] = void{}
 }
 return out
}

1 Ответ

0 голосов
/ 20 ноября 2018

Это более эффективная форма памяти карты: 

type void struct{}

func ToMap(v []int64) map[int64]void {
    m := make(map[int64]void, len(v))
    for _, i := range v {
        m[i] = void{}
    }
    return m
}

Карты Go оптимизированы для целочисленных ключей.Оптимизируйте размещение карты, указав точный размер карты в качестве подсказки.

A string имеет неявный указатель, который заставляет сборщик мусора (gc) следовать за указателем при каждом сканировании.

Вот тест Go для 2 миллионов псевдослучайных чисел: 

package main

import (
    "math/rand"
    "strconv"
    "testing"
)

type void struct{}

func ToMap1(v []int64) map[string]void {
    out := map[string]void{}
    for _, i := range v {
        out[strconv.Itoa(int(i))] = void{}
    }
    return out
}

func ToMap2(v []int64) map[int64]void {
    m := make(map[int64]void, len(v))
    for _, i := range v {
        m[i] = void{}
    }
    return m
}

var benchmarkV = func() []int64 {
    v := make([]int64, 2000000)
    for i := range v {
        v[i] = rand.Int63()
    }
    return v
}()

func BenchmarkToMap1(b *testing.B) {
    b.ReportAllocs()
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        ToMap1(benchmarkV)
    }
}

func BenchmarkToMap2(b *testing.B) {
    b.ReportAllocs()
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        ToMap2(benchmarkV)
    }
}

Вывод: 

$ go test tomap_test.go -bench=.
BenchmarkToMap1-4     2  973358894 ns/op    235475280 B/op    2076779 allocs/op
BenchmarkToMap2-4    10  188489170 ns/op     44852584 B/op         23 allocs/op
$
...