ScalaのGC量を最小限にしてプールする

Question

Scalaで書かれたAndroid用ゲームでは、プールしたいオブジェクトがたくさんあります。最初に、同じプール内にアクティブ（可視）インスタンスと非アクティブインスタンスの両方を作成しようとしました。これは、両方ともGCを引き起こし、遅いというフィルタリングのために遅かった。

私は自由なインスタンスを取得する必要があるので、2つのデータ構造を使用するように移動しました。最初のものをパッシブプールから取り出し、アクティブプールに追加します。また、アクティブなプールへのランダムアクセスを高速化しました（インスタンスを非表示にする必要がある場合）。私はこれのために2つのArrayBuffersを使用しています。

私の質問は次のとおりです。どのデータ構造がこの状況に最適でしょうか？そして、GCをできるだけ避けてAndroid（メモリとCPUの制約）上で効率的になるように、それらの（またはそれらの）特定のデータ構造をどのように追加および削除する必要がありますか？

Answer 1

最適なデータ構造を使用すると、すべてのクラスに

var next: MyClass 

を追加する内部リストです。アクティブでないインスタンスは、通常、「フリー・リスト」と呼ばれるものになりますが、アクティブ・インスタンスは単一リンク・リストであるListになります。

この方法では、オーバーヘッドはオブジェクトごとに1つのポインタにすぎません（実際にはそれ以上は得られません）。割り当てやGCはまったくありません。 （。あなたはそれがあまりにも長くなる場合は一部またはフリーリストのすべてを捨てることで、あなた自身を実装する場合を除き）

あなたは、いくつかのコレクションのnice値を失いませんが、あなたは自分のクラスはイテレータも作ることができます。

def hasNext = (next != null) 

は、すべてvarとする必要があります。 （まあ、extends Iterator[MyClass]。）プールのサイズが実際には非常に小さい場合、順次スキャンでは十分に速くなります。

アクティブプールが大きすぎてリンクリストをスキャンできず、要素が頻繁に追加または削除されない場合は、ArrayBuffer（必要に応じて要素を削除する方法を知っている）に保存する必要があります。アイテムを削除したら、それをフリーリストに投げます。

アクティブプールが急速に切り替わる（追加/削除の回数がランダムアクセスの回数に似ている）場合は、何らかの種類の階層構造が必要です。 Scalaは、Vectorではかなりうまく動作しますが、変更可能なものはありません（2.9以降）。 Javaには本当に適したものもありません。あなたが自分でビルドしたければ、左の子の数を追跡するノードを持つ赤黒またはAVLツリーがおそらく行く方法です。 （それでは索引でアクセスするのは簡単なことです）

Answer 2

私は私の考えを述べます。フィルタとマップメソッドはコレクション全体を繰り返し処理するので、コレクションを単純化して、アクティブなインスタンスを探すために単純なスキャンを行うだけです。ここを参照してください：https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/TraversableLike.scala

def filter(p: A => Boolean): Repr = { 
    val b = newBuilder 
    for (x <- this) 
    if (p(x)) b += x 
    b.result 
} 

Iは、n = 31（私は32ビットのintビットマップよりも多くを維持する必要はない）、フィルタ/ foreachのスキャンの素朴なスキャンを使用して、いくつかのテストを実行し、フィルタ/マップスキャン、およびビットマップスキャンを実行し、セットの33％をアクティブにランダムに割り当てます。私は正しい値や何かを見ないことによって私が不正行為をしていないことを再確認するランニングカウンターを持っていました。ところで、これはAndroid上で実行されていません。

アクティブな値の数によっては、ループに時間がかかりました。

結果：

naive scanned a million times in: 197 ms (sanity check: 9000000) 
filter/foreach scanned a million times in: 441 ms (sanity check: 9000000) 
map scanned a million times in: 816 ms (sanity check: 9000000) 
bitmap scanned a million times in: 351 ms (sanity check: 9000000) 

コードここに - それを離れてリッピングか良い方法があれば教えてください気軽に - 私の気持ちを傷つけることはありませんので、スカラへ - 私はかなり新しい：https://github.com/wfreeman/ScalaScanPerformance/blob/master/src/main/scala/scanperformance/ScanPerformance.scala