From 5459f2ee987014e88ece017632d73829d844cb6f Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Wed, 11 Apr 2012 11:01:00 -0400 Subject: Fix Linux UI issues introduced by moving llinitparam to llcommon. In a number of places, the viewer uses a lookup based on std::type_info*. We used to use std::map. But on Linux, &typeid(SomeType) can produce different pointer values, depending on the dynamic load module in which the code is executed. Introduce LLTypeInfoLookup, with an API that deliberately mimics std::map. LLTypeInfoLookup::find() first tries an efficient search for the specified std::type_info*. But if that fails, it scans the underlying container for a match on the std::type_info::name() string. If found, it caches the new std::type_info* to optimize subsequent lookups with the same pointer. Use LLTypeInfoLookup instead of std::map in llinitparam.h and llregistry.h. Introduce LLSortedVector, a std::vector> maintained in sorted order with binary-search lookup. It presents a subset of the std::map API. --- indra/llcommon/lltypeinfolookup.h | 112 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 112 insertions(+) create mode 100644 indra/llcommon/lltypeinfolookup.h (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h new file mode 100644 index 0000000000..fc99f7ff33 --- /dev/null +++ b/indra/llcommon/lltypeinfolookup.h @@ -0,0 +1,112 @@ +/** + * @file lltypeinfolookup.h + * @author Nat Goodspeed + * @date 2012-04-08 + * @brief Template data structure like std::map + * + * $LicenseInfo:firstyear=2012&license=viewerlgpl$ + * Copyright (c) 2012, Linden Research, Inc. + * $/LicenseInfo$ + */ + +#if ! defined(LL_LLTYPEINFOLOOKUP_H) +#define LL_LLTYPEINFOLOOKUP_H + +#include "llsortedvector.h" +#include + +/** + * LLTypeInfoLookup is specifically designed for use cases for which you might + * consider std::map. We have several such data + * structures in the viewer. The trouble with them is that at least on Linux, + * 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 +{ +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; + + 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(); } + + std::pair insert(const std::type_info* key, const VALUE& value) + { + return insert(value_type(key, value)); + } + + std::pair insert(const value_type& pair) + { + return mVector.insert(pair); + } + + const_iterator find(const std::type_info* key) const + { + return const_cast(this)->find(key); + } + + iterator find(const std::type_info* key) + { + 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(); + } + +private: + /// Our LLSortedVector is mutable so that if we're passed an unrecognized + /// std::type_info* for a registered type (which we can identify by + /// searching for the name() string), we can cache the new std::type_info* + /// to speed future lookups -- even when the containing LLTypeInfoLookup + /// is const. + vector_type mVector; +}; + +#endif /* ! defined(LL_LLTYPEINFOLOOKUP_H) */ -- cgit v1.2.3 From 7318e11571237bd55ff5972350db499a73ef6ae5 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Thu, 12 Apr 2012 09:42:51 -0400 Subject: Fix misleading comments, per Richard's code review. --- indra/llcommon/lltypeinfolookup.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index fc99f7ff33..7510cc12ed 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -66,11 +66,14 @@ public: return mVector.insert(pair); } + // const find() forwards to non-const find(): this can alter mVector! const_iterator find(const std::type_info* key) const { return const_cast(this)->find(key); } + // non-const find() caches previously-unknown type_info* to speed future + // lookups. iterator find(const std::type_info* key) { iterator found = mVector.find(key); @@ -101,11 +104,6 @@ public: } private: - /// Our LLSortedVector is mutable so that if we're passed an unrecognized - /// std::type_info* for a registered type (which we can identify by - /// searching for the name() string), we can cache the new std::type_info* - /// to speed future lookups -- even when the containing LLTypeInfoLookup - /// is const. vector_type mVector; }; -- cgit v1.2.3 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(-) (limited to 'indra/llcommon/lltypeinfolookup.h') 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 From 00ae56334c057c1ea5ad08c604b551fcbdf37a30 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Tue, 10 Jul 2012 16:41:26 -0400 Subject: MAINT-1175: Fix Windows build. It seems MSVC doesn't like boost::make_transform_iterator() in the context I was using it. Try directly invoking the iterator's constructor. --- indra/llcommon/lltypeinfolookup.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 1e62d33488..583ca8863b 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -100,11 +100,11 @@ public: private: iterator transform(impl_iterator iter) { - return boost::make_transform_iterator(iter, boost::mem_fn(&impl_value_type::second)); + return 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)); + return const_iterator(iter, boost::mem_fn(&impl_value_type::second)); } impl_map_type mMap; -- cgit v1.2.3 From 70035274093e8803f8c7f28162feef311ef725b4 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Tue, 10 Jul 2012 17:29:58 -0400 Subject: MAINT-1175: Still grappling with MSVC idiosyncracies. Maybe it's failing to correctly handle overloaded transform() methods? --- indra/llcommon/lltypeinfolookup.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 583ca8863b..679cc51f1d 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -66,8 +66,8 @@ public: 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()); } + const_iterator begin() const { return const_transform(mMap.begin()); } + const_iterator end() const { return const_transform(mMap.end()); } bool empty() const { return mMap.empty(); } std::size_t size() const { return mMap.size(); } @@ -94,7 +94,7 @@ public: const_iterator find(const std::type_info* key) const { - return transform(mMap.find(key->name())); + return const_transform(mMap.find(key->name())); } private: @@ -102,7 +102,7 @@ private: { return iterator(iter, boost::mem_fn(&impl_value_type::second)); } - const_iterator transform(impl_const_iterator iter) + const_iterator const_transform(impl_const_iterator iter) { return const_iterator(iter, boost::mem_fn(&impl_value_type::second)); } -- cgit v1.2.3 From 578d70dec0a01b5ed7b461c38503c082ac1a3608 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Wed, 11 Jul 2012 08:20:14 -0400 Subject: MAINT-1175: Change LLTypeInfoLookup API for future optimizations. Per discussion with Richard, accept the type key for insert() and find() as a template parameter rather than as std::type_info*. This permits (e.g.) some sort of compile-time prehashing for common types, without changing the API. Eliminate iterators from the API altogether, thus avoiding costs associated with transform_iterator. Fix existing references in llinitparam.h. --- indra/llcommon/lltypeinfolookup.h | 90 +++++++++++---------------------------- 1 file changed, 26 insertions(+), 64 deletions(-) (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 679cc51f1d..5267e3d2fb 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -13,11 +13,8 @@ #define LL_LLTYPEINFOLOOKUP_H #include -#include -#include -#include +#include #include -#include /** * LLTypeInfoLookup is specifically designed for use cases for which you might @@ -26,87 +23,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. + * + * The API deliberately diverges from std::map in several respects: + * * It avoids iterators, not only begin()/end() but also as return values + * from insert() and find(). This bypasses transform_iterator overhead. + * * Since we literally use compile-time types as keys, the essential insert() + * and find() methods accept the key type as a @em template parameter, + * accepting and returning value_type as a normal runtime value. This is to + * permit future optimization (e.g. compile-time type hashing) without + * changing the API. */ 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; + // std::type_info::name() string. This is one of the rare cases in which I + // dare use const char* directly, rather than std::string, because I'm + // sure that every value returned by std::type_info::name() is static. + typedef boost::unordered_map impl_map_type; public: - typedef LLTypeInfoLookup self; - 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; + typedef VALUE value_type; LLTypeInfoLookup() {} - iterator begin() { return transform(mMap.begin()); } - iterator end() { return transform(mMap.end()); } - const_iterator begin() const { return const_transform(mMap.begin()); } - const_iterator end() const { return const_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)); - } - - std::pair insert(const value_type& pair) + template + bool insert(const value_type& value) { // 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); - } - - iterator find(const std::type_info* key) - { - return transform(mMap.find(key->name())); + // Return just the bool from std::map::insert()'s return pair. + return mMap.insert(typename impl_map_type::value_type(typeid(KEY).name(), value)).second; } - const_iterator find(const std::type_info* key) const + template + boost::optional find() const { - return const_transform(mMap.find(key->name())); + // Use the std::type_info::name() string as the key. + typename impl_map_type::const_iterator found = mMap.find(typeid(KEY).name()); + if (found == mMap.end()) + return boost::optional(); + return found->second; } private: - iterator transform(impl_iterator iter) - { - return iterator(iter, boost::mem_fn(&impl_value_type::second)); - } - const_iterator const_transform(impl_const_iterator iter) - { - return const_iterator(iter, boost::mem_fn(&impl_value_type::second)); - } - impl_map_type mMap; }; -- cgit v1.2.3 From 55a7bdf8d3f59b0d1973d1ec22d3c8770a077723 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Mon, 16 Jul 2012 21:05:23 -0400 Subject: MAINT-1175: Pass boost::unordered_map hash/equals functors for char*. boost::unordered_map does NOT, by default, "do the right thing." Give it hash and equality functors that do. --- indra/llcommon/lltypeinfolookup.h | 44 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 43 insertions(+), 1 deletion(-) (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h index 5267e3d2fb..0b6862444e 100644 --- a/indra/llcommon/lltypeinfolookup.h +++ b/indra/llcommon/lltypeinfolookup.h @@ -13,9 +13,48 @@ #define LL_LLTYPEINFOLOOKUP_H #include +#include #include +#include // std::binary_function #include +/** + * The following helper classes are based on the Boost.Unordered documentation: + * http://www.boost.org/doc/libs/1_45_0/doc/html/unordered/hash_equality.html + */ + +/** + * Compute hash for a string passed as const char* + */ +struct const_char_star_hash: public std::unary_function +{ + std::size_t operator()(const char* str) const + { + std::size_t seed = 0; + for ( ; *str; ++str) + { + boost::hash_combine(seed, *str); + } + return seed; + } +}; + +/** + * Compute equality for strings passed as const char* + * + * I (nat) suspect that this is where the default behavior breaks for the + * const char* values returned from std::type_info::name(). If you compare the + * two const char* pointer values, as a naive, unspecialized implementation + * will surely do, they'll compare unequal. + */ +struct const_char_star_equal: public std::binary_function +{ + bool operator()(const char* lhs, const char* rhs) const + { + return strcmp(lhs, rhs) == 0; + } +}; + /** * LLTypeInfoLookup is specifically designed for use cases for which you might * consider std::map. We have several such data @@ -40,7 +79,10 @@ class LLTypeInfoLookup // std::type_info::name() string. This is one of the rare cases in which I // dare use const char* directly, rather than std::string, because I'm // sure that every value returned by std::type_info::name() is static. - typedef boost::unordered_map impl_map_type; + // HOWEVER, specify our own hash + equality functors: naively comparing + // distinct const char* values won't work. + typedef boost::unordered_map impl_map_type; public: typedef VALUE value_type; -- cgit v1.2.3 From bf6182daa8b4d7cea79310547f71d7a3155e17b0 Mon Sep 17 00:00:00 2001 From: Graham Madarasz Date: Fri, 29 Mar 2013 07:50:08 -0700 Subject: Update Mac and Windows breakpad builds to latest --- indra/llcommon/lltypeinfolookup.h | 0 1 file changed, 0 insertions(+), 0 deletions(-) mode change 100644 => 100755 indra/llcommon/lltypeinfolookup.h (limited to 'indra/llcommon/lltypeinfolookup.h') diff --git a/indra/llcommon/lltypeinfolookup.h b/indra/llcommon/lltypeinfolookup.h old mode 100644 new mode 100755 -- cgit v1.2.3