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

Subject: Re: [boost] [chrono/date] Performance goals and design summary
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2013-05-05 04:15:08

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 <typename Date1, typename Date2>
> 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