Repository: dateutil/dateutil (Python)

Issue:
Add LRU cache to gettz and factories
Now that #635 is resolved, `gettz`, `tzoffset` and `tzstr` satisfies the property that two `tzinfo` objects (`tz1` and `tz2`) constructed with identical arguments will always be the same object (`tz1` is `tz2`), but the cached objects expire whenever no instances of a given timezone exist outside of the cache. This satisfies the "timezone semantics" reasons for adding a cache and will have good performance characteristics so long as at least one object holds a strong reference to the time zone.

But this *does* sacrifice performance for people who would prefer a cache because they are creating the same object over and over again even though it goes out of scope every time, so for example:

```python
def NY_timestamp(dt):
    dt.astimezone(tz.gettz('America/New_York')
    return dt.timestamp()

a = []
for i in range(10000):
    a.append(NY_timestamp(datetime.now()))
```

I think the above would needlessly create 10000 copies of `tz.gettz('America/New_York')`, when even a modest LRU cache would save the trouble.

I think we should leave the `_instances` dictionary as a `WeakValueDictionary` and add a second `_lru_cache` dictionary that holds a limited (and configurable) number of strong references to used time zones. Not sure the best implementation of the cache itself, preferably something where left-append, right-pop and reordering a single element are all O(1), so I think something implemented with a doubly-linked list (maybe `OrderedDict`).

Presumably we can take some cues from the implementation of [`functools.lru_cache`](https://github.com/python/cpython/blob/master/Lib/functools.py#L445), but keep in mind that the Python implementation may not have amazing performance, since CPython has a C implementation and may not have spent much time optimizing the Python implementation.


Hints:
I'd like to work on this.

Patch:
diff --git a/dateutil/tz/_factories.py b/dateutil/tz/_factories.py
--- a/dateutil/tz/_factories.py
+++ b/dateutil/tz/_factories.py
@@ -1,5 +1,7 @@
 from datetime import timedelta
 import weakref
+from collections import OrderedDict
+
 
 class _TzSingleton(type):
     def __init__(cls, *args, **kwargs):
@@ -11,6 +13,7 @@ def __call__(cls):
             cls.__instance = super(_TzSingleton, cls).__call__()
         return cls.__instance
 
+
 class _TzFactory(type):
     def instance(cls, *args, **kwargs):
         """Alternate constructor that returns a fresh instance"""
@@ -20,6 +23,8 @@ def instance(cls, *args, **kwargs):
 class _TzOffsetFactory(_TzFactory):
     def __init__(cls, *args, **kwargs):
         cls.__instances = weakref.WeakValueDictionary()
+        cls.__strong_cache = OrderedDict()
+        cls.__strong_cache_size = 8
 
     def __call__(cls, name, offset):
         if isinstance(offset, timedelta):
@@ -31,12 +36,22 @@ def __call__(cls, name, offset):
         if instance is None:
             instance = cls.__instances.setdefault(key,
                                                   cls.instance(name, offset))
+
+        cls.__strong_cache[key] = cls.__strong_cache.pop(key, instance)
+
+        # Remove an item if the strong cache is overpopulated
+        # TODO: Maybe this should be under a lock?
+        if len(cls.__strong_cache) > cls.__strong_cache_size:
+            cls.__strong_cache.popitem(last=False)
+
         return instance
 
 
 class _TzStrFactory(_TzFactory):
     def __init__(cls, *args, **kwargs):
         cls.__instances = weakref.WeakValueDictionary()
+        cls.__strong_cache = OrderedDict()
+        cls.__strong_cache_size = 8
 
     def __call__(cls, s, posix_offset=False):
         key = (s, posix_offset)
@@ -45,5 +60,14 @@ def __call__(cls, s, posix_offset=False):
         if instance is None:
             instance = cls.__instances.setdefault(key,
                 cls.instance(s, posix_offset))
+
+        cls.__strong_cache[key] = cls.__strong_cache.pop(key, instance)
+
+
+        # Remove an item if the strong cache is overpopulated
+        # TODO: Maybe this should be under a lock?
+        if len(cls.__strong_cache) > cls.__strong_cache_size:
+            cls.__strong_cache.popitem(last=False)
+
         return instance
 
diff --git a/dateutil/tz/tz.py b/dateutil/tz/tz.py
--- a/dateutil/tz/tz.py
+++ b/dateutil/tz/tz.py
@@ -14,6 +14,7 @@
 import os
 import bisect
 import weakref
+from collections import OrderedDict
 
 import six
 from six import string_types
@@ -1538,6 +1539,8 @@ class GettzFunc(object):
         def __init__(self):
 
             self.__instances = weakref.WeakValueDictionary()
+            self.__strong_cache_size = 8
+            self.__strong_cache = OrderedDict()
             self._cache_lock = _thread.allocate_lock()
 
         def __call__(self, name=None):
@@ -1556,12 +1559,27 @@ def __call__(self, name=None):
                         # We also cannot store weak references to None, so we
                         # will also not store that.
                         self.__instances[name] = rv
+                    else:
+                        # No need for strong caching, return immediately
+                        return rv
+
+                self.__strong_cache[name] = self.__strong_cache.pop(name, rv)
+
+                if len(self.__strong_cache) > self.__strong_cache_size:
+                    self.__strong_cache.popitem(last=False)
 
             return rv
 
+        def set_cache_size(self, size):
+            with self._cache_lock:
+                self.__strong_cache_size = size
+                while len(self.__strong_cache) > size:
+                    self.__strong_cache.popitem(last=False)
+
         def cache_clear(self):
             with self._cache_lock:
                 self.__instances = weakref.WeakValueDictionary()
+                self.__strong_cache.clear()
 
         @staticmethod
         def nocache(name=None):


Test patch:
diff --git a/dateutil/test/test_tz.py b/dateutil/test/test_tz.py
--- a/dateutil/test/test_tz.py
+++ b/dateutil/test/test_tz.py
@@ -746,7 +746,15 @@ def test_tzoffset_weakref():
     del UTC1
     gc.collect()
 
-    assert UTC_ref() is None
+    assert UTC_ref() is not None    # Should be in the strong cache
+    assert UTC_ref() is tz.tzoffset('UTC', 0)
+
+    # Fill the strong cache with other items
+    for offset in range(5,15):
+        tz.tzoffset('RandomZone', offset)
+
+    gc.collect()
+    assert UTC_ref() is  None
     assert UTC_ref() is not tz.tzoffset('UTC', 0)
 
 
@@ -1106,12 +1114,33 @@ def test_gettz_cache_clear():
 
     assert NYC1 is not NYC2
 
+@pytest.mark.gettz
+@pytest.mark.xfail(IS_WIN, reason='zoneinfo separately cached')
+def test_gettz_set_cache_size():
+    tz.gettz.cache_clear()
+    tz.gettz.set_cache_size(3)
+
+    MONACO_ref = weakref.ref(tz.gettz('Europe/Monaco'))
+    EASTER_ref = weakref.ref(tz.gettz('Pacific/Easter'))
+    CURRIE_ref = weakref.ref(tz.gettz('Australia/Currie'))
+
+    gc.collect()
+
+    assert MONACO_ref() is not None
+    assert EASTER_ref() is not None
+    assert CURRIE_ref() is not None
+
+    tz.gettz.set_cache_size(2)
+    gc.collect()
+
+    assert MONACO_ref() is None
 
 @pytest.mark.xfail(IS_WIN, reason="Windows does not use system zoneinfo")
 @pytest.mark.smoke
 @pytest.mark.gettz
 def test_gettz_weakref():
     tz.gettz.cache_clear()
+    tz.gettz.set_cache_size(2)
     NYC1 = tz.gettz('America/New_York')
     NYC_ref = weakref.ref(tz.gettz('America/New_York'))
 
@@ -1120,9 +1149,17 @@ def test_gettz_weakref():
     del NYC1
     gc.collect()
 
-    assert NYC_ref() is None
-    assert tz.gettz('America/New_York') is not NYC_ref()
+    assert NYC_ref() is not None        # Should still be in the strong cache
+    assert tz.gettz('America/New_York') is NYC_ref()
+
+    # Populate strong cache with other timezones
+    tz.gettz('Europe/Monaco')
+    tz.gettz('Pacific/Easter')
+    tz.gettz('Australia/Currie')
 
+    gc.collect()
+    assert NYC_ref() is None    # Should have been pushed out
+    assert tz.gettz('America/New_York') is not NYC_ref()
 
 class ZoneInfoGettzTest(GettzTest, WarningTestMixin):
     def gettz(self, name):
@@ -1462,6 +1499,13 @@ def test_tzstr_weakref():
     del tz_t1
     gc.collect()
 
+    assert tz_t2_ref() is not None
+    assert tz.tzstr('EST5EDT') is tz_t2_ref()
+
+    for offset in range(5,15):
+        tz.tzstr('GMT+{}'.format(offset))
+    gc.collect()
+
     assert tz_t2_ref() is None
     assert tz.tzstr('EST5EDT') is not tz_t2_ref()