[xpressive] Performance Tuning?

[Stewart, Robert]

Thorsten Ottosen wrote:
>
> It would be good if you could submit your code as a case in
> optimizing expressive code.

Where and how would you have me do so?  I can see developing a performance tuning example from it to put in the documentation.  I don't know how much of that Eric has in mind already or if he is interested in such an addition (of his own doing or mine).

_____
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

[Paul Baxter]

"Stewart, Robert" <Robert.Stewart@...> wrote in message
news:DF2E67F3D097004694C8428C70A3FD6904685386F0@......
> Thorsten Ottosen wrote:
>>
>> It would be good if you could submit your code as a case in
>> optimizing expressive code.
>
> Where and how would you have me do so?  I can see developing a performance
> tuning example from it to put in the documentation.  I don't know how much
> of that Eric has in mind already or if he is interested in such an
> addition (of his own doing or mine).



This has been an incredibly useful thread. Thanks to you all.

As a potential user put off in the past by concerns over abstraction
penalties with such libraries (even compile time libraries often fail to
deliver in all but simple cases), I urge Eric to embrace such an example to
illustrate just how powerful and maintainable a solution based on expressive
can be.

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

[Eric Niebler-3]

Paul Baxter wrote:

> "Stewart, Robert" wrote:
>> Thorsten Ottosen wrote:
>>>
>>> It would be good if you could submit your code as a case in
>>> optimizing expressive code.
>>
>> Where and how would you have me do so?  I can see developing a
>> performance tuning example from it to put in the documentation.  I
>> don't know how much of that Eric has in mind already or if he is
>> interested in such an addition (of his own doing or mine).
>
> This has been an incredibly useful thread. Thanks to you all.
>
> As a potential user put off in the past by concerns over abstraction
> penalties with such libraries (even compile time libraries often fail to
> deliver in all but simple cases), I urge Eric to embrace such an example
> to illustrate just how powerful and maintainable a solution based on
> expressive can be.

I think this is a fine idea. All these tips and tricks are already
described in a doc, but they are not described in depth from an end-user
perspective. I think a performance tuning case study would make a
valuable appendix.

Robert, can you send me the latest version of your regex grammar and
your hand-coded parser? I'll see what I can do.

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

[Dave Jenkins-3]

From: "Stewart, Robert" <Robert.Stewart@...>
> 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.
>

Thanks for doing this work Rob.  It's been a really fruitful exercise.

I had one other question on performance improvement, mostly for Eric.  Could
you eliminate/minimize the need for match_results when semantic actions are
capturing the results?  In Rob's code, he's not even looking at the
match_results because his semantic actions handle the data.  Can you
optionally turn off the match_results capture in that case to save space and
time?

Regards,
Dave Jenkins

P.S. If I'm slow to respond, it's because I'm on vacation and internet
access is spotty.

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

[Kim Scheibel-2]

Eric Niebler wrote:

> Robert, can you send me the latest version of your regex grammar and
> your hand-coded parser? I'll see what I can do.

Actually, Rob, would you mind posting it here?

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

[Stewart, Robert]

Eric Niebler wrote:

> Paul Baxter wrote:
> > "Stewart, Robert" wrote:
> >> Thorsten Ottosen wrote:
> >>>
> >>> It would be good if you could submit your code as a case in
> >>> optimizing expressive code.
> >>
> >> Where and how would you have me do so?  I can see developing
> >> a performance tuning example from it to put in the
> >> documentation.  I don't know how much of that Eric has in
> >> mind already or if he is interested in such an addition (of
> >> his own doing or mine).
> >
> > This has been an incredibly useful thread. Thanks to you all.
> >
> > As a potential user put off in the past by concerns over
> > abstraction penalties with such libraries (even compile time
> > libraries often fail to deliver in all but simple cases), I
> > urge Eric to embrace such an example to illustrate just how
> > powerful and maintainable a solution based on expressive can
> > be.
>
> I think this is a fine idea. All these tips and tricks are
> already described in a doc, but they are not described in depth
> from an end-user perspective. I think a performance tuning case
> study would make a valuable appendix.
>
> Robert, can you send me the latest version of your regex
> grammar and your hand-coded parser? I'll see what I can do.

Sure.  I've attached both in one file, but with separate namespaces.  My progression, as you can ascertain from retracing this thread, was from automatic sregexes and an automatic smatch to putting the sregexes in a namespace, which required creating placeholders, to putting the smatch into thread local storage, to using BOOST_PROTO_AUTO.  That progression changed the performance of the Xpressive code from about 175X slower to less than 2X slower than the custom code.  (I haven't measured against the final, tuned custom parsing code.)

This code is used to parse whole numbers, real numbers, fractions, and mixed numbers from a string creating an integer from which the (possibly) fractional value can be recovered.  example::lcm<T>::as() returns 160,000 as type T for that purpose because 160,000 is the least common multiple of all supported denominators.  That aspect of this code should probably be removed in order to concentrate on the parsing, but was too well entrenched for me to remove.

I have changed some names and namespaces from those in the original code to normalize it.  I also have omitted exception throwing code and denominator validation logic.  I haven't compiled since making those changes, so there may be some minor mistake in the attached code.

The code references some things you'll not have access to, so allow me to explain them so you can make the necessary substitutions.

 - core::to_number(), uses TMP to select among several overloads of a conversion function which are wrappers around strtol(), strtod(), etc.  Note that specifying a conversion radix is important to avoid octal parsing in the custom code.  (Otherwise, the custom code would need to account for leading zeroes in other ways.)

 - core::numeric_cast is a function template that converts a string to a numeric type.  It uses TMP to select among several overloads of a conversion function which are wrappers around core::to_number() and which log a debug-level message and throw std::bad_cast on failure.  boost::lexical_cast should be a slower equivalent.

 - ThreadLocal, as you can well infer, manages memory referenced by thread local storage.  (It mimics the interface of Rogue Wave's RWTThreadLocal.)

FYI, direct_impl/direct_ exists because I couldn't distinguish its function call operator from one in to_price_impl/price_, without resorting to passing a dummy parameter.  While it isn't strictly necessary, I chose to provide it because it avoids using double as an intermediate type.

Notice that the rounding code assumes a positive value and that I manage the sign separately.

The custom version was tuned via profiling, which explains the different treatment of the sign between parsing reals and fractions.

Enjoy!

_____
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.

namespace example
{
   struct lcm_generator
   {
      lcm_generator() { }

      template <class T>
      T
      as() const;
   };

   template <>
   inline unsigned
   lcm_generator::as<unsigned>() const
   {
      return 160000U;
   }

   template <>
   inline int64_t
   lcm_generator::as<int64_t>() const
   {
      return INT64(160000);
   }

   template <>
   inline double
   lcm_generator::as<double>() const
   {
      return 160000.0;
   }

   int64_t
   round(double);

   lcm_generator const lcm;
}

// *****************************************************************************
// Design Notes:  Adding 0.5 to _value before calling std::floor(), which
// rounds down, causes rounding to the nearest whole number.  This only works
// for positive values, however.
// -----------------------------------------------------------------------------
inline int64_t
example::round(double const _value)
{
   return static_cast<int64_t>(std::floor(_value + 0.5));
}

namespace example { namespace custom {
   template <class T>
   T
   extract(char const * & _input, char const * _description,
      std::string const & _input);

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

   int64_t
   parse_fraction(char const *& _end, int64_t _result,
      char const * _denominator, bool _is_mixed_number,
      std::string const & _value);

   void
   raise_extract_failed(char const * _description, std::string const & _value)
      GNU_ATTRIBUTE(noreturn);

   void
   raise_zero_denominator(std::string const &) GNU_ATTRIBUTE(noreturn);
} }

// *****************************************************************************
// Design Notes:  Non-dependent exception throwing code appears in
// raise_extract_failed().
// -----------------------------------------------------------------------------
template <class T>
T
example::custom::extract(char const * & _input, char const * const _description,
   std::string const & _value)
{
   T result;
   if (!core::to_number(result, _input, &_input, 10))
   {
      raise_extract_failed(_description, _value);
   }
   return result;
}

// *****************************************************************************
// Design Notes:  This function parses several number formats: floating
// point, whole number, fraction, and mixed number.  All formats begin with a
// number, so the input is first parsed and converted to int64_t, base 10.  If
// a decimal point appears immediately after the input consumed for that
// conversion, then reparse from the beginning as floating point rather than
// jump through hoops to compute the fractional part.  If there is a space
// after the initial number, then the initial number is a whole number that may
// be followed by a fraction, meaning the input was a mixed number.  If there
// is a slash after the initial number, then the initial number is the
// numerator of a fraction.
//
// When converting a whole number, it is important to avoid floating point
// representational and radix problems.  The int64_t conversion is done with
// base 10, thus ignoring any leading zeroes.  Conversion to double would work
// without specifying the base, but then it is difficult to know whether to
// look for a fraction, for a mixed number, and the integer value may not be
// representable in a double.
//
// Negative values, except when the input is a whole number, must be processed
// as positive until after the fractional part has been parsed and computed to
// simplify accounting for rounding errors in round() and to account correctly
// for magnitude.
//
// When computing a fraction, the product of lcm and numerator is divided by
// denominator in order to reduce rounding and representational errors that
// would result from first computing the quotient of numerator and denominator.
// -----------------------------------------------------------------------------
int64_t
example::custom::parse(std::string const & _value)
{
   assert(std::string::npos != _value.find_first_not_of("-+0123456789eE ./"));
   if (_value.empty())
   {
      return 0;
   }
   char const * const start(_value.c_str());
   char const * end(start);
   int64_t result;
   (void)core::to_number(result, end, &end, 10);
   bool const is_floating_point('.' == *end);
   if (is_floating_point)
   {
      end = start;
      double value(extract<double>(end, "input", _value) * lcm.as<double>());
      bool const is_negative(0 > result);
      if (is_negative)
      {
         value = -value;
      }
      result = round(value);
      if (is_negative)
      {
         result = -result;
      }
   }
   else
   {
      result *= lcm.as<int64_t>();
      char const * const last(start + _value.length());
      if (end != last)
      {
         size_t const slash(_value.find_first_of('/', end - start));
         bool const is_fraction(std::string::npos != slash);
         if (is_fraction)
         {
            char const * const denominator(start + slash + 1);
            bool const is_mixed_number(
               std::string::npos != _value.find_last_of(' ', slash));
            bool const is_non_negative(0 <= result);
            if (is_non_negative)
            {
               result = parse_fraction(end, result, denominator,
                  is_mixed_number, _value);
            }
            else
            {
               result = -parse_fraction(end, -result, denominator,
                  is_mixed_number, _value);
            }
         }
      }
   }
   assert(end == (start + _value.length())
      || std::string::npos == _value.find_first_not_of(
         " \t\r\n", end - start, 4));
   return result;
}

// *****************************************************************************
// Design Notes:
// -----------------------------------------------------------------------------
int64_t
example::custom::parse_fraction(char const *& _end, int64_t const _result,
   char const * const _denominator, bool const _is_mixed_number,
   std::string const & _value)
{
   double value;
   if (_is_mixed_number)
   {
      unsigned const numerator(extract<unsigned>(_end, "numerator", _value));
      _end = _denominator;
      unsigned const denominator(
         extract<unsigned>(_end, "denominator", _value));
      double fraction(numerator * lcm.as<double>() / denominator);
      value = _result + fraction;
   }
   else
   {
      _end = _denominator;
      unsigned const denominator(
         extract<unsigned>(_end, "denominator", _value));
      value = _result / denominator;
   }
   int64_t const result(round(value));
   return result;
}

namespace example { namespace xpressive {
   struct direct_impl
   {
      typedef int64_t result_type;

      template <class Value>
      int64_t
      operator ()(Value const & _value) const
      {
         int64_t result(core::numeric_cast<int64_t>(_value));
         result *= lcm.as<int64_t>();
         return result;
      }
   };

   // exception type indicating denominator was zero
   struct zero_denominator { };

   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(core::numeric_cast<double>(_value));
            result = round(lcm.as<double>() * value);
         }
         return result;
      }

      template <class Value>
      int64_t
      operator ()(Value const & _numerator, Value const & _denominator) const
      {
         unsigned const numerator(core::numeric_cast<unsigned>(_numerator));
         unsigned const denominator(
            core::numeric_cast<unsigned>(_denominator));
         if (0 == denominator)
         {
            throw zero_denominator();
         }
         double const fraction(lcm.as<double>() * numerator / denominator);
         return round(fraction);
      }

      template <class Value>
      int64_t
      operator ()(Value const & _whole, double const _fraction) const
      {
         int const whole(core::numeric_cast<int>(_whole));
         double const value(lcm.as<double>() * whole + _fraction);
         return round(value);
      }
   };

   ThreadLocal<boost::xpressive::smatch> match_s;
} }

namespace example { namespace xpressive { namespace prices {
   using namespace boost::xpressive;

   function<direct_impl>::type const direct = {{}};
   function<to_price_impl>::type const to_price = {{}};
   placeholder<bool> is_negative_;
   placeholder<int64_t> price_;
   const BOOST_PROTO_AUTO(zero, as_xpr('0'));
   const BOOST_PROTO_AUTO(sign,
      as_xpr('-')                         [ is_negative_ = true ]
      | as_xpr('+'));         // ignore
   const BOOST_PROTO_AUTO(fraction,
      (
         *zero >> (s1= +_d) >> *blank >> '/' >> *blank >> *zero
         >> (s2= +_d)
      )                                   [ price_ = to_price(s1, s2) ]);
   const BOOST_PROTO_AUTO(real,
      (
         *_d >> '.' >> *_d >> !((set= 'E', 'e', 'G', 'g') >> +_d)
      )                                   [ price_ = to_price(_) ]);
   const BOOST_PROTO_AUTO(whole_number,
      (
         *zero >> (s1= +_d) >> +blank >> fraction
      )                                   [ price_ = to_price(s1, price_) ]);
   const BOOST_PROTO_AUTO(integer,
      (
         *zero >> (s1= +_d)
      )                                   [ price_ = direct(s1) ]);
   const sregex price =
      *blank
      >> !sign
      >> (real | whole_number | fraction | integer)
      >> *space;
} } }

// *****************************************************************************
// Design Notes:
// -----------------------------------------------------------------------------
int64_t
example::xpressive::parse(const std::string & _value)
{
   typedef std::string::const_iterator iterator;
   using namespace prices;

   int64_t result;
   iterator begin(_value.begin());
   iterator end(_value.end());
   bool is_negative(false);
   boost::xpressive::smatch & match(match_s.getValue());
   match.let(price_ = result);
   match.let(is_negative_ = is_negative);
   bool matched;
   try
   {
      matched = boost::xpressive::regex_match(begin, end, match, price);
   }
   catch (zero_denominator)
   {
      raise_zero_denominator(_value);
   }
   if (!matched)
   {
      raise_parse_failure(_value);
   }
   if (is_negative)
   {
      result = -result;
   }
   return result;
}

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

[OvermindDL1]

On Fri, Jul 10, 2009 at 7:32 AM, Stewart, Robert<Robert.Stewart@...> wrote:

> Eric Niebler wrote:
>> Paul Baxter wrote:
>> > "Stewart, Robert" wrote:
>> >> Thorsten Ottosen wrote:
>> >>>
>> >>> It would be good if you could submit your code as a case in
>> >>> optimizing expressive code.
>> >>
>> >> Where and how would you have me do so?  I can see developing
>> >> a performance tuning example from it to put in the
>> >> documentation.  I don't know how much of that Eric has in
>> >> mind already or if he is interested in such an addition (of
>> >> his own doing or mine).
>> >
>> > This has been an incredibly useful thread. Thanks to you all.
>> >
>> > As a potential user put off in the past by concerns over
>> > abstraction penalties with such libraries (even compile time
>> > libraries often fail to deliver in all but simple cases), I
>> > urge Eric to embrace such an example to illustrate just how
>> > powerful and maintainable a solution based on expressive can
>> > be.
>>
>> I think this is a fine idea. All these tips and tricks are
>> already described in a doc, but they are not described in depth
>> from an end-user perspective. I think a performance tuning case
>> study would make a valuable appendix.
>>
>> Robert, can you send me the latest version of your regex
>> grammar and your hand-coded parser? I'll see what I can do.
>
> Sure.  I've attached both in one file, but with separate namespaces.  My progression, as you can ascertain from retracing this thread, was from automatic sregexes and an automatic smatch to putting the sregexes in a namespace, which required creating placeholders, to putting the smatch into thread local storage, to using BOOST_PROTO_AUTO.  That progression changed the performance of the Xpressive code from about 175X slower to less than 2X slower than the custom code.  (I haven't measured against the final, tuned custom parsing code.)
>
> This code is used to parse whole numbers, real numbers, fractions, and mixed numbers from a string creating an integer from which the (possibly) fractional value can be recovered.  example::lcm<T>::as() returns 160,000 as type T for that purpose because 160,000 is the least common multiple of all supported denominators.  That aspect of this code should probably be removed in order to concentrate on the parsing, but was too well entrenched for me to remove.
>
> I have changed some names and namespaces from those in the original code to normalize it.  I also have omitted exception throwing code and denominator validation logic.  I haven't compiled since making those changes, so there may be some minor mistake in the attached code.
>
> The code references some things you'll not have access to, so allow me to explain them so you can make the necessary substitutions.
>
>  - core::to_number(), uses TMP to select among several overloads of a conversion function which are wrappers around strtol(), strtod(), etc.  Note that specifying a conversion radix is important to avoid octal parsing in the custom code.  (Otherwise, the custom code would need to account for leading zeroes in other ways.)
>
>  - core::numeric_cast is a function template that converts a string to a numeric type.  It uses TMP to select among several overloads of a conversion function which are wrappers around core::to_number() and which log a debug-level message and throw std::bad_cast on failure.  boost::lexical_cast should be a slower equivalent.
>
>  - ThreadLocal, as you can well infer, manages memory referenced by thread local storage.  (It mimics the interface of Rogue Wave's RWTThreadLocal.)
>
> FYI, direct_impl/direct_ exists because I couldn't distinguish its function call operator from one in to_price_impl/price_, without resorting to passing a dummy parameter.  While it isn't strictly necessary, I chose to provide it because it avoids using double as an intermediate type.
>
> Notice that the rounding code assumes a positive value and that I manage the sign separately.
>
> The custom version was tuned via profiling, which explains the different treatment of the sign between parsing reals and fractions.

I find this quite interesting.  I wonder if I might have the time
tonight to make a Spirit2.1 version of this, the code would certainly
be a great deal shorter.
Just to make sure, from what I gathered looking at the code, you are
trying to parse out a number from an ascii string that could
potentially be an integer (64-bit, just digits, always base 10), a
double (digits as the integer, then a period, then more digits parsed
as the integer, OR a whole integer, then a space(s), followed by an
int then a / then an int), it looks like that a real number can have a
'g' after it, but what is a g?  I know what e's means, but g?  I am
also confused, it seems your types support int64 as well as double,
but you only ever return an int64, why not a variant of both?  Should
I do this for Spirit2.1?  Spirit2.1 naturally wants to use such things
anyway so it is actually easier for me to do so, and the user would
have a more accurate value too as they would get either an int64 or a
double depending on what it parsed, I could also add in other
representations like a struct of two int64's for a
numerator/denominator as well for best accuracy.  What would you
prefer?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Michael Caisse-2]

OvermindDL1 wrote:

> I find this quite interesting.  I wonder if I might have the time
> tonight to make a Spirit2.1 version of this, the code would certainly
> be a great deal shorter.
> Just to make sure, from what I gathered looking at the code, you are
> trying to parse out a number from an ascii string that could
> potentially be an integer (64-bit, just digits, always base 10), a
> double (digits as the integer, then a period, then more digits parsed
> as the integer, OR a whole integer, then a space(s), followed by an
> int then a / then an int), it looks like that a real number can have a
> 'g' after it, but what is a g?  I know what e's means, but g?  I am
> also confused, it seems your types support int64 as well as double,
> but you only ever return an int64, why not a variant of both?  Should
> I do this for Spirit2.1?  Spirit2.1 naturally wants to use such things
> anyway so it is actually easier for me to do so, and the user would
> have a more accurate value too as they would get either an int64 or a
> double depending on what it parsed, I could also add in other
> representations like a struct of two int64's for a
> numerator/denominator as well for best accuracy.  What would you
> prefer?
> _______________________________________________
>  

I have considered doing this myself on and off. I'm still learning
Spirit 2.1 and if you were to throw this together it would be a great
example of approaching the problem three different ways.

I am looking forward to seeing your effort.

Best Regards -
michael


--

----------------------------------
Michael Caisse
Object Modeling Designs
www.objectmodelingdesigns.com


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

[OvermindDL1]

On Mon, Jul 13, 2009 at 10:22 PM, Michael
Caisse<boost@...> wrote:

> OvermindDL1 wrote:
>>
>> I find this quite interesting.  I wonder if I might have the time
>> tonight to make a Spirit2.1 version of this, the code would certainly
>> be a great deal shorter.
>> Just to make sure, from what I gathered looking at the code, you are
>> trying to parse out a number from an ascii string that could
>> potentially be an integer (64-bit, just digits, always base 10), a
>> double (digits as the integer, then a period, then more digits parsed
>> as the integer, OR a whole integer, then a space(s), followed by an
>> int then a / then an int), it looks like that a real number can have a
>> 'g' after it, but what is a g?  I know what e's means, but g?  I am
>> also confused, it seems your types support int64 as well as double,
>> but you only ever return an int64, why not a variant of both?  Should
>> I do this for Spirit2.1?  Spirit2.1 naturally wants to use such things
>> anyway so it is actually easier for me to do so, and the user would
>> have a more accurate value too as they would get either an int64 or a
>> double depending on what it parsed, I could also add in other
>> representations like a struct of two int64's for a
>> numerator/denominator as well for best accuracy.  What would you
>> prefer?
>> _______________________________________________
>>
>
> I have considered doing this myself on and off. I'm still learning
> Spirit 2.1 and if you were to throw this together it would be a great
> example of approaching the problem three different ways.
>
> I am looking forward to seeing your effort.

Spirit2.1 is by far the most easy Spirit to date, as well as the
fastest, beats out many hand-written and tuned parsers as well.
Should not be hard to do, and I think I would prefer to return a
variant of all possible types as I see no point cutting out
information, let the user decide what info they want, unless someone
tells me they only want anything/everything as an int64, then I can do
it that way too.

But still, what would the 'g' in a number like 2.4g5 do, I know what e
does, but g?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

OvermindDL1 wrote:
> On Fri, Jul 10, 2009 at 7:32 AM, Stewart,
> Robert<Robert.Stewart@...> wrote:
> > Eric Niebler wrote:
> >> Paul Baxter wrote:
> >> >> Thorsten Ottosen wrote:
> >> >>>
> >> >>> It would be good if you could submit your code as a case in
> >> >>> optimizing expressive code.
[snip]

> >> > This has been an incredibly useful thread. Thanks to you all.
> >> >
> >> > As a potential user put off in the past by concerns over
> >> > abstraction penalties with such libraries (even compile time
> >> > libraries often fail to deliver in all but simple cases), I
> >> > urge Eric to embrace such an example to illustrate just how
> >> > powerful and maintainable a solution based on expressive can
> >> > be.
> >>
> >> I think this is a fine idea. All these tips and tricks are
> >> already described in a doc, but they are not described in depth
> >> from an end-user perspective. I think a performance tuning case
> >> study would make a valuable appendix.
> >>
> >> Robert, can you send me the latest version of your regex
> >> grammar and your hand-coded parser? I'll see what I can do.
> >
> > Sure.  I've attached both in one file, but with separate
> > namespaces.

[snip]
> > This code is used to parse whole numbers, real numbers,
> fractions, and mixed numbers from a string creating an
> integer from which the (possibly) fractional value can be
> recovered.  example::lcm<T>::as() returns 160,000 as type T
> for that purpose because 160,000 is the least common multiple
> of all supported denominators.  That aspect of this code
> should probably be removed in order to concentrate on the
> parsing, but was too well entrenched for me to remove.
[snip]
> I find this quite interesting.  I wonder if I might have the
> time tonight to make a Spirit2.1 version of this, the code
> would certainly be a great deal shorter.

That would be great.  I am interested to know if I was doing anything wrong or was just trying more than Spirit v2 was capable of doing in Boost 1.37, which is what I needed to use in this case.

> Just to make sure, from what I gathered looking at the code,
> you are trying to parse out a number from an ascii string that
> could potentially be an integer (64-bit, just digits, always
> base 10), a double (digits as the integer, then a period, then
> more digits parsed as the integer, OR a whole integer, then a
> space(s), followed by an int then a / then an int), it looks
> like that a real number can have a 'g' after it, but what is a
> g?  I know what e's means, but g?

As described above, I'm looking for whole numbers, reals, fractions, and mixed numbers.  The whole numbers are 64b integers.  The reals are any of various formats such as you might get from printf().  The "g" and "G" were from a rapid, overzealous scan of the manpage; I forgot to remove them when I realized they weren't appropriate (they are not supported in the custom version, you'll note).  The fractions are expected to have a positive denominator, and a possibly signed numerator.  The mixed numbers are a whitespace delimited combination of a whole number and a fraction, except the numerator must be non-negative in that case.  As you surmised, the input is assumed to be an ASCII string.

> I am also confused, it seems your types support int64 as well
> as double, but you only ever return an int64, why not a variant
> of both?

The purpose of this code was to produce a 64b integer because the result represents a (possibly fractional) dollar amount: a price.  The 160,000 least common multiple provides rounding for all supported denominators so all supported amounts can be represented exactly in the 64b integer type (the range is, of course, reduced in doing so).

> Should I do this for Spirit2.1?  Spirit2.1 naturally wants to
> use such things anyway so it is actually easier for me to do
> so, and the user would have a more accurate value too as they
> would get either an int64 or a double depending on what it
> parsed, I could also add in other representations like a struct
> of two int64's for a numerator/denominator as well for best
> accuracy.  What would you prefer?

In order to compare your Spirit code against the two versions I supplied, your code would need to behave the same.  Otherwise, you must alter the two versions I supplied to match what you choose to provide in your Spirit version.  The purpose of this exercise is to compare the code and performance, so they must all perform the same task.

_____
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

[Paul Baxter]

>
But still, what would the 'g' in a number like 2.4g5 do, I know what e
does, but g?
<
Perhaps this follows the notation for a double much like used in printf
formatting?

http://en.wikipedia.org/wiki/Printf   3/4 of the way down giving an
imprecise but general description

Looking forward to seeing the threeway comparison - really helpful for users
particularly as each trade maintainability, learning curve and speed in
different ways.

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

[OvermindDL1]

Okay, I made a Spirit version and I am wanting to compare times,
however no one has posted any compilable code here yet, nor test
cases, nor anything I can use, so I am just guessing that it is
correct since I have no data to run through it.

Since none of the above code actually compiles as-is, and I do not
feel like dealing with incomplete examples, here are the times on my
computer using the code below.
When parsing "42", this would be an example of the fastest case:

        char const *s1 = "42", *e1 = s1 + std::strlen(s1);
        boost::long_long_type result;
        size_t counter = 1000000;
        while(counter--) parse_price_spirit(s1, e1, result);

This executed in no real measurable time... might have been optimized
out, let me check the assembly, nope, very much not optimized out, the
loop is run, the function is not inlined, and it is indeed called
1000000 times.

Okay, running this with 10000000 (7 zero's, 10 million loops, 9
million extra then the above tests) instead takes about ~1.5 seconds.

Now running the test with "42.5", which should be the *slowest*
possible case for the code I wrote, with 1000000 (6 zero's, one
million) it took still no noticeable time.  With 10000000 (7 zero's,
10 million) iterations it took roughly about ~1.5 seconds again.

I would really love to have the same test cases and scaffolds that
everyone else is using so I can do some real timings though.

And yes, my parser, for a string it returns -> value:
"42" -> 6720000 (42*160000)
"42 1/2" -> 6800000 (42*16000 + (1*16000)/2)
"42.5" -> 6800000 (42*16000 + floor(160000.0*0.5 + 0.5))
"4.2e1" -> 6720000 (42*160000)


This is comparing with someone elses above timings, have no clue of
his compile type, hardware, anything, and he did not post his code,
but these are the times that he posted:

> 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

All of the above I did was using MSVC 2k5 in release mode in Windows
XP on an old AMD Athlon 1.8ghz Opteron processor.  If anyone can give
me the above code (his original version and the xpressive version) as
compilable files so I do not need to deal with anything, then I can
run a proper, full, and millisecond detailed timings.  Based on my
above timings, either my ancient 1.8ghz computer is rather massively
faster then his computer, or Spirit2.1 is much faster then both
xpressive and the original code (which someone else said above, the
optimized xpressive takes about 20% or so longer I think?).




The code, I whipped it up quickly, not pretty, just getting it
functional since the guidelines are not very well set, do note, this
is not how I normally make my Spirit parsers, but if someone gives me
the source of the other things, then I will do this one properly once
I confirm that this parses what needs to be parsed (to compile this,
make sure you are running Boost Trunk!):
#include <boost/tr1/cmath.hpp>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>

BOOST_STATIC_ASSERT(sizeof(boost::long_long_type) == 8);

boost::long_long_type tmpResult;
inline void dotNumber(const double a1)
{
        tmpResult += static_cast<boost::long_long_type>(std::floor(160000.0*a1 + 0.5));
}

template <typename Iterator>
bool parse_price_spirit(Iterator first, Iterator last, boost::long_long_type &c)
{
        using boost::spirit::qi::double_;
        using boost::spirit::qi::_1;
        using boost::spirit::qi::_2;
        using boost::spirit::qi::phrase_parse;
        using boost::spirit::qi::lexeme;
        using boost::spirit::qi::lit;
        using boost::spirit::ascii::space;
        using boost::spirit::ascii::blank;
        using boost::phoenix::ref;
        using boost::spirit::long_long;
        using boost::long_long_type;

        bool r = phrase_parse(first, last,

                        //  Begin grammar
                        // I did not put this in a grammar class because I am being
                        // lazy, plenty of examples of that anyway, and no, it is not
                        // faster here, it is the same speed whether inline here or in
                        // a grammar class.
                        ( (long_long[ref(tmpResult)=(_1*160000)] >> !lit('.') >>
-(long_long >> '/' >> long_long)[ref(tmpResult)+=160000*_1/_2])
                        | double_[&dotNumber]
                        )
                        //  End grammar

                ,blank);

        if (!r || first != last) // fail if we did not get a full match
                return false;

        c = tmpResult;

        return r;
}
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Stewart, Robert]

Paul Baxter wrote:

> >
> But still, what would the 'g' in a number like 2.4g5 do, I know what e
> does, but g?
> <
> Perhaps this follows the notation for a double much like used
> in printf
> formatting?
>
> http://en.wikipedia.org/wiki/Printf   3/4 of the way down giving an
> imprecise but general description

Are you referring to the "Type" table that lists "g" and "G" format specifiers?  That's what I latched onto much too readily when scanning the manpage and later realized when working on the custom parsing code but didn't correct in the Xpressive parser.  Those are not used in the output; they are used to indicate the desired formatting.

_____
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

[OvermindDL1]

On Wed, Jul 15, 2009 at 6:54 AM, Stewart, Robert<Robert.Stewart@...> wrote:

> Paul Baxter wrote:
>> >
>> But still, what would the 'g' in a number like 2.4g5 do, I know what e
>> does, but g?
>> <
>> Perhaps this follows the notation for a double much like used
>> in printf
>> formatting?
>>
>> http://en.wikipedia.org/wiki/Printf   3/4 of the way down giving an
>> imprecise but general description
>
> Are you referring to the "Type" table that lists "g" and "G" format specifiers?  That's what I latched onto much too readily when scanning the manpage and later realized when working on the custom parsing code but didn't correct in the Xpressive parser.  Those are not used in the output; they are used to indicate the desired formatting.

I gathered that, hence my code only supports e/E, no g/G.  Look on my
previous email.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[OvermindDL1]

On Wed, Jul 15, 2009 at 6:57 AM, OvermindDL1<overminddl1@...> wrote:
> /* snip */

So has anyone tried the code I posted to see how it compared?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Raindog]

I would be very interested in seeing this too as your numbers look extremely good
------Original Message------
From: OvermindDL1
Sender: boost-bounces@...
To: boost@...
ReplyTo: boost@...
Sent: Jul 17, 2009 3:30 PM
Subject: Re: [boost] [xpressive] Performance Tuning?

On Wed, Jul 15, 2009 at 6:57 AM, OvermindDL1<overminddl1@...> wrote:
> /* snip */

So has anyone tried the code I posted to see how it compared?
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost




Sent from my Verizon Wireless BlackBerry
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[OvermindDL1]

On Fri, Jul 17, 2009 at 5:10 PM, <raindog@...> wrote:
> I would be very interested in seeing this too as your numbers look extremely good

As stated, the numbers are basically hogwash until all three forms are
all tested on the same hardware using the same compiler.  I *might*
have time tonight to work on the code that the others posted above to
get it compilable, although it is rather irritating that they posted
code that was incomplete, but meh.  If I have time tonight then I can
test all three versions using MSVC8 on WinXP on my old 1.8ghz Opteron
CPU.

Who knows, one of the other version may still be faster, MSVC does
tend to handle optimizing heavy templated code better then other
compilers, and Spirit is nothing but basically to be inlined templated
code, so it might be able to optimize the xpressive version better as
well, and who knows how it will handle the original code.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Eric Niebler-3]

OvermindDL1 wrote:

> On Fri, Jul 17, 2009 at 5:10 PM, <raindog@...> wrote:
>> I would be very interested in seeing this too as your numbers look extremely good
>
> As stated, the numbers are basically hogwash until all three forms are
> all tested on the same hardware using the same compiler.  I *might*
> have time tonight to work on the code that the others posted above to
> get it compilable, although it is rather irritating that they posted
> code that was incomplete, but meh.  If I have time tonight then I can
> test all three versions using MSVC8 on WinXP on my old 1.8ghz Opteron
> CPU.
>
> Who knows, one of the other version may still be faster, MSVC does
> tend to handle optimizing heavy templated code better then other
> compilers, and Spirit is nothing but basically to be inlined templated
> code, so it might be able to optimize the xpressive version better as
> well, and who knows how it will handle the original code.

I thought Rob posted his code as an attachment here:

http://lists.boost.org/Archives/boost/2009/07/153845.php

Is that not complete?

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

[OvermindDL1]

On Fri, Jul 17, 2009 at 5:51 PM, Eric Niebler<eric@...> wrote:

> OvermindDL1 wrote:
>>
>> On Fri, Jul 17, 2009 at 5:10 PM, <raindog@...> wrote:
>>>
>>> I would be very interested in seeing this too as your numbers look
>>> extremely good
>>
>> As stated, the numbers are basically hogwash until all three forms are
>> all tested on the same hardware using the same compiler.  I *might*
>> have time tonight to work on the code that the others posted above to
>> get it compilable, although it is rather irritating that they posted
>> code that was incomplete, but meh.  If I have time tonight then I can
>> test all three versions using MSVC8 on WinXP on my old 1.8ghz Opteron
>> CPU.
>>
>> Who knows, one of the other version may still be faster, MSVC does
>> tend to handle optimizing heavy templated code better then other
>> compilers, and Spirit is nothing but basically to be inlined templated
>> code, so it might be able to optimize the xpressive version better as
>> well, and who knows how it will handle the original code.
>
> I thought Rob posted his code as an attachment here:
>
> http://lists.boost.org/Archives/boost/2009/07/153845.php
>
> Is that not complete?

Have you tried compiling it?  No, it is not complete, first of all it
is missing the includes, as well as a main function to run the loops
and test the timings in.  :)
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[OvermindDL1]

On Fri, Jul 17, 2009 at 6:35 PM, OvermindDL1<overminddl1@...> wrote:
> /* snip */

Okay, I cannot for the life of me get that above attached price.cpp
file to compile.
It is missing includes (apparently expressive needs something that I
cannot find either).  It is missing a whole core:: namespace worth of
functions that both the custom and the xpressive code reference.
Other things too.  This code is completely worthless until someone
gives me something complete that I can actually compile.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost