群友提出了一个简单的任务:递归遍历一个很大的目录,根据文件名数一下有多少 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 这两个浪费了很多系统调用的版本。