VPF::Сборка мусора по поколениям - Форум программистов

lukas

Дата 26.1.2011, 15:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 771
Регистрация: 23.2.2007

Репутация: нет
Всего: 15

Приветствую, перечитал кучу статей про теорию сборки мусора, в частности до меня никак не может дойти один момент.

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

Пометить и подмести + несколько поколений.

Допустим у меня есть сущность MEMORY и LIST of MEMORY (типа массив). Когда мы создаем новое значение MEMORY оно становится достижимым по умолчанию (которое нельзя удалять из памяти).

Но у нас например есть массивы LIST of MEMORY, где допустим один элемент может ссылаться сам на массив к которому сам принадлежит, получается циклическая структура. Но встает главное проблема, как просканировать эту структуру так, чтобы самому не зациклиться. Например, мне надо что-то сделать со всеми элементами в LIST of MEMORY и естественно, если какой-то элемент ссылается на новый список я рекурсивно захожу внутрь, но это в циклических структурах ведет к зацикливанию и переполнению стека. Что делать в этом случае? Это очень тесно связано со сборкой мусора.

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

Это сообщение отредактировал(а) lukas - 26.1.2011, 15:24

--------------------

http://code.google.com/p/orionphp/ - opensource скриптовой язык Orion (аналог PHP) для freepascal/delphi.

baldina

Дата 26.1.2011, 17:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 4
Всего: 101

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

lukas

Дата 26.1.2011, 18:38 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 771
Регистрация: 23.2.2007

Репутация: нет
Всего: 15

Цитата(baldina @ 26.1.2011, 17:44

)

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

Надо просто составить быстро список всех уникальных MEMORY в списке (учитывая подуровни, т.е. заходя внутрь рекурсивно). Либо пройтись по ним, хотя по сути это одно и тоже.

Это сообщение отредактировал(а) lukas - 26.1.2011, 18:39

--------------------

http://code.google.com/p/orionphp/ - opensource скриптовой язык Orion (аналог PHP) для freepascal/delphi.

lukas

Дата 28.1.2011, 09:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 771
Регистрация: 23.2.2007

Репутация: нет
Всего: 15

Сделал вот так, вроде в рекурсию не уходит и быстро:

Код


function GetScanList: TPtrArray;
begin
  if Scaned_List.Count > 0 then
  begin
      Result := Scaned_List.Pop;
      Result.Clear;
  end else
      Result := TPtrArray.Create;
end;

procedure ScanMemoryList(List: TOriMemoryArray; callback: TCallBackScan; Scaned: TPtrArray = nil);
   var
   i: integer;
   toFree: Boolean;
begin
    toFree := false;
    for i := 0 to List.Count - 1 do
    begin
        with List[ i ] do begin
          if IsRoot then begin
              if Scaned = nil then begin
                Scaned := GetScanList;
                toFree := true;
              end;

              if not Scaned.IsExists(Mem.ptr) then
              begin
                  Scaned.Add( Mem.ptr );
                  case Typ of
                    mvtHash  :  ScanMemoryList( TOriMemoryArray(Mem.ptr), callback, Scaned );
                    mvtObject:  // ScanMemoryList( TOriMemoryArray(Mem.ptr) );  --TODO
                  end;
                  callback( List[ i ] );
              end;
          end else
              callback( List[ i ] );
        end;
    end;
    if toFree then begin
      Scaned_List.Add( Scaned );
    end;
end;

Алгоритм, который сохраняет просканеные структуры Root'типа (которые могут содержать списки). Т.е. если в списке уже есть этот элемент просканенный, он его не сканирует.

Это сообщение отредактировал(а) lukas - 28.1.2011, 09:52

--------------------

http://code.google.com/p/orionphp/ - opensource скриптовой язык Orion (аналог PHP) для freepascal/delphi.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »