PHP: проблема сборки мусора объектов узла Linkedlist - PullRequest
Новая
       20

PHP: проблема сборки мусора объектов узла Linkedlist

1 голос
/ 04 февраля 2012

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

 $this->first = NULL
 $this->last = NULL

Нужно ли нам перебирать полный связанный список и сбрасывать каждый идентификатор объекта узла один за другим?

Я считаю, что достаточно установить вначале и последнем значение NULL, а PHP выполняет сборку мусора в фоновом режиме для нашегоимени.

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

Ответы [ 2 ]

3 голосов
/ 04 февраля 2012

Если вы используете PHP <5.3.0 и используете двусвязный список, ни один из узлов не будет освобожден. Это связано с тем, что в более ранних версиях PHP использовался только счетчик ссылок <a href="http://www.php.net/manual/en/features.gc.refcounting-basics.php" rel="nofollow"> [1] , который не может распознать циклические ссылки. Даже в односвязном списке возможно, что для освобождения всего списка потребуется 'n' проходов сборщика мусора, в зависимости от используемого алгоритма (хотя я вижу это маловероятным).

Для дальнейшего объяснения в двусвязном списке каждый узел указывает на узел как до, так и после него. Рассмотрим упорядоченные узлы A, B, C. Это означает, что A указывает на, B, C указывает на B, а B указывает на A и C. Поэтому их счетчик ссылок всегда будет ненулевым, если только Вы явно удаляете узлы самостоятельно.

С односвязным списком и одинаковыми узлами A, B, C каждый узел указывается предыдущим, кроме A, на который не указывает ни один другой узел. Поэтому, если вы удалите ссылку на A, это будет сбор мусора. Тогда, поскольку B больше не указан, он будет освобожден и так далее в списке. Однако, скажем, сборщик мусора посещает список в обратном или случайном порядке (а не в оптимальном порядке слева направо). Затем он может сначала взглянуть на B и сделать вывод, что A все еще указывает на него, и поэтому не нуждается в освобождении. Тогда GC освобождает и готово. Хотя более вероятно, что алгоритм GC непрерывно собирает память с нулевым счетчиком ссылок, пока больше нечего собирать, что позволило бы избежать этой проблемы.

К счастью, начиная с PHP 5.3.0 нам не нужно беспокоиться о циклических ссылках [2] . Этот алгоритм работает путем построения дерева из корневого узла памяти. Все, что не включено в окончательное дерево, должно быть осиротевшим (и, следовательно, поддерживается только из-за циклической ссылки), и поэтому может быть освобождено. Так что да, пока ничто в вашей программе не указывает на какой-либо узел в вашем списке, весь список будет освобожден путем удаления ссылок на начало и конец.

Обратите внимание, что алгоритм освобождения потерянных циклических ссылок дороже, чем простой подсчет ссылок. Явный код освобождения может быть или не быть полезным. Тщательный сравнительный анализ должен быть сделан, чтобы найти это.

2 голосов
/ 04 февраля 2012

Иногда у меня возникают проблемы с процессом сборки мусора в PHP.

Вы можете обойти эту проблему в реализации связанного списка.

  • Каждый раз, когда вы создаете структуру данных, создайте ее как локальную переменную в функции, а НЕ глобально.Позже назначается другая часть кода, где вы собираетесь его использовать.Если вы присваиваете переменную напрямую, вы можете иметь копию для той же ссылки вместо новой структуры с такими же данными.

  • Я предлагаю реализовать структуру "Список" как независимуюструктура, , а не просто указатель на первый или последний узел .

  • В случае связанных списков я добавляю 2 специальных узла, которые сначала работают как ваш«&» last », который не хранит никаких данных и никогда не удаляется, кроме случаев, когда весь связанный список будет удален.Когда список пуст, они связаны друг с другом, при добавлении реальных узлов данных они устанавливаются в промежутке между этими узлами.

  • Когда вы удаляете первый узел, выне удаляйте специальный «первый» маркер узла, но узел, который находится после специального «первого» маркера .

  • Когда вы удаляете узел, которыйпоследний, вы не удаляете специальный «последний» маркер узла, но узел, который находится перед специальным «последним» маркером .

Предложение:

<?php

/* listitem */ function newitem($data)
{
    // executing a function that returns
    // a local variable,
    // forces php to create a new item, each time,
    // instead of making a copy,
    // that conflicts with garbage collection

    /* listitem var */ $Result = array(
      "data"  => $data,
      "prev"  => null,
      "next"  => null,
    );

    return $Result;
} // listitem function newitem(...)

/* linkedlist */ function newlist()
{
    // executing a function that returns
    // a local variable,
    // forces php to create a new item, each time,
    // instead of making a copy,
    // that conflicts with garbage collection

    /* linkedlist var */ $Result = array(
      "start" => newitem();   // <- "marker" for start of list, don't store data here
      "finish" => newitem();  // <- "marker" for end of list, don't store data here
    )

    return $Result;
} // linkedlist function newlist(...)

/* void */ function linkitem(&$before, &after)
{
  if (($before != null) && ($after != null))
  {
    "start" <=> "item"
    $before["next"] = $after; 
    $after["prev"]  = $before; 
  }
} // void function linkitem(...)

/* void */ function additem(&$list, &item)
{
  if ($item != null)
  {
    "start" <=> "item"
    linkitem(/* & */ $list["start"], /* & */ $item); 
    "item" <=> "finish"
    linkitem(/* & */ $item, /* & */ $list["start"]); 
  }
} // void function additem(...)

/* void */ function example()
{
  /* linkedlist var */ $SolarSystem = newlist();

  /* listitem var */ $item = null;

  $item = newitem("Sun");
  // check for reference parameters
  additem( /* & */ $SolarSystem, /* & */ $item);

  $item = newitem("Mercury");
  additem( /* & */ $SolarSystem, /* & */ $item);

  $item = newitem("Venus");
  additem( /* & */ $SolarSystem, /* & */ $item);

  // ...

} // void function example(...)

?>

И визуальное представление может быть таким: 

.............................................................
....+-------------------+....................................
....|    SolarSystem    |....................................
....+---------+---------+....................................
..............|..............................................
..............v..............................................
....+---------+---------+...........null.....................
....|  Last   |  First  |............^.......................
....+---+-----+----+----+............|.......................
........|..........|.........+-------+-+.....................
........|..........+-------->|  prev   |.....................
........|....................+---------+....+-----------+....
........|....................|  data   +--->|   "Sun"   |....
........|....................+---------+....+-----------+....
........|....................|  next   |.....................
........|....................+-+-------+.....................
........|......................|.....^.......................
........|......................v.....|.......................
........|....................+-------+-+.....................
........|....................|  prev   |.....................
........|....................+---------+....+-----------+....
........|....................|  data   +--->| "Mercury" |....
........|....................+---------+....+-----------+....
........|....................|  next   |.....................
........|....................+-+-------+.....................
........|......................|.....^.......................
........|......................v.....|.......................
........|....................+-------+-+.....................
........|....................|  prev   |.....................
........|....................+---------+....+-----------+....
........+------------------->|  data   |--->|  "Venus"  |....
.............................+---------+....+-----------+....
.............................|  next   |.....................
.............................+-+-------+.....................
...............................|.............................
...............................v.............................
..............................null...........................
.............................................................

Cheers.

...