Быстрое заполнение строки в Delphi

Я пытался ускорить определенную процедуру в приложении, и мой профилировщик AQTime определил один метод, в частности, как узкое место. Метод был с нами годами и является частью "misc" -unit:

function cwLeftPad(aString:string; aCharCount:integer; aChar:char): string;
var
  i,vLength:integer;
begin
  Result := aString;
  vLength := Length(aString);
  for I := (vLength + 1) to aCharCount do    
    Result := aChar + Result;
end;

В той части программы, которую я оптимизирую в данный момент, метод был вызван ~ 35k раз, и это потребовало ошеломляющего 56% времени выполнения!

Легко видеть, что это ужасный способ левого ввода строки, поэтому я заменил ее на

function cwLeftPad(const aString:string; aCharCount:integer; aChar:char): string; 
begin
  Result := StringOfChar(aChar, aCharCount-length(aString))+aString;
end;

что дало значительный толчок. Общее время работы от 10,2 с до 5,4 сек. Потрясающие! Но cwLeftPad по-прежнему составляет около 13% от общего времени работы. Есть ли простой способ оптимизировать этот метод?

Ответ 1

Ваша новая функция включает три строки, вход, результат от StringOfChar и результат функции. Один из них уничтожается, когда возвращается ваша функция. Вы можете сделать это в два раза, ничто не будет уничтожено или перераспределено.

Выделите строку общей требуемой длины.
Заполните первую часть этого символа пробега.
Заполните оставшуюся часть входной строкой.

Вот пример:

function cwLeftPad(const aString: AnsiString; aCharCount: Integer; aChar: AnsiChar): AnsiString;
var
  PadCount: Integer;
begin
  PadCount := ACharCount - Length(AString);
  if PadCount > 0 then begin
    SetLength(Result, ACharCount);
    FillChar(Result[1], PadCount, AChar);
    Move(AString[1], Result[PadCount + 1], Length(AString));
  end else
    Result := AString;
end;

Я не знаю, предоставил ли Delphi 2009 и более поздние версии эквивалент FillChar на основе двухбайтовых Char, и если они это сделают, я не знаю, что он назвал, поэтому я изменил подпись функции явно использовать AnsiString. Если вам нужна WideString или UnicodeString, вам нужно будет найти замену FillChar, которая обрабатывает двухбайтовые символы. (FillChar имеет запутанное имя в Delphi 2009, поскольку оно не обрабатывает значения размера Char).

Еще одна вещь, которую следует учитывать, - это действительно ли вам часто так часто называть эту функцию. Самый быстрый код - это код, который никогда не запускается.

Ответ 2

Другая мысль - если это Delphi 2009 или 2010, отключите "String format checking" в Project, Options, Delphi Compiler, Compiling, Code Generation.

Ответ 3

StringOfChar очень быстрый, и я сомневаюсь, что вы можете улучшить этот код. Тем не менее, попробуйте это, возможно, быстрее:

function cwLeftPad(aString:string; aCharCount:integer; aChar:char): string;
var
  i,vLength:integer;
  origSize: integer;
begin
  Result := aString;
  origSize := Length(Result);
  if aCharCount <= origSize then
    Exit;
  SetLength(Result, aCharCount);
  Move(Result[1], Result[aCharCount-origSize+1], origSize * SizeOf(char));
  for i := 1 to aCharCount - origSize do
    Result[i] := aChar;
end;

EDIT: Я провел некоторое тестирование, и моя функция медленнее, чем ваш улучшенный cwLeftPad. Но я нашел что-то еще - вам не нужно 5 секунд для выполнения 35k функций cwLeftPad, кроме случаев, когда вы работаете на ПК XT или форматируете гигабайтные строки.

Я тестировал этот простой код

for i := 1 to 35000 do begin
  a := 'abcd1234';
  b := cwLeftPad(a, 73, '.');
end;

и я получил 255 миллисекунд для вашего оригинального cwLeftPad, 8 миллисекунд для вашего улучшенного cwLeftPad и 16 миллисекунд для моей версии.

Ответ 4

Вы вызываете StringOfChar каждый раз сейчас. Конечно, этот метод проверяет, есть ли у него что-то делать и выпрыгивает, если длина достаточно мала, но, возможно, вызов StringOfChar занимает много времени, потому что внутри он выполняет другой вызов перед тем, как выпрыгнуть.

Итак, моя первая идея - выпрыгнуть из себя, если нечего делать:

function cwLeftPad(const aString: string; aCharCount: Integer; aChar: Char;): string;
var
  l_restLength: Integer;
begin
  Result  := aString;
  l_restLength := aCharCount - Length(aString);
  if (l_restLength < 1) then
    exit;

  Result := StringOfChar(aChar, l_restLength) + aString;
end;

Ответ 5

Вы можете ускорить эту процедуру еще больше, используя массив поиска.

Конечно, это зависит от ваших требований. Если вы не против потерять память... Я предполагаю, что функция называется 35 k раз, но у нее нет 35000 различных отступов и много разных символов.

Итак, если вы знаете (или вы можете оценить каким-то быстрым способом) диапазон paddings и padding chars, вы можете построить двумерный массив, который включает эти параметры. Для простоты я предполагаю, что у вас есть 10 различных длин заполнения, и вы заполняете одним символом - ".", Поэтому в примере это будет одномерный массив.

Вы реализуете его следующим образом:

type
  TPaddingArray = array of String;

var
  PaddingArray: TPaddingArray;
  TestString: String;

function cwLeftPad4(const aString:string; const aCharCount:integer; const aChar:char; var anArray: TPaddingArray ): string;
begin
  Result := anArray[aCharCount-length(aString)] + aString;
end;

begin
  //fill up the array
  SetLength(StrArray, 10);
  PaddingArray[0] := '';
  PaddingArray[1] := '.';
  PaddingArray[2] := '..';
  PaddingArray[3] := '...';
  PaddingArray[4] := '....';
  PaddingArray[5] := '.....';
  PaddingArray[6] := '......';
  PaddingArray[7] := '.......';
  PaddingArray[8] := '........';
  PaddingArray[9] := '.........';

  //and you call it..
  TestString := cwLeftPad4('Some string', 20, '.', PaddingArray);
end;

Ниже приведены результаты тестов:

Time1 - oryginal cwLeftPad          : 27,0043604142394 ms.
Time2 - your modyfication cwLeftPad : 9,25971967336897 ms.
Time3 - Rob Kennedy version       : 7,64538131122457 ms.
Time4 - cwLeftPad4                  : 6,6417059620664 ms.

Обновленные тесты:

Time1 - oryginal cwLeftPad          : 26,8360194218451 ms.
Time2 - your modyfication cwLeftPad : 9,69653117046119 ms.
Time3 - Rob Kennedy version       : 7,71149259179622 ms.
Time4 - cwLeftPad4                  : 6,58248533610693 ms.
Time5 - JosephStyons version      : 8,76641780969192 ms.

Вопрос: стоит ли хлопот? -)

Ответ 6

Возможно, что StringOfChar может быстрее использовать для выделения совершенно новой строки длину строки и дополнения, а затем использовать перемещение для копирования существующего текста за его спиной.
Я думаю, что вы создаете две новые строки выше (одна с FillChar и одна с плюсом). Для этого требуется два выделения памяти и конструкции псевдо-объекта строки. Это будет медленным. Может быть, быстрее отбросить несколько циклов процессора, делая избыточное заполнение, чтобы избежать дополнительных операций с памятью.
Это может быть еще быстрее, если вы выделили пространство памяти, а затем сделали FillChar и Move, но дополнительный вызов fn может замедлить это.
Эти вещи часто являются пробными ошибками!

Ответ 7

Вы можете получить более высокую производительность, если предварительно выделите строку.

function cwLeftPadMine
{$IFDEF VER210}  //delphi 2010
(aString: ansistring; aCharCount: integer; aChar: ansichar): ansistring;
{$ELSE}
(aString: string; aCharCount: integer; aChar: char): string;
{$ENDIF}
var
  i,n,padCount: integer;
begin
  padCount := aCharCount - Length(aString);

  if padCount > 0 then begin
    //go ahead and set Result to what it final length will be
    SetLength(Result,aCharCount);
    //pre-fill with our pad character
    FillChar(Result[1],aCharCount,aChar);

    //begin after the padding should stop, and restore the original to the end
    n := 1;
    for i := padCount+1 to aCharCount do begin
      Result[i] := aString[n];
    end;
  end
  else begin
    Result := aString;
  end;
end;

И вот шаблон, полезный для сравнения:

procedure TForm1.btnPadTestClick(Sender: TObject);
const
  c_EvalCount = 5000;  //how many times will we run the test?
  c_PadHowMany = 1000;  //how many characters will we pad
  c_PadChar = 'x';  //what is our pad character?
var
  startTime, endTime, freq: Int64;
  i: integer;
  secondsTaken: double;
  padIt: string;
begin
  //store the input locally
  padIt := edtPadInput.Text;

  //display the results on the screen for reference
  //(but we aren't testing performance, yet)
  edtPadOutput.Text := cwLeftPad(padIt,c_PadHowMany,c_PadChar);

  //get the frequency interval of the OS timer    
  QueryPerformanceFrequency(freq);

  //get the time before our test begins
  QueryPerformanceCounter(startTime);

  //repeat the test as many times as we like
  for i := 0 to c_EvalCount - 1 do begin
    cwLeftPad(padIt,c_PadHowMany,c_PadChar);
  end;

  //get the time after the tests are done
  QueryPerformanceCounter(endTime);

  //translate internal time to # of seconds and display evals / second
  secondsTaken := (endTime - startTime) / freq;
  if secondsTaken > 0 then begin
    ShowMessage('Eval/sec = ' + FormatFloat('#,###,###,###,##0',
      (c_EvalCount/secondsTaken)));
  end
  else begin
    ShowMessage('No time has passed');
  end;
end;

Используя этот тестовый шаблон, я получаю следующие результаты:

The original: 5,000 / second
Your first revision: 2.4 million / second
My version: 3.9 million / second
Rob Kennedy version: 3.9 million / second