test/stress/parallel/parallel-map/insdel_string/map_insdel_string.cpp

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #include "map_insdel_string.h"
  32 #include <cds_test/hash_func.h>
  33
  34 namespace map {
  35
  36     size_t Map_InsDel_string::s_nMapSize = 1000000;      // map size
  37     size_t Map_InsDel_string::s_nInsertThreadCount = 4;  // count of insertion thread
  38     size_t Map_InsDel_string::s_nDeleteThreadCount = 4;  // count of deletion thread
  39     size_t Map_InsDel_string::s_nThreadPassCount = 4;    // pass count for each thread
  40     size_t Map_InsDel_string::s_nFeldmanPassCount = 100;
  41     size_t Map_InsDel_string::s_nBronsonAVLTreeMapPassCount = 100;
  42     size_t Map_InsDel_string::s_nEllenBinTreeMapPassCount = 100;
  43     size_t Map_InsDel_string::s_nMichaelMapPassCount = 100;
  44     size_t Map_InsDel_string::s_nSkipListMapPassCount = 100;
  45     size_t Map_InsDel_string::s_nSplitListMapPassCount = 100;
  46
  47     size_t Map_InsDel_string::s_nMaxLoadFactor = 8;      // maximum load factor
  48
  49     size_t Map_InsDel_string::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
  50     size_t Map_InsDel_string::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
  51     size_t Map_InsDel_string::s_nCuckooProbesetThreshold = 0; // CuckooSet probeset threshold (0 - use default)
  52
  53     size_t Map_InsDel_string::s_nFeldmanMap_HeadBits = 10;
  54     size_t Map_InsDel_string::s_nFeldmanMap_ArrayBits = 4;
  55
  56     size_t Map_InsDel_string::s_nLoadFactor = 1;
  57     std::vector<std::string> Map_InsDel_string::s_arrKeys;
  58
  59     void Map_InsDel_string::setup_test_case()
  60     {
  61         cds_test::config const& cfg = get_config( "sequential_real_map_insdel_string" );
  62
  63         s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
  64         if ( s_nMapSize < 1000 )
  65             s_nMapSize = 1000;
  66
  67         s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
  68         if ( s_nInsertThreadCount == 0 )
  69             s_nInsertThreadCount = 2;
  70
  71         s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
  72         if ( s_nDeleteThreadCount == 0 )
  73             s_nDeleteThreadCount = 2;
  74
  75         s_nThreadPassCount = cfg.get_size_t( "ThreadPassCount", s_nThreadPassCount );
  76         if ( s_nThreadPassCount == 0 )
  77             s_nThreadPassCount = 4;
  78
  79         s_nFeldmanPassCount =
  80             cfg.get_size_t("FeldmanPassCount", s_nFeldmanPassCount);
  81         if (s_nFeldmanPassCount == 0)
  82           s_nFeldmanPassCount = 500;
  83
  84         s_nBronsonAVLTreeMapPassCount = cfg.get_size_t(
  85             "BronsonAVLTreeMapPassCount", s_nBronsonAVLTreeMapPassCount);
  86         if (s_nBronsonAVLTreeMapPassCount == 0)
  87           s_nBronsonAVLTreeMapPassCount = 500;
  88
  89         s_nEllenBinTreeMapPassCount = cfg.get_size_t(
  90             "EllenBinTreeMapPassCount", s_nEllenBinTreeMapPassCount);
  91         if (s_nEllenBinTreeMapPassCount == 0)
  92           s_nEllenBinTreeMapPassCount = 500;
  93
  94         s_nMichaelMapPassCount =
  95             cfg.get_size_t("MichaelMapPassCount", s_nMichaelMapPassCount);
  96         if (s_nMichaelMapPassCount == 0)
  97           s_nMichaelMapPassCount = 500;
  98
  99         s_nSkipListMapPassCount =
 100             cfg.get_size_t("SkipListMapPassCount", s_nSkipListMapPassCount);
 101         if (s_nSkipListMapPassCount == 0)
 102           s_nSkipListMapPassCount = 500;
 103
 104         s_nSplitListMapPassCount =
 105             cfg.get_size_t("SplitListMapPassCount", s_nSplitListMapPassCount);
 106         if (s_nSplitListMapPassCount == 0)
 107           s_nSplitListMapPassCount = 500;
 108
 109         s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
 110         if ( s_nMaxLoadFactor == 0 )
 111             s_nMaxLoadFactor = 1;
 112
 113         s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
 114         if ( s_nCuckooInitialSize < 256 )
 115             s_nCuckooInitialSize = 256;
 116
 117         s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
 118         if ( s_nCuckooProbesetSize < 8 )
 119             s_nCuckooProbesetSize = 8;
 120
 121         s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
 122
 123         s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
 124         if ( s_nFeldmanMap_HeadBits == 0 )
 125             s_nFeldmanMap_HeadBits = 2;
 126
 127         s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
 128         if ( s_nFeldmanMap_ArrayBits == 0 )
 129             s_nFeldmanMap_ArrayBits = 2;
 130     }
 131
 132     void Map_InsDel_string::SetUpTestCase()
 133     {
 134         setup_test_case();
 135
 136         s_arrKeys.clear();
 137         s_arrKeys.reserve( s_nMapSize );
 138         std::vector<std::string> dict = load_dictionary();
 139         for ( size_t i = 0; i < s_nMapSize; ++i )
 140             s_arrKeys.push_back( std::move( dict.at(i)));
 141     }
 142
 143     void Map_InsDel_string::TearDownTestCase()
 144     {
 145         s_arrKeys.clear();
 146     }
 147
 148     std::vector<size_t> Map_InsDel_string::get_load_factors()
 149     {
 150         cds_test::config const& cfg = get_config( "map_insdel_string" );
 151
 152         s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
 153         if ( s_nMaxLoadFactor == 0 )
 154             s_nMaxLoadFactor = 1;
 155
 156         std::vector<size_t> lf;
 157         for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
 158             lf.push_back( n );
 159
 160         return lf;
 161     }
 162
 163     template <typename Hash>
 164     void Map_InsDel_string::fill_string_array()
 165     {
 166         typedef Hash hasher;
 167         typedef typename hasher::result_type hash_type;
 168
 169         std::map<hash_type, size_t> mapHash;
 170         s_arrKeys.clear();
 171         std::vector<std::string> dict = load_dictionary();
 172
 173         size_t nSize = dict.size();
 174         if ( nSize > s_nMapSize )
 175             nSize = s_nMapSize;
 176         s_arrKeys.reserve( nSize );
 177
 178         size_t nDiffHash = 0;
 179         hasher h;
 180         for ( size_t i = 0; i < dict.size(); ++i ) {
 181             hash_type hash = h( dict.at( i ));
 182             if ( mapHash.insert( std::make_pair( hash, i )).second ) {
 183                 if ( ++nDiffHash >= nSize )
 184                     break;
 185                 s_arrKeys.push_back( std::move( dict.at( i )));
 186             }
 187         }
 188         s_nMapSize = dict.size();
 189     }
 190
 191     void Map_InsDel_string_stdhash::SetUpTestCase()
 192     {
 193         setup_test_case();
 194         fill_string_array<std::hash<std::string>>();
 195     }
 196
 197 #if CDS_BUILD_BITS == 64
 198     void Map_InsDel_string_city32::SetUpTestCase()
 199     {
 200         setup_test_case();
 201         fill_string_array<cds_test::city32>();
 202     }
 203
 204     void Map_InsDel_string_city64::SetUpTestCase()
 205     {
 206         setup_test_case();
 207         fill_string_array<cds_test::city64>();
 208     }
 209
 210     void Map_InsDel_string_city128::SetUpTestCase()
 211     {
 212         setup_test_case();
 213         fill_string_array<cds_test::city128>();
 214     }
 215
 216 #endif
 217
 218 #ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
 219     static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
 220     {
 221         return std::to_string( p.param );
 222     }
 223     INSTANTIATE_TEST_CASE_P( a, Map_InsDel_string_LF, ::testing::ValuesIn( Map_InsDel_string::get_load_factors()), get_test_parameter_name );
 224 #else
 225     INSTANTIATE_TEST_CASE_P( a, Map_InsDel_string_LF, ::testing::ValuesIn( Map_InsDel_string::get_load_factors()));
 226 #endif
 227
 228 } // namespace map