0xDEADBEEF

Samooptimalizující se kolekce

Standardní knihovna Scaly nabízí přehršel kolekcí a operací nad nimi. Bohužel někdy si musíme vybrat mezi stručným zápisem nebo efektivitou. Bylo by skvělé, kdyby jazyk, implementace kolekcí nebo runtime určité vzory rozpoznal a automaticky je přepsal na efektivnější varianty.

Klasický příklad, kdy chceme top-k položek podle určitého kritéria

xs.sorted.take(10)

by se mohl mechanicky přepsat na využití haldy

val heap = new MaxHeap(capacity = 10)
for (x <- xs) {
  if (heap.size < 10) {
    heap += x
  } else {
    if (x < heap.peek) {
      heap.pop()
      heap += x
    }
  }
}
heap.toSeq

nebo něco obdobného s quickselectem. sort + take(k) běží v čase O(n log(n)), heap v čase O(n log(k)) a je rychlejší jak asymptoticky, tak i v praxi.

Pár dalších vzorů:

xs.sorted.head    -> xs.max
xs.sorted.take(1) -> Seq(xs.max)

xs.sorted.reverse -> xs.sorted(ordering.reverse)

xs.sorted.filter(_ < y)  -> xs.sorted.takeWhile(_ < y)
xs.sorted.filter(_ < y)  -> xs.filter(_ < y).sorted

// BitSet
(xs & ys).size  // bez alokace

Kromě odstraňování noop operací, jde buď o eliminaci alokujících mezikroků nebo změnu algoritmu za efektivnější. Například v tomto framgmentu

xs.groupBy(f).map { case (k, vs) => vs.size }: Map[X, Int]

groupBy vytvoří Map[X, Seq[X]], ale dílčí sekvence jsou okamžitě zredukovány.³ V principu není nutné alokovat nic kromě finálního výsledku.

val map = mutable.Map[X, Int]() withDefaultValue 0
for (x <- xs) {
  map(f(x)) += 1
}
map.toMap

Podobně by bylo možné přepsat několik navazujících kroků i když nevím jak by rozpoznávání těchto vnořených a zřetězených vzorů mělo fungovat, jak by se měl stavět výsledný kód, ani jak komplexní výrazy by se daly reálně optimalizovat.

Následující řádek, který vrací všechny položky vyskytující se ve vstupní kolekci více než jednou, je možné přepsat na jedinou smyčku. Není to triviální transformace, ale jde to.

xs.groupBy(f).map { case (k, vs) => vs.size }.filter { case (k, v) => v > 1 }.keys

Daly by přepisovat i série nezávislých operací nad jednou zdrojovou kolekcí na smyčku, což může zlepšit paměťovou lokalitu.

val ys = xs.map(f).filter(p)

val counts = ys.count(q)
val sizes = ys.groupBy(g).map { case (k, vs) => vs.size }

na

for (x <- xs; y = f(x) if p(y)) {
  if (q(y)) counts += 1
  sizes(g(x)) += 1
}

Další možností by byl agresivní výběr nejrychlejší možné a ideálně specializovaná implementace⁴ .

xs.sortBy(f)

Řazení by probíhalo LSD radix sortem, pokud f je funkce T => Int, burst sortem nebo tímhle pokud lze výsledek f interpretovat jako sekvenci bajtů a timsortem/introsortem, pro malé vstupy nebo když všechno ostatní selže.

Nevím jak snadné by bylo kompilátor zneužít pro transformace na vyšší úrovni specializace. Možná by to zařídil plugin kompilátoru, makra nebo staging. Pro dynamickou variantu musí být všechna logika implementovaná přímo v kolekcích.

Dynamický přístup by mohl fungovat jen s malou změnou API² . Hromadné operace nevytvoří novou kolekci, ale uzel popisující výpočet. Když je pak třeba získat výsledek, uzly AST jsou optimalizovány, jejich sekvence nahrazeny za jiné, efektivnější, a pak dojde k interpretaci AST programu.

Hlavním problémem jsou jako obvykle vedlejší efekty včetně výjimek. S nimi má přepisování vliv na pozorovatelné chování programu. Pokud se změní pořadí vyhodnocování, ze striktních operací se stanou líné, xs.map(a).map(b).map(c) se vyhodnotí jako xs.map(a andThen b andThen c), dojde ke změnám v stack trace, které nekorespondují se zdrojákem.

Proto by bylo nutné přesně zdokumentovat vše, na co se můžeme spolehnout a s čím nemůžeme počítat. Například, že jedině foreach garantuje pořadí, ale všechny ostatní operace se můžou vyhodnotit v libovolném pořadí a libovolným stylem nebo může dojít k jejich odstranění, pokud nejsou potřeba.

Pozn:

2. Hlavní problém je v tom, že se rozlišuje mezi materializovanou kolekcí a operacemi nad ní, které jsou líné. V případě Scaly to může dobře zapadnout do nového frameworku kolekcí, jež je založený na líných pohledech (View). Ty také reprezentují sérii operací a jejich výsledek musí být explicitně materializován.
3. Tohle je relikt minulost. Článek jsem napsal dávno před uvedením nových metod. Teď se kýženého výsledku dá dosáhnout přímo: xs.groupMapReduce(f)(_ => 1)(_ + _).
4. Tohle je celá pointa jazyka D a design by introspection. Meta-programování za pomoci intropekce se během kompilace podívá na použité typy a jejich metody a základě toho zvolí/vygeneruje optimální program.

+1: dotty linker

+2: Otázkou na podobné téma končí tenhle článek.

+3: Operation fusion and deforestation for Scala