Ei pelkkä O(n^y) yksin kerro nopeutta vaan olennainen merkitys on sillä miten monimutkainen on yksi alkeisoperaatio. Kun tekstiä käsitellään, eri prosessien O-vaikeus on tietenkin sama merkistöstä riippumatta. Vaikuttaa siltä, että tässä on vähän hakusessa se, *miten* tehokasta 8-bittisen merkistön käsittely todella voi olla.
Jos katsotaan tätä listaa:
- case-muunnos on O(n) merkki kerrallaan tehtävä ja käy koko jonon joka tapauksessa eli ei eroa. Senkin voi O(0)-optimoida tapauskohtaisesti jos merkkijono pitäisi kirjaa kirjainkoosta.
ASCII:lle case-muunnos on yksinkertaisimmillaan OR 0x20 tai AND 0xDF, mikä riittää esim. case-epäherkän haun toteuttamiseen. 32 bit kerrallaan operoidessa OR 0x20202020 tai AND 0xDFDFDFDF, millä flipataan joka merkistä yksi bitti suuntaan tai toiseen, yhden kellojakson operaatiolla. Tämä toimii varsin hyvin myös ISO Latin-merkistölle. Vähän enemmän nypläystä tarvitaan, jos tuloksen pitää olla esityskelpoinen.
Kuinka toimii UTF:lle?
- leksikografinen vertailu käy O(n)-ajassa myös jonoa alusta kunnes löytyy eroava merkki eli ei eroa. Tässäkin jos nopeus on tärkeää, järjestyksen säilyttävän tietorakenteen käyttö hyödyttää.
Pelkkä koodivertailu on helppoa mutta yleisesti vertailua helpottaisi suuresti se, että yhdelle merkille olisi yleisesti vain yksi esitystapa. Esim. täällä näyttää olevan n. 10 erilaista välilyöntiä:
en.wikipedia.org
Vaikka katsottaisiin vain yhtä merkin esitystä, merkkien eron havaitseminen on UTF:lla vaikeampaa. 16-bit merkin 1. tavu sisältää vain 2 merkitsevää bittiä sivulta, joten kaikkien "Latin1 Supplement"-kirjainten 1. tavu on sama. Tulee paljon alkavia osumia.
Kuka tämänkin on koodannut? Jo se, että tavut olisivat käänteisessä järjestyksessä, parantaisi tehokkuutta.
- konkatenoinnin
tehokkain rakenne/algoritmi on O(1)-aikainen. O(n)-ajassa taulukoilla kopiointi on suoraviivainen ja tehokkuusero tulee enemmän muistiallokaattorista kuin koodaustavasta
Melkoinen overhead tulee siitä, että ensin rakennetaan merkkijonosta tietorakenne, jotta voidaan tehtä O(1)-operaatio ja uudestaan, kun rakenne puretaan merkkijonoksi. Yhtä riviä tuskin kannattaa purkaa tietorakenteeksi mutta riveistä tai kappaleista ehkä kannattaakin tehdä jokin rakenne.
Kopioinnissa ei tule suurta eroa paitsi tietenkin siitä, että kopioitavaa dataa on enemmän. UTF8:lla joudutaan helpommin varaamaan lisätilaa tai tilaa on aina varattava reilusti. Välimuisti, muistikaista,...
- oletetaan rakenteeksi taulukko eikä esim. trie, niin hakukin etsii alijonoa alusta asti kummassakin tapauksessa eli ei eroa
Jos etsitään vain tietokoneen mielestä identtisiä symboleita, niin näin - paitsi muistin osalta.
UTF8:lla menee hankalaksi, jos halutaan case-epäherkkä haku. Vielä hankalammaksi menee, jos halutaan, että hakusanalla "irina" löytyy myös nimi "Ирина" tai samoin mikä tahansa muu "oikein" kirjoitettu ei-latinalainen nimi. On tuolla muitakin ylläreitä kuten °C vai ℃ tai peräti K vai K.
- yhdistäminen erotinmerkillä tai ilman on myös rope-rakenteella tehokkain tai jos taulukoilla tekee, käydään läpi kaikki pääteosat ja tarvittaessa allokoidaan koko taulukko tai kuoletetulla kustannuksella tehokkaasti ihan vastaavasti.
Taulukkoon tai muistiblokkiin verrattuna kaikki rakenteet aiheuttavat omat kustannuksensa. Taas tulee UTF8:lle lisätaakkaa tehottomasta koodauksesta. Toki on niin, että blokin kopiointi onnistuu hyvinkin tehokkaasti.
- pituuden laskentaan on O(1)-algoritmi jos rakenne säilyttää tiedon pituudesta kuten Pascal
Tämä ei ole merkistöriippuvainen asia. NUL-päätteisissä merkkijonoissa on heikkoutensa.
Ei tieto merkkijonon pituudesta ihan itsestään muodostu vaan kyllä se on jossain vaiheessa laskettava, ja lasku on taas triviaali 8-bittisillä merkeillä mutta aikaa ja tupakkia palaa UTF8:n kanssa. UTF8:llä pituus ei edes ole yksikäsitteinen: pituus tavuina vs. pituus merkkeinä. Hinta silläkin on, jos pidetään yllä pituustietoa, jota ei tarvita.
- Kääntäminen on näistä eka, missä on emojien ja muiden yhdistelmämerkkien takia hiukan haastetta, mutta kompleksisuus ei siitäkään kokonaisuudessaan muutu O(n)-ajasta utf8:lla
Niinpä, UTF8 käyttää yhden merkin nypläämiseen enemmän aikaa.
8-bittisillä voi ehkä hyödyntää assemblerin little/big-endian muunnoksiin tarkoitettua BSWAP-käskyä. Yhdellä käskyllä kääntyy 4/8 merkkiä, yhden kellojakson latenssilla. Joutuisaa.
- paloittelu merkin mukaan on ihan vastaava O(n)-aikainen operaatio. Paloittelu kiinteämittaisiin paloihin on nopeampi vakiolevyisellä merkkijonolla, mutta kuulostaa melko harvinaiselta operaatiolta ylipäänsä (?)
Voi tulla esiin, esim. FORTRANin kiinteäformaattisia tuloksia parsiessa. Taas on 8-bit-koodi tehokkaampi kuin yksittäisiä merkkejä analysoiva UTF8-koodi.
- alimerkkijonojen etsinsä voi olla tehokkaampi, mutta toisaalta tässäkin utf8 ja COW-rakenne roskienkeruulla voi olla tehokkaampi kuin alkeellinen C-ohjelma
Eli etsitään vaikka riviltä sanaa "ERROR". Tämä on asia, jonka on toimittava tehokkaasti esim. tutkiessa tulostiedostoja, jotka voi helposti olla isoja. Väittäisinpä, että käsiteltäessä yhtä riviä kerrallaan ei maksa vaivaa muodostaa siitä tietorakennetta.
Alkeellinenkin C-ohjelma voi käyttää 8-bittistä kirjastoa, joka pulauttaa koodiin tehokkaan inline-assembler-pätkän.
- trimmaus on myös varsin suoraviivainen O(n)-algoritmi ja jälleen range/COW-toteutus isompi optimointi kuin mitä utf8 tuo haittaa
Listasta nähdään, että vain pari operaatiota ylipäänsä hyötyy kiinteämittaisista merkeistä. Mietin alimerkkijonojen tapausta, miten siinä saat operaatiota edeltävät indeksit? Tulevatko ne jonkin hakufunktion tuloksena? Silloin se haku voisi palauttaa utf8:n tapauksessa jo alimerkkijonon ja ainakin toisen pään indeksoinnin voisi välttää.
Kun minusta lista näyttää siltä, että parhaimmillaan UTF8 olisi likimain tasoissa ja häviäisi vain tehottomamman koodauksen vuoksi mutta kaikissa tilanteissa, missä UTF8 edellyttää mitä tahansa merkkikohtaista nypläystä, 8-bittinen koodi vie UTF8:aa kuin litran mittaa. 64-bittisellä prosessorilla 8-bittistä tekstiä prosessoidaan jopa 8 merkkiä per prosessorin kellojakso.
Joitakin operaatioita on vaikeaa tehdä ollenkaan hyvin, kun sama asia voidaan ilmaista UTF-8:lla usealla eri tavalla. Hyvä koodaus ei anna samalle merkitykselle useita eri koodeja. Ei tietokone ymmärrä merkityksiä, se tulkkaa vain koodeja.
Ja kuten aiemmin sanoin, ylipäänsä jos merkkijonojen käytössä päästäisiin eroon toteutuskeskeisyydestä ja käsiteltäisiin niitä APIn läpi, niin kaikenlaiset puskuriylivuoto-ongelmat vähenisivät. Indeksointi ja puskurihaavoittuvuudet ovat yksi yleisimmistä bugien lähteistä, jos katotaan CVE-tietokantoja. Myös paikallaan muutettavat rakenteet ovat monessa kohtaa ongelmallisia, varsinkin nykyään kun käytetään säikeitä. COW/range-pohjaiset ratkaisut, ropet ja muut olisivat myös mahdollisia vaihtoehtoisina rakenteina.
Että ihan API pitäisi olla merkkijonoille Unicode-maailmassa. Säikeetkään eivät ole ihan ilmaisia. Eikö kontekstinvaihto vie kuitenkin satoja ellei tuhansia kellojaksoja?
Ei sitä kokonaan käydä läpi vaan alusta utf8:lla. Kysymys kuuluu, miten usein indeksoit ja mikä on sille hyväksyttävä hinta? 58. merkin hakuun tyypillisellä tekstillä menee se 58-116 iteraatiota. On myös se mahdollisuus, että jos voit pysyä ASCII-merkeissä, utf8:nkin kanssa voit tehdä sen oletuksen, että merkkien pituus ei vaihtele.
8-bit koodistolla indeksin osoitus on parin-kolmen kellojakson muistihaku. Tekstimuotoisia tulostiedostoja parsiessa lähtökohtana on yleensä se, että tietty data löytyy tietyistä sarakkeista. Näissä on se hyvä puoli, että ne on helposti luettavissa koneellisesti mutta myös ihmisen luettavissa.
Ehdotus ratkaista UTF-8:n ongelmat olettamalla 70-luku onkin nerokas ehdotus. Eipä silti, tähän se käytännössä varmaan menee. Sitten tulee lokinsiipiä.
Jos ohjelman pointtina on tehdä tämäntyyppistä paljonkin, niin tämä algoritmi ei skaalaudu yhtään. Mieti vaikka megatavun kokoisen merkkijonon siirtelyä tavu kerrallaan. Ei mitään järkeä.
On tietenkin selvää, että isojen tietomassojen käsittelyyn tarvitaan kunnolliset tietorakenteet. Tässä vaan helposti lähtee laukalle. Jos gigatavun tekstitiedosto skannataan läpi, se on pienten tietomäärien käsittelyä mutta toistoja tulee melko lailla paljon.
Näihin tapauksiin kielissä on enum/variant-tyypit.
Nämä on luettavia koodarille mutta enumeita on paha tulostaa käyttäjälle.
Tai jos on valittu I=isä ja i=isoisä, niin kolmannen kohdalla jo loppuvat "järkevät" kirjaimet.
Nyt löytyi käyttöä Unicodelle! Sieltä löytyy varmasti lisää I-kirjamia.