------------------------------------------------------------------------ FPS : Fast, packed strings ------------------------------------------------------------------------ This library provides the Data.ByteString library -- strict and lazy byte arrays manipulable as strings -- providing very time and space efficient string and IO operations. For very large data requirements, or constraints on heap size, Data.ByteString.Lazy is provided, a lazy list of bytestring chunks. Efficient processing of multi-gigabyte data can be achieved this way. Requirements: > Cabal > GHC 6.4 or greater, or hugs Building: > chmod +x Setup.lhs > ./Setup.lhs configure --prefix=/f/g > ./Setup.lhs build > ./Setup.lhs install After installation, you can run the testsuite as follows: > cd tests ; make or > cd tests ; make hugs For the full test and benchmark suite, you need GHC and Hugs: > cd tests ; make everything Authors: ByteString was derived from the GHC PackedString library, originally written by Bryan O'Sullivan, and then by Simon Marlow. It was adapted, and greatly extended for darcs by David Roundy, and others. Don Stewart cleaned up and further extended the implementation. Duncan Coutts wrote much of the .Lazy code. ------------------------------------------------------------------------ Performance, some random numbers (with GHC): This table compares the performance of common operations ByteString, from various string libraries. Size of test data: 21256k, Linux 3.2Ghz P4 FPS7 SPS PS [a] ++ 0.028 ! ! 1.288 length 0.000 0.000 0.000 0.131 pack 0.303 0.502 0.337 - unpack 3.319* 1.630 7.445 - compare 0.000 0.000 0.000 0.000 index 0.000 0.000 0.000 0.000 map 2.762* 2.917 4.813 7.286 filter 0.304 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.052 1.114 1.367 2.790 unlines 0.048 ! ! 10.950 words 1.344 2.128 5.644 4.184 unwords 0.016 ! ! 1.305 reverse 0.024 12.997 13.018 1.622 concat 0.000 12.701 11.459 1.163 cons 0.016 2.064 8.358 0.131 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 elem 0.000 1.490 0.001 0.000 last 0.000 - - 0.143 init 0.000 - - 1.147 inits 0.414 - - ! tails 0.460 - - 1.136 intersperse 0.040 - - 10.517 any 0.000 - - 0.000 all 0.000 - - 0.000 sort 0.168 - - ! maximum 0.024 - - 0.183 minimum 0.025 - - 0.185 replicate 0.000 - - 0.053 findIndex 0.096 find 0.120 - - 0.000 elemIndex 0.000 - - 0.000 elemIndicies 0.008 - - 0.314 foldl 0.148 spanEnd 0.000 snoc 0.016 filterChar 0.031 filterNotChar 0.124 join 0.016 split 0.032 findIndices 0.408 splitAt 0.000 lineIndices 0.029 breakOn 0.000 breakSpace 0.000 splitWith 0.329 dropSpace 0.000 dropSpaceEnd 0.000 joinWithChar 0.017 join / 0.016 zip 0.960 zipWith 0.892 isSubstringOf 0.039 isPrefixOf 0.000 isSuffixOf 0.000 count 0.021 Key: FPS6 = FPS 0.6 SPS = Simon Marlow's packedstring prototype PS = Data.PackedString [a] = [Char] - = no function exists ! = stack or memory exhaustion ------------------------------------------------------------------------ == Stress testing really big strings Doing some stress testing of FPS, here are some results for 0.5G strings. 3.2Ghz box, 2G physical mem. Size of test data: 524288k Size of test data: 524288k Char8 Word8 Effectively O(1) or O(m) where m < n all 0.000 0.000 any 0.000 0.004 break 0.000 0.000 breakChar 0.000 0.000 breakSpace 0.000 compare 0.000 concat 0.000 drop 0.000 dropSpace 0.000 dropSpaceEnd 0.000 dropWhile 0.000 0.000 elem 0.000 0.000 elemIndex 0.000 0.000 elemIndexLast 0.000 0.000 empty 0.000 head 0.000 0.000 index 0.000 0.000 init 0.000 last 0.000 0.000 length 0.000 notElem 0.000 0.000 span 0.000 0.000 spanChar 0.000 0.000 spanEnd 0.000 0.000 splitAt 0.000 tail 0.000 take 0.000 takeWhile 0.000 0.000 isPrefixOf 0.000 isSuffixOf 0.000 addr1 0.000 addr2 0.000 O(n) ++ 0.676 map 6.080 5.868 cons 0.396 0.396 snoc 0.400 0.400 find 3.240 split 1.204 1.200 lines 2.000 foldl 3.804 unwords 0.552 reverse 0.884 findIndex 3.128 filterChar 0.756 0.732 filter/='f' 8.265 7.012 filterNotChar 4.456 3.388 join 0.400 sort 4.344 maximum 0.776 0.764 minimum 0.772 0.776 replicate 0.008 0.000 elemIndices 0.240 0.240 lineIndices 1.092 joinWithChar 0.400 0.400 isSubstringOf 0.052 count 0.748 slow O(n) words 38.722 group 77.261 groupBy 96.226 inits 32.430 tails 23.225 findIndices 13.841 15.825 splitWith 18.445 19.225 zip 33.926 zipWith 33.562