Rewriting Haskell Strings
A rewrite system for fusing operations over ByteStrings
or... How to make ByteStrings even faster!
Duncan Coutts, Don Stewart and Roman Leshchinskiy
Programming Tools Group, Oxford University Computing Laboratory
Computer Science & Engineering, University of New South Wales
Data.ByteString
A quick recap:
- Strict packed arrays of bytes
- Provides a String-like interface
- Fast operations and IO
- Lower memory usage than String
Representation
[Char]
ByteString
Data.ByteString.Lazy
Like Data.ByteString but lazy (and therefore cooler!)
- Potentially infinite, lazily generated stream of data
- Provides the same String-like interface
- Provides lazy IO
- Allows processing of streams in constant memory
- Represented internally by lazy list of strict chunks
- Almost as fast
Fusion
(also known as deforestation)
The purpose
- To improve efficiency by eliminating intermediate data structures from compositions
filter p . map f - To encourage a compositional style by making it efficient
Fusion
Existing fusion systems
- General deforestation (over arbitrary trees)
- Systems just for lists:
- Short-cut deforestation, aka 'build/fold' fusion
- 'destroy/unfoldr' fusion
- 'hylo' fusion
- Functional array fusion
build/fold fusion
- Based on two functions:
foldr :: (a -> b -> b) -> b -> [a] -> b build :: (forall b. (a -> b -> b) -> b -> b) -> [a] - and one rewrite rule:
forall g k z. foldr k z (build g) = g k z - All fusible list functions must be written in terms of these primitives
- Automated using GHC rewrite rules
- Appears to be limited to inductive structures like lists
destroy/unfoldr fusion
- Based on two functions:
destroy :: (forall b. (b -> Maybe (a, b)) -> b -> c) -> [a] -> c unfoldr :: (b -> Maybe (a, b)) -> b -> [a] - and one rewrite rule:
forall g f e. destroy g (unfoldr f e) = g f e - Also appears to be limited to inductive structures like lists
Functional array fusion
- Specifically designed for arrays
- Just one combinator:
loop :: (s -> a -> (s, Maybe a)) -> s -> Array a -> (Array a, s) - and one rewrite rule:
forall f g s t. loop f s . fst . loop g t = loop (fuse f g) (s,t) - Also uses GHC rewrite rules
Functional array fusion
Limitations
- Only expresses left to right traversals
- Cannot express functions that consume multiple arrays
- Cannot produce more element than were consumed
- so noconcatMapormapon UTF8 - Producers or consumers (rather than transformers) are awkward to write
We want something more flexible
Unfoldr again
Consider unfoldr again:
unfoldr :: (s -> Maybe (a, s)) -> s -> [a]
Take (b -> Maybe (a,b)) and b as the representation
of an abstract sequence:
data Stream a = forall s. Stream (s -> Step s a) s
data Step s a = Done
| Yield a s
| Skip s
Streams
- Can still convert to or from lists:
readList :: [a] -> Stream a writeList :: Stream a -> [a] - But now we can also convert to or from arrays
readArray :: Array a -> Stream a writeArray :: Stream a -> Array a - To support arrays better we add a length hint:
data Stream a = forall s. Stream (s -> Step s a) s Int
Operations on Streams
We can convert many common list functions to work on streams
mapS :: (a -> b) -> Stream a -> Stream b
mapS f (Stream next s n) = Stream next' s n
where next' s = case next s of
Done -> Done
Yield x s' -> Yield (f x) s'
Skip s' -> Skip s'
Which then can be lifted to work on arrays:
map :: (a -> b) -> Array a -> Array b
map f = write . mapS f . read
Fusion on Streams
Eliminate intermediate conversions to arrays with the rule
read . write = id
For example:
filter p . map f
= write . filterS p . read . write . mapS f . read
= write . filterS p . mapS f . read
Fusion on Streams
Producers and consumers are also fusable
foldl' k z = foldlS' k z . read
replicate x n = write . replicateS x n
For example:
foldl' k z . filter p . map f
= foldlS' k z . read . write . filterS p
. read . write . mapS f . read
= foldlS' k z . filterS p . mapS f . read
Example benchmark: String
Haskell String version:
main = print
. foldl' hash 5381
. map toLower
. filter isAlpha
=<< readFile f
where hash h c = h * 33 + ord c
Example benchmark: ByteString
Lazy ByteString version:
import Data.ByteString.Lazy.Char8 as B
main = print
. B.foldl' hash 5381
. B.map toLower
. B.filter isAlpha
=<< B.readFile f
where hash h c = h * 33 + ord c
Example benchmark: Naive C
#include <stdio.h>
void main () {
long h = 5381;
int c;
while ((c = getchar()) != EOF)
if (isalpha(c))
h = h * 33 + tolower(c);
printf("%li\n", h);
}
Example benchmark: Fast C
#include <stdio.h>
void main() {
long h = 5381;
char buf[4096];
int i, count;
while (count = fread(&buf, 1, 4096, stdin))
for (i = 0; i < count; i++)
if (isalpha(buf[i]))
h = h * 33 + tolower (buf[i]);
printf("%li\n", h);
}
Example benchmark: results
Comparison with Strings and C
Traversal direction
- Not limited to 'up' traversals
readUp :: Array a -> Stream a writeUp :: Stream a -> Array a - Can express and fuse 'down' traversals
readDn :: Array a -> Stream a writeDn :: Stream a -> Array a scanr f z = writeDn . scanrS f z . readDn
Folds
Arrays give a new perspective on folds
- Some folds are better as down traversals
- Allows all 4 folds:
foldr f z = foldS f z . readUp foldl f z = foldS (flip f) z . readDn foldl' f z = foldS' (flip f) z . readUp foldr' f z = foldS' f z . readDn - Accumulator strictness reverses the direction
Traversal direction again
- Fusing up and down traversals is not possible in general
- In many common caes it is possible
For example:map,filter,sum - Simple read/write fusion does not cover these cases
New formulation
- Derive new fusion primitives
producerUp f = writeUp f consumerUp f = f . readUp transformerUp f = writeUp . f . readUp - Derived rules
consumerUp f (producerUp g) = f g consumerUp f . transformerUp g = consumerUp (f . g) transformerUp f (producerUp g) = producerUp (f g) transformerUp f . transformerUp g = transformerUp (f . g)
Bidirectional traversals
- Can now express bidirectional traversals
producerBi :: Stream a -> Array a consumerBi :: (Stream a -> b) -> (Array a -> b) transformerBi :: (Stream a -> Stream b) -> (Array a -> Array b) - Side condition
producerBi f = reverse . producerBi f consumerBi f = consumerBi f . reverse transformerBi f = reverse . transformerBi f . reverse
Bidirectional fusion
- Side condition allows us to derive more fusion rules
(4 * 7 = 28 rules in total)consumerDn f . transformerBi g = consumerDn (f . g) - Less confusing to programmers, you still get fusion if you switch from
foldltofoldl'foldl['] f z . map g
Future directions
Practical applications
- Unicode
- parsing
- binary serialisation
Fusion improvements
- build/fold is better at fusing
(:)and(++) - could use Stream fusion for all sequence-like types
- used in data-parallel Haskell to fuse nested, parallel array operations, on multi-core CPUs. (40 cpu sparc servers)