tests/unit/map2/map_insdelfind.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-2016
   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 "map2/map_type.h"
  32 #include "cppunit/thread.h"
  33 #include <vector>
  34
  35 namespace map2 {
  36
  37 #define TEST_CASE(TAG, X)  void X();
  38
  39     class Map_InsDelFind: public CppUnitMini::TestCase
  40     {
  41     public:
  42         size_t  c_nMapSize = 500000;          // initial map size
  43         size_t  c_nThreadCount = 8;      // thread count
  44         size_t  c_nMaxLoadFactor = 8;    // maximum load factor
  45         unsigned int c_nInsertPercentage = 5;
  46         unsigned int c_nDeletePercentage = 5;
  47         unsigned int c_nDuration = 30;    // test duration, seconds
  48         bool    c_bPrintGCState = true;
  49
  50         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  51         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  52         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  53
  54         size_t c_nFeldmanMap_HeadBits = 10;
  55         size_t c_nFeldmanMap_ArrayBits = 4;
  56
  57         size_t  c_nLoadFactor = 2;  // current load factor
  58
  59     public:
  60         enum actions
  61         {
  62             do_find,
  63             do_insert,
  64             do_delete
  65         };
  66         static const unsigned int c_nShuffleSize = 100;
  67         actions m_arrShuffle[c_nShuffleSize];
  68
  69     protected:
  70         typedef size_t  key_type;
  71         typedef size_t  value_type;
  72
  73         template <class Map>
  74         class WorkThread: public CppUnitMini::TestThread
  75         {
  76             Map&     m_Map;
  77
  78             virtual WorkThread *    clone()
  79             {
  80                 return new WorkThread( *this );
  81             }
  82         public:
  83             size_t  m_nInsertSuccess;
  84             size_t  m_nInsertFailed;
  85             size_t  m_nDeleteSuccess;
  86             size_t  m_nDeleteFailed;
  87             size_t  m_nFindSuccess;
  88             size_t  m_nFindFailed;
  89
  90         public:
  91             WorkThread( CppUnitMini::ThreadPool& pool, Map& rMap )
  92                 : CppUnitMini::TestThread( pool )
  93                 , m_Map( rMap )
  94             {}
  95             WorkThread( WorkThread& src )
  96                 : CppUnitMini::TestThread( src )
  97                 , m_Map( src.m_Map )
  98             {}
  99
 100             Map_InsDelFind&  getTest()
 101             {
 102                 return reinterpret_cast<Map_InsDelFind&>( m_Pool.m_Test );
 103             }
 104
 105             virtual void init() { cds::threading::Manager::attachThread()   ; }
 106             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 107
 108             typedef std::pair< key_type const, value_type > map_value_type;
 109
 110             struct update_functor {
 111                 template <typename Q>
 112                 void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ )
 113                 {}
 114
 115                 // FeldmanHashMap
 116                 void operator()( map_value_type& /*cur*/, map_value_type * /*old*/)
 117                 {}
 118
 119                 // MichaelMap
 120                 void operator()( bool /*bNew*/, map_value_type& /*cur*/ )
 121                 {}
 122
 123                 // BronsonAVLTreeMap
 124                 void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ )
 125                 {}
 126             };
 127
 128             virtual void test()
 129             {
 130                 Map& rMap = m_Map;
 131
 132                 m_nInsertSuccess =
 133                     m_nInsertFailed =
 134                     m_nDeleteSuccess =
 135                     m_nDeleteFailed =
 136                     m_nFindSuccess =
 137                     m_nFindFailed = 0;
 138
 139                 actions * pAct = getTest().m_arrShuffle;
 140                 unsigned int i = 0;
 141                 size_t const nNormalize = size_t(-1) / (getTest().c_nMapSize * 2);
 142
 143                 size_t nRand = 0;
 144                 while ( !time_elapsed() ) {
 145                     nRand = cds::bitop::RandXorShift(nRand);
 146                     size_t n = nRand / nNormalize;
 147                     switch ( pAct[i] ) {
 148                     case do_find:
 149                         if ( rMap.contains( n ))
 150                             ++m_nFindSuccess;
 151                         else
 152                             ++m_nFindFailed;
 153                         break;
 154                     case do_insert:
 155                         if ( n % 2 ) {
 156                             if ( rMap.insert( n, n ))
 157                                 ++m_nInsertSuccess;
 158                             else
 159                                 ++m_nInsertFailed;
 160                         }
 161                         else {
 162                             if ( rMap.update(n, update_functor(), true ).first )
 163                                 ++m_nInsertSuccess;
 164                             else
 165                                 ++m_nInsertFailed;
 166                         }
 167                         break;
 168                     case do_delete:
 169                         if ( rMap.erase( n ))
 170                             ++m_nDeleteSuccess;
 171                         else
 172                             ++m_nDeleteFailed;
 173                         break;
 174                     }
 175
 176                     if ( ++i >= c_nShuffleSize )
 177                         i = 0;
 178                 }
 179             }
 180         };
 181
 182     protected:
 183         template <class Map>
 184         void do_test( Map& testMap )
 185         {
 186             typedef WorkThread<Map> work_thread;
 187             cds::OS::Timer    timer;
 188
 189             // fill map - only odd number
 190             {
 191                 std::vector<size_t> arr;
 192                 arr.reserve( c_nMapSize );
 193                 for ( size_t i = 0; i < c_nMapSize; ++i )
 194                     arr.push_back( i * 2 + 1);
 195                 shuffle( arr.begin(), arr.end() );
 196                 for ( size_t i = 0; i < c_nMapSize; ++i )
 197                     testMap.insert( arr[i], arr[i] );
 198             }
 199             CPPUNIT_MSG( "   Insert " << c_nMapSize << " items time (single-threaded)=" << timer.duration() );
 200
 201             timer.reset();
 202             CppUnitMini::ThreadPool pool( *this );
 203             pool.add( new work_thread( pool, testMap ), c_nThreadCount );
 204             pool.run( c_nDuration );
 205             //CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 206
 207             size_t nInsertSuccess = 0;
 208             size_t nInsertFailed = 0;
 209             size_t nDeleteSuccess = 0;
 210             size_t nDeleteFailed = 0;
 211             size_t nFindSuccess = 0;
 212             size_t nFindFailed = 0;
 213             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 214                 work_thread * pThread = static_cast<work_thread *>( *it );
 215                 assert( pThread != nullptr );
 216                 nInsertSuccess += pThread->m_nInsertSuccess;
 217                 nInsertFailed += pThread->m_nInsertFailed;
 218                 nDeleteSuccess += pThread->m_nDeleteSuccess;
 219                 nDeleteFailed += pThread->m_nDeleteFailed;
 220                 nFindSuccess += pThread->m_nFindSuccess;
 221                 nFindFailed += pThread->m_nFindFailed;
 222             }
 223
 224             size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 225
 226             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 227                       << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 228                       << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 229                       << "        Find=" << nFindSuccess   << '/' << nFindFailed   << "\n\t"
 230                       << "       Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
 231                       << "             " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
 232                       << "   Total ops=" << nTotalOps << "\n\t"
 233                       << "       speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
 234                       << "      Map size=" << testMap.size()
 235                 );
 236
 237
 238             check_before_cleanup( testMap );
 239
 240             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 241             timer.reset();
 242             testMap.clear();
 243             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 244             CPPUNIT_CHECK_EX( testMap.empty(), "size=" << ((long long) testMap.size()) );
 245
 246             additional_check( testMap );
 247             print_stat( testMap );
 248             additional_cleanup( testMap );
 249         }
 250
 251         template <class Map>
 252         void run_test()
 253         {
 254             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 255                 << " initial map size=" << c_nMapSize
 256                 << " insert=" << c_nInsertPercentage << '%'
 257                 << " delete=" << c_nDeletePercentage << '%'
 258                 << " duration=" << c_nDuration << "s"
 259                 );
 260
 261             if ( Map::c_bLoadFactorDepended ) {
 262                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 263                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 264                     Map  testMap( *this );
 265                     do_test( testMap );
 266                     if ( c_bPrintGCState )
 267                         print_gc_state();
 268                 }
 269             }
 270             else {
 271                 Map testMap( *this );
 272                 do_test( testMap );
 273                 if ( c_bPrintGCState )
 274                     print_gc_state();
 275             }
 276         }
 277
 278         void setUpParams( const CppUnitMini::TestCfg& cfg );
 279
 280 #   include "map2/map_defs.h"
 281         CDSUNIT_DECLARE_MichaelMap
 282         CDSUNIT_DECLARE_SplitList
 283         CDSUNIT_DECLARE_SkipListMap
 284         CDSUNIT_DECLARE_EllenBinTreeMap
 285         CDSUNIT_DECLARE_BronsonAVLTreeMap
 286         CDSUNIT_DECLARE_FeldmanHashMap_fixed
 287         CDSUNIT_DECLARE_FeldmanHashMap_city
 288         CDSUNIT_DECLARE_StripedMap
 289         CDSUNIT_DECLARE_RefinableMap
 290         CDSUNIT_DECLARE_CuckooMap
 291         CDSUNIT_DECLARE_StdMap
 292
 293         CPPUNIT_TEST_SUITE_(Map_InsDelFind, "map_insdelfind")
 294             CDSUNIT_TEST_MichaelMap
 295             CDSUNIT_TEST_SplitList
 296             CDSUNIT_TEST_SkipListMap
 297             CDSUNIT_TEST_EllenBinTreeMap
 298             CDSUNIT_TEST_BronsonAVLTreeMap
 299             CDSUNIT_TEST_FeldmanHashMap_fixed
 300             CDSUNIT_TEST_FeldmanHashMap_city
 301             CDSUNIT_TEST_CuckooMap
 302             CDSUNIT_TEST_StripedMap
 303             CDSUNIT_TEST_RefinableMap
 304             CDSUNIT_TEST_StdMap
 305         CPPUNIT_TEST_SUITE_END();
 306     };
 307 } // namespace map2