Улучшение линейных операций ввода-вывода в D

Ответ 1

EDIT AND 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; подсчет байтов так же хорош, поэтому он преобразует строку в ее байтовое представление (бесплатно), а затем подсчитывает байты.

Последняя версия (мой fave) считывает 4KB данных из файла за раз и с лёгкостью сбрасывает их с помощью joiner. Затем он подсчитывает байты.

Ответ 2

Я думал, что сегодня буду делать что-то новое, поэтому решил "изучить" 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, это кажется ОК. Этот код может иметь производительность O(n²) в строках длиной более 8k, но я не уверен.

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

Ответ 3

Это спорно, является ли подсчет строк является хорошим показателем общей производительности в приложениях обработки текста. Вы тестируете эффективность библиотеки 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, включите оптимизацию и отключите проверку границ.

На моей 64-битной машине HP Probook 4530s с аркой Linux, использующей последние 1 мм строки уэстбери-сервера WestburyLab, я получаю следующее:

python2: real 0m0.333s, пользователь 0m0.253s, sys 0m0.013s

pypy (разогретый): real 0m0.286s, пользователь 0m0.250s, sys 0m0.033s

DMD (по умолчанию):               real 0m0.468s, пользователь 0m0.460s, sys 0m0.007s

DMD (-O -release -inline -noboundscheck):               real 0m0.398s, пользователь 0m0.393s, sys 0m0.003s

GDC (по умолчанию): реальный 0m0.400s, пользователь 0m0.380s, sys 0m0.017s [Я не знаю переключателей для оптимизации GDC]

LDC (по умолчанию): real 0m0.396s, пользователь 0m0.380s, sys 0m0.013s

LDC (-O5): реальный 0m0.336s, пользователь 0m0.317s, sys 0m0.017s

В реальном приложении можно использовать встроенный профилировщик для определения горячих точек и настройки кода, но я согласен с тем, что наивный 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;
}

Ответ 4

Это будет быстрее, чем ваша версия, нежели версия 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.");
}

Ответ 5

tl; dr автоматически декодируются, что замедляет работу splitLines.

Текущая реализация splitLines декодирует строку "на лету", что делает ее медленной. В следующей версии phobos это будет fixed.

Будет диапазон, который сделает это и для вас.

В общем, 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);
}

Ответ 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;
}