Bug 25442 - TimeZoneInfo.GetApplicableRule() uses an O(N) search
Summary: TimeZoneInfo.GetApplicableRule() uses an O(N) search
Status: RESOLVED FIXED
Alias: None
Product: Class Libraries
Classification: Mono
Component: System ()
Version: 3.8.0
Hardware: PC Linux
: --- normal
Target Milestone: Untriaged
Assignee: Bugzilla
URL:
Depends on:
Blocks:
 
Reported: 2014-12-16 18:26 UTC by Craig Minihan
Modified: 2014-12-17 02:30 UTC (History)
2 users (show)

Tags:
Is this bug a regression?: ---
Last known good build:

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.


Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:
Status:
RESOLVED FIXED

Description Craig Minihan 2014-12-16 18:26:47 UTC
Using --profile on JSON.NET serializing CLR objects with DateTime members shows that TimeZoneInfo.GetUtcOffset() takes a significant amount of processing time. Within GetUtcOffset() the call to the private GetApplicableRule() shows O(N) search performance against the private member field adjustmentRules.

Making GetApplicableRule() public and calling directly in the following code:

public static void Main(string[] args)
{
    var time = new DateTime(2040, 12, 1);

    var timer = new Stopwatch();
    timer.Start();

    for (int i = 0; i < 100000; i++)
    {
        TimeZoneInfo.Local.GetApplicableRule(time);
    }

    timer.Stop();
    Console.WriteLine("time={0}ms", timer.ElapsedMilliseconds);
}

Results: where the year is 1940 the runtime is ~70ms, when the year is 2040 the runtime is 5000ms.

When processing large JSON documents the number of calls to this method can get very large causing serious performance degradation.
Comment 1 Craig Minihan 2014-12-16 19:32:22 UTC
The main time hog is the date.Date property call inside the GetApplicableRule() foreach loop. The value never changes and can be moved to a local var. Making this change yields an approx 10x performance boost.
Comment 2 Craig Minihan 2014-12-16 20:35:19 UTC
Submitted fix in PR1462. I've simply moved the .Date property access outside the foreach which improves performance by 10x as noted above.
Comment 3 marcos.henrich 2014-12-17 02:30:42 UTC
Thank you for the bug report and especially for the PR.

Merged in master d4a2bab840ef99b744c9494a9fac8da4a24d43a8.
https://github.com/mono/mono/commit/d4a2bab840ef99b744c9494a9fac8da4a24d43a8