文章發(fā)布于公號(hào)【數(shù)智物語(yǔ)】?（ID：decision_engine），關(guān)注公號(hào)不錯(cuò)過(guò)每一篇干貨。

作者?|?Ajeet D'Souza

譯者 |?蘇本如，責(zé)編 | maozz

出品 | CSDN（ID：CSDNnews）

作為一名程序員，應(yīng)當(dāng)具有挑戰(zhàn)精神，才能寫(xiě)出“完美”的代碼。挑戰(zhàn)歷史悠久的C語(yǔ)言版wc命令一向是件很有趣的事。今天，我們就來(lái)看一下如何用70行的Go代碼打敗C語(yǔ)言版wc命令。

以下為譯文：

Chris Penner最近發(fā)表的這篇文章——用80行Haskell代碼擊敗C（https://chrispenner.ca/posts/wc），在互聯(lián)網(wǎng)上引起了相當(dāng)大的爭(zhēng)議，從那以后，嘗試用各種不同的編程語(yǔ)言來(lái)挑戰(zhàn)歷史悠久的C語(yǔ)言版wc命令（譯者注：用于統(tǒng)計(jì)一個(gè)文件中的行數(shù)、字?jǐn)?shù)、字節(jié)數(shù)或字符數(shù)的程序命令）就變成了一種大家趨之若鶩的游戲，可以用來(lái)挑戰(zhàn)的編程語(yǔ)言列表如下：

1. Ada

2. C

3. Common Lisp

4. Dyalog APL

5. Futhark

6. Haskell

7. Rust

今天，我們將用Go語(yǔ)言來(lái)進(jìn)行這個(gè)wc命令的挑戰(zhàn)。作為一種具有優(yōu)秀并發(fā)原語(yǔ)的編譯語(yǔ)言，要獲得與C語(yǔ)言相當(dāng)?shù)男阅軕?yīng)該很容易。

雖然wc命令被設(shè)計(jì)為可以從標(biāo)準(zhǔn)輸入設(shè)備（stdin）讀取、處理非ASCII文本編碼和解析命令行標(biāo)志（wc命令的幫助可以參考這里），但我們?cè)谶@里不會(huì)這樣做。相反，像上面提到的文章一樣，我們將集中精力使我們的實(shí)現(xiàn)盡可能簡(jiǎn)單。

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

01

比較基準(zhǔn)

我們將使用GNU的time工具包，針對(duì)兩種語(yǔ)言編寫(xiě)的wc命令，從運(yùn)行耗費(fèi)時(shí)間和最大常駐內(nèi)存大小兩個(gè)方面來(lái)進(jìn)行比較。

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

用來(lái)比較的C語(yǔ)言版的wc命令和在Chris Penner的原始文章里用到的版本相同，使用gcc 9.2.1和-O3編譯。對(duì)于我們自己的實(shí)現(xiàn)，我們將使用go 1.13.4（我也嘗試過(guò)gccgo，但結(jié)果不是很好）來(lái)編譯。并且，我們將使用以下系統(tǒng)配置作為運(yùn)行的基準(zhǔn)：

1. 英特爾酷睿i5-6200U@2.30GHz 處理器（2個(gè)物理核，4個(gè)線程）

2. 4+4 GB內(nèi)存@2133 MHz

3. 240 GB M.2固態(tài)硬盤(pán)

4. Fedora 31 Linux發(fā)行版

為了確保公平的比較，所有實(shí)現(xiàn)都將使用16 KB的緩沖區(qū)來(lái)讀取輸入。輸入將是兩個(gè)大小分別為100 MB和1GB，使用us-ascii編碼的文本文件。

02

原始實(shí)現(xiàn)（wc-na?ve）

解析參數(shù)很容易，因?yàn)槲覀冎恍枰募窂?，代碼如下：

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)。幸運(yùn)的是，在這種情況下，我們只需要知道兩種狀態(tài)：

1. 前一個(gè)字節(jié)是空白；

2. 前一個(gè)字節(jié)不是空白。

當(dāng)從空白字符變?yōu)榉强瞻鬃址麜r(shí)，我們給字計(jì)數(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é)果，我們將使用本機(jī)println（）函數(shù)。在我的測(cè)試中，導(dǎo)入fmt庫(kù)（注：Go語(yǔ)言的格式化庫(kù)）會(huì)導(dǎo)致可執(zhí)行文件的大小增加大約400 KB！

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

讓我們運(yùn)行這個(gè)程序，然后看看它與C語(yǔ)言版wc的運(yùn)行結(jié)果比較（見(jiàn)下表）：

好消息是，我們的第一次嘗試已經(jīng)使我們?cè)谛阅苌辖咏麮語(yǔ)言的版本。實(shí)際上，我們?cè)趦?nèi)存使用方面做得比C更好！

03

拆分輸入（wc-chunks）

雖然緩沖I/O讀取對(duì)于提高性能至關(guān)重要，但調(diào)用ReadByte（）并檢查循環(huán)中的錯(cuò)誤會(huì)帶來(lái)很多不必要的開(kāi)銷(xiāo)。我們可以通過(guò)手動(dòng)緩沖讀取調(diào)用而不是依賴(lài)bufio.Reader來(lái)避免這種情況。

為此，我們將把輸入分成可以單獨(dú)處理的緩沖塊(chunk)。幸運(yùn)的是，要處理一個(gè)chunk，我們只需要知道前一個(gè)chunk的最后一個(gè)字符是否是空白。

讓我們編寫(xiě)幾個(gè)工具函數(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)在，我們可以將輸入分成幾個(gè)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ù)，我們可以進(jìn)行一次系統(tǒng)調(diào)用來(lái)查詢(xún)文件大?。?/p>

fileStat,?err?:=?file.Stat()

iferr?!=nil{

panic(err)

}

byteCount?:=?fileStat.Size()

現(xiàn)在我們已經(jīng)完成了，讓我們看看它與C語(yǔ)言版wc的運(yùn)行結(jié)果比較（見(jiàn)下表）：

從上表結(jié)果看，我們?cè)谶@兩個(gè)方面都超過(guò)了C語(yǔ)言版wc命令，而且我們甚至還沒(méi)有開(kāi)始并行化我們的程序。tokei報(bào)告顯示這個(gè)程序只有70行代碼！

04

使用channel并行化（wc-channel）

不可否認(rèn)，將wc這樣的命令改成并行化運(yùn)行有點(diǎn)過(guò)分了，但是讓我們看看我們到底能走多遠(yuǎn)。Chris Penner的原始文章里的測(cè)試采用了并行化來(lái)讀取輸入文件，雖然這樣做改進(jìn)了運(yùn)行時(shí)，但文章的作者也承認(rèn)，并行化讀取帶來(lái)的性能提高可能僅限于某些類(lèi)型的存儲(chǔ)，而在其他類(lèi)型的存儲(chǔ)則有害無(wú)益。

對(duì)于我們的實(shí)現(xiàn)，我們希望我們的代碼能夠在所有設(shè)備上執(zhí)行，所以我們不會(huì)這樣做。我們將建立兩個(gè)channel – chunks和counts。每個(gè)worker線程將從chunks中讀取和處理數(shù)據(jù)，直到channel關(guān)閉，然后將結(jié)果寫(xiě)入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

}

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

numWorkers?:=?runtime.NumCPU()

chunks?:=make(chanChunk)

counts?:=make(chanCount)

fori?:=0;?i?<?numWorkers;?i++?{

goChunkCounter(chunks,?counts)

}

現(xiàn)在，我們循環(huán)運(yùn)行，從磁盤(pán)讀取并將作業(yè)分配給每個(gè)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)

一旦完成，我們可以簡(jiǎn)單地將每個(gè)worker得到的計(jì)數(shù)（count）匯總來(lái)得到總的word count：

totalCount?:=?Count{}

fori?:=0;?i?<?numWorkers;?i++?{

count?:=?<-counts

totalCount.LineCount?+=?count.LineCount

totalCount.WordCount?+=?count.WordCount

}

close(counts)

讓我們運(yùn)行它，并且看看它與C語(yǔ)言版wc的運(yùn)行結(jié)果比較（見(jiàn)下表）：

從上表可以看出，我們的wc現(xiàn)在快了很多，但在內(nèi)存使用方面出現(xiàn)了相當(dāng)大的倒退。特別要注意我們的輸入循環(huán)如何在每次迭代中分配內(nèi)存的！channel是共享內(nèi)存的一個(gè)很好的抽象，但是對(duì)于某些用例來(lái)說(shuō)，簡(jiǎn)單地不使用channel通道可以極大地提高性能。

05

使用Mutex并行化（wc-mutex）

在本節(jié)中，我們將允許每個(gè)worker讀取文件，并使用sync.Mutex互斥鎖確保讀取不會(huì)同時(shí)發(fā)生。我們可以創(chuàng)建一個(gè)新的struct來(lái)處理這個(gè)問(wèn)題：

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

}

然后，我們重寫(xiě)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)在可以為每個(gè)CPU核心生成一個(gè)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)

讓我們運(yùn)行它，然后看看它與C語(yǔ)言版wc的運(yùn)行結(jié)果比較（見(jiàn)下表）：

可以看出，我們的并行實(shí)現(xiàn)運(yùn)行速度比wc快了4.5倍以上，而且內(nèi)存消耗更低！這是非常重要的，特別是如果你認(rèn)為Go是一種自動(dòng)垃圾收集語(yǔ)言的話。

06

結(jié)束語(yǔ)

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

如果你有任何建議和問(wèn)題，歡迎在評(píng)論區(qū)留言。

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

星標(biāo)我，每天多一點(diǎn)智慧