Golang: фатальная ошибка: время выполнения: из памяти

Question

Я пытаюсь использовать этот пакет в Github для соответствия строк. Мой словарь - 4 МБ. При создании Trie я получил fatal error: runtime: out of memory. Я использую Ubuntu 14.04 с 8 ГБ оперативной памяти и Golang версии 1.4.2.

Кажется, ошибка приходит из строки 99 (сейчас) here: m.trie = make([]node, max)

Программа останавливается на этой линии.

Это ошибка:

fatal error: runtime: out of memory 

runtime stack: 
runtime.SysMap(0xc209cd0000, 0x3b1bc0000, 0x570a00, 0x5783f8) 
    /usr/local/go/src/runtime/mem_linux.c:149 +0x98 
runtime.MHeap_SysAlloc(0x57dae0, 0x3b1bc0000, 0x4296f2) 
    /usr/local/go/src/runtime/malloc.c:284 +0x124 
runtime.MHeap_Alloc(0x57dae0, 0x1d8dda, 0x10100000000, 0x8) 
    /usr/local/go/src/runtime/mheap.c:240 +0x66 

goroutine 1 [running]: 
runtime.switchtoM() 
    /usr/local/go/src/runtime/asm_amd64.s:198 fp=0xc208518a60 sp=0xc208518a58 
runtime.mallocgc(0x3b1bb25f0, 0x4d7fc0, 0x0, 0xc20803c0d0) 
    /usr/local/go/src/runtime/malloc.go:199 +0x9f3 fp=0xc208518b10 sp=0xc208518a60 
runtime.newarray(0x4d7fc0, 0x3a164e, 0x1) 
    /usr/local/go/src/runtime/malloc.go:365 +0xc1 fp=0xc208518b48 sp=0xc208518b10 
runtime.makeslice(0x4a52a0, 0x3a164e, 0x3a164e, 0x0, 0x0, 0x0) 
    /usr/local/go/src/runtime/slice.go:32 +0x15c fp=0xc208518b90 sp=0xc208518b48 
github.com/mf/ahocorasick.(*Matcher).buildTrie(0xc2083c7e60, 0xc209860000, 0x26afb, 0x2f555) 
    /home/go/ahocorasick/ahocorasick.go:104 +0x28b fp=0xc208518d90 sp=0xc208518b90 
github.com/mf/ahocorasick.NewStringMatcher(0xc208bd0000, 0x26afb, 0x2d600, 0x8) 
    /home/go/ahocorasick/ahocorasick.go:222 +0x34b fp=0xc208518ec0 sp=0xc208518d90 
main.main() 
    /home/go/seme/substrings.go:66 +0x257 fp=0xc208518f98 sp=0xc208518ec0 
runtime.main() 
    /usr/local/go/src/runtime/proc.go:63 +0xf3 fp=0xc208518fe0 sp=0xc208518f98 
runtime.goexit() 
    /usr/local/go/src/runtime/asm_amd64.s:2232 +0x1 fp=0xc208518fe8 sp=0xc208518fe0 
exit status 2 

Это содержание главной функции (взято из того же репо: тестовый файл)

var dictionary = InitDictionary() 
var bytes = []byte(""Partial invoice (€100,000, so roughly 40%) for the consignment C27655 we shipped on 15th August to London from the Make Believe Town depot. INV2345 is for the balance.. Customer contact (Sigourney) says they will pay this on the usual credit terms (30 days).") 

var precomputed = ahocorasick.NewStringMatcher(dictionary)// line 66 here 
fmt.Println(precomputed.Match(bytes)) 

Answer 1

Тип node имеет размер памяти 2084 байт. я написал Litte программу, чтобы продемонстрировать использование памяти: https://play.golang.org/p/szm7AirsDB

Как вы можете видеть, три строки (11 (+1) байт) dictionary := []string{"fizz", "buzz", "123"} требуется 24 МБ памяти.

Если ваш словарь имеет длину 4 МБ, вам понадобится около 4000 * 2084 = 8.1 GB памяти.

Так что вы должны попытаться уменьшить размер словаря.

Answer 2

Ваша структура ужасно неэффективна с точки зрения памяти, давайте посмотрим на внутренности. Но до этого, быстрое напоминание пространства требуется для некоторых пойти типов:

• BOOL: 1 байт
• INT: 4 байта
• UIntPtr: 4 байта
• [N] Тип: N * SizeOf (тип)
• [] Тип: 12 + Len (срез) * SizeOf (тип)

Теперь давайте посмотрим на вашу структуру:

type node struct { 
    root bool  // 1 byte 
    b []byte   // 12 + len(slice)*1 
    output bool  // 1 byte 
    index int  // 4 bytes 
    counter int  // 4 bytes 
    child [256]*node // 256*4 = 1024 bytes 
    fails [256]*node // 256*4 = 1024 bytes 
    suffix *node  // 4 bytes 
    fail *node  // 4 bytes 
} 

Хорошо, вы должны иметь представление о том, что происходит здесь: каждый узел весит более 2 КБ, это огромный! Наконец, мы рассмотрим код, который вы используете для инициализации своего тви:

func (m *Matcher) buildTrie(dictionary [][]byte) { 
    max := 1 
    for _, blice := range dictionary { 
     max += len(blice) 
    } 
    m.trie = make([]node, max) 

    // ... 
} 

Вы сказали, что ваш словарь составляет 4 МБ. Если это всего 4 МБ, то это означает, что в конце цикла for, max = 4MB. Он содержит 4 МБ разных слов, затем max = 4MB*avg(word_length).

Мы рассмотрим первый сценарий, самый красивый. Вы инициализируете кусочек 4M узлов, каждый из которых использует 2KB. Да, это делает хороший 8 ГБ необходимым.

Вы должны изучить, как вы строите свое трю. На странице wikipedia, связанной с алгоритмом Aho-Corasick, каждый узел содержит один символ, поэтому не более 256 символов, которые идут от корня, а не 4 МБ.

Некоторые материалы, чтобы сделать это правильно: http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf