Improving line-wise I/O operations in D

Question

I need to process lots of medium to large files (a few hundred MB to GBs) in a linewise manner, so I'm interested in standard D approaches for iterating over lines. The foreach(line; file.byLine()) idiom seems to fit the bill and is pleasantly terse and readable, however performance seems to be less than ideal.

For example, below are two trivial programs in Python and D for iterating over the lines of a file and counting the lines. For a ~470 MB file (~3.6M lines) I get the following timings (best out of 10):

D times:

real    0m19.146s
user    0m18.932s
sys     0m0.190s

Python times (after EDIT 2, see below) :

real    0m0.924s
user    0m0.792s
sys     0m0.129s

Here's the D version, compiled with 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;
}

And now the corresponding Python version:

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

EDIT 2: I changed the Python code to use the more idiomatic for line in infile as suggested in the comments below, leading to an even greater speed-up for the Python version, which is now approaching the speed of the standard wc -l call to the Unix wc tool.

Any advice or pointers to what I might be doing wrong in D, that is giving such poor performance?

EDIT: And for comparison, here's a D version that throws the byLine() idiom out the window and sucks all the data into memory at once, and then splits the data into lines post-hoc. This gives better performance but is still about 2x slower than they Python version.

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;
}

The timings for this last version are as follows:

real    0m3.201s
user    0m2.820s
sys     0m0.376s

Answer 1

EDIT AND TL;DR: This problem has been solved in https://github.com/D-Programming-Language/phobos/pull/3089. The improved File.byLine performance will be available starting with D 2.068.

I tried your code on a text file with 575247 lines. The Python baseline takes about 0.125 seconds. Here's my codebase with timings embedded in the comments for each method. Explanations follow.

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;
}

I used dmd -O -release -inline for each variant.

The first version (slowest) reads one line at a time. We could and should improve the performance of byLine; currently it's hamstrung by things like mixed use of byLine with other C stdio operations, which is probably overly conservative. If we do away with that, we can easily do prefetching etc.

The second version reads the file in one fell swoop and then uses a standard algorithm to count the lines with a predicate.

The third version acknowledges the fact that there's no need to mind any UTF subtleties; counting bytes is just as fine, so it converts the string to its byte-wise representation (at no cost) and then counts the bytes.

The last version (my fave) reads 4KB of data from the file at a time and flattens them lazily using joiner. Then again it counts the bytes.

Answer 2

I thought I'd do something new today, so I decided to "learn" D. Please note that this is the first D I've written, so I might be completely off.

The first thing I tried was manually buffering:

foreach (chunk; infile.byChunk(100000)) {
    linect += splitLines(cast(string) chunk).length;
}

Note that this is incorrect since it ignores lines crossing boundaries, but fixing that comes later.

This helped a bit, but not nearly enough. It did allow me to test

foreach (chunk; infile.byChunk(100000)) {
    linect += (cast(string) chunk).length;
}

which showed that all the time was in splitLines.

I made a local copy of splitLines. This alone increased speed by a factor of 2! I wasn't expecting this. I'm running with both

dmd -release -inline -O -m64 -boundscheck=on
dmd -release -inline -O -m64 -boundscheck=off

It's about the same either way.

Then I rewrote splitLines to be specialized on s[i].sizeof == 1, which only seems to be slower than Python now because it also breaks on paragraph separators.

To finish it up, I made a Range and optimized it further, which gets the code close to Python's speed. Considering that Python doesn't break on paragraph separators and the code underlying it is written in C, this seems OK. This code may have O(n²) performance on lines longer than 8k long, but I'm not sure.

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;
}

Answer 3

It is debatable whether counting lines is a good proxy for overall performance in a text processing application. You are testing the efficiency of python's C library, as much as anything else, and you will get different results once you actually start doing useful things with the data. D has had less time than Python to hone the standard library, and there are fewer people involved. The performance of byLine has been under discussion for a couple of years now, and I think the next release will be faster.

People do seem to find D efficient and productive for text processing of exactly this sort. For example, AdRoll is well-known as a python shop, but their data science guys use D:

http://tech.adroll.com/blog/data/2014/11/17/d-is-for-data-science.html

To come back to the question, one is obviously comparing compilers and the library as much as one is the language. DMD's role is as the reference compiler, and one that compiles lightning fast. So it is great for rapid development and iteration, but if you need speed then you should use LDC or GDC, and if you do use DMD then turn on optimization and turn off bounds checking.

On my arch linux 64 bit HP Probook 4530s machine, using the last 1mm lines of the WestburyLab usenet corpus, I get the following:

python2: real 0m0.333s, user 0m0.253s, sys 0m0.013s

pypy (warmed up): real 0m0.286s, user 0m0.250s, sys 0m0.033s

DMD (defaults): real 0m0.468s, user 0m0.460s, sys 0m0.007s

DMD(-O -release -inline -noboundscheck): real 0m0.398s,user 0m0.393s,sys 0m0.003s

GDC (defaults): real 0m0.400s, user 0m0.380s, sys 0m0.017s [I don't know switches for GDC optimization]

LDC (defaults): real 0m0.396s,user 0m0.380s, sys 0m0.013s

LDC(-O5): real 0m0.336s, user 0m0.317s, sys 0m0.017s

In a real application, one will use the builtin profiler to identify hotspots and tweak the code, but I agree that naive D ought to be decent speed and at worst in same ballpark as python. And using LDC with optimization that is indeed what we see.

For completeness, I changed your D code to the following. (Some of the imports are not needed - I was playing around).

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;
}

Answer 4

This should be faster than your version even than python version:

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.");
}

Answer 5

tl;dr strings are auto-decoded, which makes splitLines slow.

The current implementation of splitLines decodes the string on the fly, which makes it slow. In the next version of phobos this will be fixed.

There will be a range that does that for you as well.

In general the D GC is not state of the art, however D gives you the opportunity to produce less garbage. To get a competitive program, you'll need to avoid useless allocations. Second big thing: For fast code use gdc or ldc, because the strength of dmd is to produce code fast and not fast code.

So I didn't time it but this version should not allocate after the biggest line, because it reuses the bufferand does not decode 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);
}

A version using ranges could look like this, if you require that every line ends with a terminator:

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);
}

In the next release, just do to get near optimal performance and breaking on all line breaking whitespace.

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);
}

Answer 6

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;
}