​70行Go程式碼打敗C

  • 2019 年 12 月 10 日
  • 筆記

作者 | 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 <-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的運行結果比較（見下表）：

從上表可以看出，我們的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 <- 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的運行結果比較（見下表）：

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

結束語

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

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

原文鏈接：

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

VirMach 便宜 VPS

QNews

QNews