linux - Golang : fatal error: runtime: out of memory

我试图在Github中使用此包进行字符串匹配。我的字典是4 MB。创建Trie时，我得到了fatal error: runtime: out of memory。我正在使用具有8 GB RAM和Golang版本1.4.2的Ubuntu 14.04。

似乎错误来自第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))

最佳答案

就内存而言，您的结构效率很低，让我们看一下内部结构。但在此之前，请快速提醒一下某些go类型所需的空间:

bool:1个字节的

int:4个字节

uintptr:4个字节的

[N]类型:N * sizeof(type)

[]类型:12 + len(slice)* sizeof(type)

现在，让我们看一下您的结构:

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
}

好的，您应该对这里发生的事情有所猜测:每个节点的重量都超过2KB，这是巨大的!最后，我们将看一下用于初始化Trie的代码:

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

    // ...
}

您说您的字典是4 MB。如果总共为4MB，则表示在for循环结束时为max = 4MB。它包含4 MB个不同的单词，然后是max = 4MB*avg(word_length)。

我们将采用第一个方案，最好的方案。您正在初始化一个4M的节点片，每个节点使用2KB。是的，这需要8GB的空间。

您应该查看如何构建自己的特里。在与Aho-Corasick算法相关的Wikipedia页面上，每个节点包含一个字符，因此从根到根最多有256个字符，而不是4MB。

一些正确的 Material :https://web.archive.org/web/20160315124629/http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

关于linux - Golang : fatal error: runtime: out of memory，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37551288/