Чтение и парсинг больших текстовых файлов

[SSerge]

Интересно, вот такой вариант сколько даст?

28 секунд.
Но это же неспортивно. Я понимаю, что сразу выкусив нужный участок строки и отправив его в выход, можно поднять быстродействие, но например если нужны все таки промежуточные строки? И, даже таким способом мы не догнали лидера, продолжающего работать по "неоптимальному алгоритму".

Добавлено спустя 4 минуты 27 секунд:

если избавиться от вызова copy():

27 секунд

[Brainenjii]

всё-таки воспользуйтесь профилировщиком. Вдруг проблема вообще в чтении из файла и всё решится заменой TextFile на TFileStream

[bormant]

Попробуйте измерить результаты вот этого варианта (в предыдущем присутствовал неявный вызов UniqueString() при модификации строки AnsiString):

Код: Выделить всё

{$H+,R-,Q-}
uses Strings, SysUtils, DateUtils;

var
  fi, fo: text;
  bufi, bufo: array [0..1024 * 8 - 1] of char;
  s: array[0..1024 * 2 - 1] of char;
  ts, te: TDateTime;

procedure ParseLine(var f: text; s: pchar);
var
  p, q: pchar;
  i: integer;
begin
  p := s;
  for i := 1 downto 0 do begin
    while not (p^ in [#0, #9, #32]) do inc(p);
    if p^ = #0 then Exit;
    inc(p);
  end;
  q := StrEnd(p);
  while (q > p) and not (q^ in [#9, #32]) do dec(q);
  if q = p then Exit;
  q^ := #0;
  Writeln(f, p, #9, q - p - 1);
end;

begin
  if ParamCount <> 1 then begin
    writeln('Usage: parse2 filename');
    exit;
  end;
  ts := now;
  Assign(fi, ParamStr(1)); Assign(fo, Paramstr(1)+'.out');
  Reset(fi); Rewrite(fo);
  SetTextBuf(fi, bufi); SetTextBuf(fo, bufo);
  while not SeekEof(fi) do begin
    Readln(fi, s); ParseLine(fo, s);
  end;
  Close(fi); Close(fo);
  te := now;
  Writeln('Elapsed: ', SecondsBetween(te, ts), ' seconds');
end.


[SSerge]

результаты вот этого варианта

28 секунд

[bormant]

Ок, а если директивы поменять на {$H+,R-,Q-,I-} ?
А если теперь убрать вызов ParseLine, то есть замерить чистое время на чтение ?
Вернуть вызов, ParseLine но на входе сразу поставить exit (время чтения + вызов) ?
Убрать exit, закомментировать Writeln() (время чтения + вызов + обработка, без вывода) ?

[SSerge]

Похоже, можно ставить точку попыткам еще выдавить скорость из "нашего тестового примера".
Потестировал на других машинах. Увы, линуксовых. Но тенденция проглядывается.

Вот что получилось в итоге.

Intel Core I5-2450M, двухядерка с гипертредингом, 64х Windows 7, RAM 6G:
(на этой изначально тренировались)

C# - 21.4 сек.
Java - 28 сек.
fp - 80 сек.
Visual C++ (fgets/fprintf) - 64 сек.

Intel Atom 540 - двухъядерка с гипертредингом, 1.6 GHz, RAM 2Gb, Debian Linux, 32x:

C# (тот же файл под mono): 247 сек.
Java: 114 сек.
fp: 108 сек.
GCC (fgets/fprintf): 183 сек.

Intel Celeron D, 2.4 GHz, Одноядерник без гипертрединга, RAM 2Gb, Debian Linux 32x:

C# (mono): 285 сек.
Java: 199 сек.
fp: 100 сек.
GCC: 156 сек.

То есть, тотальный выброс производительности на C# и JAVA получается только на многоядерных процессорах. Отсюда подозрение, что .net и виртуальная машина жабки в процессе работы распараллеливают какие-то операции - либо I/O, либо сами вычисления, либо копирование блоков памяти. Ибо C# под неполноценной средой исполнения сдулась сразу, а жабка - на чисто одноядерном процессоре ушла на показатели, где ее обычно привыкли позиционировать.

К приложению fpc для парсинга файлов из одного в другой, получаются две важные детали:

1. Обязательно поставить должное значение буферизации SetTextBuffer для открытых файлов, иначе производительность падает очень заметно
2. Транслировать все собственные функции (коды) обработки строк в ассемблер и внимательно смотреть, чтобы не появлялись фантомные присваивания и выделения памяти под промежуточные строки, иначе опять же производительность резко деградирует. Выбор между двумя полюсами - катастрофически медленная работа со строками - либо весьма плохо анализируемый и запутанный код работы с ними через указатели, с привязкой к внутреннему представлению.

Ну, и мы работаем на одном ядре. Всегда. Потому сишарп на некоторых машинах не обогнать в принципе. Ну, или ценой усилий, не стоящих того. Как то так.

Добавлено спустя 6 минут 13 секунд:
Да, полный оутсайд у строково-потоковой реализации на С++ STL, 236 секунд на первой машине
(на g++ даже откомпилировать не удалось, лезут ошибки макроопределений библиотек iostream)
и у fpc, стоит заменить ему строки на UnicodeString - 819 секунд.
Если поменять функции POS/RPOS на самописные - 297 секунд.

Жабка, кстати при работе со строками получается в некоторых случаях необчно привлекательной. Не забываем, с _какими_ она строками работает, это не жалкие байты. Получается, что шустро работает, зараза.

[bormant]

Тестовый пример (оставлен только файловый вывод):

Код: Выделить всё

{$H+,R-,Q-,I-}
{$mode objfpc}
uses Strings, SysUtils, DateUtils;

var
  fi, fo: text;
  bufi, bufo: array [0..1024*8-1] of char;
  s: array[0..1024*2-1] of char;
  ts, te:TDateTime;
  i: LongWord;

procedure ParseLine(var f: text; s: pchar);
var
  p, q: pchar;
  i: integer;
begin
  p := s;
  for i := 1 downto 0 do begin
    while not (p^ in [#0, #9, #32]) do inc(p);
    if p^ = #0 then exit;
    inc(p);
  end;
  q := StrEnd(p);
  while (q > p) and not (q^ in [#9, #32]) do dec(q);
  if q = p then exit;
  q^ := #0;
  Writeln(f, p, #9, q - p - 1);
end;
const
  sTestLine: string[255] = '1359651612'#9'6'#9'10.254.254.18'#9'65422'#9'46.46.14.228'#9'52427'#9'1'#9'52'#9'ppp31'#9'eth1'#9'F'#0;
begin
  if ParamCount <> 1 then begin
    writeln('Usage: parse2 filename');
    exit;
  end;
  ts := now;
  //Assign(fi, ParamStr(1));
  //Reset(fi);
  //SetTextBuf(fi, bufi);
  Assign(fo, Paramstr(1)+'.out');
  Rewrite(fo);
  SetTextBuf(fo, bufo);
  //while not seekeof(fi) do begin
  //  readln(fi, s); //
  for i:= $FFFFFF downto 0 do begin
    move(sTestLine[1], s, length(sTestLine));
    ParseLine(fo, s);
  end;
  //close(fi);
  close(fo);
  te := now;
  writeln('Elapsed: ', SecondsBetween(te, ts), ' seconds');
end.


Собираем с поддержкой профайлера и asm-листингом, тестируем (скорости невелики ибо действие происходит в ВМ):

Код: Выделить всё

$ fpc -al -pg parse3
$ time parse3 parse.txt; du -h parse.txt.out; gprof --flat parse3
Elapsed: 31 seconds

real   0m32.541s
user   0m7.498s
sys   0m2.245s
929M   parse.txt.out
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
time   seconds   seconds    calls   s/call   s/call  name   
19.73      1.72     1.72                             SYSTEM_FPSYSCALL$INT64$INT64$INT64$INT64$$INT64
16.51      3.16     1.44 16777216     0.00     0.00  P$PROGRAM_PARSELINE$TEXT$PCHAR
14.45      4.42     1.26                             FPC_PCHAR_LENGTH
12.61      5.52     1.10                             SYSUTILS_STREND$PCHAR$$PCHAR
10.15      6.41     0.89                             SYSTEM_INT_STR$INT64$OPENSTRING
  8.95      7.19     0.78                             FPC_MOVE
  5.16      7.64     0.45                             SYSTEM_FPC_WRITEBUFFER$TEXT$formal$INT64
  3.33      7.93     0.29                             fpc_write_text_char
  2.41      8.14     0.21                             fpc_write_text_pchar_as_pointer
  1.38      8.26     0.12                             fpc_write_text_sint
  1.26      8.37     0.11                             fpc_writeln_end
  0.80      8.44     0.07                             fpc_write_text_shortstr
  0.63      8.49     0.06                             FPC_SHORTSTR_SINT
  0.46      8.53     0.04        1     0.04     1.48  PASCALMAIN
  0.46      8.57     0.04                             fpc_get_output
  0.34      8.60     0.03                             fpc_write_text_pchar_as_array_iso
  0.23      8.62     0.02                             SYSTEM_GET_CALLER_FRAME$POINTER$$POINTER
  0.23      8.64     0.02                             fpc_write_end
  0.23      8.66     0.02                             fpc_write_text_boolean_iso
  0.17      8.68     0.02                             SYSTEM_INT_STR$LONGWORD$OPENSTRING
  0.11      8.69     0.01                             SYSTEM_FILEWRITEFUNC$TEXTREC
  0.11      8.70     0.01                             SYSTEM_FPSYSCALL$INT64$INT64$$INT64
  0.11      8.71     0.01                             fpc_shortstr_to_chararray
  0.11      8.72     0.01                             frame_dummy
  0.06      8.72     0.01                             SYSTEM_SPACE$BYTE$$SHORTSTRING


Добавлено спустя 14 минут 53 секунды:
На преобразование целого в строку (SYSTEM_INT_STR$INT64$OPENSTRING) при выводе ушло 10,2% всего времени выполнения.
На обнаружение конца строки явным вызовом StrEnd() (SYSUTILS_STREND$PCHAR$$PCHAR) -- 12,6% плюс RTL код потратил на то же самое 14,45% (FPC_PCHAR_LENGTH).
Собственно ParseLine() (P$PROGRAM_PARSELINE$TEXT$PCHAR) занимает всего 16,5% времени, что соизмеримо с прочими затратами.
Скорее всего, переход на blockread(), однократный поиск в буфере с кэшированием найденных позиций способен улучшить ситуацию, но надо проверять дополнительно.

[Brainenjii]

И попробуйте всё-таки прогнать с TFileStream

[Mirage]

Мда, не думал, что Моно так по скорости от дотнета отстаёт.
По производительности FPC:
Она, конечно, не очень, но Яву с шарпом обгонять должно. А от С отставать. У топикстартера все наоборот.

Вычисления ни ява ни шарп автоматом не распараллеливают. Техника еще до такого не дошла. I/O распараллеливать смысла нет.
Скорее всего, причина в том, что сравнивается самописная, причем не очень качественно, функция, с готовыми, включенными в платформу, а значит предельно вылизанными средствами.
Например, чтение файла наверняка буферизируется, а работа со строками вкомпилирована в код виртуальной машины.

Для FPC тоже наверняка есть соответствующие средства, просто никто не включает их в RTL. Хашмапы так точно есть. В FastCode было что-то для строк.

[debi12345]

Также можно использовать ExecRegExpr(для отсева комментов) и SplitRegExpr (для разбиения) модуля регулярных выражений
http://www.likan.uz/uploads/RegExpr.pas
есссно обрабатывать файл построчно.

Добавлено спустя 6 часов 48 минут 19 секунд:
Вариант также с отсевом комментов, берутся 3 первые числа в каждой строке.
На CPU=С2D E8400, RAM=4G DDR3, HDD=170МБайт/с, тестовый (250 МБайт) файл обрабатывается 160 секунд, из них 30 сек на чтение входных данных и 20 сек на запись выходных :

Код: Выделить всё

program ddin;
{$mode objfpc}{$apptype console}

uses regexpr,msestream,msestrings,classes,strutils, mseformatstr;

var
  s1: msestring;
  sa1: msestringarty;
  fs: ttextstream;
  r0,r1,r2: double;

begin
if ParamCount <> 1 then halt;
fs:= ttextstream.create(ParamStr(1));
with fs do begin
  try
    while not eof do begin
     readln(s1);
     s1:= ReplaceRegExpr('(^\s*)(\S+)\s+(\S+)\s+(\S+)(.*)',s1,'$2,$3,$4',true);
     sa1:= splitstring(s1,',',true);
     if high(sa1) < 2 then continue;
     if trystrtorealtydot(sa1[0],r0) and trystrtorealtydot(sa1[1],r1) and trystrtorealtydot(sa1[2],r2) then begin
       system.writeln(r0,r1,r2);
     end;
    end;
  finally
    close;
    free;
  end;
end;

end.


Итого 110 секунд тупо на обработку. И это без TStringList. Тормоза !