ANNOUNCE: FPS - FastPackedStrings 0.2
I'm pleased to announce version 0.2 of FPS, the fast, packed string library for Haskell. FPS allows you to have time and space efficient arrays of bytes accessed via a List interface, along with fast IO on those strings. FPS is, in particular, suited for heavy duty string and IO projects. It is also useful for applications that must pass strings back and forward from C. Version 0.2 features a number of improvements over v0.1. * Its faster! * There is a richer interface. * More support for converting between C, Addr# and Haskell strings. (in particular, there are 0-copy functions to create FPS strings from Addr# and to create CStrings from FPS') Get it here: Homepage: http://www.cse.unsw.edu.au/~dons/fps.html Interface: http://www.cse.unsw.edu.au/~dons/fps/Data.FastPackedString.html FTP: ftp://ftp.cse.unsw.edu.au/pub/users/dons/fps/fps-0.2.tar.gz darcs: darcs get --partial http://www.cse.unsw.edu.au/~dons/code/fps Cheers, Don ------------------------------------------------------------------------ Here are benchmarking results for 20M strings, for versions 0.1 and 0.2 of FPS, compared against Simon Marlow's prototype packedstring code, the current Data.PackedString library and traditional [Char] functions. Functions that are only provided by FPS (such as the various CString routines) are not tested. Key: FPS2 = Fast Packed String v2 FPS1 = Fast Packed String v1 SPS = Simon Marlow's packedstring prototype PS = Data.PackedString [a] = [Char] ~ = unchanged from FPS2 - = no function exists ! = stack or memory exhaustion Size of test data: 21256k Time in seconds. FPS2 FPS1 SPS PS* [a] ++ 0.078 ~ ! ! 1.288 length 0.000 ~ 0.000 0.000 0.131 pack 0.345 2.043 0.502 0.337 - unpack 1.596 ~ 1.630 7.445 - compare 0.000 ~ 0.000 0.000 0.000 index 0.000 ~ 0.000 0.000 0.000 map 2.664 4.283 2.917 4.813 7.286 filter 0.282 0.482 2.805 0.954 0.305 take 0.000 ~ 0.000 0.024 0.005 drop 0.000 ~ 0.000 11.768 0.130 takeWhile 0.000 ~ 1.498 0.000 0.000 dropWhile 0.000 ~ 1.985 8.447 0.130 span 0.000 ~ 9.289 11.144 0.131 break 0.000 ~ 9.383 11.268 0.133 lines 0.421 ~ 1.114 1.367 2.790 unlines 0.121 ~ ! ! 10.950 words 2.115 3.202 2.128 5.644 4.184 unwords 0.058 ~ ! ! 1.305 reverse 0.024 4.606 12.997 13.018 1.622 concat 0.029 ~ 12.701 11.459 1.163 cons 0.016 3.094 2.064 8.358 0.131 snoc 0.017 1.536 - - - empty 0.000 ~ 0.000 0.000 0.000 head 0.000 ~ 0.000 0.000 0.000 tail 0.000 ~ 0.000 14.490 0.130 last 0.000 ~ - - 0.143 init 0.000 ~ - - 1.147 inits 5.350 - - - ! tails 6.634 - - - 1.136 intersperse 0.034 4.590 - - 10.517 concatMap ! - - - 1.131 any 0.000 ~ - - 0.000 all 0.000 ~ - - 0.000 sort 14.380 15.773 - - ! maximum 0.024 ~ - - 0.183 minimum 0.025 ~ - - 0.185 replicate 0.008 ~ - - 0.053 elem 0.000 ~ 1.490 0.001 0.000 find 0.278 0.366 - - 0.000 elemIndex 0.000 ~ - - 0.000 elemIndicies 4.192 ~ - - 0.314 * Note that it is not possible to directly read a string larger than 1M into a Data.PackedString (due to a space leak). Instead you need to use packString
Donald Bruce Stewart wrote:
Interface: http://www.cse.unsw.edu.au/~dons/fps/Data.FastPackedString.html
I'm bothered that some of the functions work with Word8, and others with the utterly unrelated type Char. Which encoding are you implicitly using, and why? Given that FastString turns out to be an array of Word8, why are you using Char at all? Confusion of Char and Word8 is a bit of a pet peeve of mine. -- Ashley Yakeley, Seattle WA WWED? http://www.cs.utexas.edu/users/EWD/
ashley:
Donald Bruce Stewart wrote:
Interface: http://www.cse.unsw.edu.au/~dons/fps/Data.FastPackedString.html
Given that FastString turns out to be an array of Word8, why are you using Char at all?
Convenience. Some historical legacy from darcs. And others have contributed patches specifically to add more Word8 support. -- Don
On Thu, Apr 20, 2006 at 10:32:37AM +1000, Donald Bruce Stewart wrote:
ashley:
Donald Bruce Stewart wrote:
Interface: http://www.cse.unsw.edu.au/~dons/fps/Data.FastPackedString.html
Given that FastString turns out to be an array of Word8, why are you using Char at all?
Convenience. Some historical legacy from darcs. And others have contributed patches specifically to add more Word8 support.
I think the biggest barrier to using Word8 operations on String-like types is the Read/Show instance for Word8, which works like for other Word types: Prelude Data.Word> map (toEnum . fromEnum) "Haskell" :: [Word8] [72,97,115,107,101,108,108] Maybe we should introduce a Char8 type, or something like that, which would have the nice Stringy presentation? There is also a problem with literals. How about solving it by adding a Num-like Character class? Consider: Prelude> :t 1 1 :: (Num t) => t Prelude> :t "abc" "abc" :: CharAscii c => [c] Prelude> :t "aąbcć" "aąbcć" :: CharUnicode c => [c] or even: Prelude> :t "aąbcć" "aąbcć" :: CharacterPolish c => [c] ;-) And a String class would allow typing FastPackedString literals directly. Best regards Tomasz
Tomasz Zielonka wrote:
I think the biggest barrier to using Word8 operations on String-like types is the Read/Show instance for Word8, which works like for other Word types:
Prelude Data.Word> map (toEnum . fromEnum) "Haskell" :: [Word8] [72,97,115,107,101,108,108]
But FastPackedString is in fact a fast packed [Word8]. I am in favour of Word8 operations on [Word8]-like types. If you then wish to encode something (be it text, XML, video or whatever) in those bytes, you should do so explicitly. Picking one particular type (String) with one particular encoding (presumably Latin-1) is just the sort of thing that leads to text encoding errors and the kind of general programmer confusion over types that Haskell is supposed to prevent. -- Ashley Yakeley, Seattle WA WWED? http://www.cs.utexas.edu/users/EWD/
On Wed, Apr 19, 2006 at 05:24:52PM -0700, Ashley Yakeley wrote:
Donald Bruce Stewart wrote:
Interface: http://www.cse.unsw.edu.au/~dons/fps/Data.FastPackedString.html
I'm bothered that some of the functions work with Word8, and others with the utterly unrelated type Char. Which encoding are you implicitly using, and why? Given that FastString turns out to be an array of Word8, why are you using Char at all?
Confusion of Char and Word8 is a bit of a pet peeve of mine.
It is a huge pet peeve of mine too. perhaps this library should be renamed 'FastByteArray' instead? which is a very useful datatype too. John -- John Meacham - ⑆repetae.net⑆john⑈
John Meacham wrote:
Confusion of Char and Word8 is a bit of a pet peeve of mine.
It is a huge pet peeve of mine too.
perhaps this library should be renamed 'FastByteArray' instead? which is a very useful datatype too.
I agree. I would rename it and also use solely Word8-based functions. -- Ashley Yakeley, Seattle WA WWED? http://www.cs.utexas.edu/users/EWD/
participants (4)
-
Ashley Yakeley -
dons＠cse.unsw.edu.au -
John Meacham -
Tomasz Zielonka