Scala中对象引用的成本是多少？

Question

假设我们构建了一个对象来表示某种网络（社交、无线等）。因此，我们有一些“节点”对象来代表网络的种类，不同的节点可能具有不同的行为等。该网络具有节点的 MutableList。

但是每个节点都有邻居，这些邻居也是节点。因此，在每个节点上必须有一个列表，列出该节点的所有邻居，或者在需要时动态生成这样的列表。如果邻居列表存储在节点对象中，将更便宜地存储它（a）作为节点列表，还是（b）作为可用于引用网络中节点的数字列表？

以下是一些代码以增加清晰度：

//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//
}

方法（a）似乎是最简单的。我的第一个问题是，在Scala 2.8中是否成本高昂，第二个问题是它是否违反了DRY原则？

- philosodad

Answer 1

简短回答：过早的优化是万恶之源。使用干净的引用方法。当你遇到性能问题时，没有什么可以替代分析和基准测试。

长回答：Scala使用与Java完全相同的引用机制，因此这实际上是一个JVM问题而不是Scala问题。正式地说，JVM规范并没有说明引用是如何实现的。实际上，它们往往是指向对象或索引到指向对象的表的字长或更小的指针（后者有助于垃圾收集器）。

无论哪种方式，引用数组在32位虚拟机上与整数数组的大小大致相同，在64位虚拟机上大约是两倍（除非使用了压缩-oops）。这种加倍对你可能很重要，也可能不重要。

如果你选择基于引用的方法，则从节点到邻居的每个遍历都是一个引用间接寻址。对于基于整数的方法，从节点到邻居的每个遍历都是查找表然后是引用间接寻址。因此，整数方法在计算上更昂贵。而且，这还假设你将整数放入不装箱整数的集合中。如果你装箱整数，那就纯粹是疯狂的，因为现在你有和原始引用一样多的引用，还有一个表查找。

无论如何，如果你选择基于引用的方法，额外的引用可能会为垃圾收集器增加一些额外的工作量。如果节点的唯一引用都在一个数组中，则gc将非常快速地扫描它。如果它们散布在图形中，则gc将不得不更努力地跟踪它们。这可能会影响你的需求。

从清洁度的角度来看，基于引用的方法要好得多。所以采用它，然后进行分析以查看你花费时间的地方。或者对两种方法进行基准测试。

- James Iry

Answer 2

问题是 - 什么样的成本？从内存角度来看，b)方法可能会消耗更多的内存，因为您既有可变列表，又有在该列表中的装箱整数，还有另一个全局结构来保存所有索引。此外，它可能会更慢，因为您需要几个间接层才能到达相邻节点。

一个重要的注意点 - 一旦您开始将整数存储到可变列表中，它们就会经历装箱过程。因此，在两种情况下，您都将拥有堆对象列表。为了避免这种情况，并进一步节省内存，在b)方法中，您必须保持一个动态增长的整数数组，这些整数是邻居的索引。

现在，即使您按照上面建议的修改b)方法，并确保Network类中的索引列表是真正有效的结构（直接查找表或哈希表），您仍然需要支付一个间接成本才能找到您的Node。而且内存消耗仍然会更高。我唯一看到的好处是在保留某种弱引用表方面，如果您担心可能会用完内存，则在需要时重新创建Node对象，并且在indexed_list中找不到它时。

当然，这只是一种假设，您需要对代码进行分析/基准测试以查看差异。

我的建议是在Node中使用类似于ArrayBuffer的东西，并使用它来存储节点的直接引用。

如果内存问题是一个问题，并且您想要与弱引用一起执行b)方法，则我进一步建议使用自己的动态增长整数数组来存储邻居，以避免使用ArrayBuffer[Int]进行装箱。

- axel22