haskell / attoparsec

A fast Haskell library for parsing ByteStrings
http://hackage.haskell.org/package/attoparsec
Other
512 stars 93 forks source link

Fix `Text.FastSet` #118

Closed bgamari closed 8 years ago

bgamari commented 8 years ago

Otherwise consider the case of,

let fs = fromList "abcx"
in '\239' `member` fs

In this case,

The solution taken here is to ensure there is always at least one entry of padding at the end of the hashtable array. This now passes the quickcheck tests added previously.

FastSet carries a quite nice performance improvement in microbenchmarks,

benchmarking sets/Fast
time                 8.046 ns   (8.011 ns .. 8.115 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 8.076 ns   (8.042 ns .. 8.130 ns)
std dev              135.4 ps   (98.67 ps .. 193.0 ps)
variance introduced by outliers: 24% (moderately inflated)

benchmarking sets/Hash
time                 15.18 ns   (15.13 ns .. 15.24 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 15.15 ns   (15.13 ns .. 15.19 ns)
std dev              94.77 ps   (62.22 ps .. 155.6 ps)

benchmarking sets/Int
time                 14.11 ns   (14.03 ns .. 14.22 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 14.22 ns   (14.16 ns .. 14.28 ns)
std dev              210.7 ps   (184.2 ps .. 250.6 ps)
variance introduced by outliers: 19% (moderately inflated)

benchmarking sets/TextFast
time                 8.532 ns   (8.482 ns .. 8.572 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 8.485 ns   (8.461 ns .. 8.520 ns)
std dev              101.8 ps   (81.45 ps .. 161.0 ps)
variance introduced by outliers: 14% (moderately inflated)

Fixes #103.

bgamari commented 8 years ago

This also moves the tests to tasty, which I found helpful due to test-framework brokenness I encountered while tracking this down.