Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
 Производительность StringReplace  [new]
DmSer
Member

Откуда: Пенза
Сообщений: 850
Решил сравнить встроенную функцию StringReplace в Tokyo со своей реализацией FastStringReplace. И был приятно удивлён: современная реализация StringReplace очень быстрая, в большинстве случаях бьёт по скорости мой вариант, иногда в несколько раз.
Мы привыкли ругать слабую оптимизацию, тормозной rtl, однако прогресс всё же идёт, это радует.
13 апр 19, 10:03    [21861042]     Ответить | Цитировать Сообщить модератору
 Re: Производительность StringReplace  [new]
Miracle9
Member

Откуда:
Сообщений: 114
DmSer, Интересная инфа, спасибо!
13 апр 19, 10:52    [21861054]     Ответить | Цитировать Сообщить модератору
 Re: Производительность StringReplace  [new]
haydegen
Member

Откуда:
Сообщений: 186
DmSer
Решил сравнить встроенную функцию StringReplace в Tokyo со своей реализацией FastStringReplace. И был приятно удивлён: современная реализация StringReplace очень быстрая, в большинстве случаях бьёт по скорости мой вариант, иногда в несколько раз.
Мы привыкли ругать слабую оптимизацию, тормозной rtl, однако прогресс всё же идёт, это радует.




хм... а этот https://bitbucket.org/alex7691/delphi/src/ как в сравнении с Tokyo SR?
13 апр 19, 12:41    [21861109]     Ответить | Цитировать Сообщить модератору
 Re: Производительность StringReplace  [new]
rgreat
Member

Откуда:
Сообщений: 5078
Сам сравни. :)

+
function StringReplace(const Source, OldPattern, NewPattern: string; Flags: TReplaceFlags): string;
var
  Str: string;
  xOldPattern: string;
  FoundPos: Integer;
  I, J: Integer;
  SourceIdx: Integer;
  DestIdx: Integer;
  LCharsToCopy: Integer;
  FindCount: Integer;
  PosArray: array of Integer;
  LenOP: Integer;
  LenNP: Integer;
  LenS: Integer;
  ArrLen: Integer;
  LPResult, LPSource, LPNewPattern: PChar;
  LReplaceAll: Boolean;
begin
  LenOP := Length(OldPattern);
  LenS := Length(Source);
  if (LenOP = 0) or (LenS = 0) then
    Exit(Source);

  if rfIgnoreCase in Flags then
  begin
    xOldPattern := AnsiUpperCase(OldPattern);
    LenOP := Length(xOldPattern);
    if SameStr(xOldPattern, AnsiLowerCase(OldPattern)) then // Special case, for example only symbols (+ - , * .....)
      Str := Source
    else
    begin
      Str := AnsiUpperCase(Source);
      LenS := Length(Str);
    end;
  end
  else
  begin
    xOldPattern := OldPattern;
    Str := Source;
  end;

  if Str.Length <> Source.Length then
  begin
    Result := '';
    I := Low(string);
    while I <= High(Source) do
    begin
      if string.Compare(Source, I - Low(string), OldPattern, 0, LenOP, True) = 0 then
      begin
        Result := Result + NewPattern;
        Inc(I, LenOP);
        if not (rfReplaceAll in Flags) then
        begin
          Result := Result + Source.Substring(I - Low(string), MaxInt);
          Break;
        end;
      end
      else
      begin
        Result := Result + Source[I];
        Inc(I);
      end;
    end;
  end
  else
  begin
    FoundPos := 1;
    FindCount := 0;
    ArrLen := 0;
    LReplaceAll := not (rfReplaceAll in Flags);
    repeat
      FoundPos := Pos(xOldPattern, Str, FoundPos);
      if FoundPos = 0 then
        Break;

      Inc(FindCount);
      if ArrLen < FindCount then
      begin
        if ArrLen = 0 then
          ArrLen := 32
        else
          ArrLen := ArrLen * 2;
        SetLength(PosArray, ArrLen);   // call SetLength less frequently makes a huge difference when replacing multiple occurrences
      end;
      PosArray[FindCount - 1] := FoundPos - 1; // Zero based array
      Inc(FoundPos, LenOP);
    until LReplaceAll;

    if FindCount > 0 then
    begin
      LenNP := Length(NewPattern);
      LPSource := Pointer(Source);           // We use a pointer cast to avoid the _UStrToPWChar call injected by the compiler
      LPNewPattern := Pointer(NewPattern);  // We use a pointer cast to avoid the _UStrToPWChar call injected by the compiler
      if LenNP = LenOP then
      begin                           // special case where Length(OldPattern) = Length(NewPattern)
        SetLength(Result, LenS);      // in this case, we can optimize it even further
        LPResult := Pointer(Result);    // We use a pointer cast to avoid the uniquestring call injected by the compiler
        Move(LPSource^, LPResult^, LenS * SizeOf(Char));
        if LenNP = 1 then
          for I := 0 to FindCount - 1 do
            LPResult[PosArray[I]] := LPNewPattern^
        else if LenNP <= 8 then
          for I := 0 to FindCount - 1 do
            for J := 0 to LenNP -1  do
              LPResult[PosArray[I] + J] := LPNewPattern[J]
        else
          for I := 0 to FindCount - 1 do
            Move(LPNewPattern^, LPResult[PosArray[I]], LenNP * SizeOf(Char));
      end
      else
      begin
        SetLength(Result, LenS + ((LenNP - LenOP) * FindCount));
        LPResult := Pointer(Result);    // We use a pointer cast to avoid the uniquestring call injected by the compiler
        SourceIdx := 0;
        DestIdx := 0;
        if LenNP = 0 then
          for I := 0 to FindCount - 1 do
          begin
            LCharsToCopy := PosArray[I] - SourceIdx;
            if LCharsToCopy > 0 then
            begin
              if LCharsToCopy = 1 then
              begin
                LPResult[DestIdx] := LPSource[SourceIdx];
                Inc(SourceIdx);
                Inc(DestIdx);
              end
              else if LCharsToCopy <= 8 then
              begin
                for J := 0 to LCharsToCopy - 1  do
                  LPResult[DestIdx + J] := LPSource[SourceIdx + J];
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end
              else
              begin
                Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end;
            end;
            Inc(SourceIdx, LenOP);
          end
        else if LenNP = 1 then
          for I := 0 to FindCount - 1 do
          begin
            LCharsToCopy := PosArray[I] - SourceIdx;
            if LCharsToCopy > 0 then
            begin
              if LCharsToCopy = 1 then
              begin
                LPResult[DestIdx] := LPSource[SourceIdx];
                Inc(SourceIdx);
                Inc(DestIdx);
              end
              else if LCharsToCopy <= 8 then
              begin
                for J := 0 to LCharsToCopy - 1  do
                  LPResult[DestIdx + J] := LPSource[SourceIdx + J];
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end
              else
              begin
                Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end;
            end;
            LPResult[DestIdx] := LPNewPattern[0];
            Inc(DestIdx);
            Inc(SourceIdx, LenOP);
          end
        else
          for I := 0 to FindCount - 1 do
          begin
            LCharsToCopy := PosArray[I] - SourceIdx;
            if LCharsToCopy > 0 then
            begin
              if LCharsToCopy = 1 then
              begin
                LPResult[DestIdx] := LPSource[SourceIdx];
                Inc(SourceIdx);
                Inc(DestIdx);
              end
              else if LCharsToCopy <= 8 then
              begin
                for J := 0 to LCharsToCopy - 1  do
                  LPResult[DestIdx + J] := LPSource[SourceIdx + J];
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end
              else
              begin
                Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end;
            end;
            Move(LPNewPattern^, LPResult[DestIdx], LenNP * SizeOf(Char));
            Inc(DestIdx, LenNP);
            Inc(SourceIdx, LenOP);
          end;

        LCharsToCopy := LenS - SourceIdx;
        if LCharsToCopy > 0 then
          Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
      end;
    end
    else
      Result := Source;
  end;
end;
13 апр 19, 12:47    [21861116]     Ответить | Цитировать Сообщить модератору
 Re: Производительность StringReplace  [new]
defecator
Member

Откуда:
Сообщений: 39282
rgreat
Сам сравни. :)

+
function StringReplace(const Source, OldPattern, NewPattern: string; Flags: TReplaceFlags): string;
var
  Str: string;
  xOldPattern: string;
  FoundPos: Integer;
  I, J: Integer;
  SourceIdx: Integer;
  DestIdx: Integer;
  LCharsToCopy: Integer;
  FindCount: Integer;
  PosArray: array of Integer;
  LenOP: Integer;
  LenNP: Integer;
  LenS: Integer;
  ArrLen: Integer;
  LPResult, LPSource, LPNewPattern: PChar;
  LReplaceAll: Boolean;
begin
  LenOP := Length(OldPattern);
  LenS := Length(Source);
  if (LenOP = 0) or (LenS = 0) then
    Exit(Source);

  if rfIgnoreCase in Flags then
  begin
    xOldPattern := AnsiUpperCase(OldPattern);
    LenOP := Length(xOldPattern);
    if SameStr(xOldPattern, AnsiLowerCase(OldPattern)) then // Special case, for example only symbols (+ - , * .....)
      Str := Source
    else
    begin
      Str := AnsiUpperCase(Source);
      LenS := Length(Str);
    end;
  end
  else
  begin
    xOldPattern := OldPattern;
    Str := Source;
  end;

  if Str.Length <> Source.Length then
  begin
    Result := '';
    I := Low(string);
    while I <= High(Source) do
    begin
      if string.Compare(Source, I - Low(string), OldPattern, 0, LenOP, True) = 0 then
      begin
        Result := Result + NewPattern;
        Inc(I, LenOP);
        if not (rfReplaceAll in Flags) then
        begin
          Result := Result + Source.Substring(I - Low(string), MaxInt);
          Break;
        end;
      end
      else
      begin
        Result := Result + Source[I];
        Inc(I);
      end;
    end;
  end
  else
  begin
    FoundPos := 1;
    FindCount := 0;
    ArrLen := 0;
    LReplaceAll := not (rfReplaceAll in Flags);
    repeat
      FoundPos := Pos(xOldPattern, Str, FoundPos);
      if FoundPos = 0 then
        Break;

      Inc(FindCount);
      if ArrLen < FindCount then
      begin
        if ArrLen = 0 then
          ArrLen := 32
        else
          ArrLen := ArrLen * 2;
        SetLength(PosArray, ArrLen);   // call SetLength less frequently makes a huge difference when replacing multiple occurrences
      end;
      PosArray[FindCount - 1] := FoundPos - 1; // Zero based array
      Inc(FoundPos, LenOP);
    until LReplaceAll;

    if FindCount > 0 then
    begin
      LenNP := Length(NewPattern);
      LPSource := Pointer(Source);           // We use a pointer cast to avoid the _UStrToPWChar call injected by the compiler
      LPNewPattern := Pointer(NewPattern);  // We use a pointer cast to avoid the _UStrToPWChar call injected by the compiler
      if LenNP = LenOP then
      begin                           // special case where Length(OldPattern) = Length(NewPattern)
        SetLength(Result, LenS);      // in this case, we can optimize it even further
        LPResult := Pointer(Result);    // We use a pointer cast to avoid the uniquestring call injected by the compiler
        Move(LPSource^, LPResult^, LenS * SizeOf(Char));
        if LenNP = 1 then
          for I := 0 to FindCount - 1 do
            LPResult[PosArray[I]] := LPNewPattern^
        else if LenNP <= 8 then
          for I := 0 to FindCount - 1 do
            for J := 0 to LenNP -1  do
              LPResult[PosArray[I] + J] := LPNewPattern[J]
        else
          for I := 0 to FindCount - 1 do
            Move(LPNewPattern^, LPResult[PosArray[I]], LenNP * SizeOf(Char));
      end
      else
      begin
        SetLength(Result, LenS + ((LenNP - LenOP) * FindCount));
        LPResult := Pointer(Result);    // We use a pointer cast to avoid the uniquestring call injected by the compiler
        SourceIdx := 0;
        DestIdx := 0;
        if LenNP = 0 then
          for I := 0 to FindCount - 1 do
          begin
            LCharsToCopy := PosArray[I] - SourceIdx;
            if LCharsToCopy > 0 then
            begin
              if LCharsToCopy = 1 then
              begin
                LPResult[DestIdx] := LPSource[SourceIdx];
                Inc(SourceIdx);
                Inc(DestIdx);
              end
              else if LCharsToCopy <= 8 then
              begin
                for J := 0 to LCharsToCopy - 1  do
                  LPResult[DestIdx + J] := LPSource[SourceIdx + J];
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end
              else
              begin
                Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end;
            end;
            Inc(SourceIdx, LenOP);
          end
        else if LenNP = 1 then
          for I := 0 to FindCount - 1 do
          begin
            LCharsToCopy := PosArray[I] - SourceIdx;
            if LCharsToCopy > 0 then
            begin
              if LCharsToCopy = 1 then
              begin
                LPResult[DestIdx] := LPSource[SourceIdx];
                Inc(SourceIdx);
                Inc(DestIdx);
              end
              else if LCharsToCopy <= 8 then
              begin
                for J := 0 to LCharsToCopy - 1  do
                  LPResult[DestIdx + J] := LPSource[SourceIdx + J];
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end
              else
              begin
                Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end;
            end;
            LPResult[DestIdx] := LPNewPattern[0];
            Inc(DestIdx);
            Inc(SourceIdx, LenOP);
          end
        else
          for I := 0 to FindCount - 1 do
          begin
            LCharsToCopy := PosArray[I] - SourceIdx;
            if LCharsToCopy > 0 then
            begin
              if LCharsToCopy = 1 then
              begin
                LPResult[DestIdx] := LPSource[SourceIdx];
                Inc(SourceIdx);
                Inc(DestIdx);
              end
              else if LCharsToCopy <= 8 then
              begin
                for J := 0 to LCharsToCopy - 1  do
                  LPResult[DestIdx + J] := LPSource[SourceIdx + J];
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end
              else
              begin
                Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
                Inc(SourceIdx, LCharsToCopy);
                Inc(DestIdx, LCharsToCopy);
              end;
            end;
            Move(LPNewPattern^, LPResult[DestIdx], LenNP * SizeOf(Char));
            Inc(DestIdx, LenNP);
            Inc(SourceIdx, LenOP);
          end;

        LCharsToCopy := LenS - SourceIdx;
        if LCharsToCopy > 0 then
          Move(LPSource[SourceIdx], LPResult[DestIdx], LCharsToCopy * SizeOf(Char));
      end;
    end
    else
      Result := Source;
  end;
end;


развернул спойлер, и стало страшно
13 апр 19, 21:17    [21861317]     Ответить | Цитировать Сообщить модератору
Все форумы / Delphi Ответить