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