Re: [boost] [xpressive] Performance Tuning?

Subject: Re: [boost] [xpressive] Performance Tuning?
From: Stewart, Robert (Robert.Stewart_at_[hidden])
Date: 2009-07-01 09:13:27

Eric Niebler wrote:
> Stewart, Robert wrote:
> > I was experimenting with Xpressive to see how it would
> > compare with some custom, string-based numeric input parsing.
> > The Xpressive code is over 175X slower than the custom code.
> > Have I done anything to make it really slow?  Can it be made
> > faster?
> <snip>
>
> Where is the code against which you are benchmarking?

See below.  As you'll see, it isn't nearly as maintainable or clear, but the wide performance difference certainly favors it.

>  From looking at the code, I can see a few areas for
> improvement. With each call to parse(), you construct and
> discard a match_results object. For optimal performance, you
> should reuse the match_results object to avoid extra memory
> allocation. Also, many of the quantifiers in your grammar do
> not require backtracking, so you could use keep() to turn
> backtracking off selectively.

The function is called in a one-off fashion that wouldn't permit keeping the match_results object, unfortunately.  (A function local static would suffice but then the function wouldn't be thread safe.)

I'm not certain I understand where to apply keep(), but I'll have a go at it.

_______________________
FYI: bar::to_number() calls strtod(), strtol(), etc.

template <class T>
T
foo::extract(char const * & _input, char const * const _description,
   std::string const & _value)
{
   T result;
   if (!bar::to_number(result, _input, &_input, 10))
   {
      raise_extract_failed(_description, _value);
   }
   return result;
}

inline int64_t
foo::round(const double _value)
{
   return static_cast<int64_t>(std::floor(_value + 0.5));
}

int64_t
foo::parse(std::string const & _value)
{
   if (_value.empty())
   {
      return 0;
   }
   size_t offset(_value.find_first_not_of("-+0123456789eE ./"));
   const bool invalid(std::string::npos != offset);
   if (invalid)
   {
      raise_parsing_failed(_value);
   }
   const char * const input(_value.c_str());
   const char * const last(input + _value.length());
   const char * end(input);
   int64_t result;
   (void)bar::to_number(result, end, &end, 10);
   const bool floating_point('.' == *end);
   if (floating_point)
   {
      end = input;
      const double value(extract<double>(end, "input", _value));
      const bool negative(0.0 > value);
      double multiple(value * 160000.0);
      if (negative)
      {
         multiple = -multiple;
      }
      result = round(multiple);
      if (negative)
      {
         result = -result;
      }
   }
   else // not floating point
   {
      result *= 160000;
      if (end != last)
      {
         offset = _value.find_first_of('/', end - input);
         const bool is_fraction(std::string::npos != offset);
         if (is_fraction)
         {
            const bool negative(0 > result);
            if (negative)
            {
               result = -result;
            }
            offset = _value.find_last_of(' ', offset);
            const bool is_mixed_number(std::string::npos != offset);
            if (is_mixed_number)
            {
               const unsigned numerator(
                  extract<unsigned>(end, "numerator", _value));
               end += 1; // skip the slash
               const unsigned denominator(
                  extract<unsigned>(end, "denominator", _value));
               const double fraction((160000.0 * numerator) / denominator);
               result = round(result + fraction);
            }
            else
            {
               end += 1; // skip the slash
               const unsigned denominator(
                  extract<unsigned>(end, "denominator", _value));
               const double fraction(result / denominator);
               result = round(fraction);
            }
            if (negative)
            {
               result = -result;
            }
         }
      }
   }
   return result;
}

_____
Rob Stewart                           robert.stewart_at_[hidden]
Software Engineer, Core Software      using std::disclaimer;
Susquehanna International Group, LLP  http://www.sig.com

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.