我優化多年的 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來獲得計數。

<code>1stupid :: FilePath -> IO (Int, Int, Int)
2stupid fp = do
3 contents 4 return (length s, length (words s), length (lines s))
/<code>

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

90MB的測試文件

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

略微好一點的實現

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

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

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

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

<code> 1import Data.List
2import Data.Char
3
4simpleFold :: FilePath -> IO (Int, Int, Int)
5simpleFold fp = do
6 countFile  readFile fp
7
8countFile :: String -> (Int, Int, Int)
9countFile s =
10 let (cs, ws, ls, _) = foldl' go (0, 0, 0, False) s
11 in (cs, ws, ls)
12 where
13 go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)
14 go (cs, ws, ls, wasSpace) c =
15 let addLine | c == '\\n' = 1
16 | otherwise = 0
17 addWord | wasSpace = 0
18 | isSpace c = 1
19 | otherwise = 0
20 in (cs + 1, ws + addWord, ls + addLine, isSpace c)
/<code>

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

程序運行花了幾分鐘，內存佔用迅速超過了3GB！為什麼會這樣呢？我們使用的是嚴格版本的foldl'（後面的撇號 ' 表示它是嚴格的），但它只在“Weak Head Normal Form”（WHNF）中是嚴格的，也就是說，它在元組累加器中是嚴格的，但在實際的值中不是嚴格的！

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

90MB測試文件

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

<code> 1{-# LANGUAGE BangPatterns #-}
2
3...
4 go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)
5 go (!cs, !ws, !ls, !wasSpace) c =
6 let addLine | c == '\\n' = 1
7 | otherwise = 0
8 addWord | wasSpace = 0
9 | isSpace c = 1
10 | otherwise = 0
11 in (cs + 1, ws + addWord, ls + addLine, isSpace c)
/<code>

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

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版本：

<code> 1import Data.Char
2import qualified Data.ByteString.Lazy.Char8 as BS
3
4simpleFold :: FilePath -> IO (Int, Int, Int)
5simpleFold fp = do
6 simpleFoldCountFile  BS.readFile fp
7
8simpleFoldCountFile :: BS.ByteString -> (Int, Int, Int)
9simpleFoldCountFile s =
10 let (cs, ws, ls, _) = BS.foldl' go (0, 0, 0, False) s
11 in (cs, ws, ls)
12 where
13 go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool) 

14 go (!cs, !ws, !ls, !wasSpace) c =
15 let addLine | c == '\\n' = 1
16 | otherwise = 0
17 addWord | wasSpace = 0
18 | isSpace c = 1
19 | otherwise = 0
20 in (cs + 1, ws + addWord, ls + addLine, isSpace c)
/<code>

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

90MB測試文件

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

使用么半群

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

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

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

當然可以！一眼看上去似乎這種情況並不適合使用么半群，但一系列計數問題都可以歸到同一個類別下，很幸運的是我以前做過類似的問題。簡單來說，我們需要統計一個序列從頭到尾的過程中，某個不變量改變的次數。我以前曾經做過這類么半群的通用形式，叫做flux么半群（

<code>1data CharType = IsSpace | NotSpace
2 deriving Show
3
4data Flux =
5 Flux !CharType
6 {-# UNPACK #-} !Int
7 !CharType
8 | Unknown
9 deriving Show
/<code>

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

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

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

<code>1instance Semigroup Flux where
2 Unknown <> x = x
3 x <> Unknown = x 

4 Flux l n NotSpace <> Flux NotSpace n' r = Flux l (n + n' - 1) r
5 Flux l n _ <> Flux _ n' r = Flux l (n + n') r
6
7instance Monoid Flux where
8 mempty = Unknown
/<code>

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

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

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

<code>1flux :: Char -> Flux
2flux c | isSpace c = Flux IsSpace 0 IsSpace
3 | otherwise = Flux NotSpace 1 NotSpace
/<code>

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

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

<code>1>>> foldMap flux "testing one two three"
2Flux NotSpace 4 NotSpace 

3
4>>> foldMap flux "testing on" <> foldMap flux "e two three"
5Flux NotSpace 4 NotSpace
6
7>>> foldMap flux "testing one " <> foldMap flux " two three"
8Flux NotSpace 4 NotSpace
/<code>

似乎能正常工作！

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

<code> 1data Counts =
2 Counts { charCount :: {-# UNPACK #-} !Int
3
4 , wordCount :: !Flux
5 , lineCount :: {-# UNPACK #-} !Int
6 }
7 deriving (Show)
8
9instance Semigroup Counts where
10 (Counts a b c) <> (Counts a' b' c') = Counts (a + a') (b <> b') (c + c')
11
12instance Monoid Counts where
13 mempty = Counts 0 mempty 0
/<code>

沒問題！類似地，我們需要將單個字符變成Counts對象：

<code>1countChar :: Char -> Counts
2countChar c =
3 Counts { charCount = 1
4 , wordCount = flux c
5 , lineCount = if (c == '\\n') then 1 else 0
6 }
/<code>

嘗試一下：

<code>1>>> foldMap countChar "one two\\nthree"
2Counts {charCount = 13, wordCount = Flux NotSpace 3 NotSpace, lineCount = 1}/<code>

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

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

<code> 1module MonoidBSFold where
2
3import Data.Char
4import qualified Data.ByteString.Lazy.Char8 as BS
5
6monoidBSFold :: FilePath -> IO Counts
7monoidBSFold paths = monoidFoldFile  BS.readFile fp
8
9monoidFoldFile :: BS.ByteString -> Counts
10monoidFoldFile = BS.foldl' (\\a b -> a <> countChar b) mempty/<code>

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

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

來慶祝一下吧！

90MB測試文件

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

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

使用內聯！

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

<code>1monoidBSFold :: FilePath -> IO Counts
2monoidBSFold paths = monoidBSFoldFile  BS.readFile fp
3{-# INLINE monoidBSFold #-}
4
5monoidBSFoldFile :: BS.ByteString -> Counts
6monoidBSFoldFile = BS.foldl' (\\a b -> a <> countChar b) mempty
7{-# INLINE monoidBSFoldFile #-}
8
/<code>

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

90MB測試文件

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

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

90MB測試文件

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

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

543MB測試文件

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

使用核心

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

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

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

<code> 1import Types
2import Control.Monad
3import Data.Traversable
4import Data.Bits
5import GHC.Conc (numCapabilities)
6import Control.Concurrent.Async
7import Data.Foldable
8import System.IO
9import System.Posix.Files
10import qualified Data.ByteString.Lazy.Char8 as BL
11import Data.ByteString.Internal (c2w)
12import GHC.IO.Handle 

13
14multiCoreCount :: FilePath -> IO Counts
15multiCoreCount fp = do
16 putStrLn ("Using available cores: " <> show numCapabilities)
17 size  getFileStatus fp
18 let chunkSize = fromIntegral (size `div` numCapabilities)
19 fold  (forConcurrently [0..numCapabilities-1] $ \\n -> do
20 -- Take all remaining bytes on the last capability due to integer division anomolies
21 let limiter = if n == numCapabilities - 1
22 then id
23 else BL.take (fromIntegral chunkSize)
24 let offset = fromIntegral (n * chunkSize)
25 fileHandle 26 hSeek fileHandle AbsoluteSeek offset
27 countBytes . limiter  BL.hGetContents fileHandle)
28{-# INLINE handleSplitUTF #-}
29
30countBytes :: BL.ByteString -> Counts
31countBytes = BL.foldl' (\\a b -> a <> countChar b) mempty
32{-# INLINE countBytes #-}
33
/<code>

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

我們可以從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函數：

<code> 1import Data.Bits
2import Data.ByteString.Internal (c2w)
3countByte :: Char -> Counts
4countByte c =
5 Counts {
6 -- Only count bytes at the START of a codepoint, not continuation bytes
7 charCount = if (bitAt 7 && not (bitAt 6)) then 0 else 1
8 , wordCount = flux c
9 , lineCount = if (c == '\\n') then 1 else 0
10 }
11 where
12 bitAt = testBit (c2w c)
13{-# INLINE countByte #-}
/<code>

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

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

543MB文件

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

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

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

<code> 1module Streaming where
2
3import Types
4import Data.Traversable
5import GHC.Conc (numCapabilities)
6import System.IO (openFile, IOMode(..))
7import qualified Streamly as S
8import qualified Streamly.Data.String as S
9import qualified Streamly.Prelude as S
10import qualified Streamly.Internal.Memory.Array as A
11import qualified Streamly.Internal.FileSystem.Handle as FH
12
13streamingBytestream :: FilePath -> IO Counts
14streamingBytestream fp = do
15 src 16 S.foldl' mappend mempty
17 $ S.aheadly
18 $ S.maxThreads numCapabilities
19 $ S.mapM countBytes
20 $ FH.toStreamArraysOf 1024000 src
21 where
22 countBytes =
23 S.foldl' (\\acc c -> acc <> countByte c) mempty
24 . S.decodeChar8
25 . A.toStream
26
27{-# INLINE streamingBytestream #-}
/<code>

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

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

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

<code>1FH.toStreamArraysOf 1024000 src 

/<code>

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

<code>1S.mapMcountBytes
/<code>

這裡使用mapM在數組上運行countBytes函數；countBytes本身會根據數組創建流，然後使用我們的么半群字節計數器來運行流fold：

<code>1countBytes =
2 S.foldl' (\\acc c -> acc <> countByte c) mempty
3 . S.decodeChar8
4 . A.toStream
/<code>

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

<code>1S.maxThreads 
numCapabilities
/<code>

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

<code>1S.aheadly/<code>

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

<code>1S.foldl' mappend mempty
/<code>

就這些！來看看效果吧！

下面是非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】

閱讀更多 CSDN 的文章

關鍵字: C語言 CSDN Mac電腦