test/stress/map/minmax/map_minmax.h

   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_type.h"
  32 #include <cds/os/topology.h>
  33
  34 namespace map {
  35
  36     class Map_MinMax: public cds_test::stress_fixture
  37     {
  38     public:
  39         static size_t s_nInsThreadCount;      // insert thread count
  40         static size_t s_nExtractThreadCount;  // extract thread count
  41         static size_t s_nMapSize;             // max map size
  42         static size_t s_nPassCount;
  43
  44         //static size_t s_nFeldmanMap_HeadBits;
  45         //static size_t s_nFeldmanMap_ArrayBits;
  46
  47         static size_t  s_nLoadFactor;  // current load factor
  48
  49         static void SetUpTestCase();
  50         //static void TearDownTestCase();
  51
  52     protected:
  53         typedef int     key_type;
  54         typedef int     value_type;
  55         typedef std::pair<key_type const, value_type> pair_type;
  56
  57         atomics::atomic<size_t> m_nInsThreadCount;
  58         key_type    m_KeyMin;
  59         key_type    m_KeyMax;
  60
  61         enum {
  62             inserter_thread,
  63             extractor_thread,
  64         };
  65
  66         template <class Map>
  67         class Inserter: public cds_test::thread
  68         {
  69             typedef cds_test::thread base_class;
  70             Map&     m_Map;
  71             std::vector<key_type> m_arr;
  72
  73             void init_data()
  74             {
  75                 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
  76                 key_type keyMin = fixture.m_KeyMin;
  77                 key_type keyMax = fixture.m_KeyMax;
  78
  79                 for ( key_type i = keyMin + 10; i >= keyMin; --i )
  80                     m_arr.push_back( i );
  81                 for ( key_type i = keyMax - 10; i <= keyMax; ++i )
  82                     m_arr.push_back( i );
  83                 shuffle( m_arr.begin(), m_arr.end() );
  84             }
  85
  86         public:
  87             size_t m_nInsertMinSuccess = 0;
  88             size_t m_nInsertMinFailed = 0;
  89             size_t m_nInsertMaxSuccess = 0;
  90             size_t m_nInsertMaxFailed = 0;
  91
  92         public:
  93             Inserter( cds_test::thread_pool& pool, Map& map )
  94                 : base_class( pool, inserter_thread )
  95                 , m_Map( map )
  96             {
  97                 init_data();
  98             }
  99
 100             Inserter( Inserter& src )
 101                 : base_class( src )
 102                 , m_Map( src.m_Map )
 103             {
 104                 init_data();
 105             }
 106
 107             virtual thread * clone()
 108             {
 109                 return new Inserter( *this );
 110             }
 111
 112             virtual void test()
 113             {
 114                 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
 115
 116                 key_type keyMin = fixture.m_KeyMin;
 117                 key_type keyMax = fixture.m_KeyMax;
 118
 119                 for ( size_t nPass = 0; nPass < s_nPassCount; ++nPass ) {
 120                     for ( key_type key : m_arr ) {
 121                         if ( m_Map.insert( key, key ) ) {
 122                             if ( key == keyMin )
 123                                 ++m_nInsertMinSuccess;
 124                             else if ( key == keyMax )
 125                                 ++m_nInsertMaxSuccess;
 126                         }
 127                         else {
 128                             if ( key == keyMin )
 129                                 ++m_nInsertMinFailed;
 130                             else if ( key == keyMax )
 131                                 ++m_nInsertMaxFailed;
 132                         }
 133                     }
 134                 }
 135
 136                 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
 137             }
 138         };
 139
 140         // Deletes odd keys from [0..N)
 141         template <class GC, class Map >
 142         class Extractor: public cds_test::thread
 143         {
 144             typedef cds_test::thread base_class;
 145             Map&     m_Map;
 146
 147         public:
 148             size_t  m_nDeleteMin = 0;
 149             size_t  m_nDeleteMinFailed = 0;
 150             size_t  m_nDeleteMax = 0;
 151             size_t  m_nDeleteMaxFailed = 0;
 152
 153         public:
 154             Extractor( cds_test::thread_pool& pool, Map& map )
 155                 : base_class( pool, extractor_thread )
 156                 , m_Map( map )
 157             {}
 158
 159             Extractor( Extractor& src )
 160                 : base_class( src )
 161                 , m_Map( src.m_Map )
 162             {}
 163
 164             virtual thread * clone()
 165             {
 166                 return new Extractor( *this );
 167             }
 168
 169             virtual void test()
 170             {
 171                 Map& rMap = m_Map;
 172
 173                 typename Map::guarded_ptr gp;
 174                 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
 175
 176                 key_type keyMin = fixture.m_KeyMin;
 177                 key_type keyMax = fixture.m_KeyMax;
 178
 179                 do {
 180                     gp = rMap.extract_min();
 181                     if ( gp ) {
 182                         if ( gp->first == keyMin )
 183                             ++m_nDeleteMin;
 184                     }
 185                     else
 186                         ++m_nDeleteMinFailed;
 187
 188                     gp = rMap.extract_max();
 189                     if ( gp ) {
 190                         if ( gp->first == keyMax )
 191                             ++m_nDeleteMax;
 192                     }
 193                     else
 194                         ++m_nDeleteMaxFailed;
 195
 196                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 197             }
 198         };
 199
 200         template <class RCU, class Map >
 201         class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
 202         {
 203             typedef cds_test::thread base_class;
 204             Map&     m_Map;
 205
 206         public:
 207             size_t  m_nDeleteMin = 0;
 208             size_t  m_nDeleteMinFailed = 0;
 209             size_t  m_nDeleteMax = 0;
 210             size_t  m_nDeleteMaxFailed = 0;
 211
 212         public:
 213             Extractor( cds_test::thread_pool& pool, Map& map )
 214                 : base_class( pool, extractor_thread )
 215                 , m_Map( map )
 216             {}
 217
 218             Extractor( Extractor& src )
 219                 : base_class( src )
 220                 , m_Map( src.m_Map )
 221             {}
 222
 223             virtual thread * clone()
 224             {
 225                 return new Extractor( *this );
 226             }
 227
 228             virtual void test()
 229             {
 230                 Map& rMap = m_Map;
 231                 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
 232
 233                 key_type keyMin = fixture.m_KeyMin;
 234                 key_type keyMax = fixture.m_KeyMax;
 235
 236                 static_assert( !Map::c_bExtractLockExternal, "No external RCU locking required" );
 237
 238                 do {
 239                     auto res = rMap.extract_min_key();
 240                     if ( res.second ) {
 241                         if ( res.first == keyMin )
 242                             ++m_nDeleteMin;
 243                     }
 244                     else
 245                         ++m_nDeleteMinFailed;
 246
 247                     res = rMap.extract_max_key();
 248                     if ( res.second ) {
 249                         if ( res.first == keyMax )
 250                             ++m_nDeleteMax;
 251                     }
 252                     else
 253                         ++m_nDeleteMaxFailed;
 254                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 255
 256                 auto res = rMap.extract_min_key();
 257                 if ( res.second ) {
 258                     if ( res.first == keyMin )
 259                         ++m_nDeleteMin;
 260                 }
 261                 else
 262                     ++m_nDeleteMinFailed;
 263
 264                 res = rMap.extract_max_key();
 265                 if ( res.second ) {
 266                     if ( res.first == keyMax )
 267                         ++m_nDeleteMax;
 268                 }
 269                 else
 270                     ++m_nDeleteMaxFailed;
 271             }
 272         };
 273
 274     protected:
 275         template <class Map>
 276         void do_test( Map& testMap )
 277         {
 278             typedef Inserter<Map> insert_thread;
 279             typedef Extractor< typename Map::gc, Map > extract_thread;
 280
 281             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 282
 283             {
 284                 std::vector<key_type> arr;
 285                 arr.resize( s_nMapSize );
 286                 for ( int i = 0; i < static_cast<int>( s_nMapSize ); ++i )
 287                     arr[i] = i;;
 288                 shuffle( arr.begin(), arr.end() );
 289
 290                 for ( key_type key : arr )
 291                     testMap.insert( key, key );
 292             }
 293
 294             m_KeyMin = 0;
 295             m_KeyMax = static_cast<int>( s_nMapSize - 1 );
 296
 297             cds_test::thread_pool& pool = get_pool();
 298             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
 299             pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
 300
 301             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 302                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
 303                 << std::make_pair( "map_size", s_nMapSize )
 304                 << std::make_pair( "pass_count", s_nPassCount );
 305
 306             std::chrono::milliseconds duration = pool.run();
 307
 308             propout() << std::make_pair( "duration", duration );
 309
 310             size_t nInsertMinSuccess = 0;
 311             size_t nInsertMinFailed = 0;
 312             size_t nInsertMaxSuccess = 0;
 313             size_t nInsertMaxFailed = 0;
 314             size_t nDeleteMin = 0;
 315             size_t nDeleteMinFailed = 0;
 316             size_t nDeleteMax = 0;
 317             size_t nDeleteMaxFailed = 0;
 318
 319             for ( size_t i = 0; i < pool.size(); ++i ) {
 320                 cds_test::thread& thr = pool.get( i );
 321                 switch ( thr.type()) {
 322                 case inserter_thread:
 323                 {
 324                     insert_thread& inserter = static_cast<insert_thread&>(thr);
 325                     nInsertMinSuccess += inserter.m_nInsertMinSuccess;
 326                     nInsertMinFailed += inserter.m_nInsertMinFailed;
 327                     nInsertMaxSuccess += inserter.m_nInsertMaxSuccess;
 328                     nInsertMaxFailed += inserter.m_nInsertMaxFailed;
 329                 }
 330                 break;
 331                 case extractor_thread:
 332                 {
 333                     extract_thread& extractor = static_cast<extract_thread&>(thr);
 334                     nDeleteMin += extractor.m_nDeleteMin;
 335                     nDeleteMinFailed += extractor.m_nDeleteMinFailed;
 336                     nDeleteMax += extractor.m_nDeleteMax;
 337                     nDeleteMaxFailed += extractor.m_nDeleteMaxFailed;
 338                 }
 339                 break;
 340                 default:
 341                     assert( false );
 342                 }
 343             }
 344
 345             EXPECT_EQ( nDeleteMinFailed, 0u );
 346             EXPECT_EQ( nDeleteMaxFailed, 0u );
 347
 348             EXPECT_EQ( nDeleteMin, nInsertMinSuccess + 1 );
 349             EXPECT_EQ( nDeleteMax, nInsertMaxSuccess + 1 );
 350
 351             propout()
 352                 << std::make_pair( "insert_min", nInsertMinSuccess + 1 )
 353                 << std::make_pair( "insert_min_double", nInsertMinFailed )
 354                 << std::make_pair( "insert_max", nInsertMaxSuccess + 1 )
 355                 << std::make_pair( "insert_max_double", nInsertMaxFailed )
 356                 << std::make_pair( "extract_min", nDeleteMin )
 357                 << std::make_pair( "extract_min_failed", nDeleteMinFailed )
 358                 << std::make_pair( "extract_max", nDeleteMax )
 359                 << std::make_pair( "extract_max_failed", nDeleteMaxFailed );
 360
 361             analyze( testMap );
 362         }
 363
 364         template <class Map>
 365         void analyze( Map& testMap )
 366         {
 367             print_stat( propout(), testMap );
 368
 369             check_before_cleanup( testMap );
 370             testMap.clear();
 371             EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
 372
 373             additional_check( testMap );
 374             additional_cleanup( testMap );
 375         }
 376
 377         template <class Map>
 378         void run_test()
 379         {
 380             static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
 381             Map testMap( *this );
 382             do_test( testMap );
 383         }
 384     };
 385
 386 } // namespace map