Monday, December 1, 2014

Improving Parser Performance using SSE Instructions (in case of PicoHTTPParser)

PicoHTTPParser is a tiny but very fast HTTP parser library known for its use by many Perl applications. In the slides I used last month, I suggested it could be even faster if SIMD instructions were used. Now the feature is available thanks to @herumi.

The library now uses the PCMPESTRI instruction which is part of SSE 4.2, running 68% to 90% faster.

Benchmarkclang -O3clang -O3 -msse4.2Improvement
bench.c2,181,0254,140,787+90%
fukamachi.c3,213,4405,400,064+68%

PCMPxSTRx is a SIMD instruction that can be used for parsing text. In _SIDD_CMP_RANGES mode, it checks at most 16 bytes at once, if each byte is within given set of ranges. Herumi and I have created a wrapper function for the instruction named findchar_fast that iterates though every 16 bytes of a given buffer to find the first occurrence of a byte within a set of given ranges.

And the function is merged neatly into the parser; the code below at first uses the SIMD function to look for a control character (the match condition is defined as ranges1), then falls back to the non-SIMD code to handling up to 15 remaining characters (that cannot be processed by the SIMD function due to out-of-bounds access).
#ifdef __SSE4_2__
  static const char ranges1[] =
    "\0\010"
    /* allow HT */
    "\012\037"
    /* allow SP and up to but not including DEL */
    "\177\177"
    /* allow chars w. MSB set */
    ;
  int found;
  buf = findchar_fast(buf, buf_end,
                      ranges1, sizeof(ranges1) - 1,
                      &found);
  if (found)
    goto FOUND_CTL;
#endif
  /* code that handles the input byte-by-byte */
To summarize, PCMPxSTRx is an excellent instruction for performance that can be cleanly integrated into existing parsers (tokenizers). Hopefully we will see performance improvements in various parsers in the future through the use of the instruction.

This blog post has been written as part of the H2O Advent Calendar.

38 comments:

  1. Nice. This looks as if it would also be very useful for serializers - a JSON string encoder probably passes through 99%+ of its input unchanged, but still needs to check for quotes, control characters etc.

    ReplyDelete
    Replies
    1. Sounds very interesting. Had never thought of that.

      Delete
  2. Intriguing — I tried to use the STR instructions once (PCMPISTRM, to be precise), but after benchmarking it turned out that a combination of PSHUFB/MOVA/PCMPEQB was actually faster. I didn't investigate deeply why that was (and I remember little about that code now), just used the faster combination.

    ReplyDelete
  3. Want to know regular updates of Euro Cup 2016???? Venue-France,From 10th june-10july.... 24 teams,10 stadiums... Stay updated..
    Euro Cup 2016
    Euro Cup live Streaming
    Euro Cup 2016 Live Streaming
    Euro Cup 2016 Live Score
    Euro Cup 2016 Schedule
    Euro Cup 2016 Fixture

    ReplyDelete
  4. Your blog was too good. i really appreciate with your

    ReplyDelete
  5. The blog or and best that is extremely useful to keep I can share the ideas
    of the future as this is really what I was looking for, I am very comfortable and pleased to come here. Thank you very much.
    wings io| earn to die 6
    earn to die 5| happy wheels
    |Red Ball | duck life

    ReplyDelete
  6. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, great share.
    dark souls 3 emoji
    slitherio diepio

    ReplyDelete
  7. Friendship Day Images 2016
    Find Happy Friendship Day 2016 HD Images, Quotes, SMS, Greetings and Songs. Also Pictures and Wishes for Best Friends. Best Wallpaper, Wishes and Pictures you can find.



    Raksha Bandhan 2016 Quotes
    Find Happy Raksha Bandhan Day 2016 Images, Quotes, Greetings and Songs. Also Pictures and Wishes for your Brother or Sister. Best Presents, Gifts Ideas and Quotes Poems.



    15 August Independence Day
    Happy Independence Day 15th of August 2016 images and pictures. Watch fireworks, events and celebrations Here

    ReplyDelete
  8. Best Friendship day
    Actually True Best Friendship day stands the test of time. Best Friendship day Celebrate Friendship Day 2016 on August 7, Sunday. You may be separated by physical boundaries and distances. However, when your best friend calls, you can transcend any physical or mental boundary.

    http://efriendshipday.com/

    http://efriendshipday.com/best-friendship-day-2016smspoems-and-picture/


    what is National Friendship Day means now!
    we look at National Friendship day, The first time I met Stoo, a cartoonist and author, he was entertaining a group of people at a cocktail party by drawing pictures of little men with huge erections. I was instantly besotted. The next time I saw him, six months later, he was hosting a gathering for our mutual friend Maria and when I walked through the front door, his face lit up like a candle; we hugged hello as if we'd known each other forever. Later that night he pulled me into his study to show me all the books and comic strips he'd published over the years. We were squished into a pair of old leather movie-theatre seats, balancing paper plates of crudités on our knees, when he blurted out, "Kate! I just adore you.

    ReplyDelete
  9. Sharp Corporation of leading international companies in the field of electronics, is a Japanese company founded in 1922, the company name is now become a symbol of confidence for everyone who is going to buy any electronic device
    One sharp products Sharpe adaptation, sharp was designed at the highest level of efficiency so you can endure hardship especially in hot climates where people need to keep your the accommodation in work mode, so it has sharp conditioner is designed to be able to work all day without stopping
    تكييف شارب العربي
    تكييف شارب العربي

    ReplyDelete
  10. I was very impressed by this post, this site has always been pleasant news. Thank you very much for such an interesting post. Keep working, great job! In my free time, I like play game: Banana Kong, Zombie Tsunami, Swords And Souls. What about you?

    ReplyDelete
  11. The blog or and best that is extremely useful to keep I can share the ideas of the future as this is really what I was looking for, I am very comfortable and pleased to come here. Thank you very much.
    animal jam | five nights at freddy's | hotmail login

    ReplyDelete
  12. First of all i am saying that i like your post very much.I am really impressed by the way in which you presented the content and also the structure of the post. Hope you can gave us more posts like this and i really appreciate your hardwork.

    Happy New Year 2018
    valentine week list
    valentine week list 2017
    happy birthday
    good morning

    ReplyDelete
  13. your information is really awesome as well as it is very excellent and i got more interesting information from your blog. Android App Development Company in Chennai

    ReplyDelete
  14. Love it love it but it's not everyone can choose the right people and treat yourself. So many girls being in love is still wondering who picked the right or wrong side of one person should not belong to her?
    baixar musicas l geometry dash l baixar snapchat l run 2 l b612 app l slither.io

    ReplyDelete
  15. This post is really nice and informative. The explanation given is really comprehensive and informative... Wifi Camera Chennai

    ReplyDelete