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

我试图在Github中使用此包进行字符串匹配。我的字典是4 MB。创建Trie时，我得到了fatal error: runtime: out of memory。我正在使用带有8 GB RAM和Golang 1.4.2版的Ubuntu 14.04。Golang：致命错误：运行时：内存不足

看来误差来自于线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))

来源

2016-05-31 David

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

顺便说一句，一般来说，问题需要包含足够的信息以便在问题本身*中负责*;一个人只能在遵循github链接后才能回答的问题在技术上违反了规则，尽管你已经有了一些很好的答案，但这不可能被封闭。 –

的node类型具有的2084的存储器大小字节。我写了一个豆蔻程序来演示内存使用：https://play.golang.org/p/szm7AirsDB

正如你可以看到，三根弦（11（+1）的大小字节）dictionary := []string{"fizz", "buzz", "123"}需要的内存24 MB。

如果您的字典长度为4 MB，则需要大约4000 * 2084 = 8.1 GB的内存。

所以你应该尽量减少字典的大小。

来源

2016-05-31 17:26:08 stonith

您不会通过减少条目的大小来修复损坏的数据结构，而是采取更高效的条目。 –

是的，你是对的，我只是想写一些像'这个代码是垃圾，不使用它'的东西。 – stonith

好的，谢谢你的回复 – David

你的结构在内存方面效率非常低，让我们看看内部。但在此之前，对于一些所需要的空间的快速提醒去类型：

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 
}

好的，你应该猜测这里发生了什么：每个节点重量超过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必要。

你应该回顾一下你如何构建你的trie。在与Aho-Corasick算法相关的维基百科页面中，每个节点包含一个字符，因此最多有256个字符来自根，而不是4MB。

一些材料使它正确：http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

来源

2016-05-31 17:26:40

谢谢我现在看到的问题。 – David

[这个Aho-Corasick算法的实现]（https://github.com/anknown/ahocorasick）似乎更有效率。 – David

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

回答

相关问题