每日最新頭條.有趣資訊

我優化多年的 C 語言竟然被 80行Haskell 打敗了?

本文並沒有說Haskell比C“好”,也不會討論任何一種語言的相對價值,更不會討論它們的實現——本文只是簡單地探索了高性能Haskell,同時嘗試了一些有趣的技巧而已。

作者 |Chris Penner

譯者 | 彎月,責編 | 郭芮

出品 | CSDN(ID:CSDNnews)

以下為譯文:

儘管題目有些標題黨,但我仍希望這篇文章能夠對你有所啟發,至少是一篇有意思的文章!本文並沒有說Haskell比C“好”,也不會討論任何一種語言的相對價值,更不會討論它們的實現。本文只是簡單地探索了高性能Haskell,同時嘗試了一些有趣的技巧而已。

點擊這裡可以下載本文的源代碼(https://github.com/ChrisPenner/wc)。

作為參考,我使用的是Mac版的wc;其參考源代碼在此(https://opensource.apple.com/source/text_cmds/text_cmds-68/wc/wc.c.auto.html)。沒錯,其實還有更快的wc實現。

我們的問題是,利用我們喜歡的某種支持垃圾回收、基於運行時的高級語言——Haskell,編寫一個wc工具,它要比手工優化過的C實現更快。聽起來很簡單,是吧?

下面是該任務的條件:

正確性:它應當返回被測試文件的正確的字元數、單詞數和行數。

速度(真實世界的時間):與wc的執行時間相比是快是慢?

最大常駐記憶體量:最多使用多少記憶體?記憶體使用量是常量還是線性的,或者是其他?

這些是我們需要關心的主要問題。

下面讓我們開始吧。

最笨的實現

與往常一樣,我們應該從最笨的實現開始,看看情況如何,然後再以此為起點繼續前進。那麽,用Haskell統計字元數、單詞數和行數的最笨的方法是什麽?我們可以讀入文件,然後運行length、length . words和length . lines來獲得計數。

很不錯,這段代碼能正常運行,並且能獲得與wc相同的結果——如果你願意等的話。而我在測試大文件時開始不耐煩(它需要幾分鐘的時間),但在小文件(90MB)上的測試結果如下:

90MB的測試文件

嗯……不用我說你也知道,改進的空間非常大……

略微好一點的實現

我們來看看為什麽上述代碼的性能如此差。

首先,我們遍歷了三遍整個文件內容!這也意味著,在遍歷過程中,GHC不能對列表進行垃圾回收,因為在其他地方依然要用到該列表。結果就是,文件中的每個字元都在鏈表裡存儲下來,這也是為什麽僅有90MB的文件佔據了2.4GB記憶體的原因!哎呦!

好吧,這個方法實在是不怎麽樣,我們來看看如果隻遍歷一次會怎樣。我們只需要累加三個數字,所以也許可以同時處理它們?遍歷列表獲得最終結果,很自然地我想到了fold操作!

用fold來統計字元數或行數非常容易:遇到一個字元給合計值加1,當前字元為新行時給行計數加1,那單詞數怎麽辦?我們無法簡單地在遇到空格時加1,因為連續的空給不應該算作一個新單詞!我們需要跟蹤前一個字元是否為空格,只有當開始一個新單詞時才給計數器加1。這並不難實現,下面的實現使用了Data.List中的foldl':

結果這個版本遇到了更嚴重的問題!

程序運行花了幾分鐘,記憶體佔用迅速超過了3GB!為什麽會這樣呢?我們使用的是嚴格版本的foldl'(後面的撇號 ' 表示它是嚴格的),但它只在“Weak Head Normal Form”(WHNF)中是嚴格的,也就是說,它在元組累加器中是嚴格的,但在實際的值中不是嚴格的!

這很討厭,因為這意味著我們構造了一大堆巨大的加法操作,但只有在整個文件遍歷結束後才進行求值!有時候,懶惰求值就會像這樣偷偷地給我們挖坑。如果不注意,這種記憶體泄漏很容易就會搞垮你的Web伺服器。

90MB測試文件

改正這一點只需告訴GHC在每次遍歷時對內容進行嚴格求值。最容易的方法就是利用BangPatterns擴展,我們可以在參數列表中用 ! 來強迫在每次函數執行時進行求值。下面是新版本的go:

這一點小改動帶來了近乎瘋狂的性能提升。新的性能數據如下:

90MB測試文件

好,現在記憶體方面已經好很多了,90MB文件只需要使用幾個MB的記憶體,意味著文件內容是以流的形式處理的!即使仍然有懶惰求值的坑,但我們把懶惰限制在了正確的局部位置,因此它自然地帶來了流式處理!流式處理的原因是,readFile實際上是懶惰IO,有時候對於Web伺服器等情況而言,這種方式是非常自然的,因為你永遠無法確定IO何時發生,而在我們的例子中,它帶來了非常好的記憶體佔用量。

使用ByteStrings進一步優化

暫時我們可以不用考慮記憶體了,那麽回過頭來考慮一下性能問題!我能想到的一種方案就是用ByteString取代String。使用String意味著我們在讀取文件時隱含地進行了解碼,這需要花費時間,而且對一切都使用鏈表也會造成額外開銷。這樣做並不能從批量讀取或緩衝中得到任何好處。

修改方式實際上非常簡單。bytestring包提供了一個模塊:Data.ByteString.Lazy.Char8,它提供了一系列操作,可以將懶惰的ByteString當作由字元組成的字元串來處理,同時依然保留ByteString帶來的性能優勢。注意,它並不會驗證每個字節是否為有效的Character,也不會做任何解碼,所以我們需要自行保證傳遞正確的數據給它。默認情況下wc假設輸入為ASCII,所以這裡我們也可以安全地這樣假設。如果輸入是ASCII,那麽該模塊中的函數就非常合理了。

唯一的改動就是將Data.List的導入改成Data.ByteString.Lazy.Char8,然後將readFile和foldl'函數改成相應的ByteString版本:

這一點小改動將運行時間縮短到了將近一半!

90MB測試文件

顯然我們有了一些進展。記憶體使用量略微增加,但額外的開銷似乎依然是常量級別。不幸的是,我們比wc依然低了幾個數量級。我們來看看還能做什麽。

使用么半群

這裡我想做一點小實驗。現代的電腦通常有多個核心,而且新的電腦似乎核心數量增長要比處理器速度增長還要快,所以利用好這一點肯定會有優勢。

但是,像這種拆分計算的工作並不太容易。為了使用多個核心,我們需要將任務分解成小塊。理論上很容易,只需將文件拆分成小塊,然後將每個小塊分配給一個核心即可!但仔細想想就會發現問題:合並字元計數非常容易,只需計算每塊計數的總和即可。行數也一樣,但單詞數就有問題了!如果在某個單詞中間拆分,或者在連續的空格之間拆分會怎樣?為了合並單詞計數,我們需要跟蹤每塊的開頭和結尾的狀態,合並時需要考慮這些問題。我可不想做這些記錄的工作。

這時就輪到么半群出場了!么半群的結合律意味著,我們可以設計一個合法的么半群,能在這種並行處理的情況下正確工作。但是,真的能寫一個么半群來處理類似單詞數統計這種複雜的任務嗎?

當然可以!一眼看上去似乎這種情況並不適合使用么半群,但一系列計數問題都可以歸到同一個類別下,很幸運的是我以前做過類似的問題。簡單來說,我們需要統計一個序列從頭到尾的過程中,某個不變量改變的次數。我以前曾經做過這類么半群的通用形式,叫做flux么半群(http://hackage.haskell.org/package/flux-monoid)。我們需要做的就是,統計字元從空格變成非空格的次數。我們可以利用Flux么半群來表示它,但由於我們需要謹慎地處理嚴格性和性能,所以我要為這裡的問題定義一個特殊的Flux么半群。看下面:

這些類型只有在統計單詞數時才需要。

CharType表示給定的字元是否為空格;然後Flux類型表示一段文本塊,它的資料欄包括子一個字元是否為空格、整個塊中包含多少單詞,以及最後一個字元是否為空格。我們不保存實際的文本內容,對於本問題而言這些信息是不必要的。這裡UNPACK了Int,並將所有資料欄標記為嚴格,來保證不會遇到前面的懶惰元組的問題。使用嚴格數據類型意味著在計算時不需要使用BangPatterns了。

接下來需要一個半群,以及該類型的一個Monoid實例!

這裡的Unknown構造函數表示Monoidal么元,實際上我們可以不用它,而是用Maybe將Semigroupo提升為Monoid,但Maybe會給半群添加操作帶來不必要的懶惰性!所以為了簡單起見,我只是將其定義為類型的一部分。

這裡定義的()操作符用來檢查兩個文本塊的連接點是否發生在某個單詞的中間,如果發生了,就表明我們對同一個單詞的前半部分和後半部分統計了兩次,所以在統計單詞總數時要減去1,來保證平衡。

最後需要根據單個字元構建Flux對象。

這很簡單,非空格字元統計為“單詞”,所謂單詞就是以非空格開始並結束,所謂空白,就是一個長度為零的單詞,兩側被空格字元包圍。

似乎不是那麽明顯,但這些就足以用么半群的方式實現單詞統計了!

似乎能正常工作!

現在單詞數已經實現了,接下來需要么半群版本的字元數和行數。代碼如下:

沒問題!類似地,我們需要將單個字元變成Counts對象:

嘗試一下:

看起來不錯!你可以用喜歡的內容來證實這個么半群是正確的。

在繼續之前,我們在已有代碼中使用這個么半群,確保能獲得同樣的結果:

我們將一部分複雜的內容移動到了Counts類型中,這樣能大幅簡化實現。一般來說這樣做很好,因為測試單一數據類型比測試每個使用fold的地方要容易得多。

附帶的好處是,這一改變使得速度更快了!

來慶祝一下吧!

90MB測試文件

這個修改在時間和記憶體兩方面都獲得了非常好的結果……我承認我不知道這是為什麽,但意外之喜我就不挑剔了。很可能是因為我們使用了完全嚴格的數據結構,限制了某些地方的懶惰性;但我不敢確信。如果你知道為什麽,那麽請一定告訴我!

更新:guibou指出,這裡的Flux和Counts類型使用了UNPACK指令,而之前使用的是正常的ol'元組。顯然GHC有時候能夠UNPACK元組,但這裡似乎它並沒有。通過UNPACK我們節省了一些指針間接操作,也節省了記憶體!

使用內聯!

下一個任務就是將一些定義改成內聯!為什麽呢?因為需要性能時就要這麽做!我們可以用INLINE指令告訴GHC,函數的性能很重要,這樣它就會採用內聯方式;還可能會觸發更多的優化。

我還給countChar和flux函數添加了INLINE。我們來看看有沒有效果:

90MB測試文件

有意思的是,似乎內聯將執行時間縮短了75%!我不確定這是不是意外之喜,或者只是幸運而已,不過很不錯!儘管記憶體使用量上漲了一些,但還不至於達到擔心的程度。

現在與C語言比較的結果如下:

90MB測試文件

現在已經與wc很接近了,但我們但目標是縮小秒以下級別的差距,所以我想增加測試文件的尺寸,多運行幾次,看看有沒有新的發現。

我使用了543MB的純文本文件運行了幾次,以便預熱緩存。這一點十分重要,因為運行幾次之後運行時間整整下降了33%。我知道我的測試方法並不是完全“科學”,但它能夠很好地估計出效果。不論如何,在大文件上的測試結果如下:

543MB測試文件

這裡可以看出,我們已經非常接近了!考慮到我們使用的是支持垃圾回收的高級語言,而且代碼只有80行左右,我認為我們已經做得很好了!

使用核心

我們沒辦法使用多核心將這個任務完全並行化,因為整個操作是IO密集的,但我還是要試試看。

我們已經將問題表達成了一個么半群,也就是說分割計算應該相當容易了!這裡的難度在於讀取數據部分。如果將所有數據讀進來,再分隔成小塊,那就不得不將整個文件全部讀入記憶體,從而導致非常高的記憶體佔用量,也很可能會影響性能!我們也可以用流式方法來分割,但就得處理完第一塊之後才能處理第二塊。我想你應該明白問題在哪兒了。我的做法是,在每個核心上啟動一個線程,然後每個線程打開一個單獨的文件描述符。然後將文件描述符跳轉到各個互不重疊的塊的位置。

完整的代碼如下。我之前有沒有說過我很喜歡在Haskell中編寫並行代碼?

這裡涉及了很多東西,我盡量詳細地解釋一下。

我們可以從GHC.Conc中導入“能力”的數量(即能夠訪問的核心數量)。然後,在需要計數的文件上運行fileStat來獲得文件的字節數。然後使用整數除法來決定每個核心要處理多少字節。整數除法會向下取整,所以在處理剩餘的字節數時要格外小心。然後使用Control.Concurrent.Async提供的forConcurrently在每個核心上運行一個單獨的線程。

在每個線程內,我們檢查該線程是否在處理最後一塊文件,如果是,則應該一直讀取到EOF,從而避免前面提到的取整問題,否則就隻處理chunkSize字節。然後,將塊的尺寸和線程編號相乘,得到偏移量。然後以二進製方式打開文件,使用hSeek將描述符移動到偏移量的位置。然後只需簡單地讀入所需的字節數,然後使用與前面相同的邏輯進行fold。在所有線程處理完畢後,只需使用fold將每個塊的計數合並在一起即可。

有幾個地方使用了來增加額外的嚴格性,因為我們希望保證fold操作在各個線程中執行而不是在線程歸並之後再進行。也許我有點過度使用嚴格性標注了,但寫多一點總比找出哪裡漏了寫要容易得多。

我們來嘗試一下吧!

預熱緩存之後,在我的4核心、帶有SSD的MacBook Pro 2013版上分別運行了兩個版本幾次,然後平均結果:

543MB測試文件

看起來效果很好!我們實際上比某些手工優化了幾十年的C代碼還要快。當然這些結果要有條件地來看,很難說這裡是不是有某些緩存的因素。可能有多層磁盤緩存生效了。也許,多線程只有在從緩存中讀取文件時才有效果?

我做了很多測試,發現並行執行在某些存儲設備上會產生加速,但在一些存儲設備上甚至會變慢。所以你的情況可能不一樣。希望有SSD的專家能夠指出這裡的問題。不過不管怎麽說,這個結果讓我非常滿意。

更新:貌似的確有一些SSD的專家!Paul Tanner給我寫了一封郵件來解釋現代的NVME驅動器的確會從並行中受益,只要並行訪問的不是一個塊(這裡我們並沒有這樣做)。不幸的是,我的老MacBook沒有NVME驅動器,但這意味著,這段代碼在現代設備上可能會運行得更快。感謝Paul!

此外,該程序實際的用戶時間為4.22s(被分配到了4個核心上),這意味著從處理器周期的角度來看,並行版本實際上不如簡單版本有效,但能夠利用多個核心,能夠降低真實的運行時間。

處理Unicode

我們一直都在忽略一個問題:我們假設每個文件都是ASCII!而真實世界並非如此。許多文檔都是用UTF-8編碼的,也就是說,當且僅當文件隻包含有效的ASCII字元時,整個文件才和ASCII文件一樣。但是如果年輕人使用了表情符號,那就亂了。

這個問題有兩面性:首先,我們現在計算的是字節數而不是字元數,因為在ASCII的世界中,字元和字節在語義上是相同的。對於我們現在的代碼而言,如果它遇到UTF-8編碼的“皺眉”符號,那麽至少會被計算成兩個字元,而實際上應該計算成一個字元。好吧,也許我們應該嘗試進行解碼,但這件事說起來容易做起來難,因為我們分割文件的位置是任意挑選的,也就是說有可能會將“皺眉”符號分割到兩個塊中,導致非法編碼!真是噩夢啊。

這也是為什麽多線程wc也許不是個好主意,但我不會輕易放棄的。我將做一些假設:

輸入可以是ASCII或UTF-8編碼。當然還有其他流行的編碼方式,但根據我有限的經驗,絕大部分現代文本文件都採用兩者之一。實際上,有許多網站都在致力於讓UTF-8成為唯一的編碼格式。

我們僅把ASCII中的空格和換行當做空格和換行處理;MONGOLIAN VOWEL SEPARATOR等字元就不考慮了。

有了這兩個假設,我們可以看看UTF-8編碼定義,來嘗試解決問題。首先,從UTF-8規格中我們知道,它與ASCII完全向後兼容。這就是說,每個ASCII字元在UTF-8中的編碼就是字節本身。其次,我們知道,文件中的任何字節都不會與有效的ASCII字節衝突,從UTF-8的維基百科頁面(https://en.wikipedia.org/wiki/UTF-8)的這張表上就可以看出。後續字節開頭是“1”,而ASCII字節永遠不會以1開頭。

這兩個事實表明,我們不需要改變檢測“空格”的邏輯!絕無可能將空格或換行“分割”,因為它們都被編碼為單字節,我們也知道,不可能將其他代碼點的一部分錯誤地進行統計,因為它們的編碼與ASCII字節沒有交集。但是,我們需要改變字元計數的邏輯。

關於UTF-8的最後一點是,每個UTF-8編碼的代碼點都必然包含下述集合中的一個字節:0xxxxxxx,110xxxxx,1110xxxx,11110xxx。後續字節均以10開始,所以只要統計開頭不是10的所有字節,就能精確地將每個代碼點隻統計一次,即使從代碼點中間拆分也是如此!

將以上這些綜合起來,我們可以編寫一個逐字元進行處理的么半群,它既可以統計UTF-8的代碼點,也可以統計ASCII字元!

注意,理論上講Unicode的代碼點並不等價於“字元”,有許多代碼點(比如聲調符號)會與其他字元“融合”並顯示為一個字元,但據我所知,wc也沒有單獨考慮它們。

實際上,我們現在的Counts么半群不需要改動,只需要修改一下countChar函數:

這樣就好了!現在我們可以處理UTF-8和ASCII了,我們甚至都不需要知道處理的是什麽編碼,就能永遠給出正確的結果。

而wc,至少在我的MacBook上的這個版本,有一個-m選項用於在計數時處理多字節字元。進行幾次實驗就會發現,wc處理多字節字元會嚴重地拖慢處理速度(它會解碼每個字節);我們來看看我們的實現。(我已確認過,每次在大型UTF-8文件上運行都會得到相同的結果)

543MB文件

如我們猜測的那樣,我們已經遠遠超過了C!我們的新版本比簡單地統計每個字節要慢一些(因為現在要做一些額外的位檢查),所以最好還是在程序上加一個utf標記,以便在任何情況下都能達到最好的性能。

這篇文章發表後,Harendra Kumar提供了一條新的提升性能的技巧,從而獲得了更好的記憶體佔用量和性能,同時還能支持從stdin讀取流輸入!哇!代碼也十分優雅!

秘密就在streamly庫中。這個庫是個非常好的高級、高性能流處理庫。我以前見過它,但有了這次經歷,以後我一定會進一步了解它!閑話少說,直接上代碼。再次感謝Harendra Kumar提供的實現!

注意:這裡用的streamly版本7.10是直接從Github代碼庫中獲得的,很可能它很快就會被發不到hackage上。這段代碼還使用了幾個內部模塊,我希望看到,像這段代碼中的用例能夠證明,這些模塊應該暴露出來。

首先,我們要打開文件,這裡沒有什麽神秘的地方。

其次是流處理的代碼,我們從底向上來閱讀:

這一段從文件描述符中讀取字節塊放到Byte陣列的流中。使用Byte陣列可以比使用Lazy ByteString等更快!每1MB文件內容我們會使用一個單獨的陣列,這一點你可以根據情況調整。

這裡使用mapM在陣列上運行countBytes函數;countBytes本身會根據陣列創建流,然後使用我們的么半群字節計數器來運行流fold:

接下來,我們告訴streamly在陣列上並行運行map,從而實現讓每個線程處理一個1MB的文件塊。這裡將線程的數量限制在了核心數量。一旦讀入所有數據,就可以立即進行處理,我們的統計代碼沒有任何阻塞的理由,所以增加更多的線程只會給調度器帶來額外的負擔而已。

Streamly提供了許多流求值策略。這裡使用了aheadly,它可以並行處理流元素,但依然能保證輸出與輸入的順序相同。由於我們使用了么半群,所以只要它們能保證適當的順序,我們就可以用任何方式來實現計算:

此時我們已經統計了1MB的輸入塊,但我們依然需要累加所有輸入塊。這一點可以在另一個流fold中通過mappend實現:

就這些!來看看效果吧!

下面是非utf版本在543MB測試文件上的表現:

可以看到它更快,代價是佔用了大量記憶體。我認為可以通過改變分塊策略來減少記憶體用量。我們來試一下。下面是100KB分塊和1MB分塊的比較:

如我所料,我們可以用一點點性能來換取不錯的記憶體佔用量。對於這個結果我已經相當滿意了,不過你也可以繼續試驗其他的策略。

最後,我們在543MB測試文件上試一下UTF8版本。下面是結果:

我們依然比wc塊!儘管在最終版本中可能需要減少一些記憶體佔用!

總體而言,我認為力流版本是最好的,它從高層著手,非常易讀,而且可以支持從任意文件描述符讀取,其中包括stdin,這是wc非常常見的用例。streamly太酷了。

總結

那麽,我們這個支持垃圾回收的、基於運行時的高級語言Haskell究竟怎樣?我要說,它非常棒!我們的單核lazy-bytestring版本wc就達到了非常接近的性能。換成多核心之後就能超過wc!我們應當考慮在沒有磁盤緩存預熱的情況下的性能,但純粹就性能而言,我們成功地構建了比C語言還快的東西!而流版本應該不會依賴於磁盤緩存。

作為一門語言,Haskell並不完美,但如果我能寫出性能媲美C語言的程序,同時保持使用高層邏輯,使用完全支持類型的代碼,那我認為就非常好了。

原文:https://chrispenner.ca/posts/wc

本文為 CSDN 翻譯,轉載請注明來源出處。

【END】

熱 文推 薦

獲得更多的PTT最新消息
按讚加入粉絲團