Какова стоимость ссылки на объект в Scala?

Question

Предположим, мы строим объект для представления некоторой сети (социальной, беспроводной, что угодно).Таким образом, у нас есть некоторый объект 'node' для представления KIND сети, разные узлы могут иметь разное поведение и так далее.В сети есть MutableList узлов.

Но у каждого узла есть соседи, и эти соседи также являются узлами.Таким образом, где-то должен быть список, на узел, всех соседей этого узла - или такой список должен создаваться на лету, когда это необходимо.Если список соседей хранится в объектах узлов, дешевле ли его хранить (а) как список узлов или (б) как список номеров, которые можно использовать для ссылки на узлы вне сети?

Некоторый код для ясности:

//approach (a)

class network {
  val nodes = new MutableList[Node]
  // other stuff //
}

class Node {
  val neighbors = new MutableList[Node]
  // other stuff //
}

//approach (b)
class Network {
  val nodes = new MutableList[Node]
  val indexed_list = //(some function to get an indexed list off nodes)
//other stuff//
}

class Node {
  val neighbors = MutableList[Int]
//other stuff//
}

Подход (а) кажется самым простым.Мой первый вопрос: стоит ли это дорого в Scala 2.8, а второй - нарушает ли принцип DRY?

Answer 1

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

Длинный ответ: Scala использует точно такой же механизм ссылок, что и Java, так что это действительно вопрос JVM, а не вопрос Scala.Формально спецификация JVM не говорит ни слова о том, как реализованы ссылки.На практике они имеют тенденцию быть указателями размером в слово или меньше, которые либо указывают на объект, либо указывают на таблицу, которая указывает на объект (позднее помогает сборщикам мусора).

В любом случае, массив ссылок составляет околотот же размер, что и у массива целых чисел в 32-битной виртуальной машине или примерно в два раза в 64-битной виртуальной памяти (если не используются сжатые операции).Это удвоение может быть важно для вас или нет.

Если вы используете подход, основанный на ссылках, каждый переход от узла к соседу является ссылочным косвенным указанием.При использовании подхода, основанного на int, каждый переход от узла к соседу представляет собой поиск в таблице, а затем ссылку на косвенное обращение.Таким образом, подход int является более дорогим в вычислительном отношении.И это при условии, что вы положили целые числа в коллекцию, которая не упаковывает целые числа.Если вы укажете целые числа, тогда это просто сумасшествие, потому что теперь у вас столько же ссылок, сколько у оригинала, и у вас есть поиск по таблице.дополнительные ссылки могут сделать дополнительную работу для сборщика мусора.Если единственные ссылки на узлы лежат в одном массиве, то gc будет сканировать это чертовски быстро.Если они разбросаны по всему графику, то gc придется работать усерднее, чтобы отследить их все.Это может или не может повлиять на ваши потребности.

С точки зрения чистоты подход на основе ссылок гораздо приятнее.Так что пойдите с этим и затем профиль, чтобы видеть, где Вы проводите свое время.Это или эталон обоих подходов.

Answer 2

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

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

Теперь, даже если вы измените подход b)как предложено выше, и убедитесь, что индексированный список в классе Network действительно является эффективной структурой (таблица прямого просмотра или хеш-таблица), вы все равно заплатите непрямую цену, чтобы найти свой Node.И потребление памяти все равно будет выше.Единственное преимущество, которое я вижу, состоит в том, чтобы хранить какую-то таблицу слабых ссылок, если вы обеспокоены тем, что вам может не хватить памяти, и воссоздать объект Node, когда вам это нужно, и вы не можете найти его в вашем indexed_list,сохраняет набор слабых ссылок.

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

Мое предложение было бы использовать что-токак ArrayBuffer в Node и использовать его для хранения прямых ссылок на узлы.

Если проблемы с памятью являются проблемой, и вы хотите использовать b) подход вместе со слабыми ссылками, то я бы также предложилдобавление собственного динамически растущего целочисленного массива для соседей, чтобы избежать объединения с ArrayBuffer[Int].