6
14
2018
2

递归遍历目录:Python vs Go vs Rust

本文来自依云's Blog,转载请注明。

群友提出了一个简单的任务:递归遍历一个很大的目录,根据文件名数一下有多少 JPEG 文件。怎么最快呢?然后他用了 Go 语言实现。

我忽略想起 Python 3.5 的 What's New 里提到,他们优化了 os.scandir 使得目录遍历快了好几倍(PEP 471)。其核心思想是:不进行不必要的 stat 系统调用,因为读目录获得了不少信息,原来都是丢弃掉了,现在改成了通过 DirEntry 对象来返回。这些信息包括文件名等,刚好有我们需要的。

于是 Go 做了这个优化没有呢?

翻了一下代码。Go 自带的实现位于 src/path/filepath/path.go 文件中。可以看到,它对每一个文件都 lstat 了。后来一阁指出,不仅如此,而且它还莫名其妙地对目录下的文件名进行了排序

呃,前者可以说是疏忽了,毕竟 Python 也是直到 3.5 才优化的。可是,它排那个序干嘛呢……

然后我又想到,Rust 那边如何呢?

结果是,Rust 对它所包含的东西非常审慎,标准库里并没有递归遍历目录的函数。那我们自己写一个?才不呢,用第三方库啦!可以看到,它也是返回 DirEntry 对象的。

后来了解到,Go 也有一个第三方的实现 godirwalk,对这些细节进行了优化。

光是了解实现不够。我们让它们来比试一下吧。顺便,把 find 和 fd 也拖进来好了。

任务:数一数一个拥有近万文件的目录下有多少 JPEG 文件。

实现代码:walkdir-test

结果:

   Rust: top:    4.78, min:    4.72, avg:    4.90, max:    5.46, mdev:    0.17, cnt:  20
 Go_3rd: top:    7.71, min:    7.64, avg:    7.79, max:    8.41, mdev:    0.16, cnt:  20
   find: top:   11.49, min:   11.32, avg:   11.76, max:   14.18, mdev:    0.59, cnt:  20
     fd: top:   18.17, min:   15.18, avg:   21.29, max:   29.94, mdev:    3.84, cnt:  20
     Go: top:   21.08, min:   20.91, avg:   21.28, max:   22.70, mdev:    0.37, cnt:  20
 Python: top:   29.66, min:   29.51, avg:   30.43, max:   35.84, mdev:    1.45, cnt:  20
Python2: top:   30.37, min:   30.10, avg:   30.85, max:   33.15, mdev:    0.75, cnt:  20

Rust 如预期一样是最快的。Go_3rd 就是那个第三方库的实现,也非常快的。fd 是 Rust 实现的,目标之一是快,但是这次并没有比老牌的 find 快。Go 自带的那个实现,十分令人遗憾地连 find 都没比过呢,不过还是比 Python 快了不少。Python 2 这次终于没有跑在 Python 3 前边了(虽然差距很小),我猜是 PEP 471 那个优化的功劳。

对了,还有代码行数:

  15 Python/walk
  29 Rust/src/main.rs
  30 Go/walk.go
  33 Go_3rd/walk.go

Rust 竟然不是最长的。不过确实是字符数最多的。

话说 Go 的 } 竟然也是有规定的,结构体的不能另起一行写,只能跟 Lisp 的风格那样堆在一行的尾巴里。

PS: 没想到之前给 swapview 写的 benchmark 程序在另外的项目里用上了呢,果然写东西还是通用些的好。


更新:在群友的提示下,我找了一个更大的目录来测试,结果很不一样呢。这次遍历的目录是 /usr,共有 320397 个文件。

     fd: top:  265.80, min:  259.84, avg:  273.89, max:  319.76, mdev:   15.03, cnt:  20
   Rust: top:  269.98, min:  266.86, avg:  272.82, max:  282.84, mdev:    4.17, cnt:  20
 Go_3rd: top:  361.17, min:  359.05, avg:  363.82, max:  370.22, mdev:    3.31, cnt:  20
   find: top:  454.03, min:  450.79, avg:  458.51, max:  467.31, mdev:    5.08, cnt:  20
 Python: top:  624.80, min:  615.73, avg:  630.67, max:  640.88, mdev:    6.79, cnt:  20
     Go: top:  890.03, min:  876.98, avg:  910.63, max:  967.14, mdev:   24.84, cnt:  20
Python2: top: 1171.38, min: 1157.19, avg: 1189.99, max: 1228.09, mdev: 4186.28, cnt:  20

可以看到,唯一的并行版本 fd 胜出了~Rust 版本紧随其后,显然在此例中并行并没有多么有效。Go_3rd 还是慢于 Rust 但也并不多。然后,经过优化的 Python 终于在更大的数据量上明显胜过了 Go 以及 Python 2 这两个浪费了很多系统调用的版本。

Category: 编程 | Tags: python go 编程语言 Rust | Read Count: 1993
bobo 说:
Jul 09, 2018 05:00:45 PM

依云还是那么给力,这个提交都看到了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

部分静态文件存储由又拍云存储提供。 | Theme: Aeros 2.0 by TheBuckmaker.com