改进 D 中的逐行 I/O 操作
Improving line-wise I/O operations in D
我需要以逐行方式处理大量大中型文件(几百 MB 到 GB),因此我对用于遍历行的标准 D 方法很感兴趣。 foreach(line; file.byLine())
惯用语似乎符合要求,简洁易读,但性能似乎不太理想。
例如,下面是 Python 和 D 中的两个简单程序,用于遍历文件的行数并计算行数。对于约 470 MB 的文件(约 360 万行),我得到以下计时(10 次中最好):
D次:
real 0m19.146s
user 0m18.932s
sys 0m0.190s
Python 次(在 EDIT 2 之后,见下文):
real 0m0.924s
user 0m0.792s
sys 0m0.129s
这里是D版,用dmd -O -release -inline -m64
编译:
import std.stdio;
import std.string;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto infile = File(args[1]);
uint linect = 0;
foreach (line; infile.byLine())
linect += 1;
writeln("There are: ", linect, " lines.");
return 0;
}
而现在对应的Python版本:
import sys
if __name__ == "__main__":
if (len(sys.argv) < 2):
sys.exit()
infile = open(sys.argv[1])
linect = 0
for line in infile:
linect += 1
print "There are %d lines" % linect
编辑 2:我更改了 Python 代码以使用下面评论中建议的更惯用的 for line in infile
,从而提高了速度-up Python 版本,现在接近标准 wc -l
调用 Unix wc
工具的速度。
关于我在 D 中可能做错什么导致性能如此差的任何建议或指示?
编辑:为了比较,这里有一个 D 版本,它将 byLine()
惯用语从 window 中抛出并立即将所有数据吸入内存,然后将数据拆分为 post-hoc 行。这提供了更好的性能,但仍然比 Python 版本慢 2 倍。
import std.stdio;
import std.string;
import std.file;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto c = cast(string) read(args[1]);
auto l = splitLines(c);
writeln("There are ", l.length, " lines.");
return 0;
}
最后一个版本的时间安排如下:
real 0m3.201s
user 0m2.820s
sys 0m0.376s
这应该比你的版本快,甚至比 python 版本快:
module main;
import std.stdio;
import std.file;
import std.array;
void main(string[] args)
{
auto infile = File(args[1]);
auto buffer = uninitializedArray!(char[])(100);
uint linect;
while(infile.readln(buffer))
{
linect += 1;
}
writeln("There are: ", linect, " lines.");
}
我想我今天会做点新的,所以我决定"learn"D。请注意,这是我写的第一个D,所以我可能会完全离开。
我尝试的第一件事是手动缓冲:
foreach (chunk; infile.byChunk(100000)) {
linect += splitLines(cast(string) chunk).length;
}
请注意,这是不正确的,因为它忽略了跨越边界的线,但稍后会解决这个问题。
这有点帮助,但还远远不够。它确实允许我测试
foreach (chunk; infile.byChunk(100000)) {
linect += (cast(string) chunk).length;
}
这表明所有时间都在 splitLines
。
我制作了 splitLines
的本地副本。仅此一项就将速度提高了 2 倍!我没想到会这样。我 运行 都是
dmd -release -inline -O -m64 -boundscheck=on
dmd -release -inline -O -m64 -boundscheck=off
两者都差不多。
然后我重写了 splitLines
以专注于 s[i].sizeof == 1
,它现在似乎只比 Python 慢,因为它也打破了段落分隔符。
为了完成它,我做了一个 Range 并进一步优化它,这使代码接近 Python 的速度。考虑到 Python 不会中断段落分隔符并且它的底层代码是用 C 语言编写的,这似乎没问题。此代码 可能 在超过 8k 长的行上具有 O(n²)
性能,但我不确定。
import std.range;
import std.stdio;
auto lines(File file, KeepTerminator keepTerm = KeepTerminator.no) {
struct Result {
public File.ByChunk chunks;
public KeepTerminator keepTerm;
private string nextLine;
private ubyte[] cache;
this(File file, KeepTerminator keepTerm) {
chunks = file.byChunk(8192);
this.keepTerm = keepTerm;
if (chunks.empty) {
nextLine = null;
}
else {
// Initialize cache and run an
// iteration to set nextLine
popFront;
}
}
@property bool empty() {
return nextLine is null;
}
@property auto ref front() {
return nextLine;
}
void popFront() {
size_t i;
while (true) {
// Iterate until we run out of cache
// or we meet a potential end-of-line
while (
i < cache.length &&
cache[i] != '\n' &&
cache[i] != 0xA8 &&
cache[i] != 0xA9
) {
++i;
}
if (i == cache.length) {
// Can't extend; just give the rest
if (chunks.empty) {
nextLine = cache.length ? cast(string) cache : null;
cache = new ubyte[0];
return;
}
// Extend cache
cache ~= chunks.front;
chunks.popFront;
continue;
}
// Check for false-positives from the end-of-line heuristic
if (cache[i] != '\n') {
if (i < 2 || cache[i - 2] != 0xE2 || cache[i - 1] != 0x80) {
continue;
}
}
break;
}
size_t iEnd = i + 1;
if (keepTerm == KeepTerminator.no) {
// E2 80 A9 or E2 80 A9
if (cache[i] != '\n') {
iEnd -= 3;
}
// \r\n
else if (i > 1 && cache[i - 1] == '\r') {
iEnd -= 2;
}
// \n
else {
iEnd -= 1;
}
}
nextLine = cast(string) cache[0 .. iEnd];
cache = cache[i + 1 .. $];
}
}
return Result(file, keepTerm);
}
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto file = File(args[1]);
writeln("There are: ", walkLength(lines(file)), " lines.");
return 0;
}
编辑和 TL;DR:此问题已在 https://github.com/D-Programming-Language/phobos/pull/3089 中解决。改进后的 File.byLine
性能将从 D 2.068 开始提供。
我在一个包含 575247 行的文本文件上试过你的代码。 Python 基线大约需要 0.125 秒。这是我的代码库,每个方法的注释中都嵌入了计时。解释如下。
import std.algorithm, std.file, std.stdio, std.string;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
size_t linect = 0;
// 0.62 s
foreach (line; File(args[1]).byLine())
linect += 1;
// 0.2 s
//linect = args[1].readText.count!(c => c == '\n');
// 0.095 s
//linect = args[1].readText.representation.count!(c => c == '\n');
// 0.11 s
//linect = File(args[1]).byChunk(4096).joiner.count!(c => c == '\n');
writeln("There are: ", linect, " lines.");
return 0;
}
我为每个变体使用了 dmd -O -release -inline
。
第一个版本(最慢)一次读取一行。我们可以而且应该提高 byLine 的性能;目前,它受到诸如将 byLine 与其他 C stdio 操作混合使用之类的事情的阻碍,这可能过于保守。如果我们取消它,我们可以轻松地进行预取等。
第二个版本一口气读取文件,然后使用标准算法来计算带有谓词的行数。
第三个版本承认没有必要在意任何 UTF 的微妙之处;计算字节数也很好,因此它将字符串转换为其字节表示形式(免费),然后计算字节数。
最后一个版本(我最喜欢的)一次从文件中读取 4KB 的数据,并使用 joiner
懒惰地展平它们。然后它再次计算字节数。
tl;dr 字符串是自动解码的,这使得 splitLines 很慢。
splitLines 的当前实现会动态解码字符串,这使其速度很慢。在下一个版本的 phobos 中,这将是 fixed.
也会有一个 range 为您做这件事。
总的来说,D GC 不是最先进的,但是 D 使您有机会产生更少的垃圾。要获得有竞争力的程序,您需要避免无用的分配。第二件大事:对于快速代码使用 gdc 或 ldc,因为 dmd 的优势是快速生成代码而不是快速代码。
所以我没有计时但是这个版本不应该在最大行之后分配,因为它重用了缓冲区并且不解码UTF。
import std.stdio;
void main(string[] args)
{
auto f = File(args[1]);
// explicit mention ubyte[], buffer will be reused
// no UTF decoding, only looks for "\n". See docs.
int lineCount;
foreach(ubyte[] line; std.stdio.lines(f))
{
lineCount += 1;
}
writeln("lineCount: ", lineCount);
}
如果您需要,使用范围的版本可能如下所示
每行以终止符结尾:
import std.stdio, std.algorithm;
void main(string[] args)
{
auto f = File(args[1]);
auto lineCount = f.byChunk(4096) // read file by chunks of page size
` .joiner // "concatenate" these chunks
.count(cast(ubyte) '\n'); // count lines
writeln("lineCount: ", lineCount);
}
在下一个版本中,只需执行以获得接近最佳性能和
打破所有换行空白。
void main(string[] args)
{
auto f = File(args[1]);
auto lineCount = f.byChunk(4096) // read file by chunks of page size
.joiner // "concatenate" these chunks
.lineSplitter // split by line
.walkLength; // count lines
writeln("lineCount: ", lineCount);
}
int main()
{
import std.mmfile;
scope mmf = new MmFile(args[1]);
foreach(line; splitter(cast(string)mmf[], "\n"))
{
++linect;
}
writeln("There are: ", linect, " lines.");
return 0;
}
计算行数是否可以很好地代表文本处理应用程序的整体性能还存在争议。您正在测试 python 的 C 库的效率,就像其他任何东西一样,一旦您真正开始使用数据做有用的事情,您将得到不同的结果。 D 打磨标准库的时间比 Python 少,参与的人也少。 byLine 的性能已经讨论了几年了,我认为下一个版本会更快。
人们似乎确实发现 D 对于这类文本处理非常高效且富有成效。例如,AdRoll 以 python 商店而闻名,但他们的数据科学人员使用 D:
http://tech.adroll.com/blog/data/2014/11/17/d-is-for-data-science.html
回到问题上来,显然是在比较编译器和库,就像在比较语言一样。 DMD 的作用是作为参考编译器,并且编译速度快如闪电。所以它非常适合快速开发和迭代,但如果您需要速度,那么您应该使用 LDC 或 GDC,如果您确实使用 DMD,则打开优化并关闭边界检查。
在我的 arch linux 64 位 HP Probook 4530s 机器上,使用 WestburyLab usenet 语料库的最后 1mm 行,我得到以下内容:
python2:真实0m0.333s,用户0m0.253s,系统0m0.013s
pypy(预热):真实 0m0.286s,用户 0m0.250s,系统 0m0.033s
DMD(默认值):
真实 0m0.468s,用户 0m0.460s,系统 0m0.007s
DMD(-O -release -inline -noboundscheck):
真实 0m0.398s,用户 0m0.393s,系统 0m0.003s
GDC(默认值):真实 0m0.400s,用户 0m0.380s,系统 0m0.017s
[不知道GDC优化的开关]
LDC(默认值):真实 0m0.396s,用户 0m0.380s,系统 0m0.013s
LDC(-O5): 真实 0m0.336s,用户 0m0.317s,系统 0m0.017s
在真实的应用程序中,人们会使用内置分析器来识别热点并调整代码,但我同意 naive D 应该有不错的速度,最差的情况下与 python 相同。并使用 LDC 进行优化,这确实是我们所看到的。
为了完整起见,我将您的 D 代码更改为以下内容。 (不需要一些导入 - 我在玩)。
import std.stdio;
import std.string;
import std.datetime;
import std.range, std.algorithm;
import std.array;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto t=Clock.currTime();
auto infile = File(args[1]);
uint linect = 0;
foreach (line; infile.byLine)
linect += 1;
auto t2=Clock.currTime-t;
writefln("There are: %s lines and took %s", linect, t2);
return 1;
}
我需要以逐行方式处理大量大中型文件(几百 MB 到 GB),因此我对用于遍历行的标准 D 方法很感兴趣。 foreach(line; file.byLine())
惯用语似乎符合要求,简洁易读,但性能似乎不太理想。
例如,下面是 Python 和 D 中的两个简单程序,用于遍历文件的行数并计算行数。对于约 470 MB 的文件(约 360 万行),我得到以下计时(10 次中最好):
D次:
real 0m19.146s
user 0m18.932s
sys 0m0.190s
Python 次(在 EDIT 2 之后,见下文):
real 0m0.924s
user 0m0.792s
sys 0m0.129s
这里是D版,用dmd -O -release -inline -m64
编译:
import std.stdio;
import std.string;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto infile = File(args[1]);
uint linect = 0;
foreach (line; infile.byLine())
linect += 1;
writeln("There are: ", linect, " lines.");
return 0;
}
而现在对应的Python版本:
import sys
if __name__ == "__main__":
if (len(sys.argv) < 2):
sys.exit()
infile = open(sys.argv[1])
linect = 0
for line in infile:
linect += 1
print "There are %d lines" % linect
编辑 2:我更改了 Python 代码以使用下面评论中建议的更惯用的 for line in infile
,从而提高了速度-up Python 版本,现在接近标准 wc -l
调用 Unix wc
工具的速度。
关于我在 D 中可能做错什么导致性能如此差的任何建议或指示?
编辑:为了比较,这里有一个 D 版本,它将 byLine()
惯用语从 window 中抛出并立即将所有数据吸入内存,然后将数据拆分为 post-hoc 行。这提供了更好的性能,但仍然比 Python 版本慢 2 倍。
import std.stdio;
import std.string;
import std.file;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto c = cast(string) read(args[1]);
auto l = splitLines(c);
writeln("There are ", l.length, " lines.");
return 0;
}
最后一个版本的时间安排如下:
real 0m3.201s
user 0m2.820s
sys 0m0.376s
这应该比你的版本快,甚至比 python 版本快:
module main;
import std.stdio;
import std.file;
import std.array;
void main(string[] args)
{
auto infile = File(args[1]);
auto buffer = uninitializedArray!(char[])(100);
uint linect;
while(infile.readln(buffer))
{
linect += 1;
}
writeln("There are: ", linect, " lines.");
}
我想我今天会做点新的,所以我决定"learn"D。请注意,这是我写的第一个D,所以我可能会完全离开。
我尝试的第一件事是手动缓冲:
foreach (chunk; infile.byChunk(100000)) {
linect += splitLines(cast(string) chunk).length;
}
请注意,这是不正确的,因为它忽略了跨越边界的线,但稍后会解决这个问题。
这有点帮助,但还远远不够。它确实允许我测试
foreach (chunk; infile.byChunk(100000)) {
linect += (cast(string) chunk).length;
}
这表明所有时间都在 splitLines
。
我制作了 splitLines
的本地副本。仅此一项就将速度提高了 2 倍!我没想到会这样。我 运行 都是
dmd -release -inline -O -m64 -boundscheck=on
dmd -release -inline -O -m64 -boundscheck=off
两者都差不多。
然后我重写了 splitLines
以专注于 s[i].sizeof == 1
,它现在似乎只比 Python 慢,因为它也打破了段落分隔符。
为了完成它,我做了一个 Range 并进一步优化它,这使代码接近 Python 的速度。考虑到 Python 不会中断段落分隔符并且它的底层代码是用 C 语言编写的,这似乎没问题。此代码 可能 在超过 8k 长的行上具有 O(n²)
性能,但我不确定。
import std.range;
import std.stdio;
auto lines(File file, KeepTerminator keepTerm = KeepTerminator.no) {
struct Result {
public File.ByChunk chunks;
public KeepTerminator keepTerm;
private string nextLine;
private ubyte[] cache;
this(File file, KeepTerminator keepTerm) {
chunks = file.byChunk(8192);
this.keepTerm = keepTerm;
if (chunks.empty) {
nextLine = null;
}
else {
// Initialize cache and run an
// iteration to set nextLine
popFront;
}
}
@property bool empty() {
return nextLine is null;
}
@property auto ref front() {
return nextLine;
}
void popFront() {
size_t i;
while (true) {
// Iterate until we run out of cache
// or we meet a potential end-of-line
while (
i < cache.length &&
cache[i] != '\n' &&
cache[i] != 0xA8 &&
cache[i] != 0xA9
) {
++i;
}
if (i == cache.length) {
// Can't extend; just give the rest
if (chunks.empty) {
nextLine = cache.length ? cast(string) cache : null;
cache = new ubyte[0];
return;
}
// Extend cache
cache ~= chunks.front;
chunks.popFront;
continue;
}
// Check for false-positives from the end-of-line heuristic
if (cache[i] != '\n') {
if (i < 2 || cache[i - 2] != 0xE2 || cache[i - 1] != 0x80) {
continue;
}
}
break;
}
size_t iEnd = i + 1;
if (keepTerm == KeepTerminator.no) {
// E2 80 A9 or E2 80 A9
if (cache[i] != '\n') {
iEnd -= 3;
}
// \r\n
else if (i > 1 && cache[i - 1] == '\r') {
iEnd -= 2;
}
// \n
else {
iEnd -= 1;
}
}
nextLine = cast(string) cache[0 .. iEnd];
cache = cache[i + 1 .. $];
}
}
return Result(file, keepTerm);
}
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto file = File(args[1]);
writeln("There are: ", walkLength(lines(file)), " lines.");
return 0;
}
编辑和 TL;DR:此问题已在 https://github.com/D-Programming-Language/phobos/pull/3089 中解决。改进后的 File.byLine
性能将从 D 2.068 开始提供。
我在一个包含 575247 行的文本文件上试过你的代码。 Python 基线大约需要 0.125 秒。这是我的代码库,每个方法的注释中都嵌入了计时。解释如下。
import std.algorithm, std.file, std.stdio, std.string;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
size_t linect = 0;
// 0.62 s
foreach (line; File(args[1]).byLine())
linect += 1;
// 0.2 s
//linect = args[1].readText.count!(c => c == '\n');
// 0.095 s
//linect = args[1].readText.representation.count!(c => c == '\n');
// 0.11 s
//linect = File(args[1]).byChunk(4096).joiner.count!(c => c == '\n');
writeln("There are: ", linect, " lines.");
return 0;
}
我为每个变体使用了 dmd -O -release -inline
。
第一个版本(最慢)一次读取一行。我们可以而且应该提高 byLine 的性能;目前,它受到诸如将 byLine 与其他 C stdio 操作混合使用之类的事情的阻碍,这可能过于保守。如果我们取消它,我们可以轻松地进行预取等。
第二个版本一口气读取文件,然后使用标准算法来计算带有谓词的行数。
第三个版本承认没有必要在意任何 UTF 的微妙之处;计算字节数也很好,因此它将字符串转换为其字节表示形式(免费),然后计算字节数。
最后一个版本(我最喜欢的)一次从文件中读取 4KB 的数据,并使用 joiner
懒惰地展平它们。然后它再次计算字节数。
tl;dr 字符串是自动解码的,这使得 splitLines 很慢。
splitLines 的当前实现会动态解码字符串,这使其速度很慢。在下一个版本的 phobos 中,这将是 fixed.
也会有一个 range 为您做这件事。
总的来说,D GC 不是最先进的,但是 D 使您有机会产生更少的垃圾。要获得有竞争力的程序,您需要避免无用的分配。第二件大事:对于快速代码使用 gdc 或 ldc,因为 dmd 的优势是快速生成代码而不是快速代码。
所以我没有计时但是这个版本不应该在最大行之后分配,因为它重用了缓冲区并且不解码UTF。
import std.stdio;
void main(string[] args)
{
auto f = File(args[1]);
// explicit mention ubyte[], buffer will be reused
// no UTF decoding, only looks for "\n". See docs.
int lineCount;
foreach(ubyte[] line; std.stdio.lines(f))
{
lineCount += 1;
}
writeln("lineCount: ", lineCount);
}
如果您需要,使用范围的版本可能如下所示 每行以终止符结尾:
import std.stdio, std.algorithm;
void main(string[] args)
{
auto f = File(args[1]);
auto lineCount = f.byChunk(4096) // read file by chunks of page size
` .joiner // "concatenate" these chunks
.count(cast(ubyte) '\n'); // count lines
writeln("lineCount: ", lineCount);
}
在下一个版本中,只需执行以获得接近最佳性能和 打破所有换行空白。
void main(string[] args)
{
auto f = File(args[1]);
auto lineCount = f.byChunk(4096) // read file by chunks of page size
.joiner // "concatenate" these chunks
.lineSplitter // split by line
.walkLength; // count lines
writeln("lineCount: ", lineCount);
}
int main()
{
import std.mmfile;
scope mmf = new MmFile(args[1]);
foreach(line; splitter(cast(string)mmf[], "\n"))
{
++linect;
}
writeln("There are: ", linect, " lines.");
return 0;
}
计算行数是否可以很好地代表文本处理应用程序的整体性能还存在争议。您正在测试 python 的 C 库的效率,就像其他任何东西一样,一旦您真正开始使用数据做有用的事情,您将得到不同的结果。 D 打磨标准库的时间比 Python 少,参与的人也少。 byLine 的性能已经讨论了几年了,我认为下一个版本会更快。
人们似乎确实发现 D 对于这类文本处理非常高效且富有成效。例如,AdRoll 以 python 商店而闻名,但他们的数据科学人员使用 D:
http://tech.adroll.com/blog/data/2014/11/17/d-is-for-data-science.html
回到问题上来,显然是在比较编译器和库,就像在比较语言一样。 DMD 的作用是作为参考编译器,并且编译速度快如闪电。所以它非常适合快速开发和迭代,但如果您需要速度,那么您应该使用 LDC 或 GDC,如果您确实使用 DMD,则打开优化并关闭边界检查。
在我的 arch linux 64 位 HP Probook 4530s 机器上,使用 WestburyLab usenet 语料库的最后 1mm 行,我得到以下内容:
python2:真实0m0.333s,用户0m0.253s,系统0m0.013s
pypy(预热):真实 0m0.286s,用户 0m0.250s,系统 0m0.033s
DMD(默认值): 真实 0m0.468s,用户 0m0.460s,系统 0m0.007s
DMD(-O -release -inline -noboundscheck): 真实 0m0.398s,用户 0m0.393s,系统 0m0.003s
GDC(默认值):真实 0m0.400s,用户 0m0.380s,系统 0m0.017s [不知道GDC优化的开关]
LDC(默认值):真实 0m0.396s,用户 0m0.380s,系统 0m0.013s
LDC(-O5): 真实 0m0.336s,用户 0m0.317s,系统 0m0.017s
在真实的应用程序中,人们会使用内置分析器来识别热点并调整代码,但我同意 naive D 应该有不错的速度,最差的情况下与 python 相同。并使用 LDC 进行优化,这确实是我们所看到的。
为了完整起见,我将您的 D 代码更改为以下内容。 (不需要一些导入 - 我在玩)。
import std.stdio;
import std.string;
import std.datetime;
import std.range, std.algorithm;
import std.array;
int main(string[] args)
{
if (args.length < 2) {
return 1;
}
auto t=Clock.currTime();
auto infile = File(args[1]);
uint linect = 0;
foreach (line; infile.byLine)
linect += 1;
auto t2=Clock.currTime-t;
writefln("There are: %s lines and took %s", linect, t2);
return 1;
}