Optimize various usages of std::map with frequent find access with std::unordered_map

Introduce ll::string_hash heterogeneous string hasher

17 files changed, 55 insertions, 45 deletions

diff --git a/indra/llcommon/llerror.cpp b/indra/llcommon/llerror.cpp
index b14464382b..6f5e57c3de 100644
--- a/indra/llcommon/llerror.cpp
+++ b/indra/llcommon/llerror.cpp
@@ -480,7 +480,7 @@ namespace
     }
 
 
-    typedef std::map<std::string, LLError::ELevel> LevelMap;
+    typedef std::unordered_map<std::string, LLError::ELevel> LevelMap;
     typedef std::vector<LLError::RecorderPtr> Recorders;
     typedef std::vector<LLError::CallSite*> CallSiteVector;
 
@@ -501,7 +501,7 @@ namespace
         LevelMap                            mClassLevelMap;
         LevelMap                            mFileLevelMap;
         LevelMap                            mTagLevelMap;
-        std::map<std::string, unsigned int> mUniqueLogMessages;
+        std::unordered_map<std::string, unsigned int> mUniqueLogMessages;
 
         LLError::FatalFunction              mCrashFunction;
         LLError::TimeFunction               mTimeFunction;
@@ -1404,7 +1404,7 @@ namespace LLError
         {
             std::ostringstream message_stream;
 
-            std::map<std::string, unsigned int>::iterator messageIter = s->mUniqueLogMessages.find(message);
+            auto messageIter = s->mUniqueLogMessages.find(message);
             if (messageIter != s->mUniqueLogMessages.end())
             {
                 messageIter->second++;
diff --git a/indra/llcommon/llerrorcontrol.h b/indra/llcommon/llerrorcontrol.h
index d254fa5407..3c58d1df22 100644
--- a/indra/llcommon/llerrorcontrol.h
+++ b/indra/llcommon/llerrorcontrol.h
@@ -70,7 +70,6 @@ namespace LLError
         Setting a level means log messages at that level or above.
     */
 
-    LL_COMMON_API void setPrintLocation(bool);
     LL_COMMON_API void setDefaultLevel(LLError::ELevel);
     LL_COMMON_API ELevel getDefaultLevel();
     LL_COMMON_API void setAlwaysFlush(bool flush);
diff --git a/indra/llcommon/llstl.h b/indra/llcommon/llstl.h
index 9f3587886c..f8a468a132 100644
--- a/indra/llcommon/llstl.h
+++ b/indra/llcommon/llstl.h
@@ -705,5 +705,17 @@ struct ll_template_cast_impl<DEST, SOURCE>      \
     }                                           \
 }
 
+// Transparent string hashing helper for use with std::unordered_*
+// std::unordered_map<std::string, val, ll::string_hash, std::equal_to<>>
+namespace ll
+{
+    struct string_hash
+    {
+        using is_transparent = void;
+        [[nodiscard]] size_t operator()(char const* rhs) const { return std::hash<std::string_view>{}(rhs); }
+        [[nodiscard]] size_t operator()(std::string_view rhs) const { return std::hash<std::string_view>{}(rhs); }
+        [[nodiscard]] size_t operator()(const std::string& rhs) const { return std::hash<std::string>{}(rhs); }
+    };
+} // namespace ll
 
 #endif // LL_LLSTL_H
diff --git a/indra/llui/llcallbackmap.h b/indra/llui/llcallbackmap.h
index 3115606d91..69b80db1e8 100644
--- a/indra/llui/llcallbackmap.h
+++ b/indra/llui/llcallbackmap.h
@@ -27,9 +27,11 @@
 #ifndef LLCALLBACKMAP_H
 #define LLCALLBACKMAP_H
 
-#include <map>
+#include "llstl.h"
+
 #include <string>
 #include <functional>
+#include <unordered_map>
 
 class LLCallbackMap
 {
@@ -37,7 +39,7 @@ public:
     // callback definition.
     typedef std::function<void* (void* data)> callback_t;
 
-    typedef std::map<std::string, LLCallbackMap> map_t;
+    typedef std::unordered_map<std::string, LLCallbackMap> map_t;
     typedef map_t::iterator map_iter_t;
     typedef map_t::const_iterator map_const_iter_t;
 
diff --git a/indra/llui/llfloaterreg.cpp b/indra/llui/llfloaterreg.cpp
index a818e72f59..c18495ce71 100644
--- a/indra/llui/llfloaterreg.cpp
+++ b/indra/llui/llfloaterreg.cpp
@@ -40,9 +40,9 @@
 LLFloaterReg::instance_list_t LLFloaterReg::sNullInstanceList;
 LLFloaterReg::instance_map_t LLFloaterReg::sInstanceMap;
 LLFloaterReg::build_map_t LLFloaterReg::sBuildMap;
-std::map<std::string, std::string, std::less<>> LLFloaterReg::sGroupMap;
+LLFloaterReg::group_map_t LLFloaterReg::sGroupMap;
 bool LLFloaterReg::sBlockShowFloaters = false;
-std::set<std::string, std::less<>> LLFloaterReg::sAlwaysShowableList;
+LLFloaterReg::always_showable_t LLFloaterReg::sAlwaysShowableList;
 
 static LLFloaterRegListener sFloaterRegListener;
 
@@ -96,11 +96,8 @@ LLFloater* LLFloaterReg::getLastFloaterCascading()
     candidate_rect.mTop = 100000;
     LLFloater* candidate_floater = NULL;
 
-    std::map<std::string,std::string>::const_iterator it = sGroupMap.begin(), it_end = sGroupMap.end();
-    for( ; it != it_end; ++it)
+    for (const auto& [floater_name, group_name] : sGroupMap)
     {
-        const std::string& group_name = it->second;
-
         instance_list_t& instances = sInstanceMap[group_name];
 
         for (LLFloater* inst : instances)
@@ -604,17 +601,11 @@ U32 LLFloaterReg::getVisibleFloaterInstanceCount()
 {
     U32 count = 0;
 
-    std::map<std::string,std::string>::const_iterator it = sGroupMap.begin(), it_end = sGroupMap.end();
-    for( ; it != it_end; ++it)
+    for (const auto& [floater_name, group_name] : sGroupMap)
     {
-        const std::string& group_name = it->second;
-
         instance_list_t& instances = sInstanceMap[group_name];
-
-        for (instance_list_t::const_iterator iter = instances.begin(); iter != instances.end(); ++iter)
+        for (LLFloater* inst : instances)
         {
-            LLFloater* inst = *iter;
-
             if (inst->getVisible() && !inst->isMinimized())
             {
                 count++;
diff --git a/indra/llui/llfloaterreg.h b/indra/llui/llfloaterreg.h
index 24d1476dda..71a11b6f42 100644
--- a/indra/llui/llfloaterreg.h
+++ b/indra/llui/llfloaterreg.h
@@ -29,9 +29,11 @@
 /// llcommon
 #include "llrect.h"
 #include "llsd.h"
+#include "llstl.h"
 
 #include <functional>
 #include <list>
+#include <unordered_set>
 
 //*******************************************************
 //
@@ -51,26 +53,29 @@ public:
     // 2) We can change the key of a floater without altering the list.
     typedef std::list<LLFloater*> instance_list_t;
     typedef const instance_list_t const_instance_list_t;
-    typedef std::map<std::string, instance_list_t, std::less<>> instance_map_t;
+    typedef std::unordered_map<std::string, instance_list_t, ll::string_hash, std::equal_to<>> instance_map_t;
 
     struct BuildData
     {
         LLFloaterBuildFunc mFunc;
         std::string mFile;
     };
-    typedef std::map<std::string, BuildData, std::less<>> build_map_t;
+    typedef std::unordered_map<std::string, BuildData, ll::string_hash, std::equal_to<>> build_map_t;
 
 private:
     friend class LLFloaterRegListener;
     static instance_list_t sNullInstanceList;
     static instance_map_t sInstanceMap;
     static build_map_t sBuildMap;
-    static std::map<std::string, std::string, std::less<>> sGroupMap;
+
+    using group_map_t = std::unordered_map<std::string, std::string, ll::string_hash, std::equal_to<>>;
+    static group_map_t sGroupMap;
     static bool sBlockShowFloaters;
     /**
      * Defines list of floater names that can be shown despite state of sBlockShowFloaters.
      */
-    static std::set<std::string, std::less<>> sAlwaysShowableList;
+    using always_showable_t = std::unordered_set<std::string, ll::string_hash, std::equal_to<>>;
+    static always_showable_t sAlwaysShowableList;
 
 public:
     // Registration
diff --git a/indra/llui/llfunctorregistry.h b/indra/llui/llfunctorregistry.h
index 953963b683..40a3e439a6 100644
--- a/indra/llui/llfunctorregistry.h
+++ b/indra/llui/llfunctorregistry.h
@@ -29,8 +29,9 @@
 #define LL_LLFUNCTORREGISTRY_H
 
 #include <string>
-#include <map>
+#include <unordered_map>
 
+#include "llstring.h"
 #include "llsd.h"
 #include "llsingleton.h"
 
@@ -56,7 +57,7 @@ class LLFunctorRegistry : public LLSingleton<LLFunctorRegistry<FUNCTOR_TYPE> >
 
 public:
     typedef FUNCTOR_TYPE ResponseFunctor;
-    typedef typename std::map<std::string, FUNCTOR_TYPE> FunctorMap;
+    typedef typename std::unordered_map<std::string, FUNCTOR_TYPE, ll::string_hash, std::equal_to<>> FunctorMap;
 
     bool registerFunctor(const std::string& name, ResponseFunctor f)
     {
diff --git a/indra/llui/llkeywords.h b/indra/llui/llkeywords.h
index 5892238593..53b5435324 100644
--- a/indra/llui/llkeywords.h
+++ b/indra/llui/llkeywords.h
@@ -194,7 +194,7 @@ protected:
     token_list_t mLineTokenList;
     token_list_t mDelimiterTokenList;
 
-    typedef  std::map<std::string, std::string, std::less<>> element_attributes_t;
+    typedef std::unordered_map<std::string, std::string, ll::string_hash, std::equal_to<>> element_attributes_t;
     typedef element_attributes_t::const_iterator attribute_iterator_t;
     element_attributes_t mAttributes;
     std::string getAttribute(std::string_view key);
diff --git a/indra/llui/llnotifications.h b/indra/llui/llnotifications.h
index c7c7435be2..ea1cb7f638 100644
--- a/indra/llui/llnotifications.h
+++ b/indra/llui/llnotifications.h
@@ -946,7 +946,7 @@ public:
     typedef std::vector<std::string> TemplateNames;
     TemplateNames getTemplateNames() const;  // returns a list of notification names
 
-    typedef std::map<std::string, LLNotificationTemplatePtr, std::less<>> TemplateMap;
+    typedef std::unordered_map<std::string, LLNotificationTemplatePtr, ll::string_hash, std::equal_to<>> TemplateMap;
 
     TemplateMap::const_iterator templatesBegin() { return mTemplates.begin(); }
     TemplateMap::const_iterator templatesEnd() { return mTemplates.end(); }
@@ -992,7 +992,7 @@ private:
 
     LLNotificationMap mUniqueNotifications;
 
-    typedef std::map<std::string, std::string, std::less<>> GlobalStringMap;
+    typedef std::unordered_map<std::string, std::string, ll::string_hash, std::equal_to<>> GlobalStringMap;
     GlobalStringMap mGlobalStrings;
 
     bool mIgnoreAllNotifications;
diff --git a/indra/llui/llpanel.h b/indra/llui/llpanel.h
index fe861dc719..a928997c7d 100644
--- a/indra/llui/llpanel.h
+++ b/indra/llui/llpanel.h
@@ -250,7 +250,7 @@ private:
     LLButton*       mDefaultBtn;
     LLUIString      mLabel;
 
-    typedef std::map<std::string, std::string, std::less<>> ui_string_map_t;
+    typedef std::unordered_map<std::string, std::string, ll::string_hash, std::equal_to<>> ui_string_map_t;
     ui_string_map_t mUIStrings;
 
 
@@ -292,7 +292,7 @@ public:
     }
 
 private:
-    typedef std::map< std::string, LLPanelClassCreatorFunc, std::less<>> param_name_map_t;
+    typedef std::unordered_map<std::string, LLPanelClassCreatorFunc, ll::string_hash, std::equal_to<>> param_name_map_t;
 
     param_name_map_t mPanelClassesNames;
 };
diff --git a/indra/llui/lltrans.h b/indra/llui/lltrans.h
index c5d01e6f8d..4dba4c5c3e 100644
--- a/indra/llui/lltrans.h
+++ b/indra/llui/lltrans.h
@@ -125,7 +125,7 @@ public:
     }
 
 private:
-    typedef std::map<std::string, LLTransTemplate, std::less<>> template_map_t;
+    typedef std::unordered_map<std::string, LLTransTemplate, ll::string_hash, std::equal_to<>> template_map_t;
     static template_map_t sStringTemplates;
     static template_map_t sDefaultStringTemplates;
     static LLStringUtil::format_map_t sDefaultArgs;
diff --git a/indra/llui/llui.cpp b/indra/llui/llui.cpp
index 29eb887948..0056e73cce 100644
--- a/indra/llui/llui.cpp
+++ b/indra/llui/llui.cpp
@@ -65,7 +65,6 @@
 
 // for XUIParse
 #include "llquaternion.h"
-#include <boost/tokenizer.hpp>
 #include <boost/algorithm/string/find_iterator.hpp>
 #include <boost/algorithm/string/finder.hpp>
 
diff --git a/indra/llui/llui.h b/indra/llui/llui.h
index 2ef64baaf6..091e0ab1cf 100644
--- a/indra/llui/llui.h
+++ b/indra/llui/llui.h
@@ -114,7 +114,7 @@ class LLUI : public LLSimpleton<LLUI>
 {
     LOG_CLASS(LLUI);
 public:
-    typedef std::map<std::string, LLControlGroup*, std::less<> > settings_map_t;
+    typedef std::unordered_map<std::string, LLControlGroup*, ll::string_hash, std::equal_to<>> settings_map_t;
 
     LLUI(const settings_map_t &settings,
                            LLImageProviderInterface* image_provider,
diff --git a/indra/llui/lluicolortable.cpp b/indra/llui/lluicolortable.cpp
index a792cb8103..7a4f72fe4f 100644
--- a/indra/llui/lluicolortable.cpp
+++ b/indra/llui/lluicolortable.cpp
@@ -198,8 +198,8 @@ LLUIColor LLUIColorTable::getColor(std::string_view name, const LLColor4& defaul
 // update user color, loaded colors are parsed on initialization
 void LLUIColorTable::setColor(std::string_view name, const LLColor4& color)
 {
-    auto it = mUserSetColors.lower_bound(name);
-    if(it != mUserSetColors.end() && !(mUserSetColors.key_comp()(name, it->first)))
+    auto it = mUserSetColors.find(name);
+    if(it != mUserSetColors.end())
     {
         it->second = color;
     }
@@ -330,9 +330,8 @@ void LLUIColorTable::clearTable(string_color_map_t& table)
 // if the color already exists it changes the color
 void LLUIColorTable::setColor(std::string_view name, const LLColor4& color, string_color_map_t& table)
 {
-    string_color_map_t::iterator it = table.lower_bound(name);
-    if(it != table.end()
-    && !(table.key_comp()(name, it->first)))
+    string_color_map_t::iterator it = table.find(name);
+    if(it != table.end())
     {
         it->second = color;
     }
diff --git a/indra/llui/lluicolortable.h b/indra/llui/lluicolortable.h
index 0c6286e5eb..aff6f59db6 100644
--- a/indra/llui/lluicolortable.h
+++ b/indra/llui/lluicolortable.h
@@ -27,7 +27,7 @@
 #ifndef LL_LLUICOLORTABLE_H_
 #define LL_LLUICOLORTABLE_H_
 
-#include <map>
+#include <unordered_map>
 
 #include "llinitparam.h"
 #include "llsingleton.h"
@@ -42,7 +42,7 @@ class LLUIColorTable : public LLSingleton<LLUIColorTable>
     LOG_CLASS(LLUIColorTable);
 
     // consider using sorted vector, can be much faster
-    typedef std::map<std::string, LLUIColor, std::less<>>  string_color_map_t;
+    typedef std::unordered_map<std::string, LLUIColor, ll::string_hash, std::equal_to<>>  string_color_map_t;
 
 public:
     struct ColorParams : LLInitParam::ChoiceBlock<ColorParams>
diff --git a/indra/llxml/llcontrol.h b/indra/llxml/llcontrol.h
index c9bd0a8a32..5aa2b9715e 100644
--- a/indra/llxml/llcontrol.h
+++ b/indra/llxml/llcontrol.h
@@ -33,8 +33,10 @@
 #include "llrect.h"
 #include "llrefcount.h"
 #include "llinstancetracker.h"
+#include "llstl.h"
 
 #include <functional>
+#include <unordered_map>
 #include <vector>
 
 #include <boost/signals2.hpp>
@@ -165,7 +167,7 @@ class LLControlGroup : public LLInstanceTracker<LLControlGroup, std::string>
     LOG_CLASS(LLControlGroup);
 
 protected:
-    typedef std::map<std::string, LLControlVariablePtr, std::less<> > ctrl_name_table_t;
+    using ctrl_name_table_t = std::unordered_map<std::string, LLControlVariablePtr, ll::string_hash, std::equal_to<>>;
     ctrl_name_table_t mNameTable;
     static const std::string mTypeString[TYPE_COUNT];
 
diff --git a/indra/newview/tests/lldateutil_test.cpp b/indra/newview/tests/lldateutil_test.cpp
index acbf019034..3e2e5e70a2 100644
--- a/indra/newview/tests/lldateutil_test.cpp
+++ b/indra/newview/tests/lldateutil_test.cpp
@@ -34,16 +34,16 @@
 #include "lltrans.h"
 #include "llui.h"
 
-#include <map>
+#include <unordered_map>
 
 
 // Baked-in return values for getString()
-std::map< std::string, std::string, std::less<>> gString;
+std::unordered_map< std::string, std::string, ll::string_hash, std::equal_to<>> gString;
 
 // Baked-in return values for getCountString()
 // map of pairs of input xml_desc and integer count
 typedef std::pair< std::string, int > count_string_t;
-std::map< count_string_t, std::string > gCountString;
+std::map<count_string_t, std::string> gCountString;
 
 std::string LLTrans::getString(const std::string_view xml_desc, const LLStringUtil::format_map_t& args, bool def_string)
 {