這個問題在StackOverflow上經常出現,但我已經閱讀了所有以前的相關答案,並且對這個問題略有改動。在C中的大型磁盤文件上進行二進制搜索 - 問題
我有一個23Gb文件,其中包含4.75億行的大小相等,每行由40個字符的哈希代碼後跟一個標識符(整數)組成。
我有一個傳入哈希代碼流 - 總計數十億 - 我需要找到每個傳入哈希代碼並打印出相應的標識符。這項工作雖然很大,但只需要進行一次。
文件太大,我讀入內存,所以我一直在嘗試通過以下方式來usemmap:
codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0);
然後我使用基於地址的地址算術做一個二進制搜索碼。
這似乎開始工作美麗,並在幾秒鐘內使用100%的cpu產生幾百萬個標識符,但後來一些,看似隨機的時間量減緩到爬行。當我使用ps查看進程時,使用100%的cpu將狀態「R」更改爲使用1%cpu的狀態「D」(磁盤綁定)。
這是不可重複的 - 我可以在相同的數據上再次啓動進程,並且在「慢速爬行」發生之前它可能運行5秒或10秒。昨晚一次,在發生這種情況之前,我花了將近一分鐘時間。
一切都是隻讀的,我沒有試圖對文件進行任何寫操作,並且我已經停止了機器上的所有其他進程(我控制的)。它是一個現代化的紅帽企業Linux 64位機器。
有誰知道爲什麼這個過程變成了磁盤綁定以及如何阻止它?
UPDATE:
感謝大家的回答,和你的想法;之前我以前沒有嘗試過所有的各種改進,因爲我想知道我是否以某種方式錯誤地使用了mmap。但答案的要點似乎是,除非我能把所有東西都記在腦海中,否則我將不可避免地遇到問題。所以我將散列碼的大小壓縮到了不會產生任何重複的前綴前綴的大小 - 前15個字符就足夠了。然後我將結果文件拖入內存,並分別以大約20億次的批量運行傳入的哈希代碼。
你正在碰到虛擬內存的限制。雖然活動數據集適合內存,但一切都是虛擬的。當您需要對數據集進行隨機訪問時,您的數據集太大而無法存儲在內存中,因此您可以開始分頁,併成爲磁盤綁定。這不是一個簡單的方法。是整數存儲爲4字節或8字節的二進制值,還是字符串?重構23 GiB文件是否有可能? – 2013-02-14 02:34:40
@paxdiablo:問題不在於虛擬內存大小的限制;問題是底層的物理內存。該程序仍在運行,但是當物理內存爲16 GiB時,隨機訪問超過23 GiB的數據意味着一旦在內存中獲得了2/3的文件,平均而言,您必須三個內存訪問讀取新頁面,這是痛苦的緩慢。 – 2013-02-14 02:40:14
@JonathanLeffler:是的,我意識到你的意思後,重新閱讀(因此我的刪除評論)。拋出我的是斷言它是虛擬內存的限制(我把它看作是size)而不是虛擬內存_management_(即映射,正如你在響應中所解釋的那樣)。 – paxdiablo 2013-02-14 02:52:07