test/stress/parallel/parallel-map/find_string/map_find_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_find_string.h"
  32 #include <cds_test/hash_func.h>
  33
  34 namespace map {
  35
  36     size_t Map_find_string::s_nThreadCount = 8;
  37     size_t Map_find_string::s_nMapSize = 10000000;
  38     size_t Map_find_string::s_nMaxLoadFactor = 8;
  39     size_t Map_find_string::s_nPercentExists = 50;
  40     size_t Map_find_string::s_nPassCount = 2;
  41     size_t Map_find_string::s_nFeldmanPassCount = 100;
  42     size_t Map_find_string::s_nBronsonAVLTreeMapPassCount = 100;
  43     size_t Map_find_string::s_nEllenBinTreeMapPassCount = 100;
  44     size_t Map_find_string::s_nMichaelMapPassCount = 100;
  45     size_t Map_find_string::s_nSkipListMapPassCount = 100;
  46     size_t Map_find_string::s_nSplitListMapPassCount = 100;
  47
  48     size_t Map_find_string::s_nCuckooInitialSize = 1024;
  49     size_t Map_find_string::s_nCuckooProbesetSize = 16;
  50     size_t Map_find_string::s_nCuckooProbesetThreshold = 0;
  51
  52     size_t Map_find_string::s_nFeldmanMap_HeadBits = 10;
  53     size_t Map_find_string::s_nFeldmanMap_ArrayBits = 4;
  54
  55
  56     size_t Map_find_string::s_nLoadFactor = 1;
  57     Map_find_string::value_vector Map_find_string::s_Data;
  58     std::vector<std::string> Map_find_string::s_arrString;
  59
  60     void Map_find_string::setup_test_case()
  61     {
  62       cds_test::config const &cfg =
  63           get_config("sequential_real_map_find_string");
  64
  65       s_nMapSize = cfg.get_size_t("MapSize", s_nMapSize);
  66       if (s_nMapSize < 1000)
  67         s_nMapSize = 1000;
  68
  69       s_nThreadCount = cfg.get_size_t("ThreadCount", s_nThreadCount);
  70       if (s_nThreadCount == 0)
  71         s_nThreadCount = 1;
  72
  73       s_nPassCount = cfg.get_size_t("PassCount", s_nPassCount);
  74       if (s_nPassCount == 0)
  75         s_nPassCount = 100;
  76
  77       s_nFeldmanPassCount =
  78           cfg.get_size_t("FeldmanPassCount", s_nFeldmanPassCount);
  79       if (s_nFeldmanPassCount == 0)
  80         s_nFeldmanPassCount = 500;
  81
  82       s_nBronsonAVLTreeMapPassCount = cfg.get_size_t(
  83           "BronsonAVLTreeMapPassCount", s_nBronsonAVLTreeMapPassCount);
  84       if (s_nBronsonAVLTreeMapPassCount == 0)
  85         s_nBronsonAVLTreeMapPassCount = 500;
  86
  87       s_nEllenBinTreeMapPassCount = cfg.get_size_t("EllenBinTreeMapPassCount",
  88                                                    s_nEllenBinTreeMapPassCount);
  89       if (s_nEllenBinTreeMapPassCount == 0)
  90         s_nEllenBinTreeMapPassCount = 500;
  91
  92       s_nMichaelMapPassCount =
  93           cfg.get_size_t("MichaelMapPassCount", s_nMichaelMapPassCount);
  94       if (s_nMichaelMapPassCount == 0)
  95         s_nMichaelMapPassCount = 500;
  96
  97       s_nSkipListMapPassCount =
  98           cfg.get_size_t("SkipListMapPassCount", s_nSkipListMapPassCount);
  99       if (s_nSkipListMapPassCount == 0)
 100         s_nSkipListMapPassCount = 500;
 101
 102       s_nSplitListMapPassCount =
 103           cfg.get_size_t("SplitListMapPassCount", s_nSplitListMapPassCount);
 104       if (s_nSplitListMapPassCount == 0)
 105         s_nSplitListMapPassCount = 500;
 106
 107       s_nPercentExists = cfg.get_size_t("PercentExists", s_nPercentExists);
 108       if (s_nPercentExists > 100)
 109         s_nPercentExists = 100;
 110       else if (s_nPercentExists < 1)
 111         s_nPercentExists = 1;
 112
 113       s_nMaxLoadFactor = cfg.get_size_t("MaxLoadFactor", s_nMaxLoadFactor);
 114       if (s_nMaxLoadFactor == 0)
 115         s_nMaxLoadFactor = 1;
 116
 117       s_nCuckooInitialSize =
 118           cfg.get_size_t("CuckooInitialSize", s_nCuckooInitialSize);
 119       if (s_nCuckooInitialSize < 256)
 120         s_nCuckooInitialSize = 256;
 121
 122       s_nCuckooProbesetSize =
 123           cfg.get_size_t("CuckooProbesetSize", s_nCuckooProbesetSize);
 124       if (s_nCuckooProbesetSize < 8)
 125         s_nCuckooProbesetSize = 8;
 126
 127       s_nCuckooProbesetThreshold =
 128           cfg.get_size_t("CuckooProbesetThreshold", s_nCuckooProbesetThreshold);
 129
 130       s_nFeldmanMap_HeadBits =
 131           cfg.get_size_t("FeldmanMapHeadBits", s_nFeldmanMap_HeadBits);
 132       if (s_nFeldmanMap_HeadBits == 0)
 133         s_nFeldmanMap_HeadBits = 2;
 134
 135       s_nFeldmanMap_ArrayBits =
 136           cfg.get_size_t("FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits);
 137       if (s_nFeldmanMap_ArrayBits == 0)
 138         s_nFeldmanMap_ArrayBits = 2;
 139
 140       s_arrString = load_dictionary();
 141     }
 142
 143     void Map_find_string::TearDownTestCase()
 144     {
 145         s_arrString.clear();
 146         s_Data.clear();
 147     }
 148
 149     void Map_find_string::SetUpTestCase()
 150     {
 151         setup_test_case();
 152
 153         s_Data.clear();
 154
 155         size_t nSize = s_arrString.size();
 156         if ( nSize > s_nMapSize )
 157             nSize = s_nMapSize;
 158         s_Data.reserve( nSize );
 159
 160         size_t nActualSize = 0;
 161         for ( size_t i = 0; i < nSize; ++i ) {
 162             bool bExists = rand( 100 ) <= s_nPercentExists;
 163             if ( bExists )
 164                 ++nActualSize;
 165             s_Data.push_back( { &s_arrString.at( i ), bExists } );
 166         }
 167         s_nMapSize = nActualSize;
 168     }
 169
 170     template <typename Hash>
 171     void Map_find_string::fill_string_array()
 172     {
 173         typedef Hash hasher;
 174         typedef typename hasher::result_type hash_type;
 175
 176         std::map<hash_type, size_t> mapHash;
 177         s_Data.clear();
 178
 179         size_t nSize = s_arrString.size();
 180         if ( nSize > s_nMapSize )
 181             nSize = s_nMapSize;
 182         s_Data.reserve( nSize );
 183
 184         size_t nActualSize = 0;
 185         size_t nDiffHash = 0;
 186         hasher h;
 187         for ( size_t i = 0; i < s_arrString.size(); ++i ) {
 188             hash_type hash = h( s_arrString.at( i ));
 189             if ( mapHash.insert( std::make_pair( hash, i )).second ) {
 190                 if ( ++nDiffHash >= nSize )
 191                     break;
 192                 bool bExists = rand( 100 ) <= s_nPercentExists;
 193                 if ( bExists )
 194                     ++nActualSize;
 195                 s_Data.push_back( { &s_arrString.at( i ), bExists } );
 196             }
 197         }
 198         s_nMapSize = nActualSize;
 199
 200     }
 201
 202     void Map_find_string_stdhash::SetUpTestCase()
 203     {
 204         setup_test_case();
 205         fill_string_array<std::hash<std::string>>();
 206     }
 207
 208 #if CDS_BUILD_BITS == 64
 209     void Map_find_string_city32::SetUpTestCase()
 210     {
 211         setup_test_case();
 212         fill_string_array<cds_test::city32>();
 213     }
 214
 215     void Map_find_string_city64::SetUpTestCase()
 216     {
 217         setup_test_case();
 218         fill_string_array<cds_test::city64>();
 219     }
 220
 221     void Map_find_string_city128::SetUpTestCase()
 222     {
 223         setup_test_case();
 224         fill_string_array<cds_test::city128>();
 225     }
 226
 227 #endif
 228
 229     std::vector<size_t> Map_find_string::get_load_factors()
 230     {
 231         cds_test::config const& cfg = get_config( "map_find_string" );
 232
 233         s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
 234         if ( s_nMaxLoadFactor == 0 )
 235             s_nMaxLoadFactor = 1;
 236
 237         std::vector<size_t> lf;
 238         for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
 239             lf.push_back( n );
 240
 241         return lf;
 242     }
 243
 244 #ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
 245     static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
 246     {
 247         return std::to_string( p.param );
 248     }
 249     INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()), get_test_parameter_name );
 250 #else
 251     INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()));
 252 #endif
 253
 254
 255 } // namespace map