[web-devel] Data.Word8 (word8 library)
Gregory Collins
greg at gregorycollins.net
Thu Sep 20 22:55:17 CEST 2012
Hey all,
Chatted with Michael a bit and we have an explanation for why his results
were different than mine -- he was using the generated functions twice
(once in the hspec test and once in the benchmark), and without an INLINE
pragma GHC decided not to inline the code. My version deleted the hspec
stuff so GHC decided to inline.
So mystery solved there, Michael's results now correspond to what I was
getting: "Data.ByteString.Char8.map toLowerC" is about 3x faster on my
machine than "Data.ByteString.map Data.Word8.toLower". The word8 functions
don't have INLINE pragmas; adding those reduces the difference:
benchmarking Char8 toLowerC
mean: 7.322917 ms, lb 7.292270 ms, ub 7.359051 ms, ci 0.950
std dev: 170.4600 us, lb 145.3292 us, ub 207.6649 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
4 (4.0%) high mild
variance introduced by outliers: 17.066%
variance is moderately inflated by outliers
benchmarking Word8
mean: 12.70621 ms, lb 12.67685 ms, ub 12.73488 ms, ci 0.950
std dev: 148.3391 us, lb 132.9021 us, ub 166.2910 us, ci 0.950
...but mapping the function from word8 over our input is still 2x slower. I
rewrote the version from word8 to be nearly identical to the version from
the gist, and the difference persists. That's a very weird result indeed --
which piqued my curiosity, so I looked at the generated assembly output.
The word8 version is spilling a bunch of stuff to the stack, e.g. the
following basic block:
Lc2Dr:
movl $192,%eax
cmpq 24(%rbp),%rax
jbe Lc2Dw
movl $216,%eax
cmpq 24(%rbp),%rax
jbe Lc2DR
movq 24(%rbp),%rdx
movq 16(%rbp),%rax
movq 48(%rbp),%rcx
movb %dl,(%rax,%rcx,1)
movq 8(%rbp),%rbx
movq 32(%rbp),%r14
movq 40(%rbp),%rsi
movq 16(%rbp),%rdi
addq $56,%rbp
jmp _s2wd_info
while the equivalent version using Char is all in registers:
Lc2Ga:
cmpq 4(%rbx),%r14
jge Lc2Gf
movzbl (%rsi,%r14,1),%eax
movl $65,%ecx
cmpq %rax,%rcx
jbe Lc2Gq
movl $192,%ecx
cmpq %rax,%rcx
jbe Lc2H6
movl $216,%ecx
cmpq %rax,%rcx
jbe Lc2Hr
movb %al,(%rdi,%r14,1)
incq %r14
jmp _s2xW_info
I find this to be a very surprising result indeed. These functions should
be absolutely identical in every way. Even moving the functions from
Data.Word8 directly into the benchmark module doesn't help here. Gist
updated (https://gist.github.com/3756876)
Ignoring this, I think I can summarize:
- Data.ByteString.Char8 has no performance penalty: "w2c" uses
"unsafeChr" which is a no-op, and GHC.Word has a RULES pragma making the
"fromIntegral" also free (it's a narrow8Word#)
- for some reason GHC is generating worse code for the Word8 versions of
toLower than it is for the Char equivalents
- consequently, there seems to be no reason to use the word8 library:
not only is it not faster, it's actually a pessimization.
G
On Thu, Sep 20, 2012 at 9:16 PM, Gregory Collins <greg at gregorycollins.net>wrote:
> Updated my gist and looped the benchmark to run 1000 times to reduce
> variance caused by measurement error. My work machine is a 6-core Westmere,
> but I'm home now and ran the benchmark on my quad-core i7 Macbook Pro (GHC
> 7.4.1, -O2, 64-bit), I get the same results:
>
> master /Users/greg/tmp/haskell/gist-3756876 [*] $ ./bench
> warming up
> estimating clock resolution...
> mean is 1.300787 us (640001 iterations)
> found 4606 outliers among 639999 samples (0.7%)
> 3708 (0.6%) high severe
> estimating cost of a clock call...
> mean is 57.02712 ns (8 iterations)
> found 1 outliers among 8 samples (12.5%)
> 1 (12.5%) high severe
>
> benchmarking Char8
> collecting 100 samples, 1 iterations each, in estimated 19.08500 s
> mean: 190.8388 ms, lb 190.7002 ms, ub 190.9720 ms, ci 0.950
> std dev: 695.8268 us, lb 597.0216 us, ub 840.2860 us, ci 0.950
>
> benchmarking Char8 toLowerC
> mean: 7.421057 ms, lb 7.398322 ms, ub 7.444365 ms, ci 0.950
> std dev: 117.5378 us, lb 100.6587 us, ub 139.2367 us, ci 0.950
> found 9 outliers among 100 samples (9.0%)
> 4 (4.0%) low mild
> 5 (5.0%) high mild
> variance introduced by outliers: 8.495%
> variance is slightly inflated by outliers
>
> benchmarking bsToLower
> mean: 15.43166 ms, lb 15.39326 ms, ub 15.47557 ms, ci 0.950
> std dev: 210.4574 us, lb 178.0131 us, ub 256.2110 us, ci 0.950
> found 4 outliers among 100 samples (4.0%)
> 4 (4.0%) high mild
> variance introduced by outliers: 6.588%
> variance is slightly inflated by outliers
>
> benchmarking Word8
> mean: 21.76645 ms, lb 21.72059 ms, ub 21.82300 ms, ci 0.950
> std dev: 259.4630 us, lb 209.6453 us, ub 374.8074 us, ci 0.950
>
>
> G
>
> On Thu, Sep 20, 2012 at 6:58 PM, Michael Snoyman <michael at snoyman.com>wrote:
>
>>
>>
>> On Thu, Sep 20, 2012 at 7:25 PM, Gregory Collins <greg at gregorycollins.net
>> > wrote:
>>
>>> Hey Michael,
>>>
>>> BTW -- you're getting crap performance here because of the
>>> fromEnum/toEnum in toLowerC, which does checks. An updated version using
>>> unsafeChr is faster than your bsToLower call:
>>> https://gist.github.com/3756876
>>>
>>> master /home/gdc/tmp/haskell/chr/gist-3756876 ⚠ $ ./bench
>>> warming up
>>> estimating clock resolution...
>>> mean is 1.290661 us (640001 iterations)
>>> found 2935 outliers among 639999 samples (0.5%)
>>> 2541 (0.4%) high severe
>>> estimating cost of a clock call...
>>> mean is 31.63774 ns (13 iterations)
>>> found 2 outliers among 13 samples (15.4%)
>>> 2 (15.4%) high mild
>>>
>>> benchmarking Char8
>>> mean: 145.1935 us, lb 141.4375 us, ub 149.8138 us, ci 0.950
>>> std dev: 21.28567 us, lb 18.14038 us, ub 23.87625 us, ci 0.950
>>> found 22 outliers among 100 samples (22.0%)
>>> 22 (22.0%) high severe
>>> variance introduced by outliers: 89.411%
>>> variance is severely inflated by outliers
>>>
>>> benchmarking Char8 toLowerC
>>> mean: 12.74308 us, lb 12.24657 us, ub 13.31365 us, ci 0.950
>>> std dev: 2.712828 us, lb 2.434402 us, ub 2.904232 us, ci 0.950
>>> variance introduced by outliers: 94.689%
>>> variance is severely inflated by outliers
>>>
>>> benchmarking bsToLower
>>> mean: 20.68829 us, lb 20.66869 us, ub 20.70941 us, ci 0.950
>>> std dev: 104.5939 ns, lb 95.37577 ns, ub 120.6401 ns, ci 0.950
>>>
>>>
>>> G.
>>>
>>> On Thu, Sep 20, 2012 at 5:01 PM, Michael Snoyman <michael at snoyman.com>wrote:
>>>
>>>> Well... let's test it out:
>>>>
>>>> benchmarking Char8
>>>> mean: 333.0050 us, lb 329.2846 us, ub 336.2362 us, ci 0.950
>>>> std dev: 17.73400 us, lb 15.69876 us, ub 19.45947 us, ci 0.950
>>>> variance introduced by outliers: 51.452%
>>>> variance is severely inflated by outliers
>>>>
>>>> benchmarking Char8 toLowerC
>>>> mean: 117.1571 us, lb 116.8739 us, ub 117.4219 us, ci 0.950
>>>> std dev: 1.394150 us, lb 1.189928 us, ub 1.649276 us, ci 0.950
>>>>
>>>> benchmarking Word8
>>>> mean: 41.01667 us, lb 40.94708 us, ub 41.09468 us, ci 0.950
>>>> std dev: 378.4175 ns, lb 335.4655 ns, ub 462.6281 ns, ci 0.950
>>>>
>>>> benchmarking bsToLower
>>>> mean: 37.37589 us, lb 37.24453 us, ub 37.48697 us, ci 0.950
>>>> std dev: 616.5653 ns, lb 513.7510 ns, ub 752.8996 ns, ci 0.950
>>>> found 9 outliers among 100 samples (9.0%)
>>>> 3 (3.0%) low severe
>>>> 4 (4.0%) low mild
>>>> 2 (2.0%) high mild
>>>> variance introduced by outliers: 9.426%
>>>> variance is slightly inflated by outliers
>>>>
>>>> So a specialized `Char -> Char` function helps, but doesn't completely
>>>> close the performance gap. (Updates at the same gist[1].)
>>>>
>>>> I disagree with a problem with an extra package: this is such a
>>>> low-level detail that average users don't need to really be aware of
>>>> the existence of the package, and I think the marginal increase in
>>>> compile times shouldn't cause any issues. I used to worry much more
>>>> about adding extra packages to the mix, but with the more recent
>>>> versions of cabal-install and the community's general improvement in
>>>> handling dependency hell, I see less of a reason to do so.
>>>>
>>>> That said, I think having specialized toLower/toUpper in a central
>>>> place- perhaps even bytestring itself- would be a good thing.
>>>>
>>>> Michael
>>>>
>>>> [1] https://gist.github.com/3756212
>>>>
>>>> On Thu, Sep 20, 2012 at 5:47 PM, Gregory Collins
>>>> <greg at gregorycollins.net> wrote:
>>>> > This is, of course, not an apples-to-apples test:
>>>> >
>>>> > Prelude Data.Char> toUpper 'χ'
>>>> > '\935'
>>>> > Prelude Data.Char> putStrLn ('\935':[])
>>>> > Χ
>>>> >
>>>> >
>>>> > ...which I suppose is the point. I wonder whether a version of
>>>> > toUpper/toLower on Char restricted to ASCII values would have the same
>>>> > performance here.
>>>> >
>>>> > We only call toLower explicitly in one place in snap-server, but
>>>> where this
>>>> > would be nice to fix is for HTTP headers, where I think we are all
>>>> using
>>>> > case-insensitive (which just calls "map toLower"). Probably we should
>>>> send
>>>> > Bas a patch to optimize the FoldCase instance for ByteString.
>>>> >
>>>> > Personally I would prefer not to have yet another tiny package here,
>>>> as the
>>>> > package zoo has enough creatures in it as it is. Do we think we have
>>>> a real
>>>> > problem here beyond the toUpper/toLower case? I suspect that for most
>>>> other
>>>> > uses of Data.ByteString.Char8 the conversion is a no-op.
>>>> >
>>>> > G
>>>> >
>>>> > On Thu, Sep 20, 2012 at 4:17 PM, Michael Snoyman <michael at snoyman.com
>>>> >
>>>> > wrote:
>>>> >>
>>>> >> On Thu, Sep 20, 2012 at 2:10 PM, Michael Snoyman <
>>>> michael at snoyman.com>
>>>> >> wrote:
>>>> >> > On Thu, Sep 20, 2012 at 11:41 AM, Kazu Yamamoto <kazu at iij.ad.jp>
>>>> wrote:
>>>> >> >> Hello,
>>>> >> >>
>>>> >> >> ByteString is an array of Word8 but it seems to me that people
>>>> tend to
>>>> >> >> use the Char interface with Data.ByteString.Char8 instead of Word8
>>>> >> >> interface with Data.ByteString. Since the functions defined in
>>>> >> >> Data.ByteString.Char8 converts Word8 to Char and Char to Word8,
>>>> it has
>>>> >> >> unnecessary overhead. Yes, the overhead is ignorable in many
>>>> cases,
>>>> >> >> but I would like to remove it for high performance server.
>>>> >> >>
>>>> >> >> Why do people use Data.ByteString.Char8? I guess that there are
>>>> two
>>>> >> >> reasons:
>>>> >> >>
>>>> >> >> - There are no standard utility functions for Word8 such as
>>>> "isUpper"
>>>> >> >> - Numeric literal (e.g 72 for 'H') is not readable
>>>> >> >>
>>>> >> >> To fix these problems, I implemented the Data.Word8 module and
>>>> >> >> uploaded the word8 library to Hackage:
>>>> >> >>
>>>> >> >>
>>>> >> >>
>>>> http://hackage.haskell.org/packages/archive/word8/0.0.0/doc/html/Data-Word8.html
>>>> >> >>
>>>> >> >> If Michael and Bas like this, I would like to modify warp and
>>>> >> >> case-insensitive to use the word8 library. What do people think
>>>> this?
>>>> >> >>
>>>> >> >> My concern is that character names start with "_". Some people
>>>> would
>>>> >> >> dislike this convention. But I have not a better idea at this
>>>> moment.
>>>> >> >> Suggestions are welcome.
>>>> >> >>
>>>> >> >> --Kazu
>>>> >> >>
>>>> >> >> _______________________________________________
>>>> >> >> web-devel mailing list
>>>> >> >> web-devel at haskell.org
>>>> >> >> http://www.haskell.org/mailman/listinfo/web-devel
>>>> >> >
>>>> >> > Sounds good to me. I put together a simple benchmark to compare the
>>>> >> > performance of toLower, and the results are encouraging:
>>>> >> >
>>>> >> > benchmarking Char8
>>>> >> > mean: 38.04527 us, lb 37.94080 us, ub 38.12774 us, ci 0.950
>>>> >> > std dev: 470.9770 ns, lb 364.8254 ns, ub 748.3015 ns, ci 0.950
>>>> >> >
>>>> >> > benchmarking Word8
>>>> >> > mean: 4.807265 us, lb 4.798199 us, ub 4.816563 us, ci 0.950
>>>> >> > std dev: 47.20958 ns, lb 41.51181 ns, ub 55.07049 ns, ci 0.950
>>>> >> >
>>>> >> > I want to try throwing one more idea into the mix, I'll post with
>>>> >> > updates when I have them.
>>>> >> >
>>>> >> > So to answer your question: I'd be happy to include word8 in warp
>>>> :).
>>>> >> >
>>>> >> > Michael
>>>> >> >
>>>> >> >
>>>> >> > {-# LANGUAGE OverloadedStrings #-}
>>>> >> > import Criterion.Main
>>>> >> > import qualified Data.ByteString as S
>>>> >> > import qualified Data.ByteString.Char8 as S8
>>>> >> > import qualified Data.Char
>>>> >> > import qualified Data.Word8
>>>> >> >
>>>> >> > main :: IO ()
>>>> >> > main = do
>>>> >> > input <- S.readFile "bench.hs"
>>>> >> > defaultMain
>>>> >> > [ bench "Char8" $ whnf (S.length . S8.map
>>>> Data.Char.toLower)
>>>> >> > input
>>>> >> > , bench "Word8" $ whnf (S.length . S.map
>>>> Data.Word8.toLower)
>>>> >> > input
>>>> >> > ]
>>>> >>
>>>> >> I tried implementing a more low-level approach to try and avoid the
>>>> >> Word8 boxing. The results improved a bit, but not significantly:
>>>> >>
>>>> >>
>>>> >> benchmarking Char8
>>>> >> mean: 318.2341 us, lb 314.5367 us, ub 320.4834 us, ci 0.950
>>>> >> std dev: 14.48230 us, lb 10.00946 us, ub 21.22126 us, ci 0.950
>>>> >> found 9 outliers among 100 samples (9.0%)
>>>> >> 8 (8.0%) low severe
>>>> >> variance introduced by outliers: 43.472%
>>>> >> variance is moderately inflated by outliers
>>>> >>
>>>> >> benchmarking Word8
>>>> >> mean: 35.79037 us, lb 35.66547 us, ub 35.92601 us, ci 0.950
>>>> >> std dev: 665.5299 ns, lb 599.3413 ns, ub 741.6474 ns, ci 0.950
>>>> >> variance introduced by outliers: 11.349%
>>>> >> variance is moderately inflated by outliers
>>>> >>
>>>> >> benchmarking bsToLower
>>>> >> mean: 31.49299 us, lb 31.32314 us, ub 31.65027 us, ci 0.950
>>>> >> std dev: 835.2251 ns, lb 744.4337 ns, ub 946.1789 ns, ci 0.950
>>>> >> variance introduced by outliers: 20.925%
>>>> >> variance is moderately inflated by outliers
>>>> >>
>>>> >> Perhaps someone with more experience with this level of optimization
>>>> >> would be able to improve the algorithm:
>>>> >>
>>>> >> https://gist.github.com/3756212
>>>> >>
>>>> >> Michael
>>>> >>
>>>> >> _______________________________________________
>>>> >> web-devel mailing list
>>>> >> web-devel at haskell.org
>>>> >> http://www.haskell.org/mailman/listinfo/web-devel
>>>> >
>>>> >
>>>> >
>>>> >
>>>> > --
>>>> > Gregory Collins <greg at gregorycollins.net>
>>>>
>>>
>>>
>>>
>>> --
>>> Gregory Collins <greg at gregorycollins.net>
>>>
>>
>> Hmm... I don't get your results.
>>
>> benchmarking Char8
>> mean: 394.2475 us, lb 393.1611 us, ub 395.3824 us, ci 0.950
>> std dev: 5.674103 us, lb 4.574321 us, ub 7.548278 us, ci 0.950
>> found 16 outliers among 100 samples (16.0%)
>> 1 (1.0%) low severe
>> 4 (4.0%) low mild
>> 6 (6.0%) high mild
>> 5 (5.0%) high severe
>> variance introduced by outliers: 7.517%
>> variance is slightly inflated by outliers
>>
>> benchmarking Char8 toLowerC
>> mean: 81.19748 us, lb 80.95403 us, ub 81.40814 us, ci 0.950
>> std dev: 1.154865 us, lb 977.5925 ns, ub 1.497224 us, ci 0.950
>> found 2 outliers among 100 samples (2.0%)
>> 1 (1.0%) low severe
>> variance introduced by outliers: 7.506%
>> variance is slightly inflated by outliers
>>
>> benchmarking Word8
>> mean: 43.01692 us, lb 42.94030 us, ub 43.09647 us, ci 0.950
>> std dev: 401.2451 ns, lb 362.3989 ns, ub 458.7243 ns, ci 0.950
>>
>> benchmarking bsToLower
>> mean: 36.61481 us, lb 36.46137 us, ub 36.79378 us, ci 0.950
>> std dev: 850.7579 ns, lb 717.1316 ns, ub 1.004895 us, ci 0.950
>> found 16 outliers among 100 samples (16.0%)
>> 2 (2.0%) low mild
>> 10 (10.0%) high mild
>> 4 (4.0%) high severe
>> variance introduced by outliers: 17.062%
>> variance is moderately inflated by outliers
>>
>> I'm compiling with -O2 and running on 7.4.1, 64-bit Linux. I'm uncertain
>> what would lead to such a significant difference in our runtimes. Any
>> chance you can include Word8 in your run?
>>
>> Michael
>>
>
>
>
> --
> Gregory Collins <greg at gregorycollins.net>
>
--
Gregory Collins <greg at gregorycollins.net>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/web-devel/attachments/20120920/74829680/attachment-0001.htm>
More information about the web-devel
mailing list