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                 gp = rMap.extract_min();
 199                 if ( gp ) {
 200                     if ( gp->first == keyMin )
 201                         ++m_nDeleteMin;
 202                 }
 203                 else
 204                     ++m_nDeleteMinFailed;
 205
 206                 gp = rMap.extract_max();
 207                 if ( gp ) {
 208                     if ( gp->first == keyMax )
 209                         ++m_nDeleteMax;
 210                 }
 211                 else
 212                     ++m_nDeleteMaxFailed;
 213             }
 214         };
 215
 216         template <class RCU, class Map >
 217         class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
 218         {
 219             typedef cds_test::thread base_class;
 220             Map&     m_Map;
 221
 222         public:
 223             size_t  m_nDeleteMin = 0;
 224             size_t  m_nDeleteMinFailed = 0;
 225             size_t  m_nDeleteMax = 0;
 226             size_t  m_nDeleteMaxFailed = 0;
 227
 228         public:
 229             Extractor( cds_test::thread_pool& pool, Map& map )
 230                 : base_class( pool, extractor_thread )
 231                 , m_Map( map )
 232             {}
 233
 234             Extractor( Extractor& src )
 235                 : base_class( src )
 236                 , m_Map( src.m_Map )
 237             {}
 238
 239             virtual thread * clone()
 240             {
 241                 return new Extractor( *this );
 242             }
 243
 244             virtual void test()
 245             {
 246                 Map& rMap = m_Map;
 247                 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
 248
 249                 key_type keyMin = fixture.m_KeyMin;
 250                 key_type keyMax = fixture.m_KeyMax;
 251
 252                 static_assert( !Map::c_bExtractLockExternal, "No external RCU locking required" );
 253
 254                 do {
 255                     auto res = rMap.extract_min_key();
 256                     if ( res.second ) {
 257                         if ( res.first == keyMin )
 258                             ++m_nDeleteMin;
 259                     }
 260                     else
 261                         ++m_nDeleteMinFailed;
 262
 263                     res = rMap.extract_max_key();
 264                     if ( res.second ) {
 265                         if ( res.first == keyMax )
 266                             ++m_nDeleteMax;
 267                     }
 268                     else
 269                         ++m_nDeleteMaxFailed;
 270                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 271
 272                 auto res = rMap.extract_min_key();
 273                 if ( res.second ) {
 274                     if ( res.first == keyMin )
 275                         ++m_nDeleteMin;
 276                 }
 277                 else
 278                     ++m_nDeleteMinFailed;
 279
 280                 res = rMap.extract_max_key();
 281                 if ( res.second ) {
 282                     if ( res.first == keyMax )
 283                         ++m_nDeleteMax;
 284                 }
 285                 else
 286                     ++m_nDeleteMaxFailed;
 287             }
 288         };
 289
 290     protected:
 291         template <class Map>
 292         void do_test( Map& testMap )
 293         {
 294             typedef Inserter<Map> insert_thread;
 295             typedef Extractor< typename Map::gc, Map > extract_thread;
 296
 297             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 298
 299             {
 300                 std::vector<key_type> arr;
 301                 arr.resize( s_nMapSize );
 302                 for ( int i = 0; i < static_cast<int>( s_nMapSize ); ++i )
 303                     arr[i] = i;;
 304                 shuffle( arr.begin(), arr.end());
 305
 306                 for ( key_type key : arr )
 307                     testMap.insert( key, key );
 308             }
 309
 310             m_KeyMin = 0;
 311             m_KeyMax = static_cast<int>( s_nMapSize - 1 );
 312
 313             cds_test::thread_pool& pool = get_pool();
 314             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
 315             pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
 316
 317             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 318                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
 319                 << std::make_pair( "map_size", s_nMapSize )
 320                 << std::make_pair( "pass_count", s_nPassCount );
 321
 322             std::chrono::milliseconds duration = pool.run();
 323
 324             propout() << std::make_pair( "duration", duration );
 325
 326             size_t nInsertMinSuccess = 0;
 327             size_t nInsertMinFailed = 0;
 328             size_t nInsertMaxSuccess = 0;
 329             size_t nInsertMaxFailed = 0;
 330             size_t nDeleteMin = 0;
 331             size_t nDeleteMinFailed = 0;
 332             size_t nDeleteMax = 0;
 333             size_t nDeleteMaxFailed = 0;
 334
 335             for ( size_t i = 0; i < pool.size(); ++i ) {
 336                 cds_test::thread& thr = pool.get( i );
 337                 switch ( thr.type()) {
 338                 case inserter_thread:
 339                 {
 340                     insert_thread& inserter = static_cast<insert_thread&>(thr);
 341                     nInsertMinSuccess += inserter.m_nInsertMinSuccess;
 342                     nInsertMinFailed += inserter.m_nInsertMinFailed;
 343                     nInsertMaxSuccess += inserter.m_nInsertMaxSuccess;
 344                     nInsertMaxFailed += inserter.m_nInsertMaxFailed;
 345                 }
 346                 break;
 347                 case extractor_thread:
 348                 {
 349                     extract_thread& extractor = static_cast<extract_thread&>(thr);
 350                     nDeleteMin += extractor.m_nDeleteMin;
 351                     nDeleteMinFailed += extractor.m_nDeleteMinFailed;
 352                     nDeleteMax += extractor.m_nDeleteMax;
 353                     nDeleteMaxFailed += extractor.m_nDeleteMaxFailed;
 354                 }
 355                 break;
 356                 default:
 357                     assert( false );
 358                 }
 359             }
 360
 361             EXPECT_EQ( nDeleteMinFailed, 0u );
 362             EXPECT_EQ( nDeleteMaxFailed, 0u );
 363
 364             EXPECT_EQ( nDeleteMin, nInsertMinSuccess + 1 );
 365             EXPECT_EQ( nDeleteMax, nInsertMaxSuccess + 1 );
 366
 367             propout()
 368                 << std::make_pair( "insert_min", nInsertMinSuccess + 1 )
 369                 << std::make_pair( "insert_min_double", nInsertMinFailed )
 370                 << std::make_pair( "insert_max", nInsertMaxSuccess + 1 )
 371                 << std::make_pair( "insert_max_double", nInsertMaxFailed )
 372                 << std::make_pair( "extract_min", nDeleteMin )
 373                 << std::make_pair( "extract_min_failed", nDeleteMinFailed )
 374                 << std::make_pair( "extract_max", nDeleteMax )
 375                 << std::make_pair( "extract_max_failed", nDeleteMaxFailed );
 376
 377             analyze( testMap );
 378         }
 379
 380         template <class Map>
 381         void analyze( Map& testMap )
 382         {
 383             print_stat( propout(), testMap );
 384
 385             check_before_cleanup( testMap );
 386             testMap.clear();
 387             EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
 388
 389             additional_check( testMap );
 390             additional_cleanup( testMap );
 391         }
 392
 393         template <class Map>
 394         void run_test()
 395         {
 396             static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
 397             Map testMap( *this );
 398             do_test( testMap );
 399         }
 400     };
 401
 402 } // namespace map