文章發(fā)布于公號【數(shù)智物語】?（ID：decision_engine）歌豺，關(guān)注公號不錯過每一篇干貨顶岸。
作者?|?Ajeet D'Souza
譯者 |?蘇本如腔彰，責編 | maozz
出品 | CSDN（ID：CSDNnews）
作為一名程序員，應(yīng)當具有挑戰(zhàn)精神辖佣，才能寫出“完美”的代碼霹抛。挑戰(zhàn)歷史悠久的C語言版wc命令一向是件很有趣的事。今天卷谈，我們就來看一下如何用70行的Go代碼打敗C語言版wc命令杯拐。
以下為譯文：
Chris Penner最近發(fā)表的這篇文章——用80行Haskell代碼擊敗C（https://chrispenner.ca/posts/wc），在互聯(lián)網(wǎng)上引起了相當大的爭議，從那以后端逼，嘗試用各種不同的編程語言來挑戰(zhàn)歷史悠久的C語言版wc命令（譯者注：用于統(tǒng)計一個文件中的行數(shù)朗兵、字數(shù)、字節(jié)數(shù)或字符數(shù)的程序命令）就變成了一種大家趨之若鶩的游戲顶滩，可以用來挑戰(zhàn)的編程語言列表如下：
1. Ada
2. C
3. Common Lisp
4. Dyalog APL
5. Futhark
6. Haskell
7. Rust
今天余掖，我們將用Go語言來進行這個wc命令的挑戰(zhàn)。作為一種具有優(yōu)秀并發(fā)原語的編譯語言礁鲁，要獲得與C語言相當?shù)男阅軕?yīng)該很容易盐欺。
雖然wc命令被設(shè)計為可以從標準輸入設(shè)備（stdin）讀取、處理非ASCII文本編碼和解析命令行標志（wc命令的幫助可以參考這里）仅醇，但我們在這里不會這樣做冗美。相反，像上面提到的文章一樣析二，我們將集中精力使我們的實現(xiàn)盡可能簡單粉洼。
如果你想看這篇文章用到的源代碼，可以參考這里（https://github.com/ajeetdsouza/blog-wc-go）叶摄。
01
比較基準
我們將使用GNU的time工具包属韧，針對兩種語言編寫的wc命令，從運行耗費時間和最大常駐內(nèi)存大小兩個方面來進行比較蛤吓。
$?/usr/bin/time-f"%es?%MKB"wc?test.txt
用來比較的C語言版的wc命令和在Chris Penner的原始文章里用到的版本相同挫剑，使用gcc 9.2.1和-O3編譯。對于我們自己的實現(xiàn)柱衔，我們將使用go 1.13.4（我也嘗試過gccgo，但結(jié)果不是很好）來編譯愉棱。并且唆铐，我們將使用以下系統(tǒng)配置作為運行的基準：
1. 英特爾酷睿i5-6200U@2.30GHz 處理器（2個物理核，4個線程）
2. 4+4 GB內(nèi)存@2133 MHz
3. 240 GB M.2固態(tài)硬盤
4. Fedora 31 Linux發(fā)行版
為了確保公平的比較奔滑，所有實現(xiàn)都將使用16 KB的緩沖區(qū)來讀取輸入艾岂。輸入將是兩個大小分別為100 MB和1GB，使用us-ascii編碼的文本文件朋其。
02
原始實現(xiàn)（wc-na?ve）
解析參數(shù)很容易王浴，因為我們只需要文件路徑，代碼如下：
iflen(os.Args)?<2{
panic("no?file?path?specified")
}
filePath?:=?os.Args[1]
file,?err?:=?os.Open(filePath)
iferr?!=nil{
panic(err)
}
deferfile.Close()
我們將按字節(jié)遍歷文本和跟蹤狀態(tài)梅猿。幸運的是氓辣，在這種情況下，我們只需要知道兩種狀態(tài)：
1. 前一個字節(jié)是空白袱蚓；
2. 前一個字節(jié)不是空白钞啸。
當從空白字符變?yōu)榉强瞻鬃址麜r，我們給字計數(shù)器（word counter）加一。這種方法允許我們直接從字節(jié)流中讀取体斩，從而保持很低的內(nèi)存消耗梭稚。
constbufferSize?=16*1024
reader?:=?bufio.NewReaderSize(file,?bufferSize)
lineCount?:=0
wordCount?:=0
byteCount?:=0
prevByteIsSpace?:=true
for{
b,?err?:=?reader.ReadByte()
iferr?!=nil{
iferr?==?io.EOF?{
break
}else{
panic(err)
}
}
byteCount++
switchb?{
case'\n':
lineCount++
prevByteIsSpace?=true
case'?','\t','\r','\v','\f':
prevByteIsSpace?=true
default:
ifprevByteIsSpace?{
wordCount++
prevByteIsSpace?=false
}
}
}
要顯示結(jié)果，我們將使用本機println（）函數(shù)絮吵。在我的測試中弧烤，導(dǎo)入fmt庫（注：Go語言的格式化庫）會導(dǎo)致可執(zhí)行文件的大小增加大約400 KB！
println(lineCount,?wordCount,?byteCount,file.Name())
讓我們運行這個程序蹬敲，然后看看它與C語言版wc的運行結(jié)果比較（見下表）：
好消息是暇昂，我們的第一次嘗試已經(jīng)使我們在性能上接近C語言的版本。實際上粱栖，我們在內(nèi)存使用方面做得比C更好话浇！
03
拆分輸入（wc-chunks）
雖然緩沖I/O讀取對于提高性能至關(guān)重要，但調(diào)用ReadByte（）并檢查循環(huán)中的錯誤會帶來很多不必要的開銷闹究。我們可以通過手動緩沖讀取調(diào)用而不是依賴bufio.Reader來避免這種情況幔崖。
為此项鬼，我們將把輸入分成可以單獨處理的緩沖塊(chunk)版确。幸運的是，要處理一個chunk磨隘，我們只需要知道前一個chunk的最后一個字符是否是空白价认。
讓我們編寫幾個工具函數(shù)：
typeChunkstruct{
PrevCharIsSpacebool
Buffer??????????[]byte
}
typeCountstruct{
LineCountint
WordCountint
}
funcGetCount(chunk?Chunk)Count{
count?:=?Count{}
prevCharIsSpace?:=?chunk.PrevCharIsSpace
for_,?b?:=rangechunk.Buffer?{
switchb?{
case'\n':
count.LineCount++
prevCharIsSpace?=true
case'?','\t','\r','\v','\f':
prevCharIsSpace?=true
default:
ifprevCharIsSpace?{
prevCharIsSpace?=false
count.WordCount++
}
}
}
returncount
}
funcIsSpace(bbyte)bool{
returnb?=='?'||?b?=='\t'||?b?=='\n'||?b?=='\r'||?b?=='\v'||?b?=='\f'
}
現(xiàn)在嗅定，我們可以將輸入分成幾個chunk（塊），并將它們傳送給GetCount函數(shù)用踩。
totalCount?:=?Count{}
lastCharIsSpace?:=true
constbufferSize?=16*1024
buffer?:=make([]byte,?bufferSize)
for{
bytes,?err?:=?file.Read(buffer)
iferr?!=nil{
iferr?==?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
}
要獲取字節(jié)數(shù)渠退，我們可以進行一次系統(tǒng)調(diào)用來查詢文件大小：
fileStat,?err?:=?file.Stat()
iferr?!=nil{
panic(err)
}
byteCount?:=?fileStat.Size()
現(xiàn)在我們已經(jīng)完成了脐彩，讓我們看看它與C語言版wc的運行結(jié)果比較（見下表）：
從上表結(jié)果看碎乃，我們在這兩個方面都超過了C語言版wc命令，而且我們甚至還沒有開始并行化我們的程序惠奸。tokei報告顯示這個程序只有70行代碼梅誓！
04
使用channel并行化（wc-channel）
不可否認，將wc這樣的命令改成并行化運行有點過分了佛南，但是讓我們看看我們到底能走多遠梗掰。Chris Penner的原始文章里的測試采用了并行化來讀取輸入文件，雖然這樣做改進了運行時嗅回，但文章的作者也承認及穗，并行化讀取帶來的性能提高可能僅限于某些類型的存儲，而在其他類型的存儲則有害無益妈拌。
對于我們的實現(xiàn)拥坛，我們希望我們的代碼能夠在所有設(shè)備上執(zhí)行蓬蝶，所以我們不會這樣做。我們將建立兩個channel – chunks和counts猜惋。每個worker線程將從chunks中讀取和處理數(shù)據(jù)丸氛，直到channel關(guān)閉，然后將結(jié)果寫入counts中著摔。
funcChunkCounter(chunks?<-chanChunk,?countschan<-?Count){
totalCount?:=?Count{}
for{
chunk,?ok?:=?<-chunks
if!ok?{
break
}
count?:=?GetCount(chunk)
totalCount.LineCount?+=?count.LineCount
totalCount.WordCount?+=?count.WordCount
}
counts?<-?totalCount
}
我們將為每個邏輯CPU核心生成一個worker線程：
numWorkers?:=?runtime.NumCPU()
chunks?:=make(chanChunk)
counts?:=make(chanCount)
fori?:=0;?i?<?numWorkers;?i++?{
goChunkCounter(chunks,?counts)
}
現(xiàn)在缓窜，我們循環(huán)運行，從磁盤讀取并將作業(yè)分配給每個worker：
constbufferSize?=16*1024
lastCharIsSpace?:=true
for{
buffer?:=make([]byte,?bufferSize)
bytes,?err?:=?file.Read(buffer)
iferr?!=nil{
iferr?==?io.EOF?{
break
}else{
panic(err)
}
}
chunks?<-?Chunk{lastCharIsSpace,?buffer[:bytes]}
lastCharIsSpace?=?IsSpace(buffer[bytes-1])
}
close(chunks)
一旦完成谍咆，我們可以簡單地將每個worker得到的計數(shù)（count）匯總來得到總的word count：
totalCount?:=?Count{}
fori?:=0;?i?<?numWorkers;?i++?{
count?:=?<-counts
totalCount.LineCount?+=?count.LineCount
totalCount.WordCount?+=?count.WordCount
}
close(counts)
讓我們運行它禾锤，并且看看它與C語言版wc的運行結(jié)果比較（見下表）：
從上表可以看出，我們的wc現(xiàn)在快了很多摹察，但在內(nèi)存使用方面出現(xiàn)了相當大的倒退恩掷。特別要注意我們的輸入循環(huán)如何在每次迭代中分配內(nèi)存的！channel是共享內(nèi)存的一個很好的抽象供嚎，但是對于某些用例來說黄娘，簡單地不使用channel通道可以極大地提高性能。
05
使用Mutex并行化（wc-mutex）
在本節(jié)中克滴，我們將允許每個worker讀取文件逼争，并使用sync.Mutex互斥鎖確保讀取不會同時發(fā)生。我們可以創(chuàng)建一個新的struct來處理這個問題：
typeFileReaderstruct{
File????????????*os.File
LastCharIsSpacebool
mutex???????????sync.Mutex
}
func(fileReader?*FileReader)ReadChunk(buffer?[]byte)(Chunk,?error){
fileReader.mutex.Lock()
deferfileReader.mutex.Unlock()
bytes,?err?:=?fileReader.File.Read(buffer)
iferr?!=nil{
returnChunk{},?err
}
chunk?:=?Chunk{fileReader.LastCharIsSpace,?buffer[:bytes]}
fileReader.LastCharIsSpace?=?IsSpace(buffer[bytes-1])
returnchunk,nil
}
然后劝赔，我們重寫worker函數(shù)誓焦，讓它直接從文件中讀取：
funcFileReaderCounter(fileReader?*FileReader,?countschanCount){
constbufferSize?=16*1024
buffer?:=make([]byte,?bufferSize)
totalCount?:=?Count{}
for{
chunk,?err?:=?fileReader.ReadChunk(buffer)
iferr?!=nil{
iferr?==?io.EOF?{
break
}else{
panic(err)
}
}
count?:=?GetCount(chunk)
totalCount.LineCount?+=?count.LineCount
totalCount.WordCount?+=?count.WordCount
}
counts?<-?totalCount
}
與前面一樣着帽，我們現(xiàn)在可以為每個CPU核心生成一個worker線程：
fileReader?:=?&FileReader{
File:????????????file,
LastCharIsSpace:true,
}
counts?:=make(chanCount)
fori?:=0;?i?<?numWorkers;?i++?{
goFileReaderCounter(fileReader,?counts)
}
totalCount?:=?Count{}
fori?:=0;?i?<?numWorkers;?i++?{
count?:=?<-counts
totalCount.LineCount?+=?count.LineCount
totalCount.WordCount?+=?count.WordCount
}
close(counts)
讓我們運行它杂伟，然后看看它與C語言版wc的運行結(jié)果比較（見下表）：
可以看出，我們的并行實現(xiàn)運行速度比wc快了4.5倍以上仍翰，而且內(nèi)存消耗更低稿壁！這是非常重要的，特別是如果你認為Go是一種自動垃圾收集語言的話歉备。
06
結(jié)束語
雖然本文絕不暗示Go語言比C語言強，但我希望它能夠證明Go語言可以作為一種系統(tǒng)編程語言替代C語言匪燕。
如果你有任何建議和問題蕾羊，歡迎在評論區(qū)留言。
原文：https://ajeetdsouza.github.io/blog/posts/beating-c-with-70-lines-of-go/
星標我帽驯，每天多一點智慧
