Velikost objektů na JVM - Scala a specialiazce polí

20. 2. 2013

Minule jsem napsal pár rychlých řádků o velikosti specializovaných tříd. Výsledek je takový, že i když se velikost třídy o něco zvětší, ve výsledku ušetřím paměť, protože nemusím odkazovat na boxované objekty (Integer a spol).

Situace kolem specializovaných polí je o něco komplikovanější protože kromě anotace @specialized ještě potřebuji implicitní ClassManifest (nebo ClassTag jak se tomu říká ve Scale 2.10).

class ArrayList[@specialized(Int, Long) T: ClassManifest] {
  val elements = new Array[T](16)
}

Důvody jsou jasné:

Bez manifestu nemůžu vytvářet instance generických polí (informace o typu pole se ztratí během kompilace a new Array[T] nemůžu zavolat, protože neznám hodnotu typového parametru T).
Bez specializace se pro práci s poli používají generické operace ze ScalaRunTime, které provádějí pattern-matching, aby zjistily typ pole a vždycky pracují s boxovanými primitivy (jenom díky specializaci se vygenerují příslušné metody, které pracují přímo s primitivními typy).

new Array[T](len) /* se přeloží na: */ classManifest.newArray(len)

// bez specializace se kód překládá následovně:
arr(idx)          /*  ~~~~~~~~~~~>  */ ScalaRunTime.array_apply(arr, idx)
arr(idx) = x                           ScalaRunTime.array_update(arr, idx, x)
arr.length                             ScalaRunTime.array_length(arr)

Takže asi tak.

Ale je tu ještě několik zádrhelů.

Specializovaná třída dědí ze svého nespecializovaného předka a přidává atribut primitivního typu se kterým pracuje, přičemž generického atributu předka se nedotkne (detailně jsem to popsal minule). Tak to funguje i v případě polí. Předek obsahuje referenci na generické pole, specializovaný potomek přidá referenci na primitivní pole. Háček je v tom, že se inicializují oba atributy. Nejdřív se zavolá konstruktor předka, který inicializuje generický atribut a pak konstruktor potomka, který inicializuje svůj specializovaný atribut. Pokud je v konstruktoru třídy specializované pro T něco jako val elements = new Array[T](16), tak se inicializují dvě pole.

Výše uvedená třída se zkompiluje jako:

class ArrayList[T](ev: ClassManifest[T]) {
  private[this] val evidence$1: ClassManifest[T] = ev
  val elements = new Array[AnyRef](16)
}

class ArrayList$mcI$sp extends X {
  private[this] val evidence$1: ClassManifest[T] = ev
  var elements$mcI$sp: Array[Int] = evidence$1.newArray(16)
}

Nejdřív se inicializuje proměnná elements předka a pak elements$mcI$sp potomka. A to je problém. Pole referencí s délkou 16 zabírá 88 bajtů (na 32 bit architekturách, na 64 bitových je to 2x horší), které nebudou nikdy použity, protože specializovaný potomek používá svůj atribut elements$mcI$sp.

Proto se vyplatí v konstruktoru specializované pole inicializovat na null a pole alokovat až v nějaké metodě:

class ArrayList[@specialized(Int, Long) T: ClassManifest] {
  val elements = _

  def add(t: T) = {
    if (elements == null) elements = new Array[T](16)
    // ...
  }
}

Další problém spočívá v ClassManifestech. Pokud ho definuji jako type bound (tedy T: ClassManifest) kompilátor vygeneruje privátní proměnnou jak pro generického předka tak i pro specializovaného potomka, což znamená další 4 nebo 8 zbytečně vyplýtvaných bajtů na instanci. Na druhou stranu, když implicitní manifest deklaruji jako parametr implicit val m: ClassManifest[T], pak pro něj kompilátor vygeneruje veřejnou/protected proměnnou, která je sdílená předkem a potomky.

Další věc, kterou je potřeba mít na paměti je modifikátor viditelnosti private[this]. Ten způsobí, že atribut je viditelný jenom této instanci a na rozdíl od modifikátoru this negeneruje soukromý getter nebo setter. Bohužel tohle velice bizarním způsobem vadí specializaci. Jde o to, že private[this] atributy nejsou ve specializovaných metodách nahrazeny specializovanými atributy a celkově kód nefunguje jak chci a vůbec není znát proč.

Takže pokud dodržím všechna pravidla: anotace @specialized, ClassManifest jako implicitní val, inicializovat na null a žádný private[this], můžu dostat instanci se specializovaným polem, které mám může ušetřit značné množství paměti (na 64 bit platformách potřebuji k uložení jednoho intu 4 bajty namísto 32, tedy 8x méně). Můžu například vytvořit obdobu Javovského ArrayListu, která je (konečně) paměťově efektivní.

class ArrayList[@specialized(Short, Int, Long, Float, Double) T](implicit val cl: ClassManifest[T]) {
  private var arr: Array[T] = _
  private var len = 0

  def length = len

  def append(t: T): Unit = {
    if (arr == null) arr = new Array[T](16)
    if (len == arr.length) enlarge()
    arr(len) = t
    len += 1
  }

  def get(i: Int) = {
    if (i < 0 || i >= len) throw new IndexOutOfBoundsException
    arr(i)
  }

  private def enlarge() = {
    val newArr = new Array[T](arr.length * 2)
    Array.copy(arr, 0, newArr, 0, arr.length)
    arr = newArr
  }
}

A když se podívám na spotřebu paměti, je konstantní faktor specializovaných instancí překvapivě malý (zčásti kvůli zarovnání paměti):

java.util.ArrayList[Int] potřebuje 40 bajtů + 20 bajtů na každý element (popř. 52 bajtů + 32 bajtů na element na 64 bit platformách).
Specializovaný ArrayList[Int], který jsem právě naznačil, naproti tomu zabere 44 bajtů + 4 bajty na element (příp. 68 bajtů + 4 bajty na element na 64 bit platformách).

Specializovaná pole se v takovém případě vyplatí už pro miniaturní kolekce. Bohužel framework kolekcí ve Scale není vůbec specializovaný (zkuste si ve zdrojácích Scaly grepnout @specialized a uvidíte, že to nevrátí skoro nic), takže i kdyby můj ArrayList ukládal data v interních primitivních polích, přesto by většinou pracoval s boxovanými typy. To ale je jenom malá vada na kráse drasticky zredukovanému hladu po paměti.