www.hkeasychat.com

70 行 Go 代碼打敗 C! - 網站建設及程式編寫

searchsearch      



登入     註冊
網站建設及程式編寫

發新帖

70 行 Go 代碼打敗 C!

70 行 Go 代碼打敗 C! authorauthor發表於 5 天前
作者:数智物语☞
70 行 Go 代碼打敗 C!


70 行 Go 代碼打敗 C!


70 行 Go 代碼打敗 C!


文章發布于公號【數智物語】 (ID︰decision_engine),關注公號不錯過每一篇干貨。



  作者 | Ajeet D'Souza
  譯者 | 甦本如,責編 | maozz
  出品 | CSDN(ID︰CSDNnews)
作為一名程序員,應當具有挑戰精神,才能寫出“完美”的代碼。挑戰歷史悠久的C語言版wc命令一向是件很有趣的事。今天,我們就來看一下如何用70行的Go代碼打敗C語言版wc命令。

70 行 Go 代碼打敗 C!


以下為譯文︰

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

1. Ada

2. C

3. Common Lisp

4. Dyalog APL

5. Futhark

6. Haskell

7. Rust

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

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

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

01

比較基準

我們將使用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,但結果不是很好)來編譯。並且,我們將使用以下系統配置作為運行的基準︰

1. 英特爾酷睿[email protected] 處理器(2個物理核,4個線程)

2. 4+4 GB內存@2133 MHz

3. 240 GB M.2固態硬盤

4. Fedora 31 Linux發行版

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

02

原始實現(wc-nave)

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

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()

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

1. 前一個字節是空白;

2. 前一個字節不是空白。

當從空白字符變為非空白字符時,我們給字計數器(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的運行結果比較(見下表)︰

70 行 Go 代碼打敗 C!


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

03

拆分輸入(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的運行結果比較(見下表)︰

70 行 Go 代碼打敗 C!


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

04

使用channel並行化(wc-channel)

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

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

func ChunkCounter(chunks <-chan Chunk, counts chan<- 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(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 <- Chunk{lastCharIsSpace, buffer[:bytes]}

lastCharIsSpace = IsSpace(buffer[bytes-1])

}

close(chunks)

一旦完成,我們可以簡單地將每個worker得到的計數(count)匯總來得到總的word count︰

totalCount := Count{}

for i := 0; i < numWorkers; i++ {

count := <-counts

totalCount.LineCount += count.LineCount

totalCount.WordCount += count.WordCount

}

close(counts)

讓我們運行它,並且看看它與C語言版wc的運行結果比較(見下表)︰

70 行 Go 代碼打敗 C!


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

05

使用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 <- totalCount

}

與前面一樣,我們現在可以為每個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 := <-counts

totalCount.LineCount += count.LineCount

totalCount.WordCount += count.WordCount

}

close(counts)

讓我們運行它,然後看看它與C語言版wc的運行結果比較(見下表)︰

70 行 Go 代碼打敗 C!


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

06

結束語

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

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

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

70 行 Go 代碼打敗 C!


70 行 Go 代碼打敗 C!


星標我,每天多一點智慧

70 行 Go 代碼打敗 C!

相關內容:
上一篇:重新起航的【三一日】
下一篇:到今天,WordPress已經發布了145版本

更多帖子推薦

網站建設及程式編寫討論區最新帖子快速翻頁:
234567891011121314151617
發新帖

網站建設及程式編寫

70 行 Go 代碼打敗 C! -END- 

香港交友討論區hkeasychat - 香港社交論壇forum 本交友論壇採用forum形式運作,會員所講所post交友話題、發起的交友活動與本交友網立場無關 本頁面任何內容(包括但不限於:『留言、文章』)不代表廣告商同意立場及觀點,本頁面可能出現間接宣傳。hkeasychat旗下討論區業務集團之一 - hkeasychat 香港交友討論區