LazyInit: Optimize access to non-existing types by cachingv6.7.1

The function loadLazyClassesWithName() is no more repeatedly
called, because some non-existent types produce permanent
overhead. Instead, we ask a negative cache and therefore
shortcut repeated failures.

The cache is extremely efficient since it re-uses the same
mapping as the converters in question. Thanks to frkleint.

Fixes: PYSIDE-2749
Task-number: PYSIDE-2404
Change-Id: I675fe5047afe3773b66c8619aa043e66586d48a4
Reviewed-by: Friedemann Kleint <Friedemann.Kleint@qt.io>
(cherry picked from commit b829abcc7b2e9fcdb027e653a6a52cdb0706de11)
(cherry picked from commit 7672c94f2364c5d7638e8e4e150ca57eaa7708c5)
Reviewed-by: Adrian Herrmann <adrian.herrmann@qt.io>

3 files changed, 40 insertions, 3 deletions

diff --git a/sources/shiboken6/libshiboken/sbkconverter.cpp b/sources/shiboken6/libshiboken/sbkconverter.cpp
index 57697e4a3..09a21ed13 100644
--- a/sources/shiboken6/libshiboken/sbkconverter.cpp
+++ b/sources/shiboken6/libshiboken/sbkconverter.cpp
@@ -13,6 +13,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 
 static SbkConverter **PrimitiveTypeConverters;
 
@@ -422,18 +423,36 @@ void registerConverterName(SbkConverter *converter, const char *typeName)
         converters.insert(std::make_pair(typeName, converter));
 }
 
-static std::string getRealTypeName(const char *name)
+static std::string getRealTypeName(const std::string &typeName)
 {
-    std::string typeName(name);
     auto size = typeName.size();
     if (std::isalnum(typeName[size - 1]) == 0)
         return typeName.substr(0, size - 1);
     return typeName;
 }
 
-SbkConverter *getConverter(const char *typeName)
+// PYSIDE-2404: Build a negative cache of already failed lookups.
+//              The resulting list must be reset after each new import,
+//              because that can change results. Also clear the cache after
+//              reaching some threashold.
+static std::unordered_set<std::string> nonExistingTypeNames{};
+
+// Arbitrary size limit to prevent random name overflows.
+static constexpr std::size_t negativeCacheLimit = 50;
+
+static void rememberAsNonexistent(const std::string &typeName)
+{
+    if (nonExistingTypeNames.size() > negativeCacheLimit)
+        clearNegativeLazyCache();
+    converters.insert(std::make_pair(typeName, nullptr));
+    nonExistingTypeNames.insert(typeName);
+}
+
+SbkConverter *getConverter(const char *typeNameC)
 {
+    std::string typeName = typeNameC;
     auto it = converters.find(typeName);
+    // PYSIDE-2404: This can also contain explicit nullptr as a negative cache.
     if (it != converters.end())
         return it->second;
     // PYSIDE-2404: Did not find the name. Load the lazy classes
@@ -442,6 +461,9 @@ SbkConverter *getConverter(const char *typeName)
     it = converters.find(typeName);
     if (it != converters.end())
         return it->second;
+    // Cache the negative result. Don't forget to clear the cache for new modules.
+    rememberAsNonexistent(typeName);
+
     if (Shiboken::pyVerbose() > 0) {
         const std::string message =
             std::string("Can't find type resolver for type '") + typeName + "'.";
@@ -450,6 +472,15 @@ SbkConverter *getConverter(const char *typeName)
     return nullptr;
 }
 
+void clearNegativeLazyCache()
+{
+    for (const auto &typeName : nonExistingTypeNames) {
+        auto it = converters.find(typeName);
+        converters.erase(it);
+    }
+    nonExistingTypeNames.clear();
+}
+
 SbkConverter *primitiveTypeConverter(int index)
 {
     return PrimitiveTypeConverters[index];
diff --git a/sources/shiboken6/libshiboken/sbkconverter_p.h b/sources/shiboken6/libshiboken/sbkconverter_p.h
index c886c9b9f..9b2d5dbab 100644
--- a/sources/shiboken6/libshiboken/sbkconverter_p.h
+++ b/sources/shiboken6/libshiboken/sbkconverter_p.h
@@ -531,6 +531,10 @@ SbkConverter *createConverterObject(PyTypeObject *type,
                                     IsConvertibleToCppFunc toCppPointerCheckFunc,
                                     CppToPythonFunc pointerToPythonFunc,
                                     CppToPythonFunc copyToPythonFunc);
+
+/// Interface for sbkmodule which must reset cache when new module is loaded.
+LIBSHIBOKEN_API void clearNegativeLazyCache();
+
 } // namespace Shiboken::Conversions
 
 #endif // SBK_CONVERTER_P_H
diff --git a/sources/shiboken6/libshiboken/sbkmodule.cpp b/sources/shiboken6/libshiboken/sbkmodule.cpp
index 4153df27f..47977d747 100644
--- a/sources/shiboken6/libshiboken/sbkmodule.cpp
+++ b/sources/shiboken6/libshiboken/sbkmodule.cpp
@@ -455,6 +455,8 @@ PyObject *create(const char * /* modName */, void *moduleData)
     //              into `sys.modules`. This can cause a race condition.
     // Insert the module early into the module dict to prevend recursion.
     PyDict_SetItemString(sysModules, PyModule_GetName(module), module);
+    // Clear the non-existing name cache because we have a new module.
+    Shiboken::Conversions::clearNegativeLazyCache();
     return module;
 }