From e7184225f3868c5cf587f51edf76e44c78dfce2d Mon Sep 17 00:00:00 2001 From: Gunnar Beutner Date: Fri, 13 Dec 2013 12:54:14 +0100 Subject: [PATCH] Improve performance for icinga::Deserialize. Refs #5327 --- lib/base/serializer.cpp | 17 +++++--- lib/base/utility.cpp | 8 +++- lib/base/utility.h | 2 +- tools/mkclass/classcompiler.cpp | 76 +++++++++++++++++++++++++++++---- tools/mkclass/classcompiler.h | 2 + 5 files changed, 88 insertions(+), 17 deletions(-) diff --git a/lib/base/serializer.cpp b/lib/base/serializer.cpp index a23450c63..7f5faa900 100644 --- a/lib/base/serializer.cpp +++ b/lib/base/serializer.cpp @@ -161,21 +161,24 @@ static Object::Ptr DeserializeObject(const Object::Ptr& object, const Dictionary if (!instance) instance = type->Instantiate(); - for (int i = 0; i < type->GetFieldCount(); i++) { - Field field = type->GetFieldInfo(i); + BOOST_FOREACH(const Dictionary::Pair& kv, input) { + if (kv.first.IsEmpty()) + continue; - if ((field.Attributes & attributeTypes) == 0) + int fid = type->GetFieldId(kv.first); + + if (fid < 0) continue; - Value value = input->Get(field.Name); + Field field = type->GetFieldInfo(fid); - if (value.IsEmpty()) + if ((field.Attributes & attributeTypes) == 0) continue; try { - instance->SetField(i, Deserialize(value, attributeTypes)); + instance->SetField(fid, Deserialize(kv.second, attributeTypes)); } catch (const std::exception&) { - instance->SetField(i, Empty); + instance->SetField(fid, Empty); } } diff --git a/lib/base/utility.cpp b/lib/base/utility.cpp index f60e67718..f891ac8b2 100644 --- a/lib/base/utility.cpp +++ b/lib/base/utility.cpp @@ -705,12 +705,18 @@ String Utility::GetThreadName(void) return *name; } -unsigned long Utility::SDBM(const String& str) +unsigned long Utility::SDBM(const String& str, size_t len) { unsigned long hash = 0; + size_t current = 0; BOOST_FOREACH(char c, str) { + if (current >= len) + break; + hash = c + (hash << 6) + (hash << 16) - hash; + + current++; } return hash; diff --git a/lib/base/utility.h b/lib/base/utility.h index 6fef1d608..8ad1b49a3 100644 --- a/lib/base/utility.h +++ b/lib/base/utility.h @@ -102,7 +102,7 @@ public: static void SetThreadName(const String& name, bool os = true); static String GetThreadName(void); - static unsigned long SDBM(const String& str); + static unsigned long SDBM(const String& str, size_t len = String::NPos); static int CompareVersion(const String& v1, const String& v2); diff --git a/tools/mkclass/classcompiler.cpp b/tools/mkclass/classcompiler.cpp index 28892309e..561ac74c0 100644 --- a/tools/mkclass/classcompiler.cpp +++ b/tools/mkclass/classcompiler.cpp @@ -21,6 +21,8 @@ #include #include #include +#include +#include using namespace icinga; @@ -77,6 +79,27 @@ void ClassCompiler::HandleCode(const std::string& code, const ClassDebugInfo& lo std::cout << code << std::endl; } +unsigned long ClassCompiler::SDBM(const std::string& str, size_t len = std::string::npos) +{ + unsigned long hash = 0; + size_t current = 0; + + std::string::const_iterator it; + + for (it = str.begin(); it != str.end(); it++) { + if (current >= len) + break; + + char c = *it; + + hash = c + (hash << 6) + (hash << 16) - hash; + + current++; + } + + return hash; +} + void ClassCompiler::HandleClass(const Klass& klass, const ClassDebugInfo& locp) { std::vector::const_iterator it; @@ -136,11 +159,47 @@ void ClassCompiler::HandleClass(const Klass& klass, const ClassDebugInfo& locp) std::cout << ";" << std::endl << std::endl; - int num = 0; - for (it = klass.Fields.begin(); it != klass.Fields.end(); it++) { - std::cout << "\t\t" << "if (name == \"" << it->Name << "\")" << std::endl - << "\t\t\t" << "return offset + " << num << ";" << std::endl; - num++; + std::map > > jumptable; + + int hlen = 0, collisions = 0; + + do { + int num = 0; + + hlen++; + jumptable.clear(); + collisions = 0; + + for (it = klass.Fields.begin(); it != klass.Fields.end(); it++) { + int hash = static_cast(SDBM(it->Name, hlen)); + jumptable[hash].push_back(std::make_pair(num, it->Name)); + num++; + + if (jumptable[hash].size() > 1) + collisions++; + } + } while (collisions >= 5 && hlen < 8); + + if (!klass.Fields.empty()) { + std::cout << "\t\tswitch (static_cast(Utility::SDBM(name, " << hlen << "))) {" << std::endl; + + std::map > >::const_iterator itj; + + for (itj = jumptable.begin(); itj != jumptable.end(); itj++) { + std::cout << "\t\t\tcase " << itj->first << ":" << std::endl; + + std::vector >::const_iterator itf; + + for (itf = itj->second.begin(); itf != itj->second.end(); itf++) { + std::cout << "\t\t\t\t" << "if (name == \"" << itf->second << "\")" << std::endl + << "\t\t\t\t\t" << "return offset + " << itf->first << ";" << std::endl; + } + + std::cout << std::endl + << "\t\t\t\tbreak;" << std::endl; + } + + std::cout << "\t\t}" << std::endl; } std::cout << std::endl @@ -178,7 +237,7 @@ void ClassCompiler::HandleClass(const Klass& klass, const ClassDebugInfo& locp) std::cout << ") {" << std::endl; - num = 0; + size_t num = 0; for (it = klass.Fields.begin(); it != klass.Fields.end(); it++) { std::cout << "\t\t\t" << "case " << num << ":" << std::endl << "\t\t\t\t" << "return Field(" << num << ", \"" << it->Name << "\", " << it->Attributes << ");" << std::endl; @@ -259,7 +318,7 @@ void ClassCompiler::HandleClass(const Klass& klass, const ClassDebugInfo& locp) std::cout << ") {" << std::endl; - num = 0; + size_t num = 0; for (it = klass.Fields.begin(); it != klass.Fields.end(); it++) { std::cout << "\t\t\t" << "case " << num << ":" << std::endl << "\t\t\t\t" << "Set" << it->GetFriendlyName() << "("; @@ -417,7 +476,8 @@ void ClassCompiler::CompileStream(const std::string& path, std::istream *stream) << "#include \"base/debug.h\"" << std::endl << "#include \"base/value.h\"" << std::endl << "#include \"base/array.h\"" << std::endl - << "#include \"base/dictionary.h\"" << std::endl << std::endl + << "#include \"base/dictionary.h\"" << std::endl + << "#include \"base/utility.h\"" << std::endl << std::endl << "#ifdef _MSC_VER" << std::endl << "#pragma warning( push )" << std::endl << "#pragma warning( disable : 4244 )" << std::endl diff --git a/tools/mkclass/classcompiler.h b/tools/mkclass/classcompiler.h index c6298d9bc..386d21244 100644 --- a/tools/mkclass/classcompiler.h +++ b/tools/mkclass/classcompiler.h @@ -142,6 +142,8 @@ private: std::string m_Path; std::istream *m_Input; void *m_Scanner; + + static unsigned long SDBM(const std::string& str, size_t len); }; } -- 2.49.0