Optimize retrieving components by name

The PackageManagerCore::componentByName(const QString &name)
-function is called repeatedly by the InstallerCalculator class
and at minimum once for each install script, because we
automatically inject a snippet which stores the return value
of the function in the 'component' variable for the script context.

Create a <name, component> hash once per each component model reset
to make the lookups faster:

* This avoids constructing a flat list of components and all
  their descendants again and again when calling the function.

* The linear lookup from the component list is slow because it
  calls componentMatches() for each element until the satisfactory
  component was found or the list ends.

* The average time complexity of the key lookup from the QHash
  is constant even for large hashes.

Task-number: QTIFW-2790
Change-Id: I580d28f78ac6681d5bcbfbad970002b49de1a830
Reviewed-by: Katja Marttila <katja.marttila@qt.io>

5 files changed, 40 insertions, 12 deletions

diff --git a/src/libs/installer/installercalculator.cpp b/src/libs/installer/installercalculator.cpp
index 9f8293545..f71a35858 100644
--- a/src/libs/installer/installercalculator.cpp
+++ b/src/libs/installer/installercalculator.cpp
@@ -41,9 +41,8 @@ namespace QInstaller {
     \internal
 */
 
-InstallerCalculator::InstallerCalculator(PackageManagerCore *core, const QList<Component *> &allComponents, const AutoDependencyHash &autoDependencyComponentHash)
+InstallerCalculator::InstallerCalculator(PackageManagerCore *core, const AutoDependencyHash &autoDependencyComponentHash)
     : m_core(core)
-    , m_allComponents(allComponents)
     , m_autoDependencyComponentHash(autoDependencyComponentHash)
 {
 }
@@ -186,8 +185,7 @@ bool InstallerCalculator::appendComponentToInstall(Component *component, const Q
     for (const QString &dependencyComponentName : dependenciesList) {
         // PackageManagerCore::componentByName returns 0 if dependencyComponentName contains a
         // version which is not available
-        Component *dependencyComponent =
-            PackageManagerCore::componentByName(dependencyComponentName, m_allComponents);
+        Component *dependencyComponent = m_core->componentByName(dependencyComponentName);
         if (!dependencyComponent) {
             const QString errorMessage = QCoreApplication::translate("InstallerCalculator",
                 "Cannot find missing dependency \"%1\" for \"%2\".").arg(dependencyComponentName,
@@ -309,7 +307,7 @@ QSet<Component *> InstallerCalculator::autodependencyComponents(const bool rever
                 || (revertFromInstall && !m_toInstallComponentIds.contains(autoDependency))) {
                 continue;
             }
-            Component *autoDependComponent = PackageManagerCore::componentByName(autoDependency, m_allComponents);
+            Component *autoDependComponent = m_core->componentByName(autoDependency);
             if (!autoDependComponent)
                 continue;
             if ((!autoDependComponent->isInstalled()
@@ -343,8 +341,7 @@ void InstallerCalculator::calculateComponentDependencyReferences(const QString d
 
     const QStringList dependenciesList = dependencyComponent->currentDependencies();
     for (const QString &depComponentName : dependenciesList) {
-        Component *dependencyComponent =
-            PackageManagerCore::componentByName(depComponentName, m_allComponents);
+        Component *dependencyComponent = m_core->componentByName(depComponentName);
         calculateComponentDependencyReferences(depComponentName, dependencyComponent);
     }
 }
diff --git a/src/libs/installer/installercalculator.h b/src/libs/installer/installercalculator.h
index d952a1e8c..c2fa8761c 100644
--- a/src/libs/installer/installercalculator.h
+++ b/src/libs/installer/installercalculator.h
@@ -43,7 +43,7 @@ class Component;
 class INSTALLER_EXPORT InstallerCalculator
 {
 public:
-    InstallerCalculator(PackageManagerCore *core, const QList<Component *> &allComponents, const AutoDependencyHash &autoDependencyComponentHash);
+    InstallerCalculator(PackageManagerCore *core, const AutoDependencyHash &autoDependencyComponentHash);
 
     enum InstallReasonType
     {
@@ -75,7 +75,6 @@ private:
 
 private:
     PackageManagerCore *m_core;
-    QList<Component*> m_allComponents;
     QHash<Component*, QSet<Component*> > m_visitedComponents;
     QList<const Component*> m_componentsForAutodepencencyCheck;
     //for faster lookups.
diff --git a/src/libs/installer/packagemanagercore.cpp b/src/libs/installer/packagemanagercore.cpp
index a5bf98000..c68f93efe 100644
--- a/src/libs/installer/packagemanagercore.cpp
+++ b/src/libs/installer/packagemanagercore.cpp
@@ -1982,6 +1982,10 @@ ScriptEngine *PackageManagerCore::controlScriptEngine() const
 */
 void PackageManagerCore::appendRootComponent(Component *component)
 {
+    // For normal installer runs components aren't appended after model reset
+    if (Q_UNLIKELY(!d->m_componentByNameHash.isEmpty()))
+        d->m_componentByNameHash.clear();
+
     d->m_rootComponents.append(component);
     emit componentAdded(component);
 }
@@ -2063,6 +2067,10 @@ QList<Component *> PackageManagerCore::components(ComponentTypes mask, const QSt
 */
 void PackageManagerCore::appendUpdaterComponent(Component *component)
 {
+    // For normal installer runs components aren't appended after model reset
+    if (Q_UNLIKELY(!d->m_componentByNameHash.isEmpty()))
+        d->m_componentByNameHash.clear();
+
     component->setUpdateAvailable(true);
     d->m_updaterComponents.append(component);
     emit componentAdded(component);
@@ -2076,7 +2084,30 @@ void PackageManagerCore::appendUpdaterComponent(Component *component)
 */
 Component *PackageManagerCore::componentByName(const QString &name) const
 {
-    return componentByName(name, components(ComponentType::AllNoReplacements));
+    if (name.isEmpty())
+        return nullptr;
+
+    if (d->m_componentByNameHash.isEmpty()) {
+        // We can avoid the linear lookups from the component list by creating
+        // a <name,component> hash once, and reusing it on subsequent calls.
+        const QList<Component *> componentsList = components(ComponentType::AllNoReplacements);
+        for (Component *component : componentsList)
+            d->m_componentByNameHash.insert(component->name(), component);
+    }
+
+    QString fixedVersion;
+    QString fixedName;
+
+    parseNameAndVersion(name, &fixedName, &fixedVersion);
+
+    Component *component = d->m_componentByNameHash.value(fixedName);
+    if (!component)
+        return nullptr;
+
+    if (componentMatches(component, fixedName, fixedVersion))
+        return component;
+
+    return nullptr;
 }
 
 /*!
diff --git a/src/libs/installer/packagemanagercore_p.cpp b/src/libs/installer/packagemanagercore_p.cpp
index eddb44555..f4d47b718 100644
--- a/src/libs/installer/packagemanagercore_p.cpp
+++ b/src/libs/installer/packagemanagercore_p.cpp
@@ -459,6 +459,7 @@ void PackageManagerCorePrivate::cleanUpComponentEnvironment()
     m_autoDependencyComponentHash.clear();
     m_localDependencyComponentHash.clear();
     m_localVirtualComponents.clear();
+    m_componentByNameHash.clear();
     // clean up registered (downloaded) data
     if (m_core->isMaintainer())
         BinaryFormatEngineHandler::instance()->clear();
@@ -564,8 +565,7 @@ InstallerCalculator *PackageManagerCorePrivate::installerCalculator() const
 {
     if (!m_installerCalculator) {
         PackageManagerCorePrivate *const pmcp = const_cast<PackageManagerCorePrivate *> (this);
-        pmcp->m_installerCalculator = new InstallerCalculator(m_core,
-            m_core->components(PackageManagerCore::ComponentType::AllNoReplacements), pmcp->m_autoDependencyComponentHash);
+        pmcp->m_installerCalculator = new InstallerCalculator(m_core, pmcp->m_autoDependencyComponentHash);
     }
     return m_installerCalculator;
 }
diff --git a/src/libs/installer/packagemanagercore_p.h b/src/libs/installer/packagemanagercore_p.h
index 0ce081774..60b11ebda 100644
--- a/src/libs/installer/packagemanagercore_p.h
+++ b/src/libs/installer/packagemanagercore_p.h
@@ -316,6 +316,7 @@ private:
     QList<Component*> m_deletedReplacedComponents;
     AutoDependencyHash m_autoDependencyComponentHash;
     LocalDependencyHash m_localDependencyComponentHash;
+    QHash<QString, Component *> m_componentByNameHash;
 
     QStringList m_localVirtualComponents;