A Scala programozási nyelv

Generikus párhuzamos feldolgozású kollekciók

A fejezetet írta Kozma Krisztina az A Generic Parallel Collection Framework dokumentum alapján.

Kivonat

Az alkalmazások nagy része strukturált adatokat kezel. Manapság a modern programozási nyelvek és platformok által nyújtott keretrendszerek korszerű adatszerkezeteket (kollekciókat) biztosítanak számukra. Ezen adatszerkezeteket (pl. lista, fa, hashtábla) számos előre definiált művelettel - pl. rendezés, szűrés vagy keresés - látják el. A műveletek legfőbb tulajdonsága, hogy rendszerint a teljes kollekciót bejárva az elemeket szekvenciálisan dolgozzák fel. Megvalósításuk általában iterátorral történik, melynek szekvenciális természetéből adódik, hogy nem alkalmas a párhuzamosításra.
Az alábbiakban bemutatunk egy olyan keretrendszert, amely a kollekcióműveletek párhuzamosítására vállalkozik, és teszi mindezt elég általánosan ahhoz, hogy a keretrendszer könnyen használható és kiterjeszthető legyen.

Bevezetés

A többmagos számítógép-architektúrák megjelenésével a párhuzamos programozás gyorsan terjedt. Párhuzamos programokat írni és karbantartani sokkal nagyobb kihívás, mint szekvenciális programokat. Éppen ezért gyakori, hogy az általános célú programozási nyelvek mindenféle eszközt - különféle adatszerkezeteket (tömb, lista, fa, hashtábla, prioritásos sor stb.), absztrakciókat - igyekeznek biztosítani, hogy ezzel segítsék az adatmodellezését, és mentesítsék a programozót az alacsony szintű, processzor közeli megvalósítások (szinkronizáció, kiegyensúlyozott terhelés-elosztás stb.) alól.
A legtöbb keretrendszer az adatkollekcióit hierarchiába szervezi, és kezelésüket megkönnyítendő számos műveletet (pl. rendezés, szűrés, partícionálás, keresés vagy map/reduce[1]) biztosít hozzájuk. Gyakori probléma, hogy a közös, minden kollekcióban megtalálható műveletek „túl általánosra” sikerednek, és az egyes kollekcióknak újra kell őket implementálniuk. Ez megnehezíti a keretrendszer újabb kollekcióval való bővítését. Ennek orvoslására vezették be ezen műveletek iterátorral vagy generikus foreach-csel megtámogatott implementációját. Az iterátor azonban szekvenciális jellegű, nem támogatja a párhuzamos műveleteket, melyek az adatok processzorok közötti elosztását, majd az eredmény összeépítését igénylik.
Az következőkben bemutatott generikus keretrendszer rendkívül sokféle adatszerkezet reprezentálására alkalmas, melyeket beépített műveletekkel bőségesen ellát. A műveletek a felosztott kollekción párhuzamosan hajtódnak végre, némelyek visszatérési értéke maga is egy kollekció. A keretrendszer idomul a jelenlegi Scala Collection Frameworkhöz, abba teljes mértékben integrálva lett. A forráskód elérhető az Interneten.

Mit nyújt az új keretrendszer?

[1] Ezen metódusok a felhasználó által definiált műveletet a kollekció minden egyes elemén elvégzik.

Scala Collection Framework[2]

Párhuzamosított műveleteket többféleképpen adhatunk hozzá egy létező keretrendszerhez. Az egyik megközelítés szerint, amit a Data Parallel Haskellben is alkalmaztak, a párhuzamosított műveleteket új metódusokként, új névvel vezetjük be. Ennek egyik hátránya, hogy a létező programokat nagymértékben át kell dolgozni a párhuzamos feldolgozású kollekciók használatához, másrészt a program névtere számos új, a korábbi kódban most már tiltott névvel bővül. A másik megoldás, amit a Scala is választott, hogy a párhuzamosított műveleteket külön osztályokban vezetjük be. Így ezen új műveleteket nevezhetjük ugyanúgy, mint szekvenciális társaikat, és a kliensek is csak akkor tudják meghívni őket, ha adataik a megfelelő párhuzamos feldolgozású kollekció objektumai. A hagyományos kollekciók egy új metódussal bővültek: a par metódus meghívásával a kollekció párhuzamos feldolgozásúvá jelölhető meg, „csak” jelölhető, ugyanis a visszaadott, új kollekció továbbra is a korábbi adatszerkezetet hivatkozza. A párhuzamos feldolgozású kollekciókra a seq metódust alkalmazva, a kollekció „visszaalakítható” (visszajelölhető) szekvenciális feldolgozásúvá.
Ezen felül a párhuzamos feldolgozású kollekciók saját, különálló hierarchiába lettek szervezve, mely hierarchia a hagyományos kollekciók hierarchiája alá lett rendelve.

[2] Az eredeti Scala Collection Frameworköt ismertnek tételezzük fel, és a jelen dokumentumban külön nem térünk ki rá.

Igény szerinti munkamegosztás

A többprocesszoros rendszerekben a hatékonyságot nagymértékben a processzorok közötti terhelés-eloszlás határozza meg. Esetünkben a műveleteket a kollekció elemein hajtjuk végre, így adódik, hogy a munka felosztása essen egybe a kollekció részekre tördelésével. Egyes műveletek a kollekció minden elemén értelmezettek, ilyen pl. a foreach metódus. Egy párhuzamos foreach megvalósítása feltételezi, hogy a kollekció egyes részei különböző processzorok végrehajtása alatt állnak. A kollekció párhuzamos feldolgozásakor az egyes partíciókhoz szálak rendelődnek. A szálak létrehozása és inicializálása költséges, ezért érdemesebb egy bizonyos mennyiséget belőlük alvó állapotban, poolban tartani, mintsem minden egyes alkalommal, mikor párhuzamos művelet kerül végrehajtásra, újat kreálni.
Számos keretrendszer biztosít poolt a szálak számára, ilyen például a Scala által is átvett Fork/Join keretrendszer a Javaban. Az elvégzendő munka absztrakciója a fork/join taszk, mely taszkok sorba szervezhetők és a dolgozó szálakhoz rendelhetők. Egy taszk új taszkokat kezdeményezhet (fork) és megvárhatja a gyermek-taszkok befejeződését (join).
Számos terhelés-kiegyensúlyozó[3] technika létezik, azonban az optimális ütemezés nem csupán a processzorok számától és az adatok méretétől függ, hanem az adatokban rejlő szabálytalanságoktól és a processzorok rendelkezésre állásától is. Ez utóbbi kettő nem jósolható meg előre, így az igény szerinti munkamegosztás[4], mint könnyűsúlyú terhelés-kiegyensúlyozó technika, jó választásnak ígérkezik. A feladatok taszkokra vannak osztva, a taszkok (szálakhoz, a szálak pedig) processzorokhoz rendelve. Minden processzor fenntartja és kezeli taszkok egy sorát, az aktuális taszk végrehajtása után veszi a következőt a sorból. Ha elfogytak a végrehajtandó taszkjai, megpróbál egy másik processzor sorából „elcsenni” egyet.
A fork/join absztrakció megvalósítható a fenti igény szerinti munkamegosztás módszerével is, ahol a hatékonyság legfőbb meghatározója a munka megfelelő méretű taszkokra való bontása.
Mint korábban említettük a párhuzamos feldolgozású kollekciók műveletei az „oszd meg és uralkodj”-elv alapján elegánsan implementálhatók, végrehajtási sorrendjük kiszámítási fában tárolódik.
A taszkok száma és mérete mérvadó a processzorok kihasználtságát tekintve. Általános megállapítás, hogy kevesebb taszk jelentősen jobb teljesítmény-növekedést eredményez, ugyanakkor kedvezőtlenül hat a processzorok kihasználtságára, ill. a terhelés-eloszlásra. Ezért esett a Scalaban a választás a munka azonos méretű és egyre kisebb egységekre történő felosztása helyett a munka mindig exponenciálisan kisebb egységekre történő felbontására. Az ötlet e mögött az, hogy ha az épp végrehajtás alatt álló szál végzett az aktuális taszkkal, de a feldolgozási sorában még több taszk is található, akkor ez minden bizonnyal azt kell, hogy jelentse, hogy a többi szál is elfoglalt a saját feladatával, és így ő a következő alkalommal megpróbálhat kétszer annyi munkát elvégezni. Ha nem maradt már több taszk a feldolgozási sorában, akkor megpróbálhat más szálak soraiból „ellopni” egyet. Ezen a ponton két dolgot is meg kell említenünk: egyrészről a „taszklopás” költségesebb, mint a saját sorból pop művelettel kivenni a következő taszkot, másrészről a fork/join modell csak a legrégebbi taszk „ellopását” engedélyezi. Az előző azt jelenti, hogy minél kevesebbszer van szükség „lopásra”, annál jobb, és ha mégis „lopni” kényszerülünk, akkor legyen az a legnagyobb taszk. Az utóbbi arról szól, hogy mindenképp számításba kell vennünk a taszkok feldolgozási sorokba való bekerülését (fork).
Ha egy párhuzamos művelet végrehajtásra kerül egy kollekción, a kollekció azonnal két részre dobódik. Az egyes részek feldolgozásához taszk keletkezik, melyhez szál rendelődik, és a taszk bekerül egy processzor taszk-feldolgozási sorába (fork). A részek tovább „osztódnak” míg méretük el nem ér egy előre meghatározott küszöbértéket[5]. Ezen legkisebb partíció elemeinek a feldolgozása a megszokott, szekvenciális módon történik. Miután egy processzor végzett egy taszkkal, újabb taszk után néz először saját feldolgozási sorában. Mivel a sorba a taszkok a kollekció partícionálási sorrendjében kerülnek be, az utoljára berakott (legkisebb) taszk kerül először feldolgozásra. A rákövetkező taszkokkal a processzorra az előzőnél mindig kétszer annyi munka hárul. Ha egy processzor sorából elfogynak a taszkok, egy másik processzor sorának ellentétes oldaláról - kezdve a sorba legkorábban bekerült (legnagyobb) taszkkal - fog „lopni”. A lopott taszkkal a processzor az előzőeknek megfelelően jár el, tovább bontja, míg a két legkisebb partíció mérete el nem ér egy előre meghatározott küszöbértéket.

[3]load-balancing
[4]adaptive work stealing
[5]threshold

Megvalósítás

A kezdeti megközelítést hanyagolva a fejezetben rögtön rátérünk a végső megvalósításra.

Split és Combine

A splitter egy iterátor, mellyel egy kollekció elemeit járhatjuk be. A megszokott metódusok, mint a next vagy hasnext, mellett rendelkezik még a split metódussal, mely egy széttördelt kollekció elemeinek bejárásához több splittert (partíciónként egyet) bocsát rendelkezésünkre. A split meghívása után az eredeti iterátor nem aktiválható.

trait Splitter[T] extends Iterator[T] { def split: Seq(Splitter[T]) }

Üres vagy egy elemű kollekción nincs hatása, viszont egy legalább kétfelé tördelt kollekciónak már két splittere van. Az elemek partícionálása/felosztása függ a választott kollekció típusától. Ügyelni kell rá, hogy a partíciók száma ne legyen túl nagy, méretük ne legyen nagyon különböző, mert ennek a terhelés-megosztás láthatja kárát.

A párhuzamos feldolgozású szekvenciális adatszerkezetek egyes műveleteik megvalósításához speciális splittert kívánnak meg: a PreciseSplitter a Splitter leszármazottja és tetszőleges elemszámú partíciók létrehozását teszi lehetővé.
Példa: A ParArray kollekció split metódusának meghívása két splittert eredményez, egyik a tömb egyik felén, másik a másik felén iterál végig. (Ehhez persze arra van szükség, hogy a tömb mérete ismert legyen a splitter számára, benne tárolódjon.)
A combiner a builder általánosításának tekinthető. Minden párhuzamos feldolgozású kollekció rendelkezik saját combinerrel, csakúgy mint a hagyományos kollekciók builderrel. Míg azonban a builder elemek hozzáadásával építi fel a result meghívásával visszaadott kollekciót, a combinernek van egy combine metódusa, amely fog egy másik combinert és összeépíti kettejük elemhalmazát, azaz veszi elemeik unióját. A combiner szemantikájából adódik, hogy meghívása után a builder nem aktiválható.

trait Combiner[Elem, To] extends Builder[Elem, To] { def combine(other: Combiner[Elem, To]): Combiner[Elem, To] }

A combinernek két paramétere van, az egyik Elem, az elemek típusa, a másik To, az eredménykollekció típusa. Például a ParArray combine metódusa egyirányban láncolt listákban elhelyezett tömbcsonkokat egyesít. Csak a result meghívása után, az egyes tömbök méretének ismertté válása után, foglalódik le hely a memóriában az egyesített tömbnek.
A párhuzamos feldolgozású kollekciók alapvető traitje[6] a ParIterable, mely metódusait a Scala Collection Framwork Iterable traitjéből örökli, másrészt bevezet új metódusokat is, mint az absztrakt parallelIterator vagy az absztrakt newCombiner. Az előbbi egy splittert, az utóbbi egy combinert ad vissza a kollekcióra.
Egyes kollekcióműveletek megkívánják a különböző processzorok közötti kommunikációt, ezért minden egyes párhuzamos művelet meghívásakor létrejön egy Signalling objektum is. A splitter hozzárendelődik a Signalling objektumhoz, felosztáskor (split) a gyermek-splitterök is ugyanezt a Signalling objektumot kapják meg.
A kollekcióműveletek a ParIterable-t megvalósító osztályokban önálló taszkokként lettek implementálva. A süti minta[7] szerint a taszk ütemezési logika más rétegbe került, ami által bármikor könnyen lecserélhetővé válik, de ami magával vonta a Task absztrakt adattípus megjelenését is. Más műveletek taszkjai ugyanebből az absztrakt taszkból öröklődnek.
Végül az igény szerinti munkamegosztás technikájához a küszöbértéket kiszámító metódus a threshold nevet kapta. Ez a következő egyenlet szerint számított egész értéket adja vissza: threshold=max(1,n/8P), ahol n a kollekció mérete (elemszáma) és P a processzorok száma.
A ParIterable altraitjei a ParSeq, a ParMap és a ParSet olyan szekvenciális adatszerkezetek, mint a map vagy a halmaz, párhuzamos feldolgozásához definiálnak felületet.

[6] A trait olyasmi, mint a Javaban az interfész; azonban a Javaval ellentétben az absztrakt metódusok deklarálása mellett enged konkrét metódusokat definiálni. Közös még bennük, hogy mindkét nyelvben általuk valósítható meg a többszörös öröklődés.
[7]cake pattern

Közös műveletek

A Scala kollekcióit gazdagon ellátták mindenféle művelettel. Az alábbiakban felsoroljuk a párhuzamos feldolgozás révén új értelmet nyertek közül a legfontosabbakat:

foreach

Az egyik legegyszerűbb művelet a foreach:

def foreach(f: T => U): Unit

Paramétere egy magasabb rendű függvény f, amely a kollekció minden elemén meghívásra kerül. Két fontos tulajdonsággal bír, az egyik, hogy a kollekció különböző részein dolgozó különböző processzorok egymást nem befolyásolják, a másik, hogy „nincs” visszatérési értéke[8]. Mindebből következik, hogy a foreach kiválóan alkalmas a párhuzamosításra.
Egy másik példa visszatérési értékkel „nem” rendelkező metódusra, a copyToArray.

[8] Pontosabban a Unit típust adja vissza, ami megfelel a Java void típusának, azaz nem képvisel értéket.
reduce

A metódusok többsége viszont a fenti Unitnál valami érdekesebbet ad vissza.

def reduce[U >: T](op: (U, U) => U): U

A reduce paramétere egy bináris, asszociatív művelet, amely a kollekció minden elemén alkalmazásra kerül.
A bináris op függvény első két operandusa a kollekció első két eleme lesz. A kapott eredményből és a harmadik elemből lesz a következő részeredmény számítva, és így tovább, míg el nem értünk a kollekció végére és meg nem kaptuk a végeredményt. A művelet numerikus típusú kollekcióelemek esetén lehet pl. az összeadás; sztringek vagy listák esetén lehet pl. a konkatenáció. A lényeg, hogy asszociatív[9] legyen, mivel a kollekció partícionálási, ill. későbbi összeépítésének sorrendje előre nem meghatározott. Viszont nem feltétlenül szükséges, hogy a művelet kommutatív[10] is legyen, hisz az elemek relatív sorrendje az egyes partíciókon belül megőrződik.
Hasonló módon implementált metódusok: aggregate, fold, count, max, min, sum és product

[9]A kifejezés tetszőlegesen zárójelezhető, pl. a+(b+c)=(a+b)+c
[10]Az operandusok felcserélhetők, pl. a+b=b+a
forall

Eddig azt láttuk, hogy a partíciók feldolgozása egymástól függetlenül zajlott, néha azonban ennek épp az ellenkezőjére van szükség:

def forall(p: T => Boolean): Boolean

Ez a metódus csak akkor ad vissza igaz értéket, ha paramétere, a p predikátum, a kollekció összes elemén alkalmazva csak az igaz értéket állította elő. Szekvenciális kollekciók esetén ez annyit tesz, hogy bejárásuk valamilyen feltételhez köthető. Ahhoz, hogy megállapíthassuk, hogy egy párhuzamos feldolgozású kollekció feldolgozása mikor ér véget, az egyes részeknek kommunikálniuk kell egymással. A taszkok közötti üzenetküldés a korábban említett Signalling objektum segítségével történik. Ha a forall talál egy olyan elemet, mely a predikátumot nem elégíti ki, beállít egy jelölőt (flag). A többi taszk bizonyos időközönként megvizsgálja ezen jelölő értékét, és ha azt bebillentett állapotban találja, rögtön felhagy a feldolgozás folytatásával.
Az alább felsorolt metódusok ugyanezen mechanizmus segítségével döntik el, hogy meddig kell folytatni a feldolgozást: exists, find, startsWith, endsWith, sameElements és corresponds. A végső eredmény rendszerint egy, a részeredményeken alkalmazott, logikai művelet alkalmazásával áll elő.

prefixLength

A prefixLength a kollekció azon első legrövidebb szakaszának az elemszámát adja vissza, melynek minden eleme kielégíti a paraméterében megadott predikátumot. Azonban nem feltétlenül áll le a feldolgozás, ha egy taszk talál egy e elemet, amely nem tesz eleget a feltételnek. Ugyanis elképzelhető a partícionálás miatt, hogy találunk még az e-t megelőző és nála rövidebb kollekciórészt, melynek minden eleme kielégíti a feltételt. A taszkok közötti információátadásról itt is egy Signalling objektum gondoskodik. Egy egész értékű flag tárolja a feltételt kielégítő aktuálisan legkisebb elem pozícióját.
Hasonló, szintén egész értékű flaggel dolgozó metódusok: takeWhile, dropWhile, span, segmentLength, indexWhere és lastIndexWhere

filter

Sok metódus új kollekciót ad vissza, ilyen a filter is:

def filter(p: T => Boolean): Repr

A kollekció elemein alkalmazza a p logikai függvényt, majd a combinerök által összeépített eredménykollekciót téríti vissza. Egyes metódusok, mint a map, take, drop, slice és splitAt, azzal az előnnyel bírnak, hogy előre ismerik az eredménykollekció méretét. Hogy ezen információ ismerete, hogyan járul hozzá egy kollekció hatékonyabb feldolgozásához, azt a ParArray kollekcióval mutatjuk meg: ezen műveletek alkalmazása esetén először lefoglalódik egy belső tömb az eredménykollekció számára. Az egyes taszkok ugyanezen adatstruktúrára való hivatkozásokat (referenciákat) kapják meg. Minden taszk egyazon eredménykollekciót módosítja, így a munka befejezése után már nincs szükség a részeredmények összeépítésére (combine). Más műveletek, mint a flatMap, partialMap, partition, takeWhile, dropWhile és span, esetén viszont nem tudható előre az eredménykollekció mérete.

zip

A PreciseSplitter psplit metódusa a sima split-tel szemben képes egy kollekciót tesztelőges méretű részekre darabolni. A partícionálás eredményei pontosabban megfogalmazva a szekvenciák. A szekvencia a Scala terminológiában egész értékekkel ellátott elemsorozatot takar. Néhány metódus ezt a tényt használja fel: zip, startsWith, endsWith, patch, sameElements és corresponds. Az alábbiakban a zip-et mutatjuk be közelebbről:

def zip[T](that: ParSeq[S]): ParSeq[(T, S)]

A zip az aktuális és a that kollekciókból képzett, index alapján összetartozó elempárok egy szekvenciáját adja vissza. A különböző típusú párhuzamos feldolgozású kollekciók splitterjei azonban különböző méretű szekvenciákat állíthatnak elő a partícionálás során. A zip-taszkok számára innentől kezdve nem világos, hogy mely levélelemeket kell párba összefogniuk. A psplit lehetővé teszi, hogy mindkét kollekciót azonos méretű szekvenciákra daraboljuk fel.

Párhuzamos feldolgozású tömb[11]

Az egyik legnépszerűbb adatszerkezet a tömb. A ParArray a Scala párhuzamos feldolgozású kollekciói között fordul elő, és párhuzamos feldolgozású szekvencia lévén a ParSeq traitet terjeszti ki (extends). Tömb lévén elemei egymás utáni memóriarekeszekben tárolódnak.
A split metódus (csakúgy, mint a psplit) a tömböt két nem egyenlő méretű részre osztja, de ez esetben a két splitter ugyanarra az adatszerkezetre mutat a memóriában. A combinerök feladata jelen helyzetben nem több, mint a tömbcsonkok listájának egyesítése/konkatenálása. Ha a gyökér-taszk a kiszámítási fa szerint végzett a feladatával, az eredménytömb mérete ismertté válik. Csak ekkor foglalódik le hely a tömbnek a memóriában, és kezdődhet el a már kiszámított tömbelemek idemásolása. Számos platform biztosít gyors tömbmásoló műveleteket, ezen felül maga a másolás is párhuzamosítható új taszkok és új kiszámítási fa létrehozásával. Ha különböző processzorok egymáshoz közeli vagy egymást átfedő memóriaterületekkel dolgoznak, ritkán előfordulhat a téves megosztás[12] incidense. Ilyenkor a processzorok úgymond „elnézik” a tömbcsonkok indexhatárait. A probléma felmerülésének esélye kisebb, ha azonos méretűek a tömbcsonkok.
Azoknál a korábban említett párhuzamos feldolgozású tömböt visszaadó műveleteknél, melyek előre ismerik az eredménytömb indexhatárait, a feldolgozás hatékonysága nagymértékben javítható, ha az eredménytömbnek még az eredmények kiszámítása előtt allokálódik fizikai tárhely. Így ugyanis megspórolható a kettőből egy másolás művelet. Mint látjuk, itt szóba sem jöhet a lusta kiértékelés. Megjegyezzük, hogy vannak olyan speciális adatszerkezetek, mint a rope, melyek használata a másolást teljes egészében mellőzi.

[11]Parallel array
[12]false sharing

Párhuzamos feldolgozású hash trie[13]

A párhuzamosított műveletek akkor aknázhatók ki igazán, ha hatékony műveletek állnak rendelkezésünkre a kollekciók feldarabolására, ill. újbóli összeillesztésére. Egyes kollekciók belső szerkezetéből adódik, hogy feldolgozásuk nehezen párhuzamosítható: például két hashtábla összeillesztése időben akár lineáris is lehet, ami igazán nagy hashtáblák esetén már elfogadhatatlan teljesítményt jelentene.
Létrehoztunk egy, a hash fák által ihletett, saját adatszerkezetet, amit az angol hash fa nevéből (hash tree) eredeztetve hash trie-nek neveztünk el. Egy átlagos hash trie gyökere egy 2n számú elemet (pontosabban kulcs/értékpárt) tartalmazó hashtábla, ahol n értéke általában 5. Egy új elem hozzáadása a fához a kulcs hashkódjának kiszámítását, majd a táblában a kód első n bitjéből képzett indexhelyen való elhelyezését jelenti. Ha a kulcsok ütköznének, új tömböt hozunk létre a túlcsordult elemeknek, amit aztán a túlcsordulás helyére láncolunk. A túlcsordult elemek a számukra létrehozott tömb azon indexpozícióján helyezendők el, ami (az első n biten megegyező) hashkódjuk következő n bitjéből képezhető. A további túlcsordulások (ha vannak) ugyanígy, rekurzívan kezelendők. A keletkező fa adatszerkezet igen alacsony lesz, így néhány ugrással megtalálható a keresett elem. Tovább optimalizálhatjuk a keresést, ha a fa egyes csomópontjaiban a csomópontban szereplő hashkódok bitmapjét helyezzük el. Úgy találtuk, hogy a hash trie feldolgozásának hatékonysága nem marad el a hashtábláétól: gyorsabban bejárhatók, viszont lassabban konstruálhatók.
A hash trie tárhely igénye kedvező, jól pufferelhető, és a műveletek is jól párhuzamosíthatók rajta. A split fogja a gyökérben lévő hashtáblát, és kettéosztja ez alapján a fát. A két fél fához hozzárendelődik egy-egy iterátor, melyek az eredeti hash trie-t hivatkozzák. Mivel a párhuzamos feldolgozású hash trie-ket szinte kizárólag csak mapek és halmazok implementálására használjuk, a psplit megvalósítása jelen esetben nem szükséges.

Az összeépítés megvalósítására két mód is kínálkozott:

  1. Az egyik szerint a combinerök combine metódusa a belső hash trie-ket egyesíti. Ütközés esetén az összeépítés rekurzív módon folyik tovább. Ez a technika hatékonyabbnak bizonyult, mint a szekvenciális összeépítés, vagy mint egy hagyományos hashtábla felépítése. Általában egy művelet párhuzamos végrehajtása során többször is meg kell hívni a combine-t, az egyesítés ekkor akkor éri meg, ha az elemenként befektetett munka elég nagy volt. Maguknak a részeknek az összeépítése folyhat párhuzamosan is, ütköző farészek esetén új taszk gondoskodik a rekurzív folytatásról. Még jobb eredmény érhető el lusta kiértékeléssel: az aktuális kiértékelést félbeszakítjuk az eredményfa létrejöttéig, és csak „az utolsó pillanatban”, de akkor egyszerre több ágon is (párhuzamosan) elindulva, építjük fel a hash trie-t.
  2. A combinerök megvalósításához mégsem hash trie-ket, hanem egyenként 32 (=25) buckettal rendelkező tömböket használtunk. Bucketonként a tartalmazott elemek 5 bites[14] hashkódja megegyezik. A bucket tömbök egyirányban láncolt listája, mely konstrukció bővítéskor helytakarékosabbnak és olcsóbbnak bizonyul a hash trie-nél. Új elem hozzáadása a hashkód kiszámítását, a kód prefixuma alapján a megfelelő bucket megtalálását, azon belül pedig a megfelelő csomópont tömbjének a végén való bővítését jelenti.
A combine nem csinál egyebet, mint a bucketok bejárását és az őket reprezentáló láncolt listák összefűzését. Ha a gyökér-combiner végzett a feladatával, az eredmény-hash trie párhuzamosan felépíthető. Minden egyes processzor hozzáfog egy bucket által reprezentált részfa szekvenciális felépítéséhez. Egyirányban láncolt listába a beszúrás igen hatékony, megkíméli a processzorokat a hash trie-k többszöri merge-ölésétől, ráadásul az így nyert részfák mélysége átlagosan egy szinttel kisebb, mint merge-ölés esetén. Mivel a processzorok nem férnek hozzá az egymás által kezelt részfákhoz, az adatok konzisztenciája garantálható.

[13]Parallel hash trie
[14]n helyett „csupán” 5 bitet választottunk, mert ez a gyakorlatban elégnek bizonyult. n esetén tömbjeink 2n számú buckettal rendelkezhetnének.

Párhuzamos feldolgozású tartomány[15]

A legtöbb imperatív nyelv ciklusszervező utasítása a for utasítás. Az objektumorientált nyelvek, mint a Java vagy a C#, külön utasítást (foreach) biztosítanak egy kollekció elemeinek a bejárásához. A Scala for utasítása:

for (elem <- list) process(elem)

a list (egyébként tetszőleges) objektumon[16] meghívott foreach utasítássá alakítható:

list.foreach(elem => process(elem))

Ahhoz hogy a for ciklus hagyományos módon, egész számok sorozatán iteráljon végig, a Scalaban a Range osztályt kell példányosítani. A Range olyan nem módosítható[17] kollekció, mely egy számtartomány alsó-, felső határát, ill. a lépésközt képes tárolni. A Scala implicit konverziójának köszönhetően a hagyományos for ciklus felírható a megszokottabb formában is:

for (i <- 0 until 100) process(i)

A ParRange kollekció a for ciklus párhuzamosításakor kerül előtérbe. Az előző for könnyedén párhuzamos feldolgozásúvá tehető:

for (i <- 0 until 100).par process(i)

A ParRange olyan nem módosítható kollekció, mely egy számtartomány elemeit, ill. a lépésközt képes tárolni. Egészek tetszőleges kollekcióját nem képes tárolni, így combinerre nincs is szüksége. split metódussal azonban rendelkezik, mely az egészek sorozatát két részre osztja, külön iterátort biztosítva bejárásukhoz. A psplit hasonlóképpen lett megvalósítva.

[15]Parallel range
[16]Nem kell feltétlenül kollekciónak lennie.
[17]immutable

Párhuzamos feldolgozású nézet[18]

Tegyük fel, hogy szeretnénk egy c kollekció elemeihez, melyek számok, 10-et hozzáadni, majd a kollekció első felének pozitív számait leválogatni és ezeket összeadni.

c.map(_ + 10).take(c.size / 2).filter(_ > 0).reduce(_ + _)

Még ha a fenti műveletek párhuzamosíthatók is, a fenti kódrészlet vét a hatékonyság ellen, hisz minden művelet, kivéve a reduce-t új kollekciót hoz létre. A Scala kollekciókat felsorakoztató keretrendszere rendelkezésünkre bocsát egy különleges kollekciót, a nézetet[19]. A nézet becsomagol egy kollekciót, hogy aztán valamilyen úton-módon bejárhassa annak elemeit. Például a Filtered nézet csak azon kollekcióelemeken iterál végig, amelyek a megadott predikátumot kielégítik; a Mapped nézet minden elemet érint, feltéve, hogy előtte alkalmazta rájuk a megadott map függvényt. Ha bármely, kollekciót visszaadó metódust meghívunk egy nézeten, új nézet jön létre. Az így létrejövő nézetek keletkezésük sorrendjében verembe helyezhetők, minden nézet tartalmaz egy referenciát az őt létrehozó nézetre. A nézet bármikor „konkretizálható”, a force metódus kollekciót készít belőle.
A fenti példában c-re először a view-t alkalmazva eltekinthetnénk az újabb és újabb, csupán részeredményeket tároló, éppen ezért felesleges kollekciók legyártásától.

c.view.map(_ + 10).take(c.size / 2).filter(_ > 0).reduce(_ + _)

A párhuzamos feldolgozású nézetek újradefiniálják a hagyományos nézetek viselkedését azáltal, hogy vermet nem igénylő műveleteiket párhuzamosítják. A nézet a ParIterable traitet terjeszti ki, iterátora a split-et valósítja meg. Mivel a view nézetet és nem pedig kollekciót ad vissza, sem combinerre, sem pedig combine metódusra nincs szüksége.

[18]Parallel view
[19]view

Összefoglalás

Megmutattuk, miként lehet a Scala kollekcióinak széles műveletskáláját párhuzamos feldolgozás használatára átírni és optimalizálni. Mindezt tettük a splitter-combiner (feloszt és egyesít) egyszerű absztrakció bevezetésével. Az integráció sikeres volt, és jó teljesítményt is sikerült felmutatni az új, párhuzamosított műveletek alkalmazásával.
A közeljövőben tervezzük a párhuzamos feldolgozású tömbök speciális eseteinek - a primitív típusok tömbjeinek - hatékonyabb feldolgozása kidolgozását. Primitív típusok jelenleg csak boxed állapotban lehetnek tömbök elemei. A boxing/unboxing[20] technika nem pusztán plusz költséget visz a párhuzamosítás megvalósításába, hanem a tömbelemek heapen való folytonos elhelyezését is megakadályozza.
Másfelől azon vagyunk, hogy a keretrendszert bővítsük olyan új kollekciókkal és kollekcióműveletekkel, amelyek kényelmesebbé tehetik a párhuzamos programok írását és világosabbá azok szemantikáját. Például igényt látunk olyan műveletek bevezetésére, amelyek a kollekció párhuzamos feldolgozása során képesek tekintetbe venni az adatok közötti függőségeket.

[20] A primitív típusok (pl. egészek, valósak) objektummá válásához úgynevezett csomagoló (wrapper) osztályokra van szükség. Ezt nevezzük boxingnak. Ezen objektumok visszaalakítását primitív „egységekké” hívjuk unboxingnak.