qtimezoneprivate_tz: Apply a cache over the top of timezone data

Constantly re-reading the timezone information only to be told the exact
same thing is wildly expensive, which can hurt in operations that cause
a lot of QTimeZone creation, for example, V4's DateObject - which
creates them a lot (in DaylightSavingTA).

This performance problem was identified when I noticed that a
QDateTime binding updated once per frame was causing >100% CPU usage
(on a desktop!) thanks to a QtQuickControls 1 Calendar (which has a
number of bindings to the date's properties like getMonth() and so
on).

The newly added tst_QTimeZone::systemTimeZone benchmark gets a ~90%
decrease in instruction count:

--- before
+++ after
 PASS   : tst_QTimeZone::systemTimeZone()
 RESULT : tst_QTimeZone::systemTimeZone():
-     0.024 msecs per iteration (total: 51, iterations: 2048)
+     0.0036 msecs per iteration (total: 59, iterations: 16384)

Also impacted (over in QDateTime) is
tst_QDateTime::setMSecsSinceEpochTz(). The results here are - on the
surface - less impressive (~0.17% drop), however, it isn't even
creating QTimeZone on a hot path to begin with, so a large drop would
have been a surprise.

Added several further benchmarks to cover non-system zones and
traverse transitions.

Done-With: Edward Welbourne <edward.welbourne@qt.io>
Task-number: QTBUG-75585
Change-Id: I044a84fc2d3a2dc965f63cd3a3299fc509750bf7
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

2 files changed, 100 insertions, 57 deletions

diff --git a/src/corelib/time/qtimezoneprivate_p.h b/src/corelib/time/qtimezoneprivate_p.h
index 5f6491ef81..c3e9064b8c 100644
--- a/src/corelib/time/qtimezoneprivate_p.h
+++ b/src/corelib/time/qtimezoneprivate_p.h
@@ -287,6 +287,16 @@ Q_DECL_CONSTEXPR inline bool operator==(const QTzTransitionRule &lhs, const QTzT
 Q_DECL_CONSTEXPR inline bool operator!=(const QTzTransitionRule &lhs, const QTzTransitionRule &rhs) noexcept
 { return !operator==(lhs, rhs); }
 
+// These are stored separately from QTzTimeZonePrivate so that they can be
+// cached, avoiding the need to re-parse them from disk constantly.
+struct QTzTimeZoneCacheEntry
+{
+    QVector<QTzTransitionTime> m_tranTimes;
+    QVector<QTzTransitionRule> m_tranRules;
+    QList<QByteArray> m_abbreviations;
+    QByteArray m_posixRule;
+};
+
 class Q_AUTOTEST_EXPORT QTzTimeZonePrivate final : public QTimeZonePrivate
 {
     QTzTimeZonePrivate(const QTzTimeZonePrivate &) = default;
@@ -334,13 +344,11 @@ private:
     QVector<QTimeZonePrivate::Data> getPosixTransitions(qint64 msNear) const;
 
     Data dataForTzTransition(QTzTransitionTime tran) const;
-    QVector<QTzTransitionTime> m_tranTimes;
-    QVector<QTzTransitionRule> m_tranRules;
-    QList<QByteArray> m_abbreviations;
 #if QT_CONFIG(icu)
     mutable QSharedDataPointer<QTimeZonePrivate> m_icu;
 #endif
-    QByteArray m_posixRule;
+    QTzTimeZoneCacheEntry cached_data;
+    QVector<QTzTransitionTime> tranCache() const { return cached_data.m_tranTimes; }
 };
 #endif // Q_OS_UNIX
 
diff --git a/src/corelib/time/qtimezoneprivate_tz.cpp b/src/corelib/time/qtimezoneprivate_tz.cpp
index 3c2695a789..a94ed6b7a9 100644
--- a/src/corelib/time/qtimezoneprivate_tz.cpp
+++ b/src/corelib/time/qtimezoneprivate_tz.cpp
@@ -1,5 +1,6 @@
 /****************************************************************************
 **
+** Copyright (C) 2019 Crimson AS <info@crimson.no>
 ** Copyright (C) 2013 John Layt <jlayt@kde.org>
 ** Contact: https://www.qt.io/licensing/
 **
@@ -42,6 +43,7 @@
 #include "private/qlocale_tools_p.h"
 
 #include <QtCore/QFile>
+#include <QtCore/QMutex>
 #include <QtCore/QHash>
 #include <QtCore/QDataStream>
 #include <QtCore/QDateTime>
@@ -649,14 +651,26 @@ QTzTimeZonePrivate *QTzTimeZonePrivate::clone() const
     return new QTzTimeZonePrivate(*this);
 }
 
-void QTzTimeZonePrivate::init(const QByteArray &ianaId)
+class QTzTimeZoneCache
+{
+public:
+    QTzTimeZoneCacheEntry fetchEntry(const QByteArray &ianaId);
+
+private:
+    QTzTimeZoneCacheEntry findEntry(const QByteArray &ianaId);
+    QHash<QByteArray, QTzTimeZoneCacheEntry> m_cache;
+    QMutex m_mutex;
+};
+
+QTzTimeZoneCacheEntry QTzTimeZoneCache::findEntry(const QByteArray &ianaId)
 {
+    QTzTimeZoneCacheEntry ret;
     QFile tzif;
     if (ianaId.isEmpty()) {
         // Open system tz
         tzif.setFileName(QStringLiteral("/etc/localtime"));
         if (!tzif.open(QIODevice::ReadOnly))
-            return;
+            return ret;
     } else {
         // Open named tz, try modern path first, if fails try legacy path
         tzif.setFileName(QLatin1String("/usr/share/zoneinfo/") + QString::fromLocal8Bit(ianaId));
@@ -669,9 +683,9 @@ void QTzTimeZonePrivate::init(const QByteArray &ianaId)
                 if (PosixZone::parse(begin, zoneInfo.constEnd()).hasValidOffset()
                     && (begin == zoneInfo.constEnd()
                         || PosixZone::parse(begin, zoneInfo.constEnd()).hasValidOffset())) {
-                    m_id = m_posixRule = ianaId;
+                    ret.m_posixRule = ianaId;
                 }
-                return;
+                return ret;
             }
         }
     }
@@ -682,59 +696,59 @@ void QTzTimeZonePrivate::init(const QByteArray &ianaId)
     bool ok = false;
     QTzHeader hdr = parseTzHeader(ds, &ok);
     if (!ok || ds.status() != QDataStream::Ok)
-        return;
+        return ret;
     QVector<QTzTransition> tranList = parseTzTransitions(ds, hdr.tzh_timecnt, false);
     if (ds.status() != QDataStream::Ok)
-        return;
+        return ret;
     QVector<QTzType> typeList = parseTzTypes(ds, hdr.tzh_typecnt);
     if (ds.status() != QDataStream::Ok)
-        return;
+        return ret;
     QMap<int, QByteArray> abbrevMap = parseTzAbbreviations(ds, hdr.tzh_charcnt, typeList);
     if (ds.status() != QDataStream::Ok)
-        return;
+        return ret;
     parseTzLeapSeconds(ds, hdr.tzh_leapcnt, false);
     if (ds.status() != QDataStream::Ok)
-        return;
+        return ret;
     typeList = parseTzIndicators(ds, typeList, hdr.tzh_ttisstdcnt, hdr.tzh_ttisgmtcnt);
     if (ds.status() != QDataStream::Ok)
-        return;
+        return ret;
 
     // If version 2 then parse the second block of data
     if (hdr.tzh_version == '2' || hdr.tzh_version == '3') {
         ok = false;
         QTzHeader hdr2 = parseTzHeader(ds, &ok);
         if (!ok || ds.status() != QDataStream::Ok)
-            return;
+            return ret;
         tranList = parseTzTransitions(ds, hdr2.tzh_timecnt, true);
         if (ds.status() != QDataStream::Ok)
-            return;
+            return ret;
         typeList = parseTzTypes(ds, hdr2.tzh_typecnt);
         if (ds.status() != QDataStream::Ok)
-            return;
+            return ret;
         abbrevMap = parseTzAbbreviations(ds, hdr2.tzh_charcnt, typeList);
         if (ds.status() != QDataStream::Ok)
-            return;
+            return ret;
         parseTzLeapSeconds(ds, hdr2.tzh_leapcnt, true);
         if (ds.status() != QDataStream::Ok)
-            return;
+            return ret;
         typeList = parseTzIndicators(ds, typeList, hdr2.tzh_ttisstdcnt, hdr2.tzh_ttisgmtcnt);
         if (ds.status() != QDataStream::Ok)
-            return;
-        m_posixRule = parseTzPosixRule(ds);
+            return ret;
+        ret.m_posixRule = parseTzPosixRule(ds);
         if (ds.status() != QDataStream::Ok)
-            return;
+            return ret;
     }
 
     // Translate the TZ file into internal format
 
     // Translate the array index based tz_abbrind into list index
     const int size = abbrevMap.size();
-    m_abbreviations.clear();
-    m_abbreviations.reserve(size);
+    ret.m_abbreviations.clear();
+    ret.m_abbreviations.reserve(size);
     QVector<int> abbrindList;
     abbrindList.reserve(size);
     for (auto it = abbrevMap.cbegin(), end = abbrevMap.cend(); it != end; ++it) {
-        m_abbreviations.append(it.value());
+        ret.m_abbreviations.append(it.value());
         abbrindList.append(it.key());
     }
     for (int i = 0; i < typeList.size(); ++i)
@@ -752,7 +766,7 @@ void QTzTimeZonePrivate::init(const QByteArray &ianaId)
 
     // Now for each transition time calculate and store our rule:
     const int tranCount = tranList.count();;
-    m_tranTimes.reserve(tranCount);
+    ret.m_tranTimes.reserve(tranCount);
     // The DST offset when in effect: usually stable, usually an hour:
     int lastDstOff = 3600;
     for (int i = 0; i < tranCount; i++) {
@@ -806,24 +820,45 @@ void QTzTimeZonePrivate::init(const QByteArray &ianaId)
         rule.abbreviationIndex = tz_type.tz_abbrind;
 
         // If the rule already exist then use that, otherwise add it
-        int ruleIndex = m_tranRules.indexOf(rule);
+        int ruleIndex = ret.m_tranRules.indexOf(rule);
         if (ruleIndex == -1) {
-            m_tranRules.append(rule);
-            tran.ruleIndex = m_tranRules.size() - 1;
+            ret.m_tranRules.append(rule);
+            tran.ruleIndex = ret.m_tranRules.size() - 1;
         } else {
             tran.ruleIndex = ruleIndex;
         }
 
         tran.atMSecsSinceEpoch = tz_tran.tz_time * 1000;
-        m_tranTimes.append(tran);
+        ret.m_tranTimes.append(tran);
     }
-    if (m_tranTimes.isEmpty() && m_posixRule.isEmpty())
+
+    return ret;
+}
+
+QTzTimeZoneCacheEntry QTzTimeZoneCache::fetchEntry(const QByteArray &ianaId)
+{
+    QMutexLocker locker(&m_mutex);
+
+    // search the cache...
+    const auto& it = m_cache.find(ianaId);
+    if (it != m_cache.constEnd())
+        return *it;
+
+    // ... or build a new entry from scratch
+    QTzTimeZoneCacheEntry ret = findEntry(ianaId);
+    m_cache[ianaId] = ret;
+    return ret;
+}
+
+void QTzTimeZonePrivate::init(const QByteArray &ianaId)
+{
+    static QTzTimeZoneCache tzCache;
+    const auto &entry = tzCache.fetchEntry(ianaId);
+    if (entry.m_tranTimes.isEmpty() && entry.m_posixRule.isEmpty())
         return; // Invalid after all !
 
-    if (ianaId.isEmpty())
-        m_id = systemTimeZoneId();
-    else
-        m_id = ianaId;
+    cached_data = std::move(entry);
+    m_id = ianaId.isEmpty() ? systemTimeZoneId() : ianaId;
 }
 
 QLocale::Country QTzTimeZonePrivate::country() const
@@ -903,12 +938,12 @@ QString QTzTimeZonePrivate::displayName(QTimeZone::TimeType timeType,
     }
 
     // Otherwise is strange sequence, so work backwards through trans looking for first match, if any
-    auto it = std::partition_point(m_tranTimes.cbegin(), m_tranTimes.cend(),
+    auto it = std::partition_point(tranCache().cbegin(), tranCache().cend(),
                                    [currentMSecs](const QTzTransitionTime &at) {
                                        return at.atMSecsSinceEpoch <= currentMSecs;
                                    });
 
-    while (it != m_tranTimes.cbegin()) {
+    while (it != tranCache().cbegin()) {
         --it;
         tran = dataForTzTransition(*it);
         int offset = tran.daylightTimeOffset;
@@ -944,7 +979,7 @@ int QTzTimeZonePrivate::daylightTimeOffset(qint64 atMSecsSinceEpoch) const
 bool QTzTimeZonePrivate::hasDaylightTime() const
 {
     // TODO Perhaps cache as frequently accessed?
-    for (const QTzTransitionRule &rule : m_tranRules) {
+    for (const QTzTransitionRule &rule : cached_data.m_tranRules) {
         if (rule.dstOffset != 0)
             return true;
     }
@@ -960,11 +995,11 @@ QTimeZonePrivate::Data QTzTimeZonePrivate::dataForTzTransition(QTzTransitionTime
 {
     QTimeZonePrivate::Data data;
     data.atMSecsSinceEpoch = tran.atMSecsSinceEpoch;
-    QTzTransitionRule rule = m_tranRules.at(tran.ruleIndex);
+    QTzTransitionRule rule = cached_data.m_tranRules.at(tran.ruleIndex);
     data.standardTimeOffset = rule.stdOffset;
     data.daylightTimeOffset = rule.dstOffset;
     data.offsetFromUtc = rule.stdOffset + rule.dstOffset;
-    data.abbreviation = QString::fromUtf8(m_abbreviations.at(rule.abbreviationIndex));
+    data.abbreviation = QString::fromUtf8(cached_data.m_abbreviations.at(rule.abbreviationIndex));
     return data;
 }
 
@@ -972,37 +1007,37 @@ QVector<QTimeZonePrivate::Data> QTzTimeZonePrivate::getPosixTransitions(qint64 m
 {
     const int year = QDateTime::fromMSecsSinceEpoch(msNear, Qt::UTC).date().year();
     // The Data::atMSecsSinceEpoch of the single entry if zone is constant:
-    qint64 atTime = m_tranTimes.isEmpty() ? msNear : m_tranTimes.last().atMSecsSinceEpoch;
-    return calculatePosixTransitions(m_posixRule, year - 1, year + 1, atTime);
+    qint64 atTime = tranCache().isEmpty() ? msNear : tranCache().last().atMSecsSinceEpoch;
+    return calculatePosixTransitions(cached_data.m_posixRule, year - 1, year + 1, atTime);
 }
 
 QTimeZonePrivate::Data QTzTimeZonePrivate::data(qint64 forMSecsSinceEpoch) const
 {
     // If the required time is after the last transition (or there were none)
     // and we have a POSIX rule, then use it:
-    if (!m_posixRule.isEmpty()
-        && (m_tranTimes.isEmpty() || m_tranTimes.last().atMSecsSinceEpoch < forMSecsSinceEpoch)) {
+    if (!cached_data.m_posixRule.isEmpty()
+        && (tranCache().isEmpty() || tranCache().last().atMSecsSinceEpoch < forMSecsSinceEpoch)) {
         QVector<QTimeZonePrivate::Data> posixTrans = getPosixTransitions(forMSecsSinceEpoch);
         auto it = std::partition_point(posixTrans.cbegin(), posixTrans.cend(),
                                        [forMSecsSinceEpoch] (const QTimeZonePrivate::Data &at) {
                                            return at.atMSecsSinceEpoch <= forMSecsSinceEpoch;
                                        });
         // Use most recent, if any in the past; or the first if we have no other rules:
-        if (it > posixTrans.cbegin() || (m_tranTimes.isEmpty() && it < posixTrans.cend())) {
+        if (it > posixTrans.cbegin() || (tranCache().isEmpty() && it < posixTrans.cend())) {
             QTimeZonePrivate::Data data = *(it > posixTrans.cbegin() ? it - 1 : it);
             data.atMSecsSinceEpoch = forMSecsSinceEpoch;
             return data;
         }
     }
-    if (m_tranTimes.isEmpty()) // Only possible if !isValid()
+    if (tranCache().isEmpty()) // Only possible if !isValid()
         return invalidData();
 
     // Otherwise, use the rule for the most recent or first transition:
-    auto last = std::partition_point(m_tranTimes.cbegin(), m_tranTimes.cend(),
+    auto last = std::partition_point(tranCache().cbegin(), tranCache().cend(),
                                      [forMSecsSinceEpoch] (const QTzTransitionTime &at) {
                                          return at.atMSecsSinceEpoch <= forMSecsSinceEpoch;
                                      });
-    if (last > m_tranTimes.cbegin())
+    if (last > tranCache().cbegin())
         --last;
     Data data = dataForTzTransition(*last);
     data.atMSecsSinceEpoch = forMSecsSinceEpoch;
@@ -1018,8 +1053,8 @@ QTimeZonePrivate::Data QTzTimeZonePrivate::nextTransition(qint64 afterMSecsSince
 {
     // If the required time is after the last transition (or there were none)
     // and we have a POSIX rule, then use it:
-    if (!m_posixRule.isEmpty()
-        && (m_tranTimes.isEmpty() || m_tranTimes.last().atMSecsSinceEpoch < afterMSecsSinceEpoch)) {
+    if (!cached_data.m_posixRule.isEmpty()
+        && (tranCache().isEmpty() || tranCache().last().atMSecsSinceEpoch < afterMSecsSinceEpoch)) {
         QVector<QTimeZonePrivate::Data> posixTrans = getPosixTransitions(afterMSecsSinceEpoch);
         auto it = std::partition_point(posixTrans.cbegin(), posixTrans.cend(),
                                        [afterMSecsSinceEpoch] (const QTimeZonePrivate::Data &at) {
@@ -1030,19 +1065,19 @@ QTimeZonePrivate::Data QTzTimeZonePrivate::nextTransition(qint64 afterMSecsSince
     }
 
     // Otherwise, if we can find a valid tran, use its rule:
-    auto last = std::partition_point(m_tranTimes.cbegin(), m_tranTimes.cend(),
+    auto last = std::partition_point(tranCache().cbegin(), tranCache().cend(),
                                      [afterMSecsSinceEpoch] (const QTzTransitionTime &at) {
                                          return at.atMSecsSinceEpoch <= afterMSecsSinceEpoch;
                                      });
-    return last != m_tranTimes.cend() ? dataForTzTransition(*last) : invalidData();
+    return last != tranCache().cend() ? dataForTzTransition(*last) : invalidData();
 }
 
 QTimeZonePrivate::Data QTzTimeZonePrivate::previousTransition(qint64 beforeMSecsSinceEpoch) const
 {
     // If the required time is after the last transition (or there were none)
     // and we have a POSIX rule, then use it:
-    if (!m_posixRule.isEmpty()
-        && (m_tranTimes.isEmpty() || m_tranTimes.last().atMSecsSinceEpoch < beforeMSecsSinceEpoch)) {
+    if (!cached_data.m_posixRule.isEmpty()
+        && (tranCache().isEmpty() || tranCache().last().atMSecsSinceEpoch < beforeMSecsSinceEpoch)) {
         QVector<QTimeZonePrivate::Data> posixTrans = getPosixTransitions(beforeMSecsSinceEpoch);
         auto it = std::partition_point(posixTrans.cbegin(), posixTrans.cend(),
                                        [beforeMSecsSinceEpoch] (const QTimeZonePrivate::Data &at) {
@@ -1051,15 +1086,15 @@ QTimeZonePrivate::Data QTzTimeZonePrivate::previousTransition(qint64 beforeMSecs
         if (it > posixTrans.cbegin())
             return *--it;
         // It fell between the last transition (if any) and the first of the POSIX rule:
-        return m_tranTimes.isEmpty() ? invalidData() : dataForTzTransition(m_tranTimes.last());
+        return tranCache().isEmpty() ? invalidData() : dataForTzTransition(tranCache().last());
     }
 
     // Otherwise if we can find a valid tran then use its rule
-    auto last = std::partition_point(m_tranTimes.cbegin(), m_tranTimes.cend(),
+    auto last = std::partition_point(tranCache().cbegin(), tranCache().cend(),
                                      [beforeMSecsSinceEpoch] (const QTzTransitionTime &at) {
                                          return at.atMSecsSinceEpoch < beforeMSecsSinceEpoch;
                                      });
-    return last > m_tranTimes.cbegin() ? dataForTzTransition(*--last) : invalidData();
+    return last > tranCache().cbegin() ? dataForTzTransition(*--last) : invalidData();
 }
 
 static long getSymloopMax()