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