27 сентября 2010 г.

Задачка №5

На одном форуме увидел такую штуку.

Пусть есть такой код:
var
  S: String;
  List: TStringList;
begin
  ...
  while {SomeCondition} do
  begin
    // Формируем строку:
    S := '';
    while {SomeOtherCondition} do
      S := S + {...};
    
    List.Add(S);
  end;
  ...
end;
В этом коде мы для каждого чего-то формируем строку и сохраняем её в список.

Этот код работает нормально. Но если мы изменим код так:
var
  S, D: String;
  List: TStringList;
begin
  ...
  while {SomeCondition} do
  begin
    // Формируем строку:
    S := '';
    while {SomeOtherCondition} do
      S := S + {...};
    
    D := S;
    UniqueString(D);
    List.Add(D);
  end;
  ...
end;
То окажется, что новый код экономнее по расходу памяти на 30-50%.

Как это может быть? Объяснить видимое поведение.

Ответ на задачку будет выложен как обычно: примерно через месяц.

Ответ.

10 комментариев :

  1. При конкатации и, как следствие, расширении (grow) выделенного под S блока памяти, программа будет его расширять с "запасом", т.е. как раз на те 30%-50% (зависит от деталей реализации; в теории "золотым коеффициентом" будет корень из двух).

    При выполнении UniqueString копирование строки в новую область памяти "урежет" хвост, из-за чего и получим результирующую экономию в те самые 30%-50%.

    Следует также учесть, что тут выполняется дополнительное выделение памяти под D, что способствует ее фрагментации, а также пиковому ее потреблению. А в случае очень длинной строки и малого количества итераций верхнего цикла, и вовсе ставит под сомнение такую опимизацию.

    ОтветитьУдалить
  2. К словам предыдущего оратора можно добавить только рекомендацию использовать честный StringBuider, если уж хочется оптимизации.

    ОтветитьУдалить
  3. Знать бы версию Дельфи еще для ответа.
    Менеджер памяти сейчас до семерки включительно сильно разные. Сейчас FastMM, раньше другой.

    Да и вообще, как замерялся расход.

    Я задачки люблю ) Но тут, я думаю, очень все зависит от деталей. Опять же, на FastMM сильно влияют размеры блоков. Я в свое время его неплохо, как я думаю, изучил.

    Нужны детали. В абстрактном вакууме ответа не вижу.

    ОтветитьУдалить
  4. Это задачка на телепатию, а не на точный ответ.

    P.S. Это не оптимизация, а просто человек заметил различное поведение, казалось бы, идентичного кода.

    ОтветитьУдалить
  5. "..Чтобы получить уникальную ссылку для строки, состоящей из некоторой последовательности символов, можно воспользоваться функцией UniqueString. Это позволяет ускорить вычисления со строками, так как при этом можно будет сравнивать строки, просто сравнивая указатели на них. У таких строк refCnt всегда равен 1.." (с) http://www.rsdn.ru/article/Delphi/dynarrays.xml

    ОтветитьУдалить
  6. >>Следует также учесть, что тут выполняется дополнительное выделение памяти под D, что способствует ее фрагментации
    А ещё дополнительное освобождение памяти при S := '' (FreeMem). В первом случае при List.Add(S) происходило увеличение ReferenceCounter'а у S, и при S := '' (_LStrClr) не было вызова FreeMem, лишь снова уменьшаеся ReferenceCounter.

    ОтветитьУдалить
  7. Такие задачки просто не рождаются, видимо сильно критично была эта память.
    Тот же легендарный 8 гигабайтный лог )

    ОтветитьУдалить
  8. [code]procedure TForm1.Button1Click(Sender: TObject);
    var
    S, D: String;
    List: TStringList;
    i:integer;
    begin
    list:=tstringlist.Create;
    while true do
    begin
    S := '';
    for i:=0 to 100 do
    S := S + inttostr(random(26787));
    D := S;
    UniqueString(s);
    List.Add(s);
    end;
    end;[/code]

    а как определить, экономнее ли код, ведь память и так забивается за счет заполнения списка?

    ОтветитьУдалить
  9. гм... Очень любопытно, спасибо большое!
    А если у меня подобное но не `List.Add(S);` а `MyDinamicArrayOfStrings[i]:=S;` что-то изменится? Нужно будет UniqueString?

    ОтветитьУдалить
  10. И да. Как бы самому померить стал ли расход памяти экономнее и на сколько %?
    Любопытно что будет если обернуть в функцию, чтоб без переменной D и как-то более понятно. И у меня цикл-мутант, не придумал как вынести:

    SetLength(MyDinamicArrayOfStrings, maxN);
    n:=0;
    i:=1;
    buf := '';
    While (i <= maxI) And (n < maxN) Do
        Begin
        If (...) Then
            Begin
            MyDinamicArrayOfStrings[n] := buf;
            buf := '';
            Inc(n);
            End
        Else
            buf := buf + ...;
        Inc(i);
        End;
    If (n < maxN) Then
        MyDinamicArrayOfStrings[n] := buf;

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и (опционально) ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку (поддерживается OpenID).

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.