<div dir="ltr"><br><br><div class="gmail_quote">On Thu, Sep 20, 2012 at 7:25 PM, Gregory Collins <span dir="ltr"><<a href="mailto:greg@gregorycollins.net" target="_blank">greg@gregorycollins.net</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hey Michael,<div><br></div><div>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: <a href="https://gist.github.com/3756876" target="_blank">https://gist.github.com/3756876</a></div>
<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div>master /home/gdc/tmp/haskell/chr/gist-3756876 ⚠ $ ./bench </div></div><div><div>warming up</div></div><div><div>estimating clock resolution...</div>
</div><div><div>mean is 1.290661 us (640001 iterations)</div></div><div><div>found 2935 outliers among 639999 samples (0.5%)</div></div><div><div> 2541 (0.4%) high severe</div></div><div><div>estimating cost of a clock call...</div>
</div><div><div>mean is 31.63774 ns (13 iterations)</div></div><div><div>found 2 outliers among 13 samples (15.4%)</div></div><div><div> 2 (15.4%) high mild</div></div><div><div><br></div></div><div><div>benchmarking Char8</div>
</div><div><div>mean: 145.1935 us, lb 141.4375 us, ub 149.8138 us, ci 0.950</div></div><div><div>std dev: 21.28567 us, lb 18.14038 us, ub 23.87625 us, ci 0.950</div></div><div><div>found 22 outliers among 100 samples (22.0%)</div>
</div><div><div> 22 (22.0%) high severe</div></div><div><div>variance introduced by outliers: 89.411%</div></div><div class="im"><div><div>variance is severely inflated by outliers</div></div><div><div><br></div></div><div>
<div>benchmarking Char8 toLowerC</div>
</div></div><div><div>mean: 12.74308 us, lb 12.24657 us, ub 13.31365 us, ci 0.950</div></div><div><div>std dev: 2.712828 us, lb 2.434402 us, ub 2.904232 us, ci 0.950</div></div><div><div>variance introduced by outliers: 94.689%</div>
</div><div class="im"><div><div>variance is severely inflated by outliers</div></div><div><div><br></div></div></div><div><div>benchmarking bsToLower</div></div><div><div>mean: 20.68829 us, lb 20.66869 us, ub 20.70941 us, ci 0.950</div>
</div><div>
<div>std dev: 104.5939 ns, lb 95.37577 ns, ub 120.6401 ns, ci 0.950</div></div></blockquote><div><br></div><div>G.</div><div><div><div class="h5"><br><div class="gmail_quote">On Thu, Sep 20, 2012 at 5:01 PM, Michael Snoyman <span dir="ltr"><<a href="mailto:michael@snoyman.com" target="_blank">michael@snoyman.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Well... let's test it out:<br>
<br>
benchmarking Char8<br>
mean: 333.0050 us, lb 329.2846 us, ub 336.2362 us, ci 0.950<br>
std dev: 17.73400 us, lb 15.69876 us, ub 19.45947 us, ci 0.950<br>
variance introduced by outliers: 51.452%<br>
variance is severely inflated by outliers<br>
<br>
benchmarking Char8 toLowerC<br>
mean: 117.1571 us, lb 116.8739 us, ub 117.4219 us, ci 0.950<br>
std dev: 1.394150 us, lb 1.189928 us, ub 1.649276 us, ci 0.950<br>
<br>
benchmarking Word8<br>
mean: 41.01667 us, lb 40.94708 us, ub 41.09468 us, ci 0.950<br>
std dev: 378.4175 ns, lb 335.4655 ns, ub 462.6281 ns, ci 0.950<br>
<br>
benchmarking bsToLower<br>
mean: 37.37589 us, lb 37.24453 us, ub 37.48697 us, ci 0.950<br>
std dev: 616.5653 ns, lb 513.7510 ns, ub 752.8996 ns, ci 0.950<br>
<div>found 9 outliers among 100 samples (9.0%)<br>
</div> 3 (3.0%) low severe<br>
4 (4.0%) low mild<br>
2 (2.0%) high mild<br>
variance introduced by outliers: 9.426%<br>
variance is slightly inflated by outliers<br>
<br>
So a specialized `Char -> Char` function helps, but doesn't completely<br>
close the performance gap. (Updates at the same gist[1].)<br>
<br>
I disagree with a problem with an extra package: this is such a<br>
low-level detail that average users don't need to really be aware of<br>
the existence of the package, and I think the marginal increase in<br>
compile times shouldn't cause any issues. I used to worry much more<br>
about adding extra packages to the mix, but with the more recent<br>
versions of cabal-install and the community's general improvement in<br>
handling dependency hell, I see less of a reason to do so.<br>
<br>
That said, I think having specialized toLower/toUpper in a central<br>
place- perhaps even bytestring itself- would be a good thing.<br>
<br>
Michael<br>
<br>
[1] <a href="https://gist.github.com/3756212" target="_blank">https://gist.github.com/3756212</a><br>
<div><div><br>
On Thu, Sep 20, 2012 at 5:47 PM, Gregory Collins<br>
<<a href="mailto:greg@gregorycollins.net" target="_blank">greg@gregorycollins.net</a>> wrote:<br>
> This is, of course, not an apples-to-apples test:<br>
><br>
> Prelude Data.Char> toUpper 'χ'<br>
> '\935'<br>
> Prelude Data.Char> putStrLn ('\935':[])<br>
> Χ<br>
><br>
><br>
> ...which I suppose is the point. I wonder whether a version of<br>
> toUpper/toLower on Char restricted to ASCII values would have the same<br>
> performance here.<br>
><br>
> We only call toLower explicitly in one place in snap-server, but where this<br>
> would be nice to fix is for HTTP headers, where I think we are all using<br>
> case-insensitive (which just calls "map toLower"). Probably we should send<br>
> Bas a patch to optimize the FoldCase instance for ByteString.<br>
><br>
> Personally I would prefer not to have yet another tiny package here, as the<br>
> package zoo has enough creatures in it as it is. Do we think we have a real<br>
> problem here beyond the toUpper/toLower case? I suspect that for most other<br>
> uses of Data.ByteString.Char8 the conversion is a no-op.<br>
><br>
> G<br>
><br>
> On Thu, Sep 20, 2012 at 4:17 PM, Michael Snoyman <<a href="mailto:michael@snoyman.com" target="_blank">michael@snoyman.com</a>><br>
> wrote:<br>
>><br>
>> On Thu, Sep 20, 2012 at 2:10 PM, Michael Snoyman <<a href="mailto:michael@snoyman.com" target="_blank">michael@snoyman.com</a>><br>
>> wrote:<br>
>> > On Thu, Sep 20, 2012 at 11:41 AM, Kazu Yamamoto <<a href="mailto:kazu@iij.ad.jp" target="_blank">kazu@iij.ad.jp</a>> wrote:<br>
>> >> Hello,<br>
>> >><br>
>> >> ByteString is an array of Word8 but it seems to me that people tend to<br>
>> >> use the Char interface with Data.ByteString.Char8 instead of Word8<br>
>> >> interface with Data.ByteString. Since the functions defined in<br>
>> >> Data.ByteString.Char8 converts Word8 to Char and Char to Word8, it has<br>
>> >> unnecessary overhead. Yes, the overhead is ignorable in many cases,<br>
>> >> but I would like to remove it for high performance server.<br>
>> >><br>
>> >> Why do people use Data.ByteString.Char8? I guess that there are two<br>
>> >> reasons:<br>
>> >><br>
>> >> - There are no standard utility functions for Word8 such as "isUpper"<br>
>> >> - Numeric literal (e.g 72 for 'H') is not readable<br>
>> >><br>
>> >> To fix these problems, I implemented the Data.Word8 module and<br>
>> >> uploaded the word8 library to Hackage:<br>
>> >><br>
>> >><br>
>> >> <a href="http://hackage.haskell.org/packages/archive/word8/0.0.0/doc/html/Data-Word8.html" target="_blank">http://hackage.haskell.org/packages/archive/word8/0.0.0/doc/html/Data-Word8.html</a><br>
>> >><br>
>> >> If Michael and Bas like this, I would like to modify warp and<br>
>> >> case-insensitive to use the word8 library. What do people think this?<br>
>> >><br>
>> >> My concern is that character names start with "_". Some people would<br>
>> >> dislike this convention. But I have not a better idea at this moment.<br>
>> >> Suggestions are welcome.<br>
>> >><br>
>> >> --Kazu<br>
>> >><br>
>> >> _______________________________________________<br>
>> >> web-devel mailing list<br>
>> >> <a href="mailto:web-devel@haskell.org" target="_blank">web-devel@haskell.org</a><br>
>> >> <a href="http://www.haskell.org/mailman/listinfo/web-devel" target="_blank">http://www.haskell.org/mailman/listinfo/web-devel</a><br>
>> ><br>
>> > Sounds good to me. I put together a simple benchmark to compare the<br>
>> > performance of toLower, and the results are encouraging:<br>
>> ><br>
>> > benchmarking Char8<br>
>> > mean: 38.04527 us, lb 37.94080 us, ub 38.12774 us, ci 0.950<br>
>> > std dev: 470.9770 ns, lb 364.8254 ns, ub 748.3015 ns, ci 0.950<br>
>> ><br>
>> > benchmarking Word8<br>
>> > mean: 4.807265 us, lb 4.798199 us, ub 4.816563 us, ci 0.950<br>
>> > std dev: 47.20958 ns, lb 41.51181 ns, ub 55.07049 ns, ci 0.950<br>
>> ><br>
>> > I want to try throwing one more idea into the mix, I'll post with<br>
>> > updates when I have them.<br>
>> ><br>
>> > So to answer your question: I'd be happy to include word8 in warp :).<br>
>> ><br>
>> > Michael<br>
>> ><br>
>> ><br>
>> > {-# LANGUAGE OverloadedStrings #-}<br>
>> > import Criterion.Main<br>
>> > import qualified Data.ByteString as S<br>
>> > import qualified Data.ByteString.Char8 as S8<br>
>> > import qualified Data.Char<br>
>> > import qualified Data.Word8<br>
>> ><br>
>> > main :: IO ()<br>
>> > main = do<br>
>> > input <- S.readFile "bench.hs"<br>
>> > defaultMain<br>
>> > [ bench "Char8" $ whnf (S.length . S8.map Data.Char.toLower)<br>
>> > input<br>
>> > , bench "Word8" $ whnf (S.length . S.map Data.Word8.toLower)<br>
>> > input<br>
>> > ]<br>
>><br>
>> I tried implementing a more low-level approach to try and avoid the<br>
>> Word8 boxing. The results improved a bit, but not significantly:<br>
>><br>
>><br>
>> benchmarking Char8<br>
>> mean: 318.2341 us, lb 314.5367 us, ub 320.4834 us, ci 0.950<br>
>> std dev: 14.48230 us, lb 10.00946 us, ub 21.22126 us, ci 0.950<br>
>> found 9 outliers among 100 samples (9.0%)<br>
>> 8 (8.0%) low severe<br>
>> variance introduced by outliers: 43.472%<br>
>> variance is moderately inflated by outliers<br>
>><br>
>> benchmarking Word8<br>
>> mean: 35.79037 us, lb 35.66547 us, ub 35.92601 us, ci 0.950<br>
>> std dev: 665.5299 ns, lb 599.3413 ns, ub 741.6474 ns, ci 0.950<br>
>> variance introduced by outliers: 11.349%<br>
>> variance is moderately inflated by outliers<br>
>><br>
>> benchmarking bsToLower<br>
>> mean: 31.49299 us, lb 31.32314 us, ub 31.65027 us, ci 0.950<br>
>> std dev: 835.2251 ns, lb 744.4337 ns, ub 946.1789 ns, ci 0.950<br>
>> variance introduced by outliers: 20.925%<br>
>> variance is moderately inflated by outliers<br>
>><br>
>> Perhaps someone with more experience with this level of optimization<br>
>> would be able to improve the algorithm:<br>
>><br>
>> <a href="https://gist.github.com/3756212" target="_blank">https://gist.github.com/3756212</a><br>
>><br>
>> Michael<br>
>><br>
>> _______________________________________________<br>
>> web-devel mailing list<br>
>> <a href="mailto:web-devel@haskell.org" target="_blank">web-devel@haskell.org</a><br>
>> <a href="http://www.haskell.org/mailman/listinfo/web-devel" target="_blank">http://www.haskell.org/mailman/listinfo/web-devel</a><br>
><br>
><br>
><br>
><br>
> --<br>
> Gregory Collins <<a href="mailto:greg@gregorycollins.net" target="_blank">greg@gregorycollins.net</a>><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br>Gregory Collins <<a href="mailto:greg@gregorycollins.net" target="_blank">greg@gregorycollins.net</a>></font></span></div>
</blockquote></div><div><br></div>Hmm... I don't get your results.<div><br></div><div><div>benchmarking Char8</div><div>mean: 394.2475 us, lb 393.1611 us, ub 395.3824 us, ci 0.950</div><div>std dev: 5.674103 us, lb 4.574321 us, ub 7.548278 us, ci 0.950</div>
<div>found 16 outliers among 100 samples (16.0%)</div><div> 1 (1.0%) low severe</div><div> 4 (4.0%) low mild</div><div> 6 (6.0%) high mild</div><div> 5 (5.0%) high severe</div><div>variance introduced by outliers: 7.517%</div>
<div>variance is slightly inflated by outliers</div><div><br></div><div>benchmarking Char8 toLowerC</div><div>mean: 81.19748 us, lb 80.95403 us, ub 81.40814 us, ci 0.950</div><div>std dev: 1.154865 us, lb 977.5925 ns, ub 1.497224 us, ci 0.950</div>
<div>found 2 outliers among 100 samples (2.0%)</div><div> 1 (1.0%) low severe</div><div>variance introduced by outliers: 7.506%</div><div>variance is slightly inflated by outliers</div><div><br></div><div>benchmarking Word8</div>
<div>mean: 43.01692 us, lb 42.94030 us, ub 43.09647 us, ci 0.950</div><div>std dev: 401.2451 ns, lb 362.3989 ns, ub 458.7243 ns, ci 0.950</div><div><br></div><div>benchmarking bsToLower</div><div>mean: 36.61481 us, lb 36.46137 us, ub 36.79378 us, ci 0.950</div>
<div>std dev: 850.7579 ns, lb 717.1316 ns, ub 1.004895 us, ci 0.950</div><div>found 16 outliers among 100 samples (16.0%)</div><div> 2 (2.0%) low mild</div><div> 10 (10.0%) high mild</div><div> 4 (4.0%) high severe</div>
<div>variance introduced by outliers: 17.062%</div><div>variance is moderately inflated by outliers</div></div><div><br></div><div>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?</div>
<div><br></div><div>Michael</div></div>