70行Go代碼可以打敗C！

西北望msm66g9f 2019-12-11

展開(kāi)全文

作為一名程序員，應(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:///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ǔ)言列表如下：

Ada
C
Common Lisp
Dyalog APL
Futhark
Haskell
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）。

比較基準(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)：

英特爾酷睿i5-6200U@2.30GHz 處理器（2個(gè)物理核，4個(gè)線程）
4+4 GB內(nèi)存@2133 MHz
240 GB M.2固態(tài)硬盤(pán)
Fedora 31 Linux發(fā)行版

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

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

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

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

我們將按字節(jié)遍歷文本和跟蹤狀態(tài)。幸運(yùn)的是，在這種情況下，我們只需要知道兩種狀態(tài)：

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

當(dāng)從空白字符變?yōu)榉强瞻鬃址麜r(shí)，我們給字計(jì)數(shù)器（word counter）加一。這種方法允許我們直接從字節(jié)流中讀取，從而保持很低的內(nèi)存消耗。

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
        }
    }
}

要顯示結(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更好！

拆分輸入（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ù)：

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'
}

現(xiàn)在，我們可以將輸入分成幾個(gè)chunk（塊），并將它們傳送給GetCount函數(shù)。

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
}

要獲取字節(jié)數(shù)，我們可以進(jìn)行一次系統(tǒng)調(diào)用來(lái)查詢(xún)文件大?。?/p>

fileStat, err := file.Stat()
if err != 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行代碼！

使用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中。

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
}

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

numWorkers := runtime.NumCPU()

chunks := make(chan Chunk)
counts := make(chan Count)

for i := 0; i < numWorkers; i++ {
go ChunkCounter(chunks, counts)
}

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

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

totalCount := Count{}
for i := 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通道可以極大地提高性能。

使用Mutex并行化（wc-mutex）

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

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
}

然后，我們重寫(xiě)worker函數(shù)，讓它直接從文件中讀取：

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
}

與前面一樣，我們現(xiàn)在可以為每個(gè)CPU核心生成一個(gè)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)

讓我們運(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ǔ)言的話。

結(jié)束語(yǔ)

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

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

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

本文為 CSDN 翻譯。

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶(hù)發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：西北望msm66g9f > 《編程》

舉報(bào)/認(rèn)領(lǐng)