1. Johdanto Käsittelen esseessäni perinteisten järjestysalgoritmien optimointia nykyaikaisille prosessoreille kahden aiheesta tehdyn tutkimuksen pohjalta. Järjestysalgoritmien tutkimus ei enää suuntaudu pelkästään teoreettiseen järjestämiseen, vaan myös algoritmin optimointiin käytössä olevalle laitteistolle. 2. Tutkimusten sisältö Lähteissä nostetaan esille kaksi merkittävää nopeuteen vaikuttavaa tekijää prosessoreissa: virtuaalimuistin hakutaulu (TLB, translation look-aside buffer) sekä prosessorin välimuisti (cache). Kummankin koko on rajallinen, ja tiedon haku näiden välimuistien ulkopuolelta on noin 60 kertaa hitaampaa kuin haku prosessorin omasta muistista (Rahman 2006). Tilannetta, jossa haettua muistipaikkaa ei löydy välimuistista, kutsutaan cache miss -tilanteeksi. Rahman keskittyy tutkimuksessaan radix-algoritmiin, joka on teoriassa nopea, mutta ei käytännössä toimi muita algoritmeja nopeammin. Syyksi todetaan että radix sort aiheuttaa usein tilanteita, joissa haettua osoitetta ei löydy TLB-taulusta. Näitä tilanteita on pyritty vähentämään radix-avaimen koon sopivalla valinnalla. Lisäksi tutkimuksessa on etsitty tapoja nopeuttaa algoritmia erilaisten muissa julkaisussa esitettyjen optimointien avulla. Sinha käsittelee erityisesti merkkijonojen järjestämistä ja tutkii algoritmien tehokkuutta kokeellisin menetelmin. Tehokkaaksi todetaan burstsort-algoritmi, joka lajittelee kerralla joukon lähekkäin muistissa sijaitsevia alkioita, mikä vähentää cache miss -tilanteita. 3. Johtopäätökset Lajittelualgoritmien teoreettinen analysointi on edennyt pitkälle, mutta prosessorien toimintatapa aiheuttaa tarkasteluun lisävaikeuksia. Toisaalta algoritmien pitää olla myös tarpeeksi yleiskäyttöisiä, sillä harvaan toteutukseen enää etsitään erikseen lajittelualgoritmia. Sen sijaan käytetään valmiiden kirjastojen ja tietokantapalvelimien lajittelua, jonka täytyy pystyä sopeutumaan monentyyppiseen dataan. Teoreettisissa menetelmissä on haasteena erilaisten prosessorien välimuistialgoritmien mallintaminen. Useimmat prosessorit hakevat välimuistiin kerrallaan tietyn määrän dataa, joten sopivat parametrit hakualgoritmille voivat riippua prosessorin tyypistä. Toisaalta TLB-taulu viittaa muistiin sivu kerrallaan, jolloin datan sijainti muistissa suhteessa sivujen rajoihin on merkityksellistä. Vaikka kokeelliset menetelmät vaikuttavat sinällään yksinkertaililta, Sinhan tutkimuksessa nostetaan esille myös niiden kehittäminen. Satunnainen data ei vastaa kovinkaan hyvin yleisiä tilanteita, mutta toisaalta ennaltavalitut tietojoukot eivät kerro algoritmin toiminnasta kuin juuri kyseisen aineiston kanssa. Lähteet: Cache-Efficient String Sorting Using Copying Ranjan Sinha, Justin Zobel ACM Journal of Experimental Algorithmics Numero 11, Artikkeli 1.2, 2006 Adapting radix sort to the memory hierarchy Naila Rahman, Rajeev Raman Journal of Experimental Algorithmics Numero 6, Artikkeli 7, 2001