文章发布于公号【数智物语】 （ID：decision_engine），关注公号不错过每一篇干货。
作者 | Ajeet D'Souza
译者 | 苏本如，责编 | maozz
出品 | CSDN（ID：CSDNnews）
作为一名程序员，应当具有挑战精神，才能写出“完美”的代码。挑战历史悠久的C语言版wc命令一向是件很有趣的事。今天，我们就来看一下如何用70行的Go代码打败C语言版wc命令。
以下为译文：
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. 英特尔酷睿i5-6200U@2.30GHz 处理器（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-naïve）
解析参数很容易，因为我们只需要文件路径，代码如下：
iflen(os.Args) <2{
panic("no file path specified")
}
filePath := os.Args[1]
file, err := os.Open(filePath)
iferr !=nil{
panic(err)
}
deferfile.Close()
我们将按字节遍历文本和跟踪状态。幸运的是，在这种情况下，我们只需要知道两种状态：
1. 前一个字节是空白；
2. 前一个字节不是空白。
当从空白字符变为非空白字符时，我们给字计数器（word counter）加一。这种方法允许我们直接从字节流中读取，从而保持很低的内存消耗。
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
}
}
}
要显示结果，我们将使用本机println（）函数。在我的测试中，导入fmt库（注：Go语言的格式化库）会导致可执行文件的大小增加大约400 KB！
println(lineCount, wordCount, byteCount,file.Name())
让我们运行这个程序，然后看看它与C语言版wc的运行结果比较（见下表）：
好消息是，我们的第一次尝试已经使我们在性能上接近C语言的版本。实际上，我们在内存使用方面做得比C更好！
03
拆分输入（wc-chunks）
虽然缓冲I/O读取对于提高性能至关重要，但调用ReadByte（）并检查循环中的错误会带来很多不必要的开销。我们可以通过手动缓冲读取调用而不是依赖bufio.Reader来避免这种情况。
为此，我们将把输入分成可以单独处理的缓冲块(chunk)。幸运的是，要处理一个chunk，我们只需要知道前一个chunk的最后一个字符是否是空白。
让我们编写几个工具函数：
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'
}
现在，我们可以将输入分成几个chunk（块），并将它们传送给GetCount函数。
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
}
要获取字节数，我们可以进行一次系统调用来查询文件大小：
fileStat, err := file.Stat()
iferr !=nil{
panic(err)
}
byteCount := fileStat.Size()
现在我们已经完成了，让我们看看它与C语言版wc的运行结果比较（见下表）：
从上表结果看，我们在这两个方面都超过了C语言版wc命令，而且我们甚至还没有开始并行化我们的程序。tokei报告显示这个程序只有70行代码！
04
使用channel并行化（wc-channel）
不可否认，将wc这样的命令改成并行化运行有点过分了，但是让我们看看我们到底能走多远。Chris Penner的原始文章里的测试采用了并行化来读取输入文件，虽然这样做改进了运行时，但文章的作者也承认，并行化读取带来的性能提高可能仅限于某些类型的存储，而在其他类型的存储则有害无益。
对于我们的实现，我们希望我们的代码能够在所有设备上执行，所以我们不会这样做。我们将建立两个channel – chunks和counts。每个worker线程将从chunks中读取和处理数据，直到channel关闭，然后将结果写入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)
}
现在，我们循环运行，从磁盘读取并将作业分配给每个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得到的计数（count）汇总来得到总的word count：
totalCount := Count{}
fori :=0; i < numWorkers; i++ {
count := <-counts
totalCount.LineCount += count.LineCount
totalCount.WordCount += count.WordCount
}
close(counts)
让我们运行它，并且看看它与C语言版wc的运行结果比较（见下表）：
从上表可以看出，我们的wc现在快了很多，但在内存使用方面出现了相当大的倒退。特别要注意我们的输入循环如何在每次迭代中分配内存的！channel是共享内存的一个很好的抽象，但是对于某些用例来说，简单地不使用channel通道可以极大地提高性能。
05
使用Mutex并行化（wc-mutex）
在本节中，我们将允许每个worker读取文件，并使用sync.Mutex互斥锁确保读取不会同时发生。我们可以创建一个新的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函数，让它直接从文件中读取：
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
}
与前面一样，我们现在可以为每个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的运行结果比较（见下表）：
可以看出，我们的并行实现运行速度比wc快了4.5倍以上，而且内存消耗更低！这是非常重要的，特别是如果你认为Go是一种自动垃圾收集语言的话。
06
结束语
虽然本文绝不暗示Go语言比C语言强，但我希望它能够证明Go语言可以作为一种系统编程语言替代C语言。
如果你有任何建议和问题，欢迎在评论区留言。
原文：https://ajeetdsouza.github.io/blog/posts/beating-c-with-70-lines-of-go/
星标我，每天多一点智慧
