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

[SSerge]

может все таки не до оптимизировал?

Естественно, не дооптимизировал. Ибо дооптимизировать "до конца" будет означать переписать заново.

К примеру вот мы считываем строку и парсим, получаем первый параметр (C#):

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

            while ((s = sr.ReadLine()) != null)
            {
                string[] sp = s.Split('t');
                if (sp.Length < 11)
                {
                    ++Errors;
                    continue;
                }
                uint unixdate;
                try
                {
                    unixdate = uint.Parse(sp[0]);
                }
                catch (Exception e)
                {
                    ++Errors;
                    continue;
                }



Вот переведенное:

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

  sp:=TStringList.Create;
  while not eof(sr) do begin
    readln(sr,s);
    spl:=ParsingWithTabsSpaces(s,sp);
    if (spl < 11) then begin
      inc(Errors);
      continue;
    end;
    unixdate:=StrToIntDef(sp.Strings[0],0);
    if (unixdate=0) then begin
      inc(Errors);
      continue;
    end;



...Которое вместо обсосанного всячески рунтайма .net framework применяет вот такое вот самоделко:

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

function ParsingWithTabsSpaces(Var s:string; var sl:TStringList):integer;
Var s1:string;
    so:string;
    i:integer;
begin
  Result:=0;
  sl.Clear;
  so:=s;
  while true do begin
     so:=TrimLeft(so);
     if (so='') then break;
     s1:='';
     i:=1;
     while(true) do begin
        if not (so[i] in [#9,#32]) then
        begin
          s1+=so[i];
          if (i<>length(so)) then begin inc(i); continue; end;
        end;
        so:=Copy(so,i+1,256);
        inc(i);
        break;
     end;
     sl.Add(s1);
     inc(Result);
  end;
end;



Добавлено спустя 6 минут 5 секунд:
Для корректного сравнения по скорости, конечно, нужен сравниваемый код приводимый один к другому более адекватно.

Ну так оригинал то особо тоже не оптимизировался - сваян быстренько для получения результатов и работает. На стандартных средствах, подчеркиваю. А в переводе что ни строка, то buttheard - еще и надо крепко призадуматься, как это сделать - средств библиотек нет, то что есть - архаично-корявое. Вплоть до того (не задумывались кстати?) что у функций разный порядок следования аргументов. Это я про POS.

Добавлено спустя 3 минуты 47 секунд:
Я сейчас ради спортивного интереса занялся переводом этого самого на С++. Любопытно, какие показатели окажутся там. Уже вылавливаю очередной unhandled exception, созданный где-то вне моего кода при завершении программы.
Жесть вообще. У этой реализации приходится вообще менять логику работы из-за гениальной реализации STL

[bormant]

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

  p:=@s1[2];
  s1[6]:=#0;

Поменяйте строчки местами, сначала модифицируете строку, потом получаете адрес.

Результат работы зависит от наличия или отсутствия ключа компилятора {$H+}Если ключ есть, то дает ошибку, если нет - работает без ошибки. Но почему-то только на нижеприведенном примере.

0) Ваша строка изначально в сегменте кода, который read-only (либо количество ссылок на неё больше одной),
1) Вы взяли её адрес в памяти,
2) Вы попытались модифицировать строку,
3) сработал механизм copy-on-write,
4) строка была скопирована, была модифицирована копия, s1 изменился, а p -- нет, продолжая адресовать память со старой строкой,
5) Вы передали старое содержимое Val(), который наткнулся на пробел внутри числа и вернул ошибку.

Вот иллюстрация такого поведения в вашем коде, обратите внимание, что содержимое по указателю p -- старое значение строки "2.47 4 ", позиция ошибки 5 -- пробел после 2.47:

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

{$H+}
var
  s: string;
  p: pchar;
  xp: double;
  e: integer;
 
begin
  s := ' 2.47 4 ';
  p := @s[2];
  s[6] := #0;
  val(p, xp, e);
  writeln(p, '; ', xp, '; ', e);
end.


Прогон:

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

2.47 4 ;  0.00000000000000E+000; 5

[IvanS]

Поменяйте строчки местами, сначала модифицируете строку, потом получаете адрес.

Но почему если убрать {H+} (или поставить {H-}), то ошибка исчезает?

Добавлено спустя 6 минут 11 секунд:

3) сработал механизм copy-on-write,

Этого мне не надо. Как сделать так, чтобы я менял строку s, и по всем созданным указателям на строку тоже содержимое менялось?

[rxt]

Чтобы что-то оптимизировать, нужно посмотреть, как это устроено изнутри.

В самом деле, уже третью страницу обсуждается вопрос об оптимизации, а
код при этом выглядит так: s1+=so[i] из этого поста
или вот так: s1[6]:=#0 из этого.

Ну да ладно, попробуем поглядеть:

Попытка №1:

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

var
  i : Integer;
  Source, Dest : string;
begin
  Dest := '';
  for i := 1 to Length(Source) do
    Dest := Dest + Source[i]; // то же, что и Dest += Source[i]
end;


ассемблерный листинг:

Dest := Dest + Source[i];
lea eax, [ebp - $0C] ; 3-тья дополнительная строка, созданная компилятором
lea edx, [ebp - $04] ; Source
mov dl, [edx + esi - $01] ; символ Source[i]; esi = i(индекс)
call @LStrFromChar ; 1* выделяется память для 3-тьей строки и присваивается значение
mov edx, [ebp - $0C] ; 3-тья строка, уже содержащая символ Source[i]
lea eax, [ebp - $08] ; строка Dest
call @LStrCat; 2* объединение Dest + 3-тья строка
inc esi
for i := 1 to Length(Source) do ; счётчик цикла
dec ebx
jnz -$1E

1* - внутри подпрограммы(LStrFromChar) следуют вызовы -> call @LStrFromCharlen -> call @NewAnsiString -> call @Getmem -> ... call @LStrClr ...
2* - внутри подпрограммы(LStrCat) следуют вызовы -> call @LstrAsg -> call @LStrSetLength - call @Move -> ...

Как видим, при таком исходном коде создаётся ещё одна строка, в которую записывается символ.
Потом она объединяется с результирующей строкой. И в ходе этого происходит множественное
выделение \освобождение памяти.
Что с этим можно сделать? Теоретически, - вручную выделить один раз память под результирующую строку
и потом только изменять данные. Проверим на практике.

Попытка №2:

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

var
  i : Integer;
  Source, Dest : string;
begin
  SetLength(Dest, Length(Source));
  for i := 1 to Length(Source) do
    Dest[i] := Source[i]; // на первый взгляд ничего особенного
end;

ассемблерный листинг:

Dest := Dest + Source[i];
lea eax, [ebp - $08]; Dest
call @UniqueStringA ; 1* раздвоение Dest
mov edx, [ebp - $04]; Source
mov dl, [edx + ebx + $01] ; символ Source[i]; ebx = i(индекс)
mov [eax + ebx - $01], dl ; прямиком в Dest[i] ложем символ
inc ebx
for i := 1 to Length(Source) do ; счётчик цикла
dec esi
jnz -$17

1* - внутри подпрограммы(UniqueStringA), если на строку ещё есть ссылки, то -> call @NewAnsiString ...

На практике теория подтвердилась.
Уже лучше. На много лучше и быстрее. Но все же вызов некоторых подпрограмм остался.
Из справки: UniqueStringA вызывается только, когда приложение пытается модифицировать данные находящиеся в строке. Функция увеличивает счётчик на строку, копируя саму строку при необходимости.
Можно ли её тоже убрать? Попробуем.

Попытка №3:

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

var
  i : Integer;
  Source, Dest : string;
begin
  SetLength(Dest, Length(Source));
  for i := 1 to Length(Source) do
    PChar(Integer(Dest) + i - 1)^ := Source[i];  // красиво, не правда ли
end;

ассемблерный листинг:

PChar(Integer(Dest) + i - 1)^ := Source[i];
mov ecx, [ebp - $04] ; Source
mov cl, [ecx + eax -$01] ; символ Source[i]; eax= i(индекс)
mov esi, [ebp - $08] ; Dest
add esi, eax; cмещение указателя Dest
dec esi
mov [esi], cl ; прямиком в Dest[i] ложем символ
inc eax
for i := 1 to Length(Source) do ; счётчик цикла
dec edx
jnz -$13

Во. То, что доктор прописал. Ни одного косвенного вызова подпрограмм не происходит. Вот это да.
Вот это оптимизация. И это не конечная точка, есть ещё куда оптимизировать.


Всё вышесказанное справедливо как для Delphi так и для FPC.
Небольшие различия в названиях функций RTL:

LStrFromChar = fpc_char_to_ansistr
LStrCat = fpc_ansistr_concat
UniqueStringA = fpc_ansistr_uniquei

От себя порекомендую не грешить на директивы компилятора, а начать изучение механизма управления строками с замечательных статей: «Тонкости работы со строками» © Антон Григорьев и «Длинные строки и динамические массивы в Delphi» © Вишневский Павел.

[SSerge]

Уважаемый rxt нам наглядно пояснил, какие мы идиоты и почему наш говнокод сливает по производительности. Аргументированно и доходчиво. Я не ёрничаю, действительно всё правильно.
НО, понять не могу, почему даже этот код, в котором посимвольного добора строк нет вообще:

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

program fpcls;
{$mode objfpc}{$H+}

uses strutils,sysutils,dateutils;


function finds(s:AnsiString; var fsp, lsp:integer):boolean;
begin
    fsp := pos(' ',s);
    if (fsp<1) then fsp:=pos(#9,s);
    if (fsp<1) then exit(false);

    lsp := rpos(' ',s);
    if (lsp<1) then lsp:=rpos(#9,s);
    if (lsp<1) then exit(false);

    result:= fsp <> lsp;
end;

function tail(s:AnsiString):AnsiString;
Var fsp,lsp:integer;
begin
    finds(s, fsp, lsp);
    result:=Copy(s,lsp + 1);
end;

Var ts,te:TDateTime;
    fname:AnsiString;
    sr,sw:TextFile;
    s,s1,s2,s3:AnsiString;
    fsp,lsp:integer;
    what:boolean;
    sum:LongWord;
begin
     ts:=now;
     if (ParamCount<> 1) then begin
        writeln('No file name founded in command line');
        exit;
     end;
     fname := ParamStr(1);
     assign(sr,fname);
     assign(sw,fname+'.out');
     reset(sr);
     rewrite(sw);
     while not eof(sr) do begin
           readln(sr,s);
           what := finds(s, fsp, lsp);
           if (not what) then continue;

           s1 := Copy(s,fsp + 1, lsp - fsp - 1);

           what := finds(s1, fsp, lsp);

           s2 := Copy(s1,fsp + 1, lsp - fsp - 1);

           sum := length(s1) + length(s2);

           s3 := tail(s1);

           Write(sw,s2);
           Write(sw,#9);
           Write(sw,s3);
           Write(sw,#9);
           Write(sw,sum);
           Writeln(sw);
     end;
     CloseFile(sr);
     CloseFile(sw);

     te := now;

     writeln('Elapsed: ',SecondsBetween(te,ts),' seconds');
end.



... весьма ощутимо сливает по производительности вот этому коду:

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace csharpt
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime ts = DateTime.Now;

            if (args.Length != 1)
            {
                Console.WriteLine("No file name founded in command line");
                return;
            }
            string fname = args[0];
            StreamReader sr = new StreamReader(fname,Encoding.ASCII,false,32768);
            StreamWriter sw = new StreamWriter(fname + ".out",false,Encoding.ASCII,32768);
            string s, s1, s2, s3;
            int fsp, lsp;
            bool what;
            uint sum;
            while (null != (s = sr.ReadLine()))
            {
                what = finds(s, out fsp, out lsp);
                if (!what) continue;

                s1 = s.Substring(fsp + 1, lsp - fsp - 1);

                what = finds(s1, out fsp, out lsp);

                s2 = s1.Substring(fsp + 1, lsp - fsp - 1);

                sum = (uint)(s1.Length + s2.Length);

                s3 = tail(s1);

                sw.Write(s2);
                sw.Write("\t");
                sw.Write(s3);
                sw.Write("\t");
                sw.Write(sum);
                sw.WriteLine();
            }
            sr.Close();
            sw.Close();
            DateTime te = DateTime.Now;

            Console.WriteLine("Elapsed " + (te - ts).TotalSeconds + " seconds");

        }

        static bool finds(string s, out int fsp, out int lsp)
        {
            fsp = s.IndexOfAny(new char[] { ' ', '\t' });
            if (fsp == -1) { lsp = 0; return false; }

            lsp = s.LastIndexOfAny(new char[] { ' ', '\t' });
            if (lsp == -1) return false;

            return fsp != lsp;
        }

        static string tail(string s)
        {
            int fsp, lsp;
            finds(s, out fsp, out lsp);
            return s.Substring(lsp + 1);
        }

    }
}



FP: 81 секунда
C#: 21.4 секунд

[haword]

ну самое первое что в глаза бросается так это то что ты в функции finds в паскале делаешь 4 прохода по строке для поиска пробела или табуляции в c# 2 прохода. Вот тебе и двукратное увеличение времени. Перепиши функцию POS на свою где будешь ОДИН раз бежать по строке и возвращать первый найденный требуемый символ. И напиши результат.

[SSerge]

Ппц... Вот уж не ожидал.
Жабка. 28 секунд. С той же самой логикой поиска с четырьмя проходами по строке.

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

package javaa;

import java.io.*;
import java.util.*;

/**
*
* @author sir
*/
public class JavaA {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        fsp=lsp=0;
            long ts=System.currentTimeMillis();
           
            if (args.length != 1)
            {
                System.out.println("No file name founded in command line");
                return;
            }
            String fname = args[0];
            try {
                        BufferedReader sr=new BufferedReader(
                           new InputStreamReader(new FileInputStream(fname)));
                        BufferedWriter sw=new BufferedWriter(
                                new OutputStreamWriter(new FileOutputStream(fname+".out")));

                        String s, s1, s2, s3;

                        boolean what;
                        long sum;
                        while (null != (s = sr.readLine()))
                        {
                           
                            what = finds(s);
                           
                            if (!what)
                            {
                                continue;
                            }

                            s1 = s.substring(fsp + 1, fsp+1+lsp - fsp - 1);

                            what = finds(s1);

                            s2 = s1.substring(fsp + 1, fsp+1+lsp - fsp - 1);

                            sum = s1.length() + s2.length();

                            s3 = tail(s1);

                            sw.write(s2);
                            sw.write("\t");
                            sw.write(s3);
                            sw.write("\t");
                            sw.write(Long.toString(sum));
                            sw.newLine();
                        }
                        sr.close();
                        sw.close();
            } catch (Exception e) {
                System.out.println("I/O error:"+ e.toString());
            }
            long te=System.currentTimeMillis();
           
            System.out.println("Elapsed " + (te-ts)/1000 + " seconds");
    }
   
    static int fsp,lsp;
    static boolean finds(String s)
    {
            fsp = s.indexOf(' ');
            if (fsp == -1) { fsp=s.indexOf('\t'); }
            if (fsp == -1) { lsp = 0; return false; }

            lsp = s.lastIndexOf(' ');
            if (lsp == -1) { lsp=s.lastIndexOf('\t'); }
            if (lsp == -1) { return false; }

            return fsp != lsp;
    }

        static String tail(String s)
        {
            finds(s);
            return s.substring(lsp + 1);
        }
}



[haword]

у паскаля время какое новое?

Добавлено спустя 1 минуту 11 секунд:
кстати на делфи не пробовал пересобрать код и проверить? вроде как у последних делфей оптимизатор получше чем у фрипаскаля.

[Brainenjii]

выложите, плз, на какой-нибудь файлообменник пример файла.
Ещё вопрос - вы прогоняли результат через профилировщик? Или оптимизируете по кофейной гуще? ^_^

[bormant]

... и пример результата. Какой-то странный способ разбора, право слово.

[haword]

да и еще, попробуй убрать запись в файл и опять сравнить время.

[bormant]

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

var
  srbuf, swbuf: array [0..1024*8-1] of char;
...
  Reset(sr); Rewrite(sw);
  SetTextBuf(sr, srbuf); SetTextBuf(sw, swbuf);
...
  Writeln(sw, s2, #9, s3, #9, sum);


на время не повлияют ли?

[haword]

потестил на своем первом попавшемся текстовом файлике размером в 200 метров, делфи 7 компилятор делает фрипаскалевский 2,5,1 на одном и том же тексте в два раза.

[SSerge]

Строка исходного файла,
Поля разделены табулятором, конец строки - линуксовый CR (#10)

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

1359651612      6       10.254.254.18   65422   46.46.14.228    52427   1       52      ppp31   eth1    F


Строка, получающаяся в результате "парсинга":

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

10.254.254.18   65422   46.46.14.228    52427   1       52      ppp31   eth1    105


Что мы делаем.
- Построчно читаем исходный файл (s)
- копируем в S1 фрагмент, выделенный первым и последним табулятором из S
- копируем в S2 фрагмене, выделенный первым и последним табулятором из S1
- В S3 копируем фрагмент от последнего табулятора до конца строки из S
- в sum складываем длины строк S1 и S2
- s2,s3,sum разделенные табуляторами отписываем в результат

Практического применения конструкция, конечно, не имеет. Парсер сотворён исключительно ради спортивного интереса. То, что мне действительно нужно, имеет совсем другую логику обработки.
Так что если есть охота проверять тоже, можно нагенерировать какого-нибудь мусора, лишь бы структура примерно соблюдалась, ну и поля были переменной длины, чтобы не было линейности. Парсим файл длиною примерно 1.3 гигабайта.

Добавлено спустя 1 минуту 54 секунды:
Да, без профилировщика. Время замеряется и выводится самой программкой.

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

попробуй убрать запись в файл и опять сравнить время.

35 секунд у паскалевского при отключенном выводе получается.
Убирание анализа на "пробел" (т.е. 2 прохода вместо 4-х), дало 8 секунд.

Надо сказать, что весьма неконструктивные результаты получаются и не только на fpc.

Visual C++, через потоки и с использованием STL, тот же алгоритм - 236 секунд
Visual C++, Си-шные функции на структуре FILE * и строки-указатели, тот же алгоритм - 64 секунды.

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

srbuf, swbuf: array [0..1024*8-1] of char;

А вот это влияет хорошо. 35 секунд.

[bormant]

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

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

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

var
  fi, fo: text;
  bufi, bufo: array [0..1024*8-1] of char;
  s: AnsiString;
  ts, te:TDateTime;
 
procedure ParseLine(var f: text; const s: AnsiString);
var
  i, l: integer;
begin
  i := 1;
  l := length(s);
  while (i <= l) and (s[i] <> #9) and (s[i] <> #32) do inc(i);
  inc(i);
  while (i <= l) and (s[i] <> #9) and (s[i] <> #32) do inc(i);
  inc(i);
  while (l > i) and (s[l] <> #9) and (s[l] <> #32) do dec(l);
  if i >= l then exit;
  Writeln(f, copy(s, i, l - i), #9, l - i - 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.

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

35 секунд у паскалевского при отключенном выводе получается.

А вот это влияет хорошо. 35 секунд

То есть, установкой буферов удалось убрать накладные расходы ввода/вывода, можно заняться собственно алгоритмом разбора.

Добавлено спустя 5 минут 29 секунд:
И будет ли существенная разница, если избавиться от вызова copy():

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

procedure ParseLine(var f: text; var s: AnsiString);
var
  i, l: integer;
begin
  i := 1;
  l := length(s);
  while (i <= l) and (s[i] <> #9) and (s[i] <> #32) do inc(i);
  inc(i);
  while (i <= l) and (s[i] <> #9) and (s[i] <> #32) do inc(i);
  inc(i);
  while (l > i) and (s[l] <> #9) and (s[l] <> #32) do dec(l);
  if i >= l then exit;
  s[l] := #0;
  Writeln(f, pchar(@s[i]), #9, l - i - 1);
end;