From b6ffedb03da628d809124da24b7f2c20252710a5 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Tue, 10 Jul 2012 15:46:27 -0400 Subject: MAINT-1175: Reimplement LLTypeInfoLookup for better lookup failure. The original LLTypeInfoLookup implementation was based on two assumptions: small overall container size, and infrequent normal-case lookup failures. Those assumptions led to binary-searching a sorted vector, with linear search as a fallback to cover the problem case of two different type_info* values for the same type. As documented in the Jira, this turned out to be a problem. The container size was larger than expected, and failed lookups turned out to be far more common than expected. The new implementation is based on a hash map of std::type_info::name() strings, which should perform equally well in the success and failure cases: no special-case fallback logic. --- indra/llcommon/lltypeinfolookup.h | 119 +++++++++++++++++++------------------- 1 file changed, 61 insertions(+), 58 deletions(-) diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 7510cc12ed..1e62d33488 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -12,8 +12,12 @@ #if ! defined(LL_LLTYPEINFOLOOKUP_H) #define LL_LLTYPEINFOLOOKUP_H -#include "llsortedvector.h" +#include +#include +#include +#include #include +#include /** * LLTypeInfoLookup is specifically designed for use cases for which you might @@ -22,40 +26,52 @@ * you can't rely on always getting the same std::type_info* for a given type: * different load modules will produce different std::type_info*. * LLTypeInfoLookup contains a workaround to address this issue. - * - * Specifically, when we don't find the passed std::type_info*, - * LLTypeInfoLookup performs a linear search over registered entries to - * compare name() strings. Presuming that this succeeds, we cache the new - * (previously unrecognized) std::type_info* to speed future lookups. - * - * This worst-case fallback search (linear search with string comparison) - * should only happen the first time we look up a given type from a particular - * load module other than the one from which we initially registered types. - * (However, a lookup which wouldn't succeed anyway will always have - * worst-case performance.) This class is probably best used with less than a - * few dozen different types. */ template class LLTypeInfoLookup { + // We present an interface like this: + typedef std::map intf_map_type; + // Use this for our underlying implementation: lookup by + // std::type_info::name() string. Note that we must store a std::pair -- in other words, an intf_map_type::value_type + // pair -- so we can present iterators that do the right thing. + // (This might result in a lookup with one std::type_info* returning an + // iterator to a different std::type_info*, but frankly, my dear, we don't + // give a damn.) + typedef boost::unordered_map impl_map_type; + // Iterator shorthand + typedef typename intf_map_type::iterator intf_iterator; + typedef typename intf_map_type::const_iterator intf_const_iterator; + typedef typename intf_map_type::value_type intf_value_type; + typedef typename impl_map_type::iterator impl_iterator; + typedef typename impl_map_type::const_iterator impl_const_iterator; + typedef typename impl_map_type::value_type impl_value_type; + // Type of function that transforms impl_value_type to intf_value_type + typedef boost::function iterfunc; + typedef boost::function const_iterfunc; + public: typedef LLTypeInfoLookup self; - typedef LLSortedVector vector_type; - typedef typename vector_type::key_type key_type; - typedef typename vector_type::mapped_type mapped_type; - typedef typename vector_type::value_type value_type; - typedef typename vector_type::iterator iterator; - typedef typename vector_type::const_iterator const_iterator; + typedef typename intf_map_type::key_type key_type; + typedef typename intf_map_type::mapped_type mapped_type; + typedef intf_value_type value_type; + + // Iterators are different because we have to transform + // impl_map_type::iterator to intf_map_type::iterator. + typedef boost::transform_iterator iterator; + typedef boost::transform_iterator const_iterator; LLTypeInfoLookup() {} - iterator begin() { return mVector.begin(); } - iterator end() { return mVector.end(); } - const_iterator begin() const { return mVector.begin(); } - const_iterator end() const { return mVector.end(); } - bool empty() const { return mVector.empty(); } - std::size_t size() const { return mVector.size(); } + iterator begin() { return transform(mMap.begin()); } + iterator end() { return transform(mMap.end()); } + const_iterator begin() const { return transform(mMap.begin()); } + const_iterator end() const { return transform(mMap.end()); } + bool empty() const { return mMap.empty(); } + std::size_t size() const { return mMap.size(); } + // Shorthand -- I've always wished std::map supported this signature. std::pair insert(const std::type_info* key, const VALUE& value) { return insert(value_type(key, value)); @@ -63,48 +79,35 @@ public: std::pair insert(const value_type& pair) { - return mVector.insert(pair); + // Obtain and store the std::type_info::name() string as the key. + // Save the whole incoming pair as the value! + std::pair + inserted(mMap.insert(impl_value_type(pair.first->name(), pair))); + // Have to transform the iterator before returning. + return std::pair(transform(inserted.first), inserted.second); } - // const find() forwards to non-const find(): this can alter mVector! - const_iterator find(const std::type_info* key) const + iterator find(const std::type_info* key) { - return const_cast(this)->find(key); + return transform(mMap.find(key->name())); } - // non-const find() caches previously-unknown type_info* to speed future - // lookups. - iterator find(const std::type_info* key) + const_iterator find(const std::type_info* key) const { - iterator found = mVector.find(key); - if (found != mVector.end()) - { - // If LLSortedVector::find() found, great, we're done. - return found; - } - // Here we didn't find the passed type_info*. On Linux, though, even - // for the same type, typeid(sametype) produces a different type_info* - // when used in different load modules. So the fact that we didn't - // find the type_info* we seek doesn't mean this type isn't - // registered. Scan for matching name() string. - for (typename vector_type::iterator ti(mVector.begin()), tend(mVector.end()); - ti != tend; ++ti) - { - if (std::string(ti->first->name()) == key->name()) - { - // This unrecognized 'key' is for the same type as ti->first. - // To speed future lookups, insert a new entry that lets us - // look up ti->second using this same 'key'. - return insert(key, ti->second).first; - } - } - // We simply have never seen a type with this type_info* from any load - // module. - return mVector.end(); + return transform(mMap.find(key->name())); } private: - vector_type mVector; + iterator transform(impl_iterator iter) + { + return boost::make_transform_iterator(iter, boost::mem_fn(&impl_value_type::second)); + } + const_iterator transform(impl_const_iterator iter) + { + return boost::make_transform_iterator(iter, boost::mem_fn(&impl_value_type::second)); + } + + impl_map_type mMap; }; #endif /* ! defined(LL_LLTYPEINFOLOOKUP_H) */ -- cgit v1.2.3