TimeZone Initialization SLOW

Topics: Developer Forum, Project Management Forum, User Forum
Sep 30, 2007 at 10:48 PM
Hi,

I've noticed that the method PublicDomain.TzTimeZone.InitializeZones() (lines 876 - 5349) is incredibly slow. The good news is that it doesn't seem to be reading from the "tzdata" files. I understand the value of loading timezone information for 556 timezones. However, it takes about 4.5 seconds to do so. It's great that it's only 0.00809352 seconds to load each timezone. However, when n = 556, that's a long time. I've thought about a few options to replace the "monolitich static initialization" of these timezones.

1. Somehow complile the objects at runtime into Machine Source Code. And then, we can hard bake those objects into a resource file.
2. A hashtable might be faster for access, instead of a Dictionary or List.
3. Maybe load a sub-set of these. (30 or so, perhaps), and then the user could load multiple subsets?
4. Maybe a Config file could allow the user to enable or disable timzeones or subsets?
5. Or, what about ON-DEMAND? -- That might even be faster.
5a. You could say, something like "IsInitialized"? -- No? Then, spend the 0.008 seconds to initialize it.
5b. Unless you're printing out a list of all the world timezones, you probably don't need ALL 556.

Thoughts?
Lawrence
Oct 9, 2007 at 5:07 PM
I agree that the initialization should be lazy since most apps don't need ALL timezones. :)

Can Kevin Grigorenko please comment?

Thanks.

James.


LDawggie wrote:
Hi,

I've noticed that the method PublicDomain.TzTimeZone.InitializeZones() (lines 876 - 5349) is incredibly slow. The good news is that it doesn't seem to be reading from the "tzdata" files. I understand the value of loading timezone information for 556 timezones. However, it takes about 4.5 seconds to do so. It's great that it's only 0.00809352 seconds to load each timezone. However, when n = 556, that's a long time. I've thought about a few options to replace the "monolitich static initialization" of these timezones.

1. Somehow complile the objects at runtime into Machine Source Code. And then, we can hard bake those objects into a resource file.
2. A hashtable might be faster for access, instead of a Dictionary or List.
3. Maybe load a sub-set of these. (30 or so, perhaps), and then the user could load multiple subsets?
4. Maybe a Config file could allow the user to enable or disable timzeones or subsets?
5. Or, what about ON-DEMAND? -- That might even be faster.
5a. You could say, something like "IsInitialized"? -- No? Then, spend the 0.008 seconds to initialize it.
5b. Unless you're printing out a list of all the world timezones, you probably don't need ALL 556.

Thoughts?
Lawrence

Coordinator
Oct 10, 2007 at 12:19 PM
Edited Oct 10, 2007 at 12:22 PM
Hey James & Lawrence,

Sorry for the late response, I got caught up in vacation and work, and codeplex doesn't tell me when there are new conversations. Alas.

I knew this issue would end up hitting a lot of people when I did it, and I think a healthy debate is great. First, let me just clarify one aspect of how it works. The TzTimeZone static initialization code is only run if your code itself references the TzTimeZone class. Static initialization is all done lazily by .NET, so if you are referencing PublicDomain (for example, for some other part of it), and you don't access TzTimeZone, then you will not be hit by this initialization time.

Here are my thoughts on your suggestions:

#1: I'm not sure what you mean by compiling the objects at runtime into Machine code. I think you mean JIT compiling by this, and this can be done by running NGEN on PublicDomain.dll in the GAC. This may significantly help performance, although I haven't tried it yet. If you do try it, please let me know what you find.

#2: The main access is done by a Hashtable, keying off of the time zone name. Here, Zones is a Dictionary:

public static TzTimeZone GetTimeZone(string tzName)
        {
            TzTimeZone result = null;
            TzZoneInfo zoneInfo;
            if (Zones.TryGetValue(tzName, out zoneInfo))
            {
                result = new TzTimeZone(zoneInfo);
            }
            return result;
        }

#3: I'm a bit worried about this from a user perspective -- do you mean that a user would specify before hand that only certain zones are loaded at first, but then they would have to manually load the rest by some call such as TzTimeZone.Load("subset name") before any access of a "non-popular" time zone? I wouldn't want to put this onus on the user of the code.

#4: This is interesting -- some way to say, "I'll never use these X time zones, so don't bother loading them." The only problem is, let's say for example that you parse a Date time from the web somewhere which has a timezone of some random country, if you didn't load that time zone since you never thought you would use it, then there would be a nasty exception.

#5a: I believe this is what is happening now. The first time you use TzTimeZone, it sparks the static initialization, so it is the same as checking if it was Initialized or not.

#5b: See my answer to #4

So, now let me try to think of this problem a bit more deeply than I had...

The reason static initialization is so "brute force" in loading all time zones is really just for thread safety. Static initialization is inherently single threaded, and so I can be sure that I can safely load all time zone data in one shot.

The alternative would be to take it out of static initialization and add locks to any code that accesses the Zones Dictionary. I wanted to avoid this because it will add bottlenecks to multi-threaded code, such as websites. Now, truthfully, time zone data, in most cases, will not be such a contentious thing, so that is probably not a big deal.

So, I'm okay with removing the "full load" out of static initialization, and instead lazily loading only the time zones used at runtime. The next question is how to do this. At runtime, the user will pass the zone name that they want (e.g. America/New_York to TzTimeZone.GetTimeZone), so now we have to generate this data out of thin air. We could compile into the code something like:

public static TzTimeZone GetTimeZone(string tzName)
        {
            TzTimeZone result = null;
            TzZoneInfo zoneInfo;
            lock (zonesLock)
            {
                 if (Zones.TryGetValue(tzName, out zoneInfo))
                 {
                     result = new TzTimeZone(zoneInfo);
                 }
                 else
                 {
                        // Auto-generated code
                        int nameHash = tzName.GetHashCode();
                        switch (nameHash)
                        {
                              case 0:
                                   // load first of 556 time zones
                              case 1:
                                   // load second of 556 time zones
                              // etc.
                        }
                 }
            }
            return result;
        }

The only issue I see here is that .NET will probably still JIT that entire function (unless NGEN is run on it) the first time it's hit, so that will be a significant "initialization time." Also, it could be up to 556 integer comparisons, plus switch overhead, which isn't too bad.

Do either of you have any ideas on how to implement this?

Thanks,
Kevin
Coordinator
Oct 10, 2007 at 2:10 PM
Hey Guys, good news. I tested this change from static initialization to runtime lazy loading, and the performance is incredibly better (as well as memory usage). Please try out the latest 0.2.27.0 release and let me know if it solves your performance issues:

http://www.codeplex.com/publicdomain/Release/ProjectReleases.aspx?ReleaseId=7632

Thanks for your feedback!
Kevin
Oct 10, 2007 at 4:04 PM
RE: Locks
Since initialization is only ONCE per TZ, and most access is READ only, you should consider using System.Threading.ReadWriterLock instead of the simpler lock(){} statement (based on System.Threading.Monitor).

I am only assuming that you are using lock(){} based on your comment as I have not downloaded the source for 0.2.27.0. :P

I will check out your changes once the source is available. :)

Thanks for responding to our requests!

James.
Oct 10, 2007 at 8:41 PM
Just read the code. And it looks like it would benefit from using ReaderWriterLock. lock(){} would punish most readers and make them serialize their access to the TZ they want.

ReaderWriterLock allows readers to access the data concurrently, and make the writer wait. When the writer writes, all readers will have to wait. Since writes are rare in this case, ReaderWriterLock is perfect for this. :)
Coordinator
Oct 10, 2007 at 10:20 PM

jang wrote:
Just read the code. And it looks like it would benefit from using ReaderWriterLock. lock(){} would punish most readers and make them serialize their access to the TZ they want.

ReaderWriterLock allows readers to access the data concurrently, and make the writer wait. When the writer writes, all readers will have to wait. Since writes are rare in this case, ReaderWriterLock is perfect for this. :)


Hi jang, very good point, so instead of:

lock (s_zonesLock)
            {
                if (Zones.TryGetValue(tzName, out zoneInfo))
                {
                    result = new TzTimeZone(zoneInfo);
                }
                else
                {
                    // No zone found in the cache, lazily load it
                    int hash = tzName.GetHashCode();
                    switch (hash)
                    {

The following:

            ReaderWriterLock zonesLock = new ReaderWriterLock();
            try
            {
                zonesLock.AcquireReaderLock(-1);
 
                if (Zones.TryGetValue(tzName, out zoneInfo))
                {
                    result = new TzTimeZone(zoneInfo);
                }
                else
                {
                    LockCookie? writerCookie = null;
 
                    try
                    {
                        writerCookie = zonesLock.UpgradeToWriterLock(-1);
 
                        // No zone found in the cache, lazily load it
                        int hash = tzName.GetHashCode();
                        switch (hash)
                        {
                            #region Time Zone lookup
 
 
                            #endregion
                        }
 
                        if (zoneInfo != null)
                        {
                            // Found the time zone
                            result = new TzTimeZone(zoneInfo);
                            s_zones[tzName] = zoneInfo;
                        }
                    }
                    finally
                    {
                        if (writerCookie != null)
                        {
                            LockCookie cookie = writerCookie.Value;
                            zonesLock.DowngradeFromWriterLock(ref cookie);
                        }
                    }
                }
            }
            finally
            {
                zonesLock.ReleaseLock();
            }

Thanks for your help,
Kevin
Oct 11, 2007 at 4:38 AM
Kevin,

You should not be instantiating a new ReaderWriterLock every time your method is called.

The other thing you should do is perform another check once the writer lock has been obtained. ReaderWriterLock does not guarantee FIFO.

Check out the patch I submitted earlier today.

James.
Coordinator
Oct 11, 2007 at 11:24 PM
Hi jang,

Do you mean there should be a static ReaderWriterLock instance?

I tried unzipping your patch but 7g said that it was corrupt -- are you able to download and open from http://www.codeplex.com/publicdomain/Project/Download/FileDownload.aspx?DownloadId=20036

By the way, I'm feeling this speed boost in my application already! I don't know why I was so focused on the micro-optimization of static initialization which does not nearly hit the critical path of user usage (including my own!). The ReaderWriterLock makes it even more appealing, although what is the overhead of it compared to whatever is the underlying mechanism/semaphore of the lock statement?

Thanks,
Kevin
Coordinator
Oct 12, 2007 at 2:31 AM
Not sure if your patch contained anything else or not as I cannot see it yet, but I think I've at least got the ReaderWriterLock correct now:

s_zonesLock.AcquireReaderLock(-1);
 
            try
            {
                if (Zones.TryGetValue(tzName, out zoneInfo))
                {
                    result = new TzTimeZone(zoneInfo);
                }
                else
                {
                    LockCookie writerCookie = s_zonesLock.UpgradeToWriterLock(-1);
 
                    try
                    {
                        if (Zones.TryGetValue(tzName, out zoneInfo))
                        {
                            result = new TzTimeZone(zoneInfo);
                        }
                        else
                        {
                             ...
                        }
                    }
                    finally
                    {
                        s_zonesLock.DowngradeFromWriterLock(ref writerCookie);
                    }
                }
            }
            finally
            {
                s_zonesLock.ReleaseReaderLock();
            }
 

Right?

Thanks,
Kevin
Oct 12, 2007 at 4:31 PM
Kevin,

Your use of ReaderWriterLock looks correct now. =)

FYI, I have emailed the same 7zip archive to your GMail account but it appears that your changes are better (TryGetValue vs. ContainsKey + Actual Get). =)

The only minor thing I would ask that you do is to use System.Threading.Timeout.Infinite instead of "-1" since it reads better and also better documents your intent. :)

Thanks.

James.
Oct 12, 2007 at 4:36 PM
Forgot to answer your System.Threading.Monitor vs. System.Threading.ReaderWriterLock question.

lock(){} uses System.Threading.Monitor.

Overhead differences? I think lock(){} has less setup overhead but overall performance, ReaderWriterLock is much better when most of the accesses are reads. It does have a higher penalty for writers since a writer has to wait for all readers before it to be done before a writer can write. I believe the algorithm in ReaderWriterLock addresses the fairness issue by having some sort of queue to guarantee the execution of a writer.

In this PublicDomain's specific case, ReaderWriterLock is much more suitable than Monitor lock.

Thanks.

James.