Re: [boost] [xpressive] Performance Tuning?

Subject: Re: [boost] [xpressive] Performance Tuning?
From: Joel de Guzman (joel_at_[hidden])
Date: 2009-07-19 06:03:51

OvermindDL1 wrote:

> I just changed the file to use spirit for parsing where I had used
> lexical_cast got very different timings for xpressive now, so now,
> with xpressive using a bit of spirit I get:
> Loop count:  10000000
> Parsing:  42.5
> xpressive:  15.4841
> spirit-quick(static):  3.01117
> spirit-quick_new(threadsafe):  3.10548
> spirit-grammar(threadsafe/reusable):  3.81694
> 
> Vast increase, 3x faster xpressive is now.
> Also, how do you fix that rather bloody massive warning about
> double->int64 truncation?
> I also changed all int64_t to boost::long_long_type since they are the
> same thing anyway (on 32-bit at least?), as well as it being
> multi-platform unlike int64_t.
> My changed file is attached.  Do not know if this is considered
> cheating now that xpressive is using some spirit now.  ;-)

This is somewhat cheating. We've tuned the numeric parsers of Spirit
with TMP tricks, loop unrolling, etc. Those are very finely tuned
numeric parsers you see there that beats the fastest C code such as
strtol and atoi. The following benchmarks reveal 2X+ speed against
low level strtol and atoi (attached). I am getting:

   atoi: 0.82528 [s]
   strtol: 0.792227 [s]
   int_: 0.358016 [s]

The first and second are the low-level C routines. The third is
Spirit's int_ parser. I need not mention that the C routines only
accept C strings while the Spirit int_ parser can accept any
forward iterator. So, in a sense, we're comparing apples and
oranges. But this goes to show that you can write highly optimized
code in generic C++.

Regards,
-- 
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net

/*=============================================================================
    Copyright (c) 2001-2009 Joel de Guzman

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#if defined(BOOST_MSVC)
#pragma inline_depth(255)
#pragma inline_recursion(on)
#define _SECURE_SCL 0 
#endif // defined(BOOST_MSVC)

#include "../high_resolution_timer.hpp"
#include <boost/spirit/include/qi.hpp>
#include <boost/lexical_cast.hpp>
#include <climits>
#include <cstdlib>
#include <string>
#include <vector>

#define MAX_ITERATION 10000000

void check(int a, int b)
{
    if (a != b)
    {
        std::cout << "Parse Error" << std::endl;
        abort();
    }
}

int main()
{
    namespace qi = boost::spirit::qi;
    using qi::int_;
    
    std::cout << "initializing input strings..." << std::endl;
    std::vector<int> src(MAX_ITERATION);
    std::vector<std::string> src_str(MAX_ITERATION);
    for (int i = 0; i < MAX_ITERATION; ++i)
    {
        src[i] = std::rand() * std::rand();
        src_str[i] = boost::lexical_cast<std::string>(src[i]);
    }
    
    std::vector<int> v(MAX_ITERATION);

    // test the C libraries atoi function (the most low level function for
    // string conversion available)
    {
        util::high_resolution_timer t;

        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            v[i] = atoi(src_str[i].c_str());
        }

        std::cout << "atoi: " << t.elapsed() << " [s]" << std::flush << std::endl;
        
        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            check(v[i], src[i]);
        }
    }
    
    // test the C libraries strtol function (the most low level function for
    // string conversion available)
    {
        util::high_resolution_timer t;

        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            v[i] = strtol(src_str[i].c_str(), 0, 10);
        }

        std::cout << "strtol: " << t.elapsed() << " [s]" << std::flush << std::endl;
        
        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            check(v[i], src[i]);
        }
    }
    
    // test the Qi int_ parser routines 
    {
        std::vector<char const*> f(MAX_ITERATION);
        std::vector<char const*> l(MAX_ITERATION);

        // get the first/last iterators
        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            f[i] = src_str[i].c_str();
            l[i] = f[i];
            while (*l[i])
                l[i]++;
        }
    
        util::high_resolution_timer t;

        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            qi::parse(f[i], l[i], int_, v[i]);
        }

        std::cout << "int_: " << t.elapsed() << " [s]" << std::flush << std::endl;
        
        for (int i = 0; i < MAX_ITERATION; ++i)
        {
            check(v[i], src[i]);
        }
    }

    return 0;
}