XobotOS: Почему в бинарном дереве C# используется структура?

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

Java-версия узла двоичного дерева:

private static class TreeNode
{
    private TreeNode left, right;
    private int item;
}

Версия C#:

struct TreeNode
{
  class Next
  {
    public TreeNode left, right;
  }

  private Next next;
  private int item;
}

Мне интересно, каково преимущество использования структуры здесь, так как указатели Next и Previous все еще заключены в класс.

Ну, есть один - листовые узлы - это чистые типы значений, так как им не нужны левый и правый указатели. В типичном двоичном дереве, где половина узлов - листья, это означает сокращение количества объектов на 50%. Тем не менее, перечисленные улучшения производительности кажутся гораздо большими.

Вопрос: есть еще что-то к этому?

Кроме того, поскольку я не думал бы об определении узлов дерева таким способом в C# (спасибо Xamarin!), Какие другие структуры данных могут получить выгоду от использования структур неочевидным способом? (Хотя это немного не по теме и с открытым концом.)

Источник

4 ответа

Решение

Это группирует два узла в одно выделение, в идеале вдвое сокращая количество общих выделений.

ИМО это делает сравнение довольно бессмысленным.

Источник

Я просто наткнулся на этот странный код и у меня возник тот же вопрос. Если вы измените код в соответствии с версией Java, он будет работать немного медленнее. Я полагаю, что большая часть "struct TreeNode" будет упакована и размещена в любом случае, за исключением нижнего ряда. Однако каждый узел имеет 2 распределения: TreeNode в штучной упаковке и класс Next. Распределение сбережений быстро исчезнет. ИМО, это не правильное использование структуры.

Источник

Структуры могут быть размещены в стеке вместо кучи (но не в каждом случае), что означает, что они удаляются из памяти, как только выходят из области видимости - сборщик мусора не участвует в этом сценарии. Это может привести к меньшей нагрузке на память и меньшему количеству сборок мусора. Кроме того, стек является (в основном) доступной областью памяти, поэтому доступ к нему имеет лучшую локальность, что может (опять же, возможно) улучшить коэффициент попадания в кэш на уровне ЦП.

Рекомендации Microsoft по выбору классов и структур:

  • структуры должны быть небольшими (16 байтов в целом) и недолговечными
  • они должны быть неизменными

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

Источник

Я не думаю, что использование структуры здесь имеет какое-либо значение. Особенно после просмотра исходного кода TreeNode, где экземпляры TreeNode всегда копируются в конструкторе и рекурсивном вызове bottomUpTree.

Источник
Другие вопросы по тегам