85112 - YearFromTime function can be optimized

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[joemansh]

from http://lxr.mozilla.org/seamonkey/source/js/src/jsdate.c#190

190 static jsint
191 YearFromTime(jsdouble t)
192 {
193     jsint lo = (jsint) floor((t / msPerDay) / 366) + 1970;
194     jsint hi = (jsint) floor((t / msPerDay) / 365) + 1970;
195     jsint mid;
196 
197     /* above doesn't work for negative dates... */
198     if (hi < lo) {
199         jsint temp = lo;
200         lo = hi;
201         hi = temp;
202     }
203 
204     /* Use a simple binary search algorithm to find the right
205        year.  This seems like brute force... but the computation
206        of hi and lo years above lands within one year of the
207        correct answer for years within a thousand years of
208        1970; the loop below only requires six iterations
209        for year 270000. */
210     while (hi > lo) {
211         mid = (hi + lo) / 2;
212         if (TimeFromYear(mid) > t) {
213             hi = mid - 1;
214         } else {
215             if (TimeFromYear(mid) <= t) {
216                 jsint temp = mid + 1;
217                 if (TimeFromYear(temp) > t) {
218                     return mid;
219                 }
220                 lo = mid + 1;
221             }
222         }
223     }
224     return lo;
225 }

can be simplified as:

static jsint
YearFromTime(jsdouble t)
{
        jsint y = (jsint) floor((t / msPerDay) / 365.2425) + 1970;
        jsint t2 = (jsint) TimeFromYear(y)
        if (t2 > t) {
                y--
                t2 = TimeFromYear(y)
        } else {
                if (t2 + msPerDay * DaysInYear(y) <= t) {
                        y++
                        t2 = TimeFromYear(y)
                }
        }
        return t2;
}

Comment 1

[Phil Schwartau]

Reassigning to Kenton, cc'ing Patrick -

Comment 2

[Patrick C. Beard]

Would you mind explaining the simplification? Is there a reference for this 
simplified algorithm? I'm curious about the 365.2425 factor.

Comment 3

[joemansh]

Sorry no reference.
365.2425 is the average number of days per year under the Gregorian calender.
= 365 + 1/4 (every fourth year is a leap year)
      - 1/100 (years divisable by 100 are not)
      + 1/400 (years divisable by 400 are)

Comment 4

[Kenton Hanson (gone)]

static jsint
YearFromTime(jsdouble t)
{
        jsint y = (jsint) floor(t /(msPerDay*365.2425)) + 1970;
        jsdouble t2 = (jsdouble) TimeFromYear(y);
        if (t2 > t) {
                y--;
        } else {
                if (t2 + msPerDay * DaysInYear(y) <= t) {
                        y++;
                }
        }
        return y;
}


Here is a corrected version, tested with the first and last millisecond of each 
year from 0 to 8000.  Also, 100,000,000 random head to head tests between the 
current and new versions where performed with no discrepancies.  The first guess 
was high 0.063564% of the time and low 0.037859% of the time, implying that the 
first guess is correct 99.9% of the time.

Comment 5

[Kenton Hanson (gone)]

Attachment: new YearFromTime routine

Comment 6

[Patrick C. Beard]

r=beard

Good work kenton.

Comment 7

[Brendan Eich [:brendan]]

sr=[e-mail], except for the tabs, which I'll fix.  I'm checking in
for 0.9.4.

/be

Comment 8

[Brendan Eich [:brendan]]

Fix is in, testsuite passes as before (same 5 failures).

/be

Comment 9

[Phil Schwartau]

Marking Verified - I have the same test results that Brendan reports.