Difference between revisions of "Performance/Strings"

From HaskellWiki
Jump to: navigation, search
(Rewrite the last case, which made me notice a space leak in Data.ByteString, and an inefficient algorithm)
(Clean up)
Line 46: Line 46:
import qualified Data.FastPackedString as P
import qualified Data.FastPackedString as P
import IO
import IO
main = P.readFile "/usr/share/dict/words" >>= P.hPut stdout . last . P.lines
main = P.readFile "/usr/share/dict/words" >>= P.putStr . last . P.lines

Revision as of 13:49, 24 April 2006

Haskell Performance Resource

Data Types - Functions
Overloading - FFI - Arrays
Strings - Integers - I/O
Floating point - Concurrency
Modules - Monads

Strictness - Laziness
Avoiding space leaks
Accumulating parameter

GHC - nhc98 - Hugs
Yhc - JHC


Sometimes the cost of representing strings as lists of Char can be too much. In this case, you can instead use packed strings. There are a number of options:

  • The standard Data.PackedString type
  • One of the newer packed string libraries, for example FastPackedString
  • Unboxed arrays of Word8 or Char
  • Ptrs to foreign malloced Word8 buffers

The packed string libraries have the benefit over arrays of Word8 or Char types, in that they provide the usual list-like operations.

Some interesting results for FastPackedString are documented here. In particular, it compares FPS against the existing PackedString and [Char] functions, and is used successfully with 1 gigabyte strings.


Pete Chown asked the question:

I want to read a text file.  As an example, let's use
/usr/share/dict/words and try to print out the last line of the file.

The python version completes in around 0.05s.

Attempt 1 : [Char]

import System.IO                                                                                  
main = readFile "/usr/share/dict/words" >>= putStrLn.last.lines

Run in hugs, this program took several seconds to complete. Problem: interpreted (solution, use a Haskell compiler). Compiled, the program completes in a fairly quick 0.2s. Still, we can do better.

Attempt 2 : Packed Strings

Using fast, packed strings, we get:

import qualified Data.FastPackedString as P                                                     
import IO                                                                                       
main = P.readFile "/usr/share/dict/words" >>= P.putStr . last . P.lines

Runs in 0.063s

Attempt 3 : No Lists

Avoid splitting the file into lists at all, and just keep a single buffer (as a C programmer would perhaps do):

import qualified Data.ByteString as P
import Maybe
import IO

main = P.readFile "/usr/share/dict/words" >>= P.putStrLn . snd . fromJust . P.breakLast '\n'

Runs in 0.013s

Related work

An extended tutorial on using PackedStrings/ByteStrings for high performance string manipulating code is here.