松鼠乐园 松鼠乐园
  • 注册
  • 登录
  • 首页
  • 快捷入口
    • Vue
    • Tensorflow
    • Springboot
    • 语言类
      • CSS
      • ES5
      • ES6
      • Go
      • Java
      • Javascript
    • 工具类
      • Git
      • 工具推荐
    • 服务器&运维
      • Centos
      • Docker
      • Linux
      • Mac
      • MySQL
      • Nginx
      • Redis
      • Windows
    • 资源类
      • 论文
      • 书籍推荐
      • 后端资源
      • 前端资源
      • html网页模板
      • 代码
    • 性能优化
    • 测试
  • 重大新闻
  • 人工智能
  • 开源项目
  • Vue2.0从零开始
  • 广场
首页 › Go › 70 行 Go 代码打败 C

70 行 Go 代码打败 C

迦娜王
2年前Go
518 0 0

作为一名程序员,应当具有挑战精神,才能写出“完美”的代码。挑战历史悠久的C语言版wc命令一向是件很有趣的事。今天,我们就来看一下如何用70行的Go代码打败C语言版wc命令。

70 行 Go 代码打败 C

作者 | 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)。

70 行 Go 代码打败 C

比较基准

我们将使用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,但结果不是很好)来编译。并且,我们将使用以下系统配置作为运行的基准:

  • 英特尔酷睿i5-6200U@2.30GHz 处理器(2个物理核,4个线程)
  • 4 4 GB内存@2133 MHz
  • 240 GB M.2固态硬盘
  • Fedora 31 Linux发行版

为了确保公平的比较,所有实现都将使用16 KB的缓冲区来读取输入。输入将是两个大小分别为100 MB和1GB,使用us-ascii编码的文本文件。

70 行 Go 代码打败 C

原始实现(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 * 1024reader := bufio.NewReaderSize(file, bufferSize)lineCount := 0wordCount := 0byteCount := 0prevByteIsSpace := truefor {b, err := reader.ReadByteif err != nil {if err == io.EOF {break} else {panic(err)}}byteCount  switch b {case \'\n\':lineCount  prevByteIsSpace = truecase \' \', \'\t\', \'\r\', \'\v\', \'\f\':prevByteIsSpace = truedefault:if prevByteIsSpace {wordCount  prevByteIsSpace = false}}}

要显示结果,我们将使用本机println函数。在我的测试中,导入fmt库(注:Go语言的格式化库)会导致可执行文件的大小增加大约400 KB!

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

让我们运行这个程序,然后看看它与C语言版wc的运行结果比较(见下表):

70 行 Go 代码打败 C

好消息是,我们的第一次尝试已经使我们在性能上接近C语言的版本。实际上,我们在内存使用方面做得比C更好!

70 行 Go 代码打败 C

拆分输入(wc-chunks)

虽然缓冲I/O读取对于提高性能至关重要,但调用ReadByte并检查循环中的错误会带来很多不必要的开销。我们可以通过手动缓冲读取调用而不是依赖bufio.Reader来避免这种情况。

为此,我们将把输入分成可以单独处理的缓冲块(chunk)。幸运的是,要处理一个chunk,我们只需要知道前一个chunk的最后一个字符是否是空白。

让我们编写几个工具函数:

type Chunk struct {PrevCharIsSpace boolBuffer byte}type Count struct {LineCount intWordCount int}func GetCount(chunk Chunk)Count{count := Count{}prevCharIsSpace := chunk.PrevCharIsSpacefor _, b := range chunk.Buffer {switch b {case \'\n\':count.LineCount  prevCharIsSpace = truecase \' \', \'\t\', \'\r\', \'\v\', \'\f\':prevCharIsSpace = truedefault:if prevCharIsSpace {prevCharIsSpace = falsecount.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 := trueconst bufferSize = 16 * 1024buffer := 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.LineCounttotalCount.WordCount  = count.WordCount}

要获取字节数,我们可以进行一次系统调用来查询文件大小:

fileStat, err := file.Statif err != nil {panic(err)}byteCount := fileStat.Size

现在我们已经完成了,让我们看看它与C语言版wc的运行结果比较(见下表):

70 行 Go 代码打败 C

从上表结果看,我们在这两个方面都超过了C语言版wc命令,而且我们甚至还没有开始并行化我们的程序。tokei报告显示这个程序只有70行代码!

70 行 Go 代码打败 C

使用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 := <-chunksif !ok {break}count := GetCount(chunk)totalCount.LineCount  = count.LineCounttotalCount.WordCount  = count.WordCount}counts <- totalCount}

我们将为每个逻辑CPU核心生成一个worker线程:

numWorkers := runtime.NumCPUchunks := make(chan Chunk)counts := make(chan Count)for i := 0; i < numWorkers; i   {go ChunkCounter(chunks, counts)}

现在,我们循环运行,从磁盘读取并将作业分配给每个worker:

const bufferSize = 16 * 1024lastCharIsSpace := truefor {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 := <-countstotalCount.LineCount  = count.LineCounttotalCount.WordCount  = count.WordCount}close(counts)

让我们运行它,并且看看它与C语言版wc的运行结果比较(见下表):

70 行 Go 代码打败 C

从上表可以看出,我们的wc现在快了很多,但在内存使用方面出现了相当大的倒退。特别要注意我们的输入循环如何在每次迭代中分配内存的!channel是共享内存的一个很好的抽象,但是对于某些用例来说,简单地不使用channel通道可以极大地提高性能。

70 行 Go 代码打败 C

使用Mutex并行化(wc-mutex)

在本节中,我们将允许每个worker读取文件,并使用sync.Mutex互斥锁确保读取不会同时发生。我们可以创建一个新的struct来处理这个问题:

type FileReader struct {File *os.FileLastCharIsSpace boolmutex sync.Mutex}func (fileReader *FileReader) ReadChunk(buffer []byte)(Chunk, error){fileReader.mutex.Lockdefer fileReader.mutex.Unlockbytes, 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 * 1024buffer := 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.LineCounttotalCount.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 := <-countstotalCount.LineCount  = count.LineCounttotalCount.WordCount  = count.WordCount}close(counts)

让我们运行它,然后看看它与C语言版wc的运行结果比较(见下表):

70 行 Go 代码打败 C

可以看出,我们的并行实现运行速度比wc快了4.5倍以上,而且内存消耗更低!这是非常重要的,特别是如果你认为Go是一种自动垃圾收集语言的话。

70 行 Go 代码打败 C

结束语

虽然本文绝不暗示Go语言比C语言强,但我希望它能够证明Go语言可以作为一种系统编程语言替代C语言。

如果你有任何建议和问题,欢迎在评论区留言。

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

本文为 CSDN 翻译,转载请注明来源出处。

Go
0
你离可视化酷炫大屏只差一套 Kylin + Davinci
上一篇
为什么项目中用了JOOQ后大家都不愿再用Mybatis?
下一篇
评论 (0)

请登录以参与评论。

现在登录
聚合文章
Servicios profesionales Organizaciones
1年前
在Gitee收获近 5k Star,更新后的Vue版RuoYi有哪些新变化?
1年前
vue3.x reactive、effect、computed、watch依赖关系及实现原理
1年前
Vue 3 新特性:在 Composition API 中使用 CSS Modules
1年前
标签
AI AI项目 css docker Drone Elaticsearch es5 es6 Geometry Go gru java Javascript jenkins lstm mysql mysql优化 mysql地理位置索引 mysql索引 mysql规范 mysql设计 mysql配置文件 mysql面试题 mysql高可用 nginx Redis redis性能 rnn SpringBoot Tensorflow tensorflow2.0 UI设计 vue vue3.0 vue原理 whistle ZooKeeper 开源项目 抓包工具 日志输出 机器学习 深度学习 神经网络 论文 面试题
相关文章
Uber 开放公司内部《Go 语言风格指南》
go微服务框架
golang-orm框架
松鼠乐园

资源整合,创造价值

小伙伴
墨魇博客 无同创意
目录
重大新闻 Centos CSS Docker ES5 ES6 Go Java Javascript Linux Mac MySQL Nginx Redis Springboot Tensorflow Vue Vue2.x从零开始 Windows 书籍推荐 人工智能 前端资源 后端资源 壁纸 开源项目 测试 论文
Copyright © 2018-2022 松鼠乐园. Designed by nicetheme. 浙ICP备15039601号-4
  • 重大新闻
  • Centos
  • CSS
  • Docker
  • ES5
  • ES6
  • Go
  • Java
  • Javascript
  • Linux
  • Mac
  • MySQL
  • Nginx
  • Redis
  • Springboot
  • Tensorflow
  • Vue
  • Vue2.x从零开始
  • Windows
  • 书籍推荐
  • 人工智能
  • 前端资源
  • 后端资源
  • 壁纸
  • 开源项目
  • 测试
  • 论文
热门搜索
  • jetson nano
  • vue
  • java
  • mysql
  • 人工智能
  • 人脸识别
迦娜王
坚持才有希望
1224 文章
35 评论
242 喜欢
  • 0
  • 0
  • Top