Golang: 致命错误：运行时内存不足

Question

我想在Github中使用这个包进行字符串匹配。我的字典有4MB。创建Trie时，我遇到了fatal error: runtime: out of memory的问题。我正在使用Ubuntu 14.04，拥有8GB的RAM和Golang版本1.4.2。

看起来错误是来自于现在（here）的第99行：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))

- David

---

你的程序在第66行有什么？ - squiguy

顺便说一句，在一般情况下，问题需要包含足够的信息才能在问题本身得到答案；只有在跟随 GitHub 链接之后才能回答问题的问题在技术上违反了规则，尽管您已经得到了一些好的回答，这不太可能被关闭。 - Charles Duffy

我遇到了类似的问题，但是容量是256GB。结果发现这是一个Linux内核设置问题。https://dev59.com/Hp3ha4cB1Zd3GeqPWI52 - Josh Hibschman

Answer 1

从内存效率角度来看，你的结构非常低效。让我们先来看一下内部情况。但在此之前，请快速了解一些 Go 类型所需的空间：

• bool：1 字节
• int：4 字节
• uintptr：4 字节
• [N]type：N*sizeof(type) 字节
• []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，这太大了！最后，我们将看一下用于初始化字典树的代码：

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

    // ...
}

你说你的字典是4MB。如果总共是4MB，那么在for循环结束时，max = 4MB。如果它包含了4MB不同的单词，则max = 4MB*avg(word_length)。

我们将采用第一种情况，这是最好的情况。您正在初始化一个包含4M个节点的切片，每个节点使用2KB。是的，需要8GB的内存。

您应该审查如何构建您的trie树。从和Aho-Corasick算法相关的维基百科页面，每个节点只包含一个字符，因此从根节点开始最多有256个字符，而不是4MB。

一些资料可以帮助您更正：https://web.archive.org/web/20160315124629/http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

- T. Claverie

---

谢谢，我现在看到问题了。 - David

这个Aho-Corasick算法的实现（https://github.com/anknown/ahocorasick）看起来更加高效。 - David

素材链接已经失效了，如果可能的话，您能否更新一下？谢谢。 - Drubio

Answer 2

node 类型的内存大小为 2084 字节。 我编写了一个小程序来演示记忆使用情况：https://play.golang.org/p/szm7AirsDB 如您所见，三个字符串 (大小为 11(+1) 字节) dictionary := []string{"fizz", "buzz", "123"} 需要占用 24 MB 的内存。 如果您的字典长度为 4 MB，则需要大约 4000 * 2084 = 8.1 GB 的内存。 因此，您应该尽量减小字典的大小。

- stonith

---

你不能通过减少数据结构的条目大小来修复它，而应该选择更高效的方法。 - T. Claverie

没错，你说得对。我只是不想写像“这段代码很糟糕，不要用它”这样的话。 - stonith

Answer 3

将资源限制设置为无限对我有用

如果ulimit -a返回0，则运行ulimit -c unlimited

也许设置一个真实的大小限制会更安全

- franciscorode