Re: [boost] [xint] Third release is ready, requesting preliminary review

Subject: Re: [boost] [xint] Third release is ready, requesting preliminary review
From: Stewart, Robert (Robert.Stewart_at_[hidden])
Date: 2010-05-05 11:01:18

Chad Nelson wrote:
> On 05/05/2010 07:56 AM, Stewart, Robert wrote:
>
> > However, there is an inherent
> > inefficiency here, though it may be miniscule relative to the
> > comparison code. A compare() function must return one of three
> > values: less than zero, zero, or greater than zero. That implies
> > additional logic that isn't necessary when computing <, ==, etc.
> > (Splitting those apart means duplicating portions of the logic in
> > compare(), of course.)
>
> It's quite minuscule. I'm no CPU hardware expert, but my
> educated guess
> would be two additional clock cycles per comparison at most. I'll take
> that cost over the cost of duplicating the logic in multiple
> functions, especially as it's not trivial.

I wasn't referring to the comparisons in the operator functions, but rather to the logic in compare() that must produce one of three results; I can't tell if we're talking about the same thing.  When implementing the operators directly, there are shortcuts in the logic you can't take in compare():

// untested, written in e-mail editor
bool
operator ==(base_integer const & _rhs) const
{
   if (_is_zero() != _rhs._is_zero()
      || _get_negative() != _rhs._get_negative())
   {
      return false;
   }
   size_t const length(_get_length());
   if (length != _rhs._get_length())
   {
      return false;
   }
   detail::digit_t * start(_get_digits());
   detail::digit_t * it(start + length);
   detail::digit_t * rhs_it(_rhs._get_digits() + length);
   while (it > start)
   {
      if (*(--it) != *(--rhs_it))
      {
         return false;
      }
   }
   return true;
}

That function is simpler than compare() plus a check for zero, so it could prove faster due to fewer branches and comparisons.  Is it measurably faster in any meaningful use case?  Perhaps.

You can reuse some of the algorithm by supplying a predicate and default result so multiple operators -- and compare() -- could use the same comparison loop.  (The early returns probably can't be reused appropriately.)

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