ruby-changes:12249
From: akr <ko1@a...>
Date: Fri, 3 Jul 2009 02:53:56 +0900 (JST)
Subject: [ruby-changes:12249] Ruby:r23939 (trunk): * time.c (find_time_t): time guess strategy refined again.
akr 2009-07-03 02:53:21 +0900 (Fri, 03 Jul 2009) New Revision: 23939 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=23939 Log: * time.c (find_time_t): time guess strategy refined again. Modified files: trunk/ChangeLog trunk/time.c Index: time.c =================================================================== --- time.c (revision 23938) +++ time.c (revision 23939) @@ -1860,31 +1860,38 @@ DIV(tm_year+299,400))*86400; } -#ifdef FIND_TIME_NUMGUESS +#if 0 +#define DEBUG_FIND_TIME_NUMGUESS +#define DEBUG_REPORT_GUESSRANGE fprintf(stderr, "find time guess range: %ld - %ld : %lu\n", guess_lo, guess_hi, (unsigned_time_t)(guess_hi-guess_lo)) +#endif + +#ifndef DEBUG_REPORT_GUESSRANGE +#define DEBUG_REPORT_GUESSRANGE +#endif + +#ifdef DEBUG_FIND_TIME_NUMGUESS +#define DEBUG_FIND_TIME_NUMGUESS_INC find_time_numguess++, static unsigned long long find_time_numguess; static VALUE find_time_numguess_getter(void) { return ULL2NUM(find_time_numguess); } +#else +#define DEBUG_FIND_TIME_NUMGUESS_INC #endif static const char * find_time_t(struct tm *tptr, int utc_p, time_t *tp) { - time_t guess, guess_lo, guess_hi; + time_t guess, guess0, guess_lo, guess_hi; struct tm *tm, tm_lo, tm_hi; int d; int find_dst; struct tm result; - int try_interpolation; - unsigned long range = 0; + int status; -#ifdef FIND_TIME_NUMGUESS -#define GUESS(p) (find_time_numguess++, (utc_p ? gmtime_with_leapsecond(p, &result) : LOCALTIME(p, result))) -#else -#define GUESS(p) (utc_p ? gmtime_with_leapsecond(p, &result) : LOCALTIME(p, result)) -#endif +#define GUESS(p) (DEBUG_FIND_TIME_NUMGUESS_INC (utc_p ? gmtime_with_leapsecond(p, &result) : LOCALTIME(p, result))) find_dst = 0 < tptr->tm_isdst; @@ -1897,7 +1904,8 @@ (time_t)((unsigned_time_t)~(time_t)0 >> 1) : ~(time_t)0; - guess = timegm_noleapsecond(tptr); + DEBUG_REPORT_GUESSRANGE; + guess0 = guess = timegm_noleapsecond(tptr); tm = GUESS(&guess); if (tm) { d = tmcmp(tptr, tm); @@ -1910,6 +1918,7 @@ guess_lo = guess; guess += 24 * 60 * 60; } + DEBUG_REPORT_GUESSRANGE; if (guess_lo < guess && guess < guess_hi && (tm = GUESS(&guess)) != NULL) { d = tmcmp(tptr, tm); if (d == 0) { goto found; } @@ -1917,6 +1926,7 @@ guess_hi = guess; else guess_lo = guess; + DEBUG_REPORT_GUESSRANGE; } } @@ -1934,106 +1944,36 @@ if (d == 0) { guess = guess_hi; goto found; } tm_hi = *tm; - try_interpolation = 1; + DEBUG_REPORT_GUESSRANGE; - while (guess_lo + 1 < guess_hi) { - if (try_interpolation == 1) { - int a, b; - /* there is a gap between guess_lo and guess_hi. */ - range = 0; - /* - Try precious guess by a linear interpolation at first. - `a' and `b' is a coefficient of guess_lo and guess_hi as: + status = 1; - guess = (guess_lo * a + guess_hi * b) / (a + b) - - However this causes overflow in most cases, following assignment - is used instead: - - guess = guess_lo / d * a + (guess_lo % d) * a / d - + guess_hi / d * b + (guess_hi % d) * b / d - where d = a + b - - To avoid overflow in this assignment, `d' is restricted to less than - sqrt(2**31). By this restriction and other reasons, the guess is - not accurate and some error is expected. `range' approximates - the maximum error. - - When these parameters are not suitable, i.e. guess is not within - guess_lo and guess_hi, simple guess by binary search is used. - */ - range = 366 * 24 * 60 * 60; - a = (tm_hi.tm_year - tptr->tm_year); - b = (tptr->tm_year - tm_lo.tm_year); - /* 46000 is selected as `some big number less than sqrt(2**31)'. */ - if (a + b <= 46000 / 12) { - range = 31 * 24 * 60 * 60; - a *= 12; - b *= 12; - a += tm_hi.tm_mon - tptr->tm_mon; - b += tptr->tm_mon - tm_lo.tm_mon; - if (a + b <= 46000 / 31) { - range = 24 * 60 * 60; - a *= 31; - b *= 31; - a += tm_hi.tm_mday - tptr->tm_mday; - b += tptr->tm_mday - tm_lo.tm_mday; - if (a + b <= 46000 / 24) { - range = 60 * 60; - a *= 24; - b *= 24; - a += tm_hi.tm_hour - tptr->tm_hour; - b += tptr->tm_hour - tm_lo.tm_hour; - if (a + b <= 46000 / 60) { - range = 60; - a *= 60; - b *= 60; - a += tm_hi.tm_min - tptr->tm_min; - b += tptr->tm_min - tm_lo.tm_min; - if (a + b <= 46000 / 60) { - range = 1; - a *= 60; - b *= 60; - a += tm_hi.tm_sec - tptr->tm_sec; - b += tptr->tm_sec - tm_lo.tm_sec; - } - } - } - } - } - if (a <= 0) a = 1; - if (b <= 0) b = 1; - d = a + b; - /* - Although `/' and `%' may produce unexpected result with negative - argument, it doesn't cause serious problem because there is a - fail safe. - */ - guess = guess_lo / d * a + (guess_lo % d) * a / d - + guess_hi / d * b + (guess_hi % d) * b / d; - try_interpolation = 2; - } - else if (try_interpolation == 2) { - guess = guess - range; - range = 0; - try_interpolation = 1; - } - else if (try_interpolation == 3) { - guess = guess + range; - range = 0; - try_interpolation = 1; - } - - if (try_interpolation == 0 || guess <= guess_lo || guess_hi <= guess) { - /* Precious guess is invalid. try binary search. */ + while (guess_lo + 1 < guess_hi) { + if (status == 0) { + binsearch: guess = guess_lo / 2 + guess_hi / 2; if (guess <= guess_lo) guess = guess_lo + 1; else if (guess >= guess_hi) guess = guess_hi - 1; - range = 0; - try_interpolation = 1; + status = 1; } + else { + if (status == 1) { + time_t guess0_hi = timegm_noleapsecond(&tm_hi); + guess = guess_hi - (guess0_hi - guess0); + status = 2; + } + else if (status == 2) { + time_t guess0_lo = timegm_noleapsecond(&tm_lo); + guess = guess_lo + (guess0 - guess0_lo); + status = 0; + } + if (guess <= guess_lo || guess_hi <= guess) { + /* Precious guess is invalid. try binary search. */ + goto binsearch; + } + } tm = GUESS(&guess); if (!tm) goto error; @@ -2041,24 +1981,14 @@ d = tmcmp(tptr, tm); if (d < 0) { - if (range) - try_interpolation = 2; - else if ((unsigned_time_t)(guess-guess_lo) > (unsigned_time_t)(guess_hi-guess)) - try_interpolation = 0; - else - try_interpolation = 1; guess_hi = guess; tm_hi = *tm; + DEBUG_REPORT_GUESSRANGE; } else if (d > 0) { - if (range) - try_interpolation = 3; - else if ((unsigned_time_t)(guess-guess_lo) < (unsigned_time_t)(guess_hi-guess)) - try_interpolation = 0; - else - try_interpolation = 1; guess_lo = guess; tm_lo = *tm; + DEBUG_REPORT_GUESSRANGE; } else { found: @@ -3831,7 +3761,7 @@ rb_define_method(rb_cTime, "marshal_load", time_mload, 1); #endif -#ifdef FIND_TIME_NUMGUESS +#ifdef DEBUG_FIND_TIME_NUMGUESS rb_define_virtual_variable("$find_time_numguess", find_time_numguess_getter, NULL); #endif } Index: ChangeLog =================================================================== --- ChangeLog (revision 23938) +++ ChangeLog (revision 23939) @@ -1,3 +1,7 @@ +Fri Jul 3 02:52:20 2009 Tanaka Akira <akr@f...> + + * time.c (find_time_t): time guess strategy refined again. + Fri Jul 3 00:36:16 2009 Tanaka Akira <akr@f...> * time.c (find_time_t): time guess strategy refined. -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/