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：致命錯誤：運行時：內存不足

回答

相關問題