12.03 70 行 Go 代碼打敗 C

作為一名程序員，應當具有挑戰精神，才能寫出“完美”的代碼。挑戰歷史悠久的C語言版wc命令一向是件很有趣的事。今天，我們就來看一下如何用70行的Go代碼打敗C語言版wc命令。

作者 | Ajeet D'Souza

譯者 | 蘇本如，責編 | maozz

出品 | CSDN（ID：CSDNnews）

Chris Penner最近發表的這篇文章——用80行Haskell代碼擊敗C（https://chrispenner.ca/posts/wc），在互聯網上引起了相當大的爭議，從那以後，嘗試用各種不同的編程語言來挑戰歷史悠久的C語言版wc命令（譯者注：用於統計一個文件中的行數、字數、字節數或字符數的程序命令）就變成了一種大家趨之若鶩的遊戲，可以用來挑戰的編程語言列表如下：

• Ada

• C

• Common Lisp

• Dyalog APL

• Futhark

• Haskell

• Rust

今天，我們將用Go語言來進行這個wc命令的挑戰。作為一種具有優秀併發原語的編譯語言，要獲得與C語言相當的性能應該很容易。

雖然wc命令被設計為可以從標準輸入設備（stdin）讀取、處理非ASCII文本編碼和解析命令行標誌（wc命令的幫助可以參考這裡），但我們在這裡不會這樣做。相反，像上面提到的文章一樣，我們將集中精力使我們的實現儘可能簡單。

如果你想看這篇文章用到的源代碼，可以參考這裡（https://github.com/ajeetdsouza/blog-wc-go）。

比較基準

我們將使用GNU的time工具包，針對兩種語言編寫的wc命令，從運行耗費時間和最大常駐內存大小兩個方面來進行比較。

$ /usr/bin/time -f "%es %MKB" wc test.txt

用來比較的C語言版的wc命令和在Chris Penner的原始文章裡用到的版本相同，使用gcc 9.2.1和-O3編譯。對於我們自己的實現，我們將使用go 1.13.4（我也嘗試過gccgo，但結果不是很好）來編譯。並且，我們將使用以下系統配置作為運行的基準：

• 英特爾酷睿[email protected] 處理器（2個物理核，4個線程）

• 4+4 GB內存@2133 MHz

• 240 GB M.2固態硬盤

• Fedora 31 Linux發行版

為了確保公平的比較，所有實現都將使用16 KB的緩衝區來讀取輸入。輸入將是兩個大小分別為100 MB和1GB，使用us-ascii編碼的文本文件。

原始實現（wc-naïve）

解析參數很容易，因為我們只需要文件路徑，代碼如下：

if len(os.Args) < 2 {
panic("no file path specified")
}
filePath := os.Args[1]
file, err := os.Open(filePath)
if err != nil {
panic(err) 
}
defer file.Close

我們將按字節遍歷文本和跟蹤狀態。幸運的是，在這種情況下，我們只需要知道兩種狀態：

• 前一個字節是空白；

• 前一個字節不是空白。

當從空白字符變為非空白字符時，我們給字計數器（word counter）加一。這種方法允許我們直接從字節流中讀取，從而保持很低的內存消耗。

const bufferSize = 16 * 1024
reader := bufio.NewReaderSize(file, bufferSize)
lineCount := 0
wordCount := 0
byteCount := 0
prevByteIsSpace := true
for {
b, err := reader.ReadByte
if err != nil {
 
if err == io.EOF {
break
} else {
panic(err)
}
}
byteCount++
switch b {
case '\\n':
lineCount++
prevByteIsSpace = true
case ' ', '\\t', '\\r', '\\v', '\\f':
prevByteIsSpace = true
default:
if prevByteIsSpace {
wordCount++
prevByteIsSpace = false
}
}
}

要顯示結果，我們將使用本機println函數。在我的測試中，導入fmt庫（注：Go語言的格式化庫）會導致可執行文件的大小增加大約400 KB！

println(lineCount, wordCount, byteCount, file.Name) 

讓我們運行這個程序，然後看看它與C語言版wc的運行結果比較（見下表）：

好消息是，我們的第一次嘗試已經使我們在性能上接近C語言的版本。實際上，我們在內存使用方面做得比C更好！

拆分輸入（wc-chunks）

雖然緩衝I/O讀取對於提高性能至關重要，但調用ReadByte並檢查循環中的錯誤會帶來很多不必要的開銷。我們可以通過手動緩衝讀取調用而不是依賴bufio.Reader來避免這種情況。

為此，我們將把輸入分成可以單獨處理的緩衝塊(chunk)。幸運的是，要處理一個chunk，我們只需要知道前一個chunk的最後一個字符是否是空白。

讓我們編寫幾個工具函數：

type Chunk struct {
PrevCharIsSpace bool
Buffer byte
}
type Count struct {
LineCount int
WordCount int
}
func GetCount(chunk Chunk)Count{
count := Count{}
prevCharIsSpace := chunk.PrevCharIsSpace 
for _, b := range chunk.Buffer {
switch b {
case '\\n':
count.LineCount++
prevCharIsSpace = true
case ' ', '\\t', '\\r', '\\v', '\\f':
prevCharIsSpace = true
default:
if prevCharIsSpace {
prevCharIsSpace = false
count.WordCount++
}
}
}
return count
}
func IsSpace(b byte)bool{
return b == ' ' || b == '\\t' || b == '\\n' || b == '\\r' || b == '\\v' || b == '\\f'
}

現在，我們可以將輸入分成幾個chunk（塊），並將它們傳送給GetCount函數。

totalCount := Count{} 
lastCharIsSpace := true
const bufferSize = 16 * 1024
buffer := make([]byte, bufferSize)
for {
bytes, err := file.Read(buffer)
if err != nil {
if err == io.EOF {
break
} else {
panic(err)
}
}
count := GetCount(Chunk{lastCharIsSpace, buffer[:bytes]})
lastCharIsSpace = IsSpace(buffer[bytes-1])
totalCount.LineCount += count.LineCount
totalCount.WordCount += count.WordCount
}

要獲取字節數，我們可以進行一次系統調用來查詢文件大小：

fileStat, err := file.Stat
if err != nil {
panic(err)
}
byteCount := fileStat.Size 

現在我們已經完成了，讓我們看看它與C語言版wc的運行結果比較（見下表）：

從上表結果看，我們在這兩個方面都超過了C語言版wc命令，而且我們甚至還沒有開始並行化我們的程序。tokei報告顯示這個程序只有70行代碼！

使用channel並行化（wc-channel）

不可否認，將wc這樣的命令改成並行化運行有點過分了，但是讓我們看看我們到底能走多遠。Chris Penner的原始文章裡的測試採用了並行化來讀取輸入文件，雖然這樣做改進了運行時，但文章的作者也承認，並行化讀取帶來的性能提高可能僅限於某些類型的存儲，而在其他類型的存儲則有害無益。

對於我們的實現，我們希望我們的代碼能夠在所有設備上執行，所以我們不會這樣做。我們將建立兩個channel – chunks和counts。每個worker線程將從chunks中讀取和處理數據，直到channel關閉，然後將結果寫入counts中。

func ChunkCounter(chunks {
totalCount := Count{}
for {
chunk, ok := 
if !ok {
break
}
count := GetCount(chunk)
totalCount.LineCount += count.LineCount 
totalCount.WordCount += count.WordCount
}
counts 
}

我們將為每個邏輯CPU核心生成一個worker線程：

numWorkers := runtime.NumCPU
chunks := make(chan Chunk)
counts := make(chan Count)
for i := 0; i < numWorkers; i++ {
go ChunkCounter(chunks, counts)
}

現在，我們循環運行，從磁盤讀取並將作業分配給每個worker：

const bufferSize = 16 * 1024
lastCharIsSpace := true
for {
buffer := make([]byte, bufferSize)
bytes, err := file.Read(buffer)
if err != nil {
if err == io.EOF {
break
} else { 
panic(err)
}
}
chunks 
lastCharIsSpace = IsSpace(buffer[bytes-1])
}
close(chunks)

一旦完成，我們可以簡單地將每個worker得到的計數（count）彙總來得到總的word count：

totalCount := Count{}
for i := 0; i < numWorkers; i++ {
count := 
totalCount.LineCount += count.LineCount
totalCount.WordCount += count.WordCount
}
close(counts)

讓我們運行它，並且看看它與C語言版wc的運行結果比較（見下表）：

從上表可以看出，我們的wc現在快了很多，但在內存使用方面出現了相當大的倒退。特別要注意我們的輸入循環如何在每次迭代中分配內存的！channel是共享內存的一個很好的抽象，但是對於某些用例來說，簡單地不使用channel通道可以極大地提高性能。

使用Mutex並行化（wc-mutex）

在本節中，我們將允許每個worker讀取文件，並使用sync.Mutex互斥鎖確保讀取不會同時發生。我們可以創建一個新的struct來處理這個問題：

type FileReader struct {
File *os.File
LastCharIsSpace bool
mutex sync.Mutex
}
func (fileReader *FileReader) ReadChunk(buffer []byte)(Chunk, error){
fileReader.mutex.Lock
defer fileReader.mutex.Unlock
bytes, err := fileReader.File.Read(buffer)
if err != nil {
return Chunk{}, err
}
chunk := Chunk{fileReader.LastCharIsSpace, buffer[:bytes]}
fileReader.LastCharIsSpace = IsSpace(buffer[bytes-1])
return chunk, nil
}

然後，我們重寫worker函數，讓它直接從文件中讀取：

func FileReaderCounter(fileReader *FileReader, counts chan Count){
const bufferSize = 16 * 1024 
buffer := make([]byte, bufferSize)
totalCount := Count{}
for {
chunk, err := fileReader.ReadChunk(buffer)
if err != nil {
if err == io.EOF {
break
} else {
panic(err)
}
}
count := GetCount(chunk)
totalCount.LineCount += count.LineCount
totalCount.WordCount += count.WordCount
}
counts 
}

與前面一樣，我們現在可以為每個CPU核心生成一個worker線程：

fileReader := &FileReader{
File: file,
LastCharIsSpace: true,
}
counts := make(chan Count) 
for i := 0; i < numWorkers; i++ {
go FileReaderCounter(fileReader, counts)
}
totalCount := Count{}
for i := 0; i < numWorkers; i++ {
count := 
totalCount.LineCount += count.LineCount
totalCount.WordCount += count.WordCount
}
close(counts)

讓我們運行它，然後看看它與C語言版wc的運行結果比較（見下表）：

可以看出，我們的並行實現運行速度比wc快了4.5倍以上，而且內存消耗更低！這是非常重要的，特別是如果你認為Go是一種自動垃圾收集語言的話。

結束語

雖然本文絕不暗示Go語言比C語言強，但我希望它能夠證明Go語言可以作為一種系統編程語言替代C語言。

如果你有任何建議和問題，歡迎在評論區留言。

原文：https://ajeetdsouza.github.io/blog/posts/beating-c-with-70-lines-of-go/

本文為 CSDN 翻譯，轉載請註明來源出處。

【End】

閱讀更多 CSDN 的文章

關鍵字: Haskell 打敗 Fedora