From: khizmax Date: Thu, 22 Oct 2015 20:50:51 +0000 (+0300) Subject: FeldmanHashSet/Map: added level statistics X-Git-Tag: v2.1.0~82 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=c9091bac79a393e0d777790b4ed5d6694a1d0309;hp=-c FeldmanHashSet/Map: added level statistics Optimized MT-test memory usage Improved doxygen-generated docs --- c9091bac79a393e0d777790b4ed5d6694a1d0309 diff --git a/cds/container/details/feldman_hashmap_base.h b/cds/container/details/feldman_hashmap_base.h index 20eab6b3..6e8a3f00 100644 --- a/cds/container/details/feldman_hashmap_base.h +++ b/cds/container/details/feldman_hashmap_base.h @@ -23,6 +23,9 @@ namespace cds { namespace container { template using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >; + /// \p FeldmanHashMap level statistics + typedef cds::intrusive::feldman_hashset::level_statistics level_statistics; + /// \p FeldmanHashMap traits struct traits { diff --git a/cds/container/details/feldman_hashset_base.h b/cds/container/details/feldman_hashset_base.h index 2f319627..b321b7b8 100644 --- a/cds/container/details/feldman_hashset_base.h +++ b/cds/container/details/feldman_hashset_base.h @@ -29,6 +29,9 @@ namespace cds { namespace container { template using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >; + /// \p FeldmanHashSet level statistics + typedef cds::intrusive::feldman_hashset::level_statistics level_statistics; + /// \p FeldmanHashSet traits struct traits { diff --git a/cds/container/feldman_hashmap_rcu.h b/cds/container/feldman_hashmap_rcu.h index 501766a3..7ad23b84 100644 --- a/cds/container/feldman_hashmap_rcu.h +++ b/cds/container/feldman_hashmap_rcu.h @@ -639,6 +639,14 @@ namespace cds { namespace container { return base_class::array_node_size(); } + /// Collects tree level statistics into \p stat + /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics + */ + void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const + { + base_class::get_level_statistics(stat); + } + public: ///@name Thread-safe iterators /** @anchor cds_container_FeldmanHashMap_rcu_iterators diff --git a/cds/container/feldman_hashset_rcu.h b/cds/container/feldman_hashset_rcu.h index b8bbccff..d6b3bfa9 100644 --- a/cds/container/feldman_hashset_rcu.h +++ b/cds/container/feldman_hashset_rcu.h @@ -396,6 +396,14 @@ namespace cds { namespace container { return base_class::array_node_size(); } + /// Collects tree level statistics into \p stat + /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics + */ + void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const + { + base_class::get_level_statistics(stat); + } + public: ///@name Thread-safe iterators /** @anchor cds_container_FeldmanHashSet_rcu_iterators diff --git a/cds/container/impl/feldman_hashmap.h b/cds/container/impl/feldman_hashmap.h index 7fd1c141..2f8a03af 100644 --- a/cds/container/impl/feldman_hashmap.h +++ b/cds/container/impl/feldman_hashmap.h @@ -78,7 +78,7 @@ namespace cds { namespace container { There are several specializations of \p %FeldmanHashMap for each \p GC. You should include: - for \p gc::HP garbage collector - for \p gc::DHP garbage collector - - for \ref cds_intrusive_FeldmanHashMap_rcu "RCU type". RCU specialization + - for \ref cds_container_FeldmanHashMap_rcu "RCU type". RCU specialization has a slightly different interface. */ template < @@ -679,6 +679,14 @@ namespace cds { namespace container { return base_class::array_node_size(); } + /// Collects tree level statistics into \p stat + /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics + */ + void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const + { + base_class::get_level_statistics( stat ); + } + public: ///@name Thread-safe iterators /** @anchor cds_container_FeldmanHashMap_iterators diff --git a/cds/container/impl/feldman_hashset.h b/cds/container/impl/feldman_hashset.h index 4e05f39c..50462de3 100644 --- a/cds/container/impl/feldman_hashset.h +++ b/cds/container/impl/feldman_hashset.h @@ -437,6 +437,14 @@ namespace cds { namespace container { return base_class::array_node_size(); } + /// Collects tree level statistics into \p stat + /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics + */ + void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const + { + base_class::get_level_statistics(stat); + } + public: ///@name Thread-safe iterators /** @anchor cds_container_FeldmanHashSet_iterators diff --git a/cds/intrusive/details/feldman_hashset_base.h b/cds/intrusive/details/feldman_hashset_base.h index cb37cc29..e3bf8e41 100644 --- a/cds/intrusive/details/feldman_hashset_base.h +++ b/cds/intrusive/details/feldman_hashset_base.h @@ -250,6 +250,26 @@ namespace cds { namespace intrusive { } }; + /// One-level statistics, see \p FeldmanHashSet::get_level_statistics + struct level_statistics + { + size_t array_node_count; ///< Count of array node at the level + size_t node_capacity; ///< Array capacity + + size_t data_cell_count; ///< The number of data cells in all array node at this level + size_t array_cell_count; ///< The number of array cells in all array node at this level + size_t empty_cell_count; ///< The number of empty cells in all array node at this level + + //@cond + level_statistics() + : array_node_count(0) + , data_cell_count(0) + , array_cell_count(0) + , empty_cell_count(0) + {} + //@endcond + }; + //@cond namespace details { template diff --git a/cds/intrusive/feldman_hashset_rcu.h b/cds/intrusive/feldman_hashset_rcu.h index 52e79b2d..6eea7ed4 100644 --- a/cds/intrusive/feldman_hashset_rcu.h +++ b/cds/intrusive/feldman_hashset_rcu.h @@ -5,6 +5,7 @@ #include // std::ref #include // std::iterator_traits +#include #include #include @@ -531,6 +532,15 @@ namespace cds { namespace intrusive { return m_Metrics.array_node_size; } + /// Collects tree level statistics into \p stat + /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics + */ + void get_level_statistics(std::vector& stat) const + { + stat.clear(); + gather_level_statistics(stat, 0, m_Head, head_size()); + } + protected: //@cond class iterator_base @@ -1307,7 +1317,7 @@ namespace cds { namespace intrusive { void destroy_array_nodes(array_node * pArr, size_t nSize) { for (atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p) { - node_ptr slot = p->load(memory_model::memory_order_acquire); + node_ptr slot = p->load(memory_model::memory_order_relaxed); if (slot.bits() == flag_array_node) { destroy_array_nodes(to_array(slot.ptr()), array_node_size()); free_array_node(to_array(slot.ptr())); @@ -1316,6 +1326,29 @@ namespace cds { namespace intrusive { } } + void gather_level_statistics(std::vector& stat, size_t nLevel, array_node * pArr, size_t nSize) const + { + if (stat.size() <= nLevel) { + stat.resize(nLevel + 1); + stat[nLevel].node_capacity = nSize; + } + + ++stat[nLevel].array_node_count; + for (atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p) { + node_ptr slot = p->load(memory_model::memory_order_relaxed); + if (slot.bits() == flag_array_node) { + ++stat[nLevel].array_cell_count; + gather_level_statistics(stat, nLevel + 1, to_array(slot.ptr()), array_node_size()); + } + else if (slot.bits() == flag_array_converting) + ++stat[nLevel].array_cell_count; + else if (slot.ptr()) + ++stat[nLevel].data_cell_count; + else + ++stat[nLevel].empty_cell_count; + } + } + void clear_array(array_node * pArrNode, size_t nSize) { back_off bkoff; diff --git a/cds/intrusive/impl/feldman_hashset.h b/cds/intrusive/impl/feldman_hashset.h index fb713bbd..3f2e4606 100644 --- a/cds/intrusive/impl/feldman_hashset.h +++ b/cds/intrusive/impl/feldman_hashset.h @@ -5,6 +5,7 @@ #include // std::ref #include // std::iterator_traits +#include #include #include @@ -945,6 +946,21 @@ namespace cds { namespace intrusive { return m_Metrics.array_node_size; } + /// Collects tree level statistics into \p stat + /** @anchor cds_intrusive_FeldmanHashSet_hp_get_level_statistics + The function traverses the set and collects staistics for each level of the tree + into \p feldman_hashset::level_statistics struct. The element of \p stat[i] + represents statistics for level \p i, level 0 is head array. + The function is thread-safe and may be called in multi-threaded environment. + + Result can be useful for estimating efficiency of hash functor you use. + */ + void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const + { + stat.clear(); + gather_level_statistics( stat, 0, m_Head, head_size() ); + } + public: ///@name Thread-safe iterators /** @anchor cds_intrusive_FeldmanHashSet_iterators @@ -1101,8 +1117,8 @@ namespace cds { namespace intrusive { void destroy_array_nodes( array_node * pArr, size_t nSize ) { - for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) { - node_ptr slot = p->load( memory_model::memory_order_acquire ); + for ( atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p ) { + node_ptr slot = p->load( memory_model::memory_order_relaxed ); if ( slot.bits() == flag_array_node ) { destroy_array_nodes(to_array(slot.ptr()), array_node_size()); free_array_node( to_array(slot.ptr())); @@ -1111,6 +1127,28 @@ namespace cds { namespace intrusive { } } + void gather_level_statistics(std::vector& stat, size_t nLevel, array_node * pArr, size_t nSize) const + { + if (stat.size() <= nLevel) { + stat.resize(nLevel + 1); + stat[nLevel].node_capacity = nSize; + } + + ++stat[nLevel].array_node_count; + for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) { + node_ptr slot = p->load(memory_model::memory_order_relaxed); + if ( slot.bits()) { + ++stat[nLevel].array_cell_count; + if ( slot.bits() == flag_array_node ) + gather_level_statistics( stat, nLevel + 1, to_array(slot.ptr()), array_node_size()); + } + else if ( slot.ptr()) + ++stat[nLevel].data_cell_count; + else + ++stat[nLevel].empty_cell_count; + } + } + void clear_array( array_node * pArrNode, size_t nSize ) { back_off bkoff; diff --git a/doxygen/cds.doxy b/doxygen/cds.doxy index e0e50cac..94382b41 100644 --- a/doxygen/cds.doxy +++ b/doxygen/cds.doxy @@ -601,7 +601,7 @@ INPUT = $(DOXYPRJ_ROOT)/cds # into libc) for the transcoding. See http://www.gnu.org/software/libiconv for # the list of possible encodings. -INPUT_ENCODING = windows-1251 +INPUT_ENCODING = utf-8 # If the value of the INPUT tag contains directories, you can use the # FILE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp @@ -791,13 +791,13 @@ VERBATIM_HEADERS = NO # of all compounds will be generated. Enable this if the project # contains a lot of classes, structs, unions or interfaces. -ALPHABETICAL_INDEX = NO +ALPHABETICAL_INDEX = YES # If the alphabetical index is enabled (see ALPHABETICAL_INDEX) then # the COLS_IN_ALPHA_INDEX tag can be used to specify the number of columns # in which this list will be split (can be a number in the range [1..20]) -COLS_IN_ALPHA_INDEX = 5 +COLS_IN_ALPHA_INDEX = 2 # In case all classes in a project start with a common prefix, all # classes will be put under the same header in the alphabetical index. diff --git a/doxygen/image/feldman_hashset.png b/doxygen/image/feldman_hashset.png new file mode 100644 index 00000000..63b213bc Binary files /dev/null and b/doxygen/image/feldman_hashset.png differ diff --git a/doxygen/image/multilevel_hashset.png b/doxygen/image/multilevel_hashset.png deleted file mode 100644 index 63b213bc..00000000 Binary files a/doxygen/image/multilevel_hashset.png and /dev/null differ diff --git a/tests/unit/map2/map_delodd.cpp b/tests/unit/map2/map_delodd.cpp index 8d933e7d..2642b099 100644 --- a/tests/unit/map2/map_delodd.cpp +++ b/tests/unit/map2/map_delodd.cpp @@ -37,4 +37,10 @@ namespace map2 { shuffle( m_arrRemove.begin(), m_arrRemove.end() ); } + void Map_DelOdd::endTestCase() + { + m_arrInsert.resize(0); + m_arrRemove.resize(0); + } + } // namespace map2 diff --git a/tests/unit/map2/map_delodd.h b/tests/unit/map2/map_delodd.h index 9b39b8d8..cee00c41 100644 --- a/tests/unit/map2/map_delodd.h +++ b/tests/unit/map2/map_delodd.h @@ -11,12 +11,12 @@ namespace map2 { namespace { struct key_thread { - size_t nKey; - size_t nThread; + uint32_t nKey; + uint32_t nThread; key_thread( size_t key, size_t threadNo ) - : nKey( key ) - , nThread( threadNo ) + : nKey( static_cast(key)) + , nThread( static_cast(threadNo)) {} key_thread() @@ -708,6 +708,8 @@ namespace map2 { CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found"); } + print_stat(testMap); + check_before_cleanup( testMap ); CPPUNIT_MSG( " Clear map (single-threaded)..." ); @@ -766,6 +768,7 @@ namespace map2 { } void setUpParams( const CppUnitMini::TestCfg& cfg ); + virtual void endTestCase(); # include "map2/map_defs.h" CDSUNIT_DECLARE_MichaelMap diff --git a/tests/unit/map2/map_type_feldman_hashmap.h b/tests/unit/map2/map_type_feldman_hashmap.h index ec1bbc28..b858846c 100644 --- a/tests/unit/map2/map_type_feldman_hashmap.h +++ b/tests/unit/map2/map_type_feldman_hashmap.h @@ -220,6 +220,21 @@ namespace map2 { static inline void print_stat( FeldmanHashMap< GC, K, T, Traits > const& m ) { CPPUNIT_MSG( m.statistics() ); + + std::vector< cds::intrusive::feldman_hashset::level_statistics > level_stat; + m.get_level_statistics( level_stat ); + CPPUNIT_MSG( "Level statistics, height=" << level_stat.size()); + size_t i = 0; + CPPUNIT_MSG( " i node_count capacity data_cell array_cell empty_cell" ); + for (auto it = level_stat.begin(); it != level_stat.end(); ++it, ++i) { + CPPUNIT_MSG( std::setw(3) << i << std::setw(0) << " " + << std::setw(12) << it->array_node_count << std::setw(0) << " " + << std::setw(8) << it->node_capacity << std::setw(0) << " " + << std::setw(12) << it->data_cell_count << std::setw(0) << " " + << std::setw(12) << it->array_cell_count << std::setw(0) << " " + << std::setw(12) << it->empty_cell_count << std::setw(0) + ); + } } } // namespace map2