tests/unit/set2/set_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 "set2/set_type.h"
  32 #include "cppunit/thread.h"
  33
  34 namespace set2 {
  35
  36 #define TEST_CASE(TAG, X)  void X();
  37
  38     class Set_InsDelFind: public CppUnitMini::TestCase
  39     {
  40     public:
  41         size_t c_nSetSize = 500000;      // initial set size
  42         size_t c_nThreadCount = 8;       // thread count
  43         size_t c_nMaxLoadFactor = 8;     // maximum load factor
  44         unsigned int c_nInsertPercentage = 5;
  45         unsigned int c_nDeletePercentage = 5;
  46         unsigned int c_nDuration = 30;   // test duration, seconds
  47         bool c_bPrintGCState = true;
  48
  49         size_t  c_nCuckooInitialSize = 1024;// initial size for CuckooSet
  50         size_t  c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
  51         size_t  c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
  52
  53         size_t c_nFeldmanSet_HeadBits = 10;
  54         size_t c_nFeldmanSet_ArrayBits = 4;
  55
  56         size_t c_nLoadFactor = 2;
  57
  58     public:
  59         enum actions
  60         {
  61             do_find,
  62             do_insert,
  63             do_delete
  64         };
  65         static const unsigned int c_nShuffleSize = 100;
  66         actions m_arrShuffle[c_nShuffleSize];
  67
  68     protected:
  69         typedef size_t  key_type;
  70         typedef size_t  value_type;
  71
  72         template <class Set>
  73         class WorkThread: public CppUnitMini::TestThread
  74         {
  75             Set&     m_Map;
  76
  77             virtual WorkThread *    clone()
  78             {
  79                 return new WorkThread( *this );
  80             }
  81         public:
  82             size_t  m_nInsertSuccess;
  83             size_t  m_nInsertFailed;
  84             size_t  m_nDeleteSuccess;
  85             size_t  m_nDeleteFailed;
  86             size_t  m_nFindSuccess;
  87             size_t  m_nFindFailed;
  88
  89         public:
  90             WorkThread( CppUnitMini::ThreadPool& pool, Set& rMap )
  91                 : CppUnitMini::TestThread( pool )
  92                 , m_Map( rMap )
  93             {}
  94             WorkThread( WorkThread& src )
  95                 : CppUnitMini::TestThread( src )
  96                 , m_Map( src.m_Map )
  97             {}
  98
  99             Set_InsDelFind&  getTest()
 100             {
 101                 return reinterpret_cast<Set_InsDelFind&>( m_Pool.m_Test );
 102             }
 103
 104             virtual void init() { cds::threading::Manager::attachThread()   ; }
 105             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 106
 107             virtual void test()
 108             {
 109                 Set& rMap = m_Map;
 110
 111                 m_nInsertSuccess =
 112                     m_nInsertFailed =
 113                     m_nDeleteSuccess =
 114                     m_nDeleteFailed =
 115                     m_nFindSuccess =
 116                     m_nFindFailed = 0;
 117
 118                 actions * pAct = getTest().m_arrShuffle;
 119                 unsigned int i = 0;
 120                 size_t const nNormalize = size_t(-1) / ( getTest().c_nSetSize * 2);
 121
 122                 size_t nRand = 0;
 123                 while ( !time_elapsed() ) {
 124                     nRand = cds::bitop::RandXorShift(nRand);
 125                     size_t n = nRand / nNormalize;
 126                     switch ( pAct[i] ) {
 127                     case do_find:
 128                         if ( rMap.contains( n ))
 129                             ++m_nFindSuccess;
 130                         else
 131                             ++m_nFindFailed;
 132                         break;
 133                     case do_insert:
 134                         if ( rMap.insert( n ))
 135                             ++m_nInsertSuccess;
 136                         else
 137                             ++m_nInsertFailed;
 138                         break;
 139                     case do_delete:
 140                         if ( rMap.erase( n ))
 141                             ++m_nDeleteSuccess;
 142                         else
 143                             ++m_nDeleteFailed;
 144                         break;
 145                     }
 146
 147                     if ( ++i >= c_nShuffleSize )
 148                         i = 0;
 149                 }
 150             }
 151         };
 152
 153     protected:
 154         template <class Set>
 155         void do_test( Set& testSet )
 156         {
 157             typedef WorkThread<Set> work_thread;
 158
 159             // fill map - only odd number
 160             {
 161                 size_t * pInitArr = new size_t[ c_nSetSize ];
 162                 size_t * pEnd = pInitArr + c_nSetSize;
 163                 for ( size_t i = 0; i < c_nSetSize; ++i )
 164                     pInitArr[i] = i * 2 + 1;
 165                 shuffle( pInitArr, pEnd );
 166                 for ( size_t * p = pInitArr; p < pEnd; ++p )
 167                     testSet.insert( typename Set::value_type( *p, *p ) );
 168                 delete [] pInitArr;
 169             }
 170
 171             cds::OS::Timer    timer;
 172
 173             CppUnitMini::ThreadPool pool( *this );
 174             pool.add( new work_thread( pool, testSet ), c_nThreadCount );
 175             pool.run( c_nDuration );
 176             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 177
 178             size_t nInsertSuccess = 0;
 179             size_t nInsertFailed = 0;
 180             size_t nDeleteSuccess = 0;
 181             size_t nDeleteFailed = 0;
 182             size_t nFindSuccess = 0;
 183             size_t nFindFailed = 0;
 184             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 185                 work_thread * pThread = static_cast<work_thread *>( *it );
 186                 assert( pThread != nullptr );
 187                 nInsertSuccess += pThread->m_nInsertSuccess;
 188                 nInsertFailed += pThread->m_nInsertFailed;
 189                 nDeleteSuccess += pThread->m_nDeleteSuccess;
 190                 nDeleteFailed += pThread->m_nDeleteFailed;
 191                 nFindSuccess += pThread->m_nFindSuccess;
 192                 nFindFailed += pThread->m_nFindFailed;
 193             }
 194
 195             size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 196
 197             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 198                       << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 199                       << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 200                       << "        Find=" << nFindSuccess   << '/' << nFindFailed   << "\n\t"
 201                       << "       Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
 202                       << "             " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
 203                       << "   Total ops=" << nTotalOps << "\n\t"
 204                       << "       speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
 205                       << "      Set size=" << testSet.size()
 206                 );
 207
 208
 209             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 210             timer.reset();
 211             testSet.clear();
 212             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 213             CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) );
 214
 215             additional_check( testSet );
 216             print_stat( testSet );
 217             additional_cleanup( testSet );
 218         }
 219
 220         template <class Set>
 221         void run_test()
 222         {
 223             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 224                 << " initial map size=" << c_nSetSize
 225                 << " insert=" << c_nInsertPercentage << '%'
 226                 << " delete=" << c_nDeletePercentage << '%'
 227                 << " duration=" << c_nDuration << "s"
 228                 );
 229
 230             if ( Set::c_bLoadFactorDepended ) {
 231                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 232                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 233                     Set s( *this );
 234                     do_test( s );
 235                     if ( c_bPrintGCState )
 236                         print_gc_state();
 237                 }
 238             }
 239             else {
 240                 Set s( *this );
 241                 do_test( s );
 242                 if ( c_bPrintGCState )
 243                     print_gc_state();
 244             }
 245         }
 246
 247         void setUpParams( const CppUnitMini::TestCfg& cfg );
 248
 249 #   include "set2/set_defs.h"
 250         CDSUNIT_DECLARE_MichaelSet
 251         CDSUNIT_DECLARE_SplitList
 252         CDSUNIT_DECLARE_StripedSet
 253         CDSUNIT_DECLARE_RefinableSet
 254         CDSUNIT_DECLARE_CuckooSet
 255         CDSUNIT_DECLARE_SkipListSet
 256         CDSUNIT_DECLARE_EllenBinTreeSet
 257         CDSUNIT_DECLARE_FeldmanHashSet
 258         CDSUNIT_DECLARE_StdSet
 259
 260         CPPUNIT_TEST_SUITE_(Set_InsDelFind, "Map_InsDelFind")
 261             CDSUNIT_TEST_MichaelSet
 262             CDSUNIT_TEST_SplitList
 263             CDSUNIT_TEST_SkipListSet
 264             CDSUNIT_TEST_FeldmanHashSet
 265             CDSUNIT_TEST_EllenBinTreeSet
 266             CDSUNIT_TEST_StripedSet
 267             CDSUNIT_TEST_RefinableSet
 268             CDSUNIT_TEST_CuckooSet
 269             CDSUNIT_TEST_StdSet
 270         CPPUNIT_TEST_SUITE_END();
 271
 272     };
 273 } // namespace set2