Re: [boost] [chrono/date] Performance goals and design summary

5 May 2013

      Le 05/05/13 09:31, Vicente J. Botet Escriba a écrit :
...
Le 05/05/13 04:31, Howard Hinnant a écrit :
...
Fwiw, I went to 
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3344.pdf to 
experiment with the "Modified Following" benchmark which has some 
code shown for it.
I wanted to see what it would look like with two date types: field 
and serial, instead of just one (date) which has been implemented as 
both.
Here is the original code from N3344:
bool
isNonBusinessDay(const Date& targetDate,
                  const Date& startDate,
                  const int* calendar)
{
     int offset = targetDate - startDate;
     int wordIndex = offset / 8 / sizeof(int);
     int bitIndex = offset - wordIndex * sizeof(int);
     return (1 == (calendar[wordIndex] & (1 << bitIndex)));
}
Date
modifiedFollowing(const Date& targetDate,
                   const Date& startDate,
                   const int* calendar)
{
     Date date(targetDate);
     while (isNonBusinessDay(date, startDate, calendar))
         ++date;
     if (targetDate.month() == date.month())
         return date;
     date = targetDate;
     do
     {
         --date;
     } while (isNonBusinessDay(date, startDate, calendar));
     return date;
}
For purposes of discussion, assume we now have two date types:
1.  Serial type named day_point, which is a chrono::time_point.
2.  Field type named ymd (not a great name, just trying to 
differentiate it).
All isNonBusinessDay does is subtract two Dates.  This is clearly the 
domain of a serial type:
bool
isNonBusinessDay(const day_point& targetDate,
                  const day_point& startDate,
                  const int* calendar)
{
     days offset = targetDate - startDate;
     days wordIndex = offset / (8 * sizeof(int));
     days bitIndex = offset - wordIndex * sizeof(int);
     return (1 == (calendar[wordIndex.count()] & (1 << 
bitIndex.count())));
}
The modifications are trivial and expense is not compromised. The 
code is perhaps a little more type safe, utilizing the days units, 
but nothing spectacular.  I would expect the exact same assembly to 
be generated.
modifiedFollowing is more interesting.  If it takes two day_points 
(two serial dates), it might look like this:
day_point
modifiedFollowing(const day_point& targetDate,
                   const day_point& startDate,
                   const int* calendar)
{
     day_point date(targetDate);
     while (isNonBusinessDay(date, startDate, calendar))
         ++date;
     if (ymd(targetDate).month() == ymd(date).month())  // 
serial->field twice
         return date;
     date = targetDate;
     do
     {
         --date;
     } while (isNonBusinessDay(date, startDate, calendar));
     return date;
}
The only difference is the need to convert the serial dates to a ymd 
type so that the month can be extracted.  This is done exactly twice 
on the line commented.  Otherwise the code is remarkably similar, and 
I would argue, the exact same efficiency.
<disclaimer>
std::chrono::time_point is currently missing operator-- and 
operator++.  I view this a defect that should be corrected.
</disclaimer>
One could explore with passing in targetDate as a ymd type instead:
day_point
modifiedFollowing(const ymd& targetDate,
                   const day_point& startDate,
                   const int* calendar)
{
     day_point date(targetDate);  // field->serial
     day_point sdate = date;
     while (isNonBusinessDay(date, startDate, calendar))
         ++date;
     if (targetDate.month() == ymd(date).month())  // serial->field
         return date;
     date = sdate;
     do
     {
         --date;
     } while (isNonBusinessDay(date, startDate, calendar));
     return date;
}
This rewrite trades one serial->field conversion for one 
field->serial conversion.  It might be a win if the client actually 
has a ymd already for input, as my measurements are showing that 
serial->field conversions are more expensive than field->serial.  My 
measurements are raw and new, so I could be off on that.  And no 
doubt such a measurement is going to depend upon things like hardware 
and algorithms (caches).
But the main point is that having two date types is not disruptive, 
and mainly serves to give the client more options in optimizing his 
date algorithms.
I agree completely that we heed several dates and the standard (the 
library) must describe the performances provided by each one.
<snip>
For the purpose of showing the Date concept I will use a template
template 
days_date
modifiedFollowing(const Date1& targetDate,
                  const Date2& startDate,
                  const int* calendar)
{
    ymd_date ymdTargetDate(targetDate);   // serial->field  or nothing 
(so that the month() is efficient - we could store the month also).
    days_date date(targetDate);  // field->serial or nothing, but at 
least there is a conversion (as we are making day arithmetic)
    days_date sdate = date;
        while (isNonBusinessDay(date, startDate, calendar))
        ++date;
    if (ymdTargetDate.month() == date.month())  // serial->field  ++ 
No need to convert explicitly
        return date;
    date = sdate;
    do
    {
        --date;
    } while (isNonBusinessDay(date, startDate, calendar));
    return date;
}
As you can see the two dates with the same interface have not only 
drawbacks ;-) Providing the same interface and been convertible to 
each other helps the user.
One additional advantage of using date.month() and not using a specific 
conversion:
* class days_date could have a better algorithm that converting the 
days_date to ymd_date, e.g. can convert it to an ordinal_date and use a 
table to get the month from the is_leap() and day_of_year().

How better than the class days_date could know how to make these 
operations more efficient? itself or the user?

Best,
Vicente