Improve DST offset computation performance.

src/date-delay.js

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 97 matching lines @@
   return FromJulianDay(Day(time) + kDayZeroInJulianDay).date;
 }
 
 
 // ECMA 262 - 15.9.1.9
 function EquivalentYear(year) {
   // Returns an equivalent year in the range [2008-2035] matching
   // - leap year.
   // - week day of first day.
   var time = TimeFromYear(year);
-  var recent_year = (InLeapYear(time) == 0 ? 1967 : 1956) + 
+  var recent_year = (InLeapYear(time) == 0 ? 1967 : 1956) +
       (WeekDay(time) * 12) % 28;
   // Find the year in the range 2008..2037 that is equivalent mod 28.
   // Add 3*28 to give a positive argument to the modulus operator.
   return 2008 + (recent_year + 3*28 - 2008) % 28;
 }
 
 
 function EquivalentTime(t) {
   // The issue here is that some library calls don't work right for dates
   // that cannot be represented using a non-negative signed 32 bit integer
   // (measured in whole seconds based on the 1970 epoch).
   // We solve this by mapping the time to a year with same leap-year-ness
   // and same starting day for the year.  The ECMAscript specification says
-  // we must do this, but for compatability with other browsers, we use
+  // we must do this, but for compatibility with other browsers, we use
   // the actual year if it is in the range 1970..2037
   if (t >= 0 && t <= 2.1e12) return t;
   var day = MakeDay(EquivalentYear(YearFromTime(t)), MonthFromTime(t), DateFromTime(t));
   return TimeClip(MakeDate(day, TimeWithinDay(t)));
 }
 
-var daylight_cache_time = $NaN;
-var daylight_cache_offset;
+
+// Because computing the DST offset is a pretty expensive operation
+// we keep a cache of last computed offset along with a time interval
+// where we know the cache is valid.
+var DST_offset_cache = {
+  // Cached DST offset.
+  offset: 0,
+  // Time interval where the cached offset is valid.
+  start: 0, end: -1,
+  // Size of next interval expansion.
+  increment: 0
+};
+
 
 function DaylightSavingsOffset(t) {

[William Hesse, 2009/06/16 07:11:29]

Comment the function to state that the algorithm is valid as long as the
daylight savings offset does not change from value A to B, then back to A,
within any one month period.

Won't this cause a problem with laptops and mobile devices?  Do we have any way
of getting notified when the system time settings change?  Otherwise,
long-running javascript may go nuts.  I think it is quite possible for a web
page to stay open while the user adjusts the time zone.

-  if (t == daylight_cache_time) {
-    return daylight_cache_offset;
+  // Load the cache object from the builtins object.
+  var cache = DST_offset_cache;
+
+  // Cache the start and the end in local variables for fast access.
+  var start = cache.start;
+  var end = cache.end;
+
+  if (start <= t) {
+    // If the time fits in the cached interval, return the cached offset.
+    if (t <= end) return cache.offset;
+
+    // Compute a possible new interval end.
+    var new_end = end + cache.increment;
+
+    if (t <= new_end) {
+      var end_offset = %DateDaylightSavingsOffset(EquivalentTime(new_end));
+      if (cache.offset == end_offset) {
+        // If the offset at the end of the new interval still matches
+        // the offset in the cache, we grow the cached time interval
+        // and return the offset.
+        cache.end = new_end;
+        cache.increment = msPerMonth;
+        return end_offset;
+      } else {
+        var offset = %DateDaylightSavingsOffset(EquivalentTime(t));
+        if (offset == end_offset) {
+          // The offset at the given time is equal to the offset at the
+          // new end of the interval, so that means that we've just skipped
+          // the point in time where the DST offset change occurred. Updated
+          // the interval to reflect this and reset the increment.
+          cache.start = t;
+          cache.end = new_end;
+          cache.increment = msPerMonth;
+        } else {
+          // The interval contains a DST offset change and the given time is
+          // before it. Adjust the increment to avoid a linear search for
+          // the offset change point and change the end of the interval.
+          cache.increment /= 3;
+          cache.end = t;
+        }
+        // Update the offset in the cache and return it.
+        cache.offset = offset;
+        return offset;
+      }
+    }
   }
+
+  // Compute the DST offset for the time and shrink the cache interval
+  // to only contain the time. This allows fast repeated DST offset
+  // computations for the same time.
   var offset = %DateDaylightSavingsOffset(EquivalentTime(t));
-  daylight_cache_time = t;
-  daylight_cache_offset = offset;
+  cache.offset = offset;
+  cache.start = cache.end = t;
+  cache.increment = msPerMonth;
   return offset;
 }
 
 
 var timezone_cache_time = $NaN;
 var timezone_cache_timezone;
 
 function LocalTimezone(t) {
-  if(t == timezone_cache_time) {
+  if (t == timezone_cache_time) {
     return timezone_cache_timezone;
   }
   var timezone = %DateLocalTimezone(EquivalentTime(t));
   timezone_cache_time = t;
   timezone_cache_timezone = timezone;
   return timezone;
 }
 
 
 function WeekDay(time) {
@@ skipping 895 matching lines @@
     "toGMTString", DateToGMTString,
     "toUTCString", DateToUTCString,
     "getYear", DateGetYear,
     "setYear", DateSetYear,
     "toISOString", DateToISOString,
     "toJSON", DateToJSON
   ));
 }
 
 SetupDate();