% ByteString-esitelmä Funktio-ohjelmointi 2 -kurssia varten
% Joel Lehtonen 7.5.2008
%

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[finnish]{babel}
\usepackage{fancyvrb}

% Hakkeroidaan babel-paketin suomenkielisiä käännöksiä:
% Vaihdetaan lähdeluettelon otsikoksi Lähteet
\addto\captionsfinnish{\def\refname{Lähteet}}
% Hakkerointi päättyy

% Verbatim-blokkien säätöä
\DefineShortVerb{\_}

\usepackage[dvips]{graphicx} % tarvitaan vain, jos halutaan mukaan EPS-kuvia

\title{Haskellin ByteString}
\author{Joel Lehtonen\\ \texttt{jopesale@jyu.fi}}
\date{7.5.2008}

\begin{document}

\maketitle

\begin{abstract}
ByteString on Haskellille kirjoitettu tavanomaista _[Char]_-merkkijonoa tehokkaampi tavujono. Käytännön toteutukset käyttäen ByteStringiä vaikuttavat olevan silminnähtävästi tehokkaampia säilyttäen kuitenkin koodin luettavuuden.

\end{abstract}

\section{Millainen ByteString on?}

ByteString~\cite{bytestring} on nimensä mukaisesti tavujono. 
ByteStringin väitetään dokumentaation mukaan olevan toteutukseltaan 
Stringiin verrattuna tilankäytöltään ja suorituksen tehokkuuden kannalta 
tehokkaampi.

ByteStringin alkuperäisen toteutuksen GHC:lle on tehnyt 
Bryan O\'~Sullivan. Toteutusta on sittemmin parannettu ja laajennettu 
useampaan otteeseen.

\section{Käyttötarkoituksesta}

Silmäiltäessä ByteStringin dokumentaatiota~\cite{bytestring} huomataan, 
että moduuliin kuuluvat funktiot on nimetty pitkälti samoin kuin 
moduulissa Data.List~\cite{list}. Tämä madaltaa kynnystä ByteStringin 
käyttöön, koska moduulissa vastaavan nimiset funktiot toimivat 
analogisesti Data.List-moduulin funktioihin nähden.

Toteutus eroaa tavanomaiseen listaan nähden siten, että ByteString ei 
säilö tietoaan listana, vaan tieto pakataan (pack) C:n tapaan 
taulukoksi. Käytännössä ohjelmoitaessa ei tarvitse asiasta huolehtia, 
vaan voidaan käyttää ByteStringin tarjoamia funktioita kuten _foldr_ 
tavanomaisen _Data.List.foldr_:n sijaan.

Koska tavujono koodataan C:n char-jonon tapaan Word8-taulukoksi, se on 
kuljetettavissa Haskell- ja  C-ohjelmien välillä ilman raskaita 
muunnoksia.

\section{Suorituskyky}

Jotta saataisiin riittävää pohjaa ByteStringin dokumentaatiossa väitettyyn
tehokkuuteen, suorituskyvyn eroja Stringeihin ja ByteStringeihin perustuvien
toteutusten välillä testattiin kirjainten esiintymiä laskevalla 
sovelluksella (ks. luku \ref{koodi}). 
Sovellus hyödyntää funktioita, jotka ovat saavavilla niin Stringejä
kuin ByteStringejä käytettäessä. Sovelluksesta kirjoitettiin kaksi
toteutukseltaan erilaista, mutta toiminnallisuudeltaan samanlaista
versiota; CharCount on toteutettu käyttäen Stringiä (eli Char-listaa)
ja ByteCount käyttää ByteStringiä ja Word8:a.

Alla esimerkkinä testiohjelmien kääntäminen ja suoritusajan mittaus. 
Sama toiminnallisuus on toteutettu käyttäen Char-listaa (CharCount.hs) 
ja ByteStringiä (ByteCount). Molemmat ohjelmat on käännetty optimointi 
päällä käyttäen GHC:n versiota 6.6.1. Testidatana käytettiin miljoona 
ensimmäistä alkulukua sisältävä tekstitiedostoa~\cite{primes}.

\begin{verbatim}
$ ghc -O -o char CharCount.hs
$ time ./char primes1.txt 
'\n'    125002
'\r'    125002
' '     2879117
'('     1
')'     1
...

real    1m13.194s
user    1m11.002s
sys     0m2.165s
\end{verbatim}

\begin{verbatim}
$ ghc -O -o byte ByteCount.hs
$ time ./byte primes1.txt
...
real    0m0.176s
user    0m0.144s
sys     0m0.025s
\end{verbatim}

Toistettaessa mittausta lukuisia kertoja suoritusajat säilyvät samoissa 
kokoluokissa. Toteutusten välinen suoritusajan suhde on 
monisatakertainen ByteStringin hyväksi. Vaikuttaa siltä, että 
käsiteltäessä dataa tavutasolla saadaan valtaisia tehoeroja 
käyttämällä ByteStringejä Stringien sijaan.

Eräässä vertailussa~\cite[sivu 62]{rewriting} testattiin tehokkuutta 
vertaamalla GNU-komentorivityökaluja ja näiden toiminnallisuutta 
vastaavilla, mutta Haskellin Stringeillä ja ByteStringeillä toteutettuja 
versioita. Testissä ByteString-toteutukset ovat suoritusajan suhteen 
samassa suuruusluokassa C:llä toteutettujen perusteellisesti 
optimoitujen GNU-työkalujen kanssa. Artikkelissa myös väitettiin 
Haskell-toteutuksen olevan yleensä vastaavaa C-kielistä toteutusta 
intuitiivisempi.


\subsection{Rajoituksia}

Tavallisiin listoihin verrattuna ByteString ei ole lista vaan tyyppi. 
Tästä seuraa, että siihen ei pysty käyttämään tavanomaisille listoille 
suunniteltuja funktioita. Mikäli _Data.ByteString_-moduulista löytyvät 
funktiot eivät riitä, on mahdollista muuttaa ByteString Word8-alkioista 
koostuvaksi listaksi _unpack_-funktiolla. Käänteinen funktio listasta 
ByteStringiksi on nimeltään _pack_.

Huomionarvoista on myös, että ByteString soveltuu ainoastaan tavujonojen 
käsittelyyn eikä sillä ole tekemisistä merkkijonojen kanssa. 
Char-moduuli tukee Unicodea ja sisältää lukiisia merkkijonojen 
käsittelyssä hyödyllisiä funktioita esimerkiksi kirjainkoon ja 
merkkiluokkien tunnistamiseen.


\section{Esimerkkikoodit}\label{koodi}

Käytetyt esimerkkikoodit suorituskyvyn testaamisessa:

\subsection{ByteCount.hs}
\begin{Verbatim}[label=ByteCount.hs,numbers=left]
module Main where

import Data.ByteString(ByteString)
import qualified Data.ByteString as B
import System.Environment(getArgs)
import Data.Word
import Data.Char

type ByteCount = (Word8,Int)

main = do
	args <- getArgs
	let file = head args
	contents <- B.readFile file
	putStr $ goodLooking $ count contents

count :: ByteString -> [ByteCount]
count contents = map couple $ B.group $ B.sort contents

couple :: ByteString -> ByteCount
couple bytes = (B.head bytes,B.length bytes)

goodLooking :: [ByteCount] -> String
goodLooking stuff = unlines $ map lineString stuff

-- This converts fst to Char (destroys non-ascii characters)
lineString :: ByteCount -> String
lineString (byte,count) = show (fix byte) ++ "\t" ++ show count

fix :: Word8 -> Char
fix = toEnum . fromIntegral
\end{Verbatim}

\subsection{CharCount.hs}
\begin{Verbatim}[label=CharCount.hs,numbers=left]
module Main where

import System.Environment(getArgs)
import Data.List

type CharCount = (Char,Int)

main = do
	args <- getArgs
	let file = head args
	contents <- readFile file
	putStr $ goodLooking $ count contents

count :: String -> [CharCount]
count contents = map couple $ group $ sort contents

couple :: String -> CharCount
couple chars = (head chars,length chars)

goodLooking :: [CharCount] -> String
goodLooking stuff = unlines $ map lineString stuff

lineString :: CharCount -> String
lineString (char,count) = show char ++ "\t" ++ show count
\end{Verbatim}

\section{Yhteenveto}

Usein ohjelmointia joko työkseen tai harrastuksekseen tekevät haluavat 
tietää, miksi heidän pitäisi hallita juuri jokin tietty työkalu 
lukuisten vaihtoehtojen joukosta. Oma näkemykseni on:

\begin{itemize}
\item Mahdollistaa intuitiivisen koodin, joka on myös tehokasta
\item Vähentää tarvetta kirjoittaa osia sovelluksesta C-kiellellä
\item Sisäinen toteutus on mielenkiintoinen
\end{itemize}

Voin suositella ByteStringiin tutustumista kaikille 
Haskell-ohjelmoinnista kiinnostuneille.

\begin{thebibliography}{9} % numero aaltosuluissa kertoo, miten paljon
                           % varataan tilaa viitenumerolle
\bibitem{bytestring}
Haskell Documentation, \textit{Data.ByteString module}, \\<URL: 
\texttt{http://haskell.org/ghc/docs/latest/html/libraries/\\bytestring/Data-ByteString.html}>, 
viitattu 7.5.2008.

\bibitem{list}
Haskell Documentation, \textit{Data.List module}, \\<URL: 
\texttt{http://haskell.org/ghc/docs/latest/html/libraries/\\base/Data-List.html}>, 
viitattu 7.5.2008.

\bibitem{primes}
Miljoona ensimmäistä alkulukua, Zip-pakattu tekstitiedosto. <URL: \texttt{http://primes.utm.edu/lists/small/millions/primes1.zip}>, viitattu 7.5.2008.

\bibitem{rewriting}
Duncan Coutts, Don Stewart ja Roman Leshchinskiy, \textit{Rewriting 
Haskell Strings}, 2007, ISSN 0302-9743 (painettu) 1611-3349 (online).

\end{thebibliography}

\end{document}
