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

Интересно о ожидаемом повышении производительности в xobotos, я проверил двоичное дерево код теста.

Java-версия двоичного дерева node:

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

версия С#:

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

  private Next next;
  private int item;
}

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

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

Вопрос: Есть ли еще что?

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

Ответы

Ответ 1

Это объединяет два узла в одно размещение, в идеале - вдвое меньшее количество общих распределений.

IMO делает сравнение довольно бессмысленным.

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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