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

方法（一）似乎是最容易的。我的第一個問題是，在Scala 2.8中這是否代價高昂，其次是它是否違反了DRY原則？

Answer 1

簡答：過早優化是等等的根源。使用乾淨的參考方法。如果您遇到性能問題，則無法替代性能分析和基準測試。

長答案：Scala使用與Java完全相同的參考機器，所以這實際上是一個超過Scala問題的JVM問題。在形式上，JVM規範並沒有說明如何實現引用。在實踐中，它們往往是單詞大小或更小的指針，它們指向一個對象或索引到指向該對象的表中（後者有助於垃圾收集器）。無論哪種方式，refs的數組大小與32位vm上的整數大小大致相同，或64bit vm大約是double（除非使用壓縮oops）。這種加倍可能對你很重要，或者可能不重要。

如果採用基於ref的方法，則每個從節點到鄰居的遍歷都是引用間接引用。使用基於int的方法，從節點到鄰居的每次遍歷都是查找表，然後是參考間接。所以int方法在計算上更加昂貴。假設您將這些整數放入不包含整數的集合中。如果你把盒子整理出來，那麼它就是純粹的瘋狂，因爲現在你已經有了和原來一樣多的引用，並且你有一個表格查找。

無論如何，如果你使用基於引用的方法，那麼額外的引用可以爲垃圾回收器做一些額外的工作。如果只有節點的引用位於一個數組中，那麼gc將會很快地掃描該數據。如果他們被分散在一個圖表中，那麼gc將不得不更加努力地追蹤它們。這可能會或可能不會影響您的需求。

從清潔的角度來看，基於ref的方法更好。所以，一起去看看，然後看看你在哪裏花時間。這或兩種方法的基準。

Answer 2

問題是 - 什麼樣的成本？在內存方面，b）方法可能最終消耗更多的內存，因爲在列表中有兩個可變列表和裝箱整數，另一個是包含所有索引的全局結構。此外，它可能會更慢，因爲您需要幾個間接級別才能到達鄰居節點。

一個重要的注意事項 - 只要你開始存儲整數到可變列表中，他們將經歷拳擊。所以，在這兩種情況下你都會有一堆堆對象。爲了避免這種情況，並且爲了節省內存，在b）方法中，你將不得不保持動態增長的整數數組，這些整數是鄰居的索引。

現在，即使您修改上述方法b），並確保Network類中的索引列表實際上是一個有效的結構（直接查找表或哈希表），您仍然會支付間接費用找到你的Node。內存消耗仍然會更高。我看到的唯一好處是如果您擔心可能會耗盡內存，請保留某些弱引用表，然後在需要時重新創建對象Node，並且在您的indexed_list中找不到它，該對象會保留一組弱引用。

這當然只是一個假設，您必須對您的代碼進行配置/基準測試以查看其差異。

我的建議是在Node中使用類似ArrayBuffer的東西，並使用它存儲對節點的直接引用。

如果內存問題是一個問題，並且您希望將b）方法與弱引用一起執行，那麼我會進一步建議在您自己的動態增長的整數數組中爲鄰居滾動，以避免使用ArrayBuffer[Int]進行裝箱。