From 1eb2b23f4b254052924b198d446c052df9ca3124 Mon Sep 17 00:00:00 2001 From: Henri Beauchamp Date: Tue, 7 Feb 2023 13:51:53 +0100 Subject: SL-19159 Faster LLUUID and LLMaterialID hashing for std and boost containers keys (#70) LLUUID and LLMaterialID already have an excellent entropy and value dispersion; there is therefore strictly no need to further (slowly) hash their value for use with std and boost libraries containers. This commit adds a trivial getDigest64() method to both LLUUID and LLMaterialID (which simply returns the XOR of the two 64 bits long words their value is made of), and uses it in std::hash and hash_value() specializations for use with containers. --- indra/llcommon/lluuid.cpp | 2 +- indra/llcommon/lluuid.h | 50 +++++++++++++++++----------------------- indra/llprimitive/llmaterialid.h | 26 +++++++++++++++++++++ indra/newview/llmaterialmgr.h | 27 +++++++++++++++------- 4 files changed, 67 insertions(+), 38 deletions(-) (limited to 'indra') diff --git a/indra/llcommon/lluuid.cpp b/indra/llcommon/lluuid.cpp index 8ff6c45760..aa8045e6ab 100644 --- a/indra/llcommon/lluuid.cpp +++ b/indra/llcommon/lluuid.cpp @@ -878,7 +878,7 @@ U32 LLUUID::getRandomSeed() seed[7]=(unsigned char)(pid); getSystemTime((uuid_time_t *)(&seed[8])); - U64 seed64 = HBXXH64((const void*)seed, 16).digest(); + U64 seed64 = HBXXH64::digest((const void*)seed, 16); return U32(seed64) ^ U32(seed64 >> 32); } diff --git a/indra/llcommon/lluuid.h b/indra/llcommon/lluuid.h index 86a396ab06..2c36a1d222 100644 --- a/indra/llcommon/lluuid.h +++ b/indra/llcommon/lluuid.h @@ -119,6 +119,14 @@ public: U16 getCRC16() const; U32 getCRC32() const; + // Returns a 64 bits digest of the UUID, by XORing its two 64 bits long + // words. HB + inline U64 getDigest64() const + { + U64* tmp = (U64*)mData; + return tmp[0] ^ tmp[1]; + } + static BOOL validate(const std::string& in_string); // Validate that the UUID string is legal. static const LLUUID null; @@ -165,36 +173,20 @@ public: LLAssetID makeAssetID(const LLUUID& session) const; }; -// Generate a hash of an LLUUID object using the boost hash templates. -template <> -struct boost::hash -{ - typedef LLUUID argument_type; - typedef std::size_t result_type; - result_type operator()(argument_type const& s) const - { - result_type seed(0); - - for (S32 i = 0; i < UUID_BYTES; ++i) - { - boost::hash_combine(seed, s.mData[i]); - } - - return seed; - } -}; - -// Adapt boost hash to std hash +// std::hash implementation for LLUUID namespace std { - template<> struct hash - { - std::size_t operator()(LLUUID const& s) const noexcept - { - return boost::hash()(s); - } - }; + template<> struct hash + { + inline size_t operator()(const LLUUID& id) const noexcept + { + return (size_t)id.getDigest64(); + } + }; } -#endif - +// For use with boost containers. +inline size_t hash_value(const LLUUID& id) noexcept +{ + return (size_t)id.getDigest64(); +} diff --git a/indra/llprimitive/llmaterialid.h b/indra/llprimitive/llmaterialid.h index ee663f8f99..c66e3e30a3 100644 --- a/indra/llprimitive/llmaterialid.h +++ b/indra/llprimitive/llmaterialid.h @@ -66,6 +66,14 @@ public: static const LLMaterialID null; + // Returns a 64 bits digest of the material Id, by XORing its two 64 bits + // long words. HB + inline U64 getDigest64() const + { + U64* tmp = (U64*)mID; + return tmp[0] ^ tmp[1]; + } + private: void parseFromBinary(const LLSD::Binary& pMaterialID); void copyFromOtherMaterialID(const LLMaterialID& pOtherMaterialID); @@ -74,5 +82,23 @@ private: U8 mID[MATERIAL_ID_SIZE]; } ; +// std::hash implementation for LLMaterialID +namespace std +{ + template<> struct hash + { + inline size_t operator()(const LLMaterialID& id) const noexcept + { + return (size_t)id.getDigest64(); + } + }; +} + +// For use with boost containers. +inline size_t hash_value(const LLMaterialID& id) noexcept +{ + return (size_t)id.getDigest64(); +} + #endif // LL_LLMATERIALID_H diff --git a/indra/newview/llmaterialmgr.h b/indra/newview/llmaterialmgr.h index 843dc66fbc..47c322357a 100644 --- a/indra/newview/llmaterialmgr.h +++ b/indra/newview/llmaterialmgr.h @@ -102,13 +102,6 @@ private: (lhs.materialID < rhs.materialID); } - struct TEMaterialPairHasher - { - enum { bucket_size = 8 }; - size_t operator()(const TEMaterialPair& key_value) const { return *((size_t*)key_value.materialID.get()); } // cheesy, but effective - bool operator()(const TEMaterialPair& left, const TEMaterialPair& right) const { return left < right; } - }; - typedef std::set material_queue_t; typedef std::map get_queue_t; typedef std::pair pending_material_t; @@ -116,7 +109,7 @@ private: typedef std::map get_callback_map_t; - typedef boost::unordered_map get_callback_te_map_t; + typedef boost::unordered_map get_callback_te_map_t; typedef std::set getall_queue_t; typedef std::map getall_pending_map_t; typedef std::map getall_callback_map_t; @@ -146,5 +139,23 @@ private: U32 getMaxEntries(const LLViewerRegion* regionp); }; +// std::hash implementation for TEMaterialPair +namespace std +{ + template<> struct hash + { + inline size_t operator()(const LLMaterialMgr::TEMaterialPair& p) const noexcept + { + return size_t((p.te + 1) * p.materialID.getDigest64()); + } + }; +} + +// For use with boost containers. +inline size_t hash_value(const LLMaterialMgr::TEMaterialPair& p) noexcept +{ + return size_t((p.te + 1) * p.materialID.getDigest64()); +} + #endif // LL_LLMATERIALMGR_H -- cgit v1.2.3