[xpressive] Performance Tuning?

[Stewart, Robert]

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?  I have included the Xpressive code and the performance testing code below for your study.  Can you spot anything I've done wrong?

(BTW, I tried using Spirit.Qi for this -- with Boost 1.37 -- but never could get things to compile.  I gave up and decided I'd wait until I can use a newer release before I fight that fight again. :-} )

FYI: bar::numeric_cast winds up calling strtod(), strtol(), etc.  It is semantically equivalent to lexical_cast.

#include <boost/xpressive/xpressive_static.hpp>
#include <boost/xpressive/regex_actions.hpp>

namespace foo
{
   namespace op
   {
      template <class T>
      struct numeric_cast
      {
         typedef T result_type;

         template <class Value>
         T
         operator ()(Value const & _value) const
         {
            return bar::numeric_cast<T>(_value);
         }
      };
   }

   struct direct_impl
   {
      typedef int64_t result_type;

      template <class Value>
      int64_t
      operator ()(Value const & _value) const
      {
         int64_t result(bar::numeric_cast<int64_t>(_value));
         result *= 160000;
         return result;
      }
   };

   struct to_price_impl
   {
      typedef int64_t result_type;

      template <class Value>
      int64_t
      operator ()(Value const & _value) const
      {
         int64_t result(0);
         if (_value)
         {
            double const value(bar::numeric_cast<double>(_value));
            result = static_cast<int64_t>(
               std::floor(160000.0 * value + 0.5));
         }
         return result;
      }

      template <class Value>
      int64_t
      operator ()(Value const & _numerator, Value const & _denominator) const
      {
         unsigned const numerator(bar::numeric_cast<unsigned>(_numerator));
         unsigned const denominator(bar::numeric_cast<unsigned>(_denominator));
         double const fraction((160000.0 * numerator) / denominator);
         return static_cast<int64_t>(std::floor(fraction + 0.5));
      }

      template <class Value>
      int64_t
      operator ()(Value const & _whole, double const _fraction) const
      {
         int const whole(bar::numeric_cast<int>(_whole));
         double const value(160000.0 * whole + _fraction);
         return static_cast<int64_t>(std::floor(value + 0.5));
      }
   };

   int64_t
   parse(std::string const & _value);

   boost::xpressive::function<direct_impl>::type const direct = {{}};
   boost::xpressive::function<to_price_impl>::type const to_price = {{}};
   BOOST_PROTO_DEFINE_FUNCTION_TEMPLATE(
      1
      , numeric_cast
      , boost::proto::default_domain
      , (boost::proto::tag::function)
      , ((op::numeric_cast)(typename))
      )
}

int64_t
foo::parse(std::string const & _value)
{
   using namespace boost::xpressive;

   if (_value.empty())
   {
      return 0;
   }
   int64_t result;
   bool negative(false);
   sregex zero = as_xpr('0');
   sregex sign =
      as_xpr('-')             [ ref(negative) = true ]
      | as_xpr('+');          // ignore
   // ignore leading zeroes to avoid octal parsing
   sregex fraction =
      (
         !zero >> (s1= +_d) >> !blank >> '/' >> !blank >> !zero >> (s2= +_d)
      )                       [ ref(result) = to_price(s1, s2) ];
   sregex real =
      (
         *_d >> '.' >> *_d >> !((set= 'E', 'e', 'G', 'g') >> +_d)
      )                       [ ref(result) = to_price(_) ];
   // ignore leading zeroes to avoid octal parsing
   sregex whole_number =
      (
         !zero >> (s1= +_d) >> +blank >> fraction
      )                       [ ref(result) = to_price(s1, ref(result)) ];
   // ignore leading zeroes to avoid octal parsing
   sregex integer =
      (
         !zero >> (s1= +_d)
      )                       [ ref(result) = direct(s1) ];
   sregex price =
      *blank
      >> !sign
      >> (real | whole_number | fraction | integer)
      >> *space;
   smatch match;
   if (!regex_match(_value.begin(), _value.end(), match, price))
   {
      throw price_parsing_failed(_value);
   }
   if (negative)
   {
      result = -result;
   }
   return result;
}

void
test_performance()
{
   Timer timer;
   std::string const input("1234.5678e10");
   int64_t total(0);
   foo::parse(input); // prime the cache
   timer.start();
   for (int i(0); i < 10000000; ++i)
   {
      int64_t price(foo::parse(input));
      price += i;
      total += price;
   }
   timer.stop();
   std::cout << timer.elapsed() << "s elapsed (total = " << total ')'
      << std::endl;
}

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Eric Niebler-3]

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?

 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.

That's all I have for now.

--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

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@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Dave Jenkins-3]

"Stewart, Robert" <Robert.Stewart@...> wrote in message
news:DF2E67F3D097004694C8428C70A3FD69046843E230@......
>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.

Each call to parse() is constructing the sregex variables.  If you make them
static or move them out of the loop, it should help a lot.

Regards,
Dave Jenkins


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Dave Jenkins wrote:

> "Stewart, Robert" <Robert.Stewart@...> wrote in message
> news:DF2E67F3D097004694C8428C70A3FD69046843E230@...
> usq.com...
> >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.
>
> Each call to parse() is constructing the sregex variables.
> If you make them
> static or move them out of the loop, it should help a lot.

Thanks, but see my reply to Eric's.  While that would help with the benchmark performance, the nature of the function I'm testing means I can't do that otherwise.

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Dave Jenkins-3]

>> Each call to parse() is constructing the sregex variables.
>> If you make them
>> static or move them out of the loop, it should help a lot.
>
> Thanks, but see my reply to Eric's.  While that would help with the
> benchmark performance, the nature of the function I'm testing means I
> can't do that otherwise.

How about making them static const?  That should be thread safe.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Dave Jenkins wrote:

>
> >> Each call to parse() is constructing the sregex variables.
> >> If you make them static or move them out of the loop, it
> >> should help a lot.
> >
> > Thanks, but see my reply to Eric's.  While that would help
> > with the benchmark performance, the nature of the function
> > I'm testing means I can't do that otherwise.
>
> How about making them static const?  That should be thread safe.

I'm sorry, I read your original suggestion as being the same as Eric's: reuse the match_results.  Unfortunately, the semantic actions reference local variables, so I don't think I can make the sregex's static (please correct me if I'm wrong, but I can't see how multiple parallel invocations of the function could reference separate stack variables from static sregex's).  I did make the sregex's const; that appears to have improved performance a bit.

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Eric Niebler-3]

Stewart, Robert wrote:

> Dave Jenkins 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.
>>
>> Each call to parse() is constructing the sregex variables. If you
>> make them static or move them out of the loop, it should help a
>> lot.
>
> Thanks, but see my reply to Eric's.  While that would help with the
> benchmark performance, the nature of the function I'm testing means I
> can't do that otherwise.

Really what you're saying is: "I can't/don't want to use xpressive in
the ways that are *documented* to make it perform well. Why is it slow?"
You already have your answer.

--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Eric Niebler-3]

Stewart, Robert wrote:

> Dave Jenkins wrote:
>>>> Each call to parse() is constructing the sregex variables.
>>>> If you make them static or move them out of the loop, it
>>>> should help a lot.
>>> Thanks, but see my reply to Eric's.  While that would help
>>> with the benchmark performance, the nature of the function
>>> I'm testing means I can't do that otherwise.
>> How about making them static const?  That should be thread safe.
>
> I'm sorry, I read your original suggestion as being the same as Eric's: reuse the match_results.  Unfortunately, the semantic actions reference local variables, so I don't think I can make the sregex's static (please correct me if I'm wrong, but I can't see how multiple parallel invocations of the function could reference separate stack variables from static sregex's).  I did make the sregex's const; that appears to have improved performance a bit.

You can still make the regex objects static const and use placeholders
in the semantic actions. See the following section:

http://www.boost.org/doc/libs/1_39_0/doc/html/xpressive/user_s_guide.html#boost_xpressive.user_s_guide.semantic_actions_and_user_defined_assertions.referring_to_non_local_variables

--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Eric Niebler wrote:
>
> Really what you're saying is: "I can't/don't want to use
> xpressive in the ways that are *documented* to make it perform
> well. Why is it slow?" You already have your answer.

So be it.  I was just hoping I had done something silly and could rearrange things to improve the performance.

Thanks for your attention.

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Eric Niebler wrote:
> Stewart, Robert wrote:
> > Dave Jenkins wrote:
> >>>> Each call to parse() is constructing the sregex variables.
[snip]
> >> How about making them static const?  That should be thread safe.
>
> You can still make the regex objects static const and use
> placeholders in the semantic actions. See the following
> section:
>
> http://www.boost.org/doc/libs/1_39_0/doc/html/xpressive/user_s_guide.html#boost_xpressive.user_s_guide.semantic_actions_and_user_defined_assertions.referring_to_non_local_variables

I forgot about that section.  Thanks for the pointer.

Whoa!  The performance just shot up to a mere 6X the custom code (from 175X).  That might well be fast enough to keep the Xpressive version because of its readability!

Thanks Eric!

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Dave Jenkins-3]

> Whoa!  The performance just shot up to a mere 6X the custom code (from
> 175X).  That might well be fast enough to keep the Xpressive version
> because of its readability!

Can you create thread-local match_results objects and reuse them?  If so, I
think you'll see parsing dwindle to almost nothing and your semantic actions
will account for the bulk of the time spent.

Regards,
Dave Jenkins


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Matthew Chambers-3]

Why is Xpressive more readable than using lexical_cast or your
numeric_cast? I've implemented specializations of lexical_cast for
string->numeric conversions using strto[ld]. It is a vast speed
improvement of course, and since those specializations are hidden away
in a header, readability is the same as with normal lexical_casts. Maybe
I'm misunderstanding your use case? Do you not know ahead of time what
the type of the number will be?

-Matt


Dave Jenkins wrote:

>> Whoa!  The performance just shot up to a mere 6X the custom code
>> (from 175X).  That might well be fast enough to keep the Xpressive
>> version because of its readability!
>
> Can you create thread-local match_results objects and reuse them?  If
> so, I think you'll see parsing dwindle to almost nothing and your
> semantic actions will account for the bulk of the time spent.
>
> Regards,
> Dave Jenkins
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Eric Niebler-3]

Dave Jenkins wrote:
> Robert Stuart wrote:
>> Whoa!  The performance just shot up to a mere 6X the custom code (from
>> 175X).  That might well be fast enough to keep the Xpressive version
>> because of its readability!
>
> Can you create thread-local match_results objects and reuse them?  If
> so, I think you'll see parsing dwindle to almost nothing and your
> semantic actions will account for the bulk of the time spent.

Dave, thanks for spotting the obvious perf problem I missed. I can
confirm that reusing the match results object largely eliminates the
remaining performance problem. I tried 3 different scenarios:

1) The original code
2) Static const regexes
3) Static const regexes with reused match results objects

I ran each config for 1000000 iterations and got roughly these numbers:

1) ~950 sec
2) ~45 sec
3) ~9 sec

So reusing the match results object (3) results in a 5x speedup over
just using static const regexes (2). That almost completely erases any
performance advantage of the hand-crafted parsing code.

I'll also point out this section of the docs:
http://www.boost.org/doc/libs/1_39_0/doc/html/xpressive/user_s_guide.html#boost_xpressive.user_s_guide.tips_n_tricks

Both of the above optimizations (reuse regexes and match_results
objects) are recommended there.

Thanks,

--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Eric Niebler wrote:

> Dave Jenkins wrote:
> > Robert Stewart wrote:
> >> Whoa!  The performance just shot up to a mere 6X the custom
> >> code (from 175X).  That might well be fast enough to keep
> >> the Xpressive version because of its readability!
> >
> > Can you create thread-local match_results objects and reuse
> > them?  If so, I think you'll see parsing dwindle to almost
> > nothing and your semantic actions will account for the bulk
> > of the time spent.

At Dave's suggestion, I tried that.

> Dave, thanks for spotting the obvious perf problem I missed. I can
> confirm that reusing the match results object largely eliminates the
> remaining performance problem. I tried 3 different scenarios:
>
> 1) The original code
> 2) Static const regexes
> 3) Static const regexes with reused match results objects
>
> I ran each config for 1000000 iterations and got roughly
> these numbers:
>
> 1) ~950 sec
> 2) ~45 sec
> 3) ~9 sec
>
> So reusing the match results object (3) results in a 5x speedup
> over just using static const regexes (2). That almost
> completely erases any performance advantage of the hand-crafted
> parsing code.

Unfortunately, my results don't bear that out with the added overhead of locating the smatch via thread local storage.  I see no difference between default constructing an smatch each time and reusing an instance from TLS.

> I'll also point out this section of the docs:
> http://www.boost.org/doc/libs/1_39_0/doc/html/xpressive/user_s_guide.html#boost_xpressive.user_s_guide.tips_n_tricks
>
> Both of the above optimizations (reuse regexes and
> match_results objects) are recommended there.

I read through some of those quickly upon an initial read through the documentation.  I chose static regexes because I understood them to be faster.  I did not reuse the match_results<> because they aren't thread safe.  Dave's TLS suggestion hadn't occurred to me to reconcile the competing forces of reuse and no thread safety, of course.

Upon rereading, I see that you note that reusing a static regex improves performance, but I'd forgotten it by the time I needed the information.  May I suggest a "Performance Tuning" section that discusses such things apart from common pitfalls, etc. and stands out better in the TOC?  I didn't expect to find such information in a "Tips and Tricks" section, and forgotten that I had seen it when it was wanted.

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Matthew Chambers wrote:
>
> Why is Xpressive more readable than using lexical_cast or your
> numeric_cast? I've implemented specializations of lexical_cast
> for string->numeric conversions using strto[ld]. It is a vast
> speed improvement of course, and since those specializations
> are hidden away in a header, readability is the same as with
> normal lexical_casts. Maybe I'm misunderstanding your use case?
> Do you not know ahead of time what the type of the number will
> be?

If you'll have a look at my first post in this thread, you'll see the Xpressive code and the grammar I've implemented.  A later post shows the string-based parsing logic that uses string-to-number conversions similar to what you suggest.  (Indeed, the Xpressive semantic actions involve the same sorts of conversions.)  As you'll see, the code must parse whole numbers, fractions, mixed numbers, and real numbers.

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Dave Jenkins-3]

"Stewart, Robert" <Robert.Stewart@...> wrote in message
news:DF2E67F3D097004694C8428C70A3FD69046843E622@......
> Unfortunately, my results don't bear that out with the added overhead of
> locating the smatch via thread local storage.  I see no difference between
> default constructing an smatch each time and reusing an instance from TLS.
>

It's disappointing that locating a match_results object in thread-local
storage takes approximately the same amount of time as default constructing
a new one.  I had hoped for better.

Anyway, if you don't mind spending a little more time on this, I'd be
interested in seeing a breakdown of the amount of time spent on (1) locating
the match_results object in TLS, (2) parsing, and (3) semantic actions.

You could determine (1) by changing match_results to static (even though
this won't work in your actual case) and see what the time difference is.
Then if you comment out the semantic actions, you can determine the split
between parsing and semantic actions.

In any case, thanks for supplying a interesting test case of Xpressive in a
multi-threaded environment.

Dave Jenkins


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Dave Jenkins wrote:

> "Stewart, Robert" <Robert.Stewart@...> wrote in message
> news:DF2E67F3D097004694C8428C70A3FD69046843E622@......
>
> > Unfortunately, my results don't bear that out with the added
> > overhead of locating the smatch via thread local storage.  I
> > see no difference between default constructing an smatch each
> > time and reusing an instance from TLS.
>
> It's disappointing that locating a match_results object in
> thread-local storage takes approximately the same amount of
> time as default constructing a new one.  I had hoped for
> better.

Your hopes were justified: I just noticed that while my TLS accessor returns a reference to the smatch, I saved it to a copy rather than a reference where I was using it.  Correcting that mistake shows the Xpressive code taking around 1.5X the time used by the custom code.

I've seen added more test cases and updated the custom code and must now correct some things in the Xpressive code to handle all of the same cases before I can do any more measurements.

> Anyway, if you don't mind spending a little more time on this,
> I'd be interested in seeing a breakdown of the amount of time
> spent on (1) locating the match_results object in TLS, (2)
> parsing, and (3) semantic actions.

With TLS, a straightforward performance test required about 68s, whereas with a function local static, it required about 65s.

Keeping the static smatch and omitting the semantic actions changed the time to about 40s.

>From that, one can conclude that the matching takes about 40s, the semantic actions add 25s, and the TLS lookups add an additional 3s, in a loop of 100,000,000 iterations.

_____
Rob Stewart                           robert.stewart@...
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.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Eric Niebler-3]

Stewart, Robert wrote:

> Dave Jenkins wrote:
>>
>> It's disappointing that locating a match_results object in
>> thread-local storage takes approximately the same amount of time as
>> default constructing a new one.  I had hoped for better.
>
> I just noticed that while my TLS accessor
> returns a reference to the smatch, I saved it to a copy rather than a
> reference where I was using it.  Correcting that mistake shows the
> Xpressive code taking around 1.5X the time used by the custom code.

That's much better than 175X slower!

> I've seen added more test cases and updated the custom code and must
> now correct some things in the Xpressive code to handle all of the
> same cases before I can do any more measurements.

At this point, most of the low hanging fruit is picked clean. If you are
hungry for even more performance, you can eliminate the nested regex
invocations by changing the definition of the regex objects from this:

   static const sregex zero = as_xpr('0');

...to this:

   static const BOOST_PROTO_AUTO(zero, as_xpr('0'));

Do this for all but the top-most regex (the one named "price" in your
first example). You must also #include <boost/proto/proto_typeof.hpp>.

When I do this, performance drops from 9.5s to 6.0s.

> With TLS, a straightforward performance test required about 68s,
> whereas with a function local static, it required about 65s.
>
> Keeping the static smatch and omitting the semantic actions changed
> the time to about 40s.
>
> From that, one can conclude that the matching takes about 40s, the
> semantic actions add 25s, and the TLS lookups add an additional 3s,
> in a loop of 100,000,000 iterations.

Very interesting. Thanks for the measurements.

--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Thorsten Ottosen-3]

Hi Robert,

It would be good if you could submit your code as a case in optimizing
expressive code.

-Thorsten
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost