​70行Go代码打败C

news/2024/7/2 6:09:05

【12月公开课预告】，入群直接获取报名地址

12月11日晚8点直播主题：人工智能消化道病理辅助诊断平台——从方法到落地

12月12日晚8点直播：利用容器技术打造AI公司技术中台

12月17日晚8点直播主题：可重构计算：能效比、通用性，一个都不能少

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

  • 英特尔酷睿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编码的文本文件。

原始实现（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/

推荐阅读

  • 我收集了12款自动生成器，无聊人士自娱自乐专用

  • 如何用Neo4j和Scikit-Learn做机器学习任务？| 附超详细分步教程

  • 谷歌母公司创始人双双引退，劈柴哥上位！

  • 对话阿里云叔同：释放云价值，让容器成为“普适”技术

  • 激辩：机器究竟能否理解常识？

  • Instagram个性化推荐工程中三个关键技术是什么？

  • 从YARN迁移到k8s，滴滴机器学习平台二次开发是这样做的

  • 丁磊向左，刘强东向右

  • 华裔候选人Andrew Yang加密政策公布，如果当选美国总统这些法规将会实施

  • 你点的每个“在看”，我都认真当成了AI


http://lihuaxi.xjx100.cn/news/275864.html

相关文章

android 禁止插件化,Android 插件化实现方式(Hook)

android 禁止插件化,Android 插件化实现方式(Hook)

一、首先我们要找到Hook的点1. 分析我们先大概看下activity的启动流程(图片来自Android 插件化开发指南)image当我们调用startActivity的时候&#xff0c;AMS对我们要启动的Activity进行检查&#xff0c;是否在AndroidManifest中声明过&#xff0c;如果没有就报没有在AndroidMa…
阅读更多...
深度学习三巨头也成了大眼萌，这个一键转换动画电影形象的网站竟因「太火」而下线...

深度学习三巨头也成了大眼萌，这个一键转换动画电影形象的网站竟因「太火」而下线...

机器之心报道作者&#xff1a;魔王、杜伟想不想在动画电影中拥有自己的角色&#xff1f;这个网站一键满足你的需求&#xff0c;不过竟因流量太大成本过高而下线。近期热映的电影《花木兰》总是让人回想起 1998 年上映的同名动画电影。说起来&#xff0c;动漫真人化或动画版翻拍…
阅读更多...
VIRTUAL COMMUNITY INFORMATICS

VIRTUAL COMMUNITY INFORMATICS

这段时间老师叫我研究下VIRTUAL COMMUNITY INFORMATICS相关的课题,准备写毕业论文.老师说考虑到我开始上班了,时间精力有限,给我个轻松的课题(多体贴的老师啊^_^).不过说实在,我对这方面根本不了解,希望cnBlogs的朋友可以提供一些有用的信息给我,中英文的都行,谢谢!当然我自己也…
阅读更多...
tabcontainer控件太长_AjaxControlToolKit--TabContainer控件的介绍收藏[摘录]

tabcontainer控件太长_AjaxControlToolKit--TabContainer控件的介绍收藏[摘录]

AjaxControlToolKit--TabContainer控件的介绍收藏1. Introduction:Tab本身就应该是个以页签形式显示组织网页内容的一个控件。在AJAX Control Tool Kit的控件中有TabContainer控件,它是一些TabPanel控件的载体,而每个TabPanel可以像标准的Panel控件一样,成为其它一些ASP.NET控件…
阅读更多...
如何解决触摸屏的电磁干扰问题【转】

如何解决触摸屏的电磁干扰问题【转】

转自&#xff1a;http://design.eccn.com/design_2013040815090540.htm 开发具有触摸屏人机界面的移动手持设备是一项复杂的设计挑战&#xff0c;尤其是对于投射式电容触摸屏设计来说更是如此&#xff0c;它代表了当前多点触摸界面的主流技术。投射式电容触摸屏能够精确定位手指…
阅读更多...
你真的会写二分检索吗？

你真的会写二分检索吗？

点击上方“方志朋”&#xff0c;选择“设为星标”回复”666“获取新整理的面试资料来源&#xff1a;http://t.cn/EiwP9qJ1. 找出第一个与key相等的元素2. 找出最后一个与key相等的元素3. 查找第一个等于或者大于Key的元素4. 查找第一个大于key的元素5. 查找最后一个等于或者小于…
阅读更多...
Nature：13个维度，手把手教“研究er”如何做学术报告

Nature：13个维度，手把手教“研究er”如何做学术报告

↑ 点击蓝字 关注视学算法作者丨蒋宝尚来源丨AI科技评论编辑丨极市平台交流科研进展和想法除了公开发表论文&#xff0c;最好的方式无疑是公开演讲、报告。毕竟&#xff0c;通过自己的语言将自己的科研想法“讲”给大家听&#xff0c;更多的是展示学术魅力。 文章地址&…
阅读更多...
“掘金”金融AI落地，英特尔趟出一套通关攻略

“掘金”金融AI落地，英特尔趟出一套通关攻略

有人说&#xff0c;金融业是最大的AI应用场景&#xff0c;但不管怎样&#xff0c;不可否认的事实是金融业已经从数字化走向AI化。某种程度上&#xff0c;AI与金融业有着天然的契合性&#xff1a;其一&#xff0c;金融业本身就是以数据为基本元素的行业&#xff0c;它为AI的模型…
阅读更多...
最新文章

Copyright @ 2022~2023