test/stress/set/insdel_find/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 "set_type.h"
  32
  33 namespace set {
  34
  35     class Set_InsDelFind: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nSetSize;           // initial set size
  39         static size_t s_nThreadCount;       // thread count
  40         static size_t s_nMaxLoadFactor;     // maximum load factor
  41         static unsigned int s_nInsertPercentage;
  42         static unsigned int s_nDeletePercentage;
  43         static unsigned int s_nDuration;   // test duration, seconds
  44
  45         static size_t  s_nCuckooInitialSize;        // initial size for CuckooSet
  46         static size_t  s_nCuckooProbesetSize;       // CuckooSet probeset size (only for list-based probeset)
  47         static size_t  s_nCuckooProbesetThreshold;  // CUckooSet probeset threshold (0 - use default)
  48
  49         static size_t s_nFeldmanSet_HeadBits;
  50         static size_t s_nFeldmanSet_ArrayBits;
  51
  52         static size_t s_nLoadFactor;
  53
  54         static void SetUpTestCase();
  55         //static void TearDownTestCase();
  56
  57     public:
  58         enum actions
  59         {
  60             do_find,
  61             do_insert,
  62             do_delete
  63         };
  64         static const unsigned int c_nShuffleSize = 100;
  65         actions m_arrShuffle[c_nShuffleSize];
  66
  67     protected:
  68         typedef size_t  key_type;
  69         typedef size_t  value_type;
  70
  71         template <class Set>
  72         class Worker: public cds_test::thread
  73         {
  74             typedef cds_test::thread base_class;
  75             Set&     m_Set;
  76
  77         public:
  78             size_t  m_nInsertSuccess = 0;
  79             size_t  m_nInsertFailed = 0;
  80             size_t  m_nDeleteSuccess = 0;
  81             size_t  m_nDeleteFailed = 0;
  82             size_t  m_nFindSuccess = 0;
  83             size_t  m_nFindFailed = 0;
  84
  85         public:
  86             Worker( cds_test::thread_pool& pool, Set& set )
  87                 : base_class( pool )
  88                 , m_Set( set )
  89             {}
  90
  91             Worker( Worker& src )
  92                 : base_class( src )
  93                 , m_Set( src.m_Set )
  94             {}
  95
  96             virtual thread * clone()
  97             {
  98                 return new Worker( *this );
  99             }
 100
 101             virtual void test()
 102             {
 103                 Set& rSet = m_Set;
 104                 Set_InsDelFind& fixture = pool().template fixture<Set_InsDelFind>();
 105
 106                 actions * pAct = fixture.m_arrShuffle;
 107                 unsigned int i = 0;
 108                 size_t const nNormalize = size_t(-1) / ( fixture.s_nSetSize * 2);
 109
 110                 size_t nRand = 0;
 111                 while ( !time_elapsed() ) {
 112                     nRand = cds::bitop::RandXorShift(nRand);
 113                     size_t n = nRand / nNormalize;
 114                     switch ( pAct[i] ) {
 115                     case do_find:
 116                         if ( rSet.contains( n ))
 117                             ++m_nFindSuccess;
 118                         else
 119                             ++m_nFindFailed;
 120                         break;
 121                     case do_insert:
 122                         if ( rSet.insert( n ))
 123                             ++m_nInsertSuccess;
 124                         else
 125                             ++m_nInsertFailed;
 126                         break;
 127                     case do_delete:
 128                         if ( rSet.erase( n ))
 129                             ++m_nDeleteSuccess;
 130                         else
 131                             ++m_nDeleteFailed;
 132                         break;
 133                     }
 134
 135                     if ( ++i >= c_nShuffleSize )
 136                         i = 0;
 137                 }
 138             }
 139         };
 140
 141     protected:
 142         template <class Set>
 143         void do_test( Set& testSet )
 144         {
 145             typedef Worker<Set> work_thread;
 146
 147             // fill map - only odd number
 148             {
 149                 size_t * pInitArr = new size_t[ s_nSetSize ];
 150                 size_t * pEnd = pInitArr + s_nSetSize;
 151                 for ( size_t i = 0; i < s_nSetSize; ++i )
 152                     pInitArr[i] = i * 2 + 1;
 153                 shuffle( pInitArr, pEnd );
 154                 for ( size_t * p = pInitArr; p < pEnd; ++p )
 155                     testSet.insert( typename Set::value_type( *p, *p ) );
 156                 delete [] pInitArr;
 157             }
 158
 159             cds_test::thread_pool& pool = get_pool();
 160             pool.add( new work_thread( pool, testSet ), s_nThreadCount );
 161
 162             propout() << std::make_pair( "thread_count", s_nThreadCount )
 163                 << std::make_pair( "set_size", s_nSetSize )
 164                 << std::make_pair( "insert_percentage", s_nInsertPercentage )
 165                 << std::make_pair( "delete_percentage", s_nDeletePercentage )
 166                 << std::make_pair( "total_duration", s_nDuration );
 167
 168             std::chrono::milliseconds duration = pool.run( std::chrono::seconds( s_nDuration ));
 169
 170             propout() << std::make_pair( "duration", duration );
 171
 172             size_t nInsertSuccess = 0;
 173             size_t nInsertFailed = 0;
 174             size_t nDeleteSuccess = 0;
 175             size_t nDeleteFailed = 0;
 176             size_t nFindSuccess = 0;
 177             size_t nFindFailed = 0;
 178             for ( size_t i = 0; i < pool.size(); ++i ) {
 179                 work_thread& thr = static_cast<work_thread&>( pool.get( i ));
 180                 nInsertSuccess += thr.m_nInsertSuccess;
 181                 nInsertFailed  += thr.m_nInsertFailed;
 182                 nDeleteSuccess += thr.m_nDeleteSuccess;
 183                 nDeleteFailed  += thr.m_nDeleteFailed;
 184                 nFindSuccess   += thr.m_nFindSuccess;
 185                 nFindFailed    += thr.m_nFindFailed;
 186             }
 187
 188             propout()
 189                 << std::make_pair( "insert_success", nInsertSuccess )
 190                 << std::make_pair( "insert_failed", nInsertFailed )
 191                 << std::make_pair( "delete_success", nDeleteSuccess )
 192                 << std::make_pair( "delete_failed", nDeleteFailed )
 193                 << std::make_pair( "find_success", nFindSuccess )
 194                 << std::make_pair( "find_failed", nFindFailed );
 195
 196             {
 197                 ASSERT_TRUE( std::chrono::duration_cast<std::chrono::seconds>(duration).count() > 0 );
 198                 size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 199                 propout() << std::make_pair( "avg_speed", nTotalOps / std::chrono::duration_cast<std::chrono::seconds>(duration).count() );
 200             }
 201
 202
 203             testSet.clear();
 204             EXPECT_TRUE( testSet.empty()) << "set size=" << testSet.size();
 205
 206             additional_check( testSet );
 207             print_stat( propout(), testSet );
 208             additional_cleanup( testSet );
 209         }
 210
 211         template <class Set>
 212         void run_test()
 213         {
 214             Set s( *this );
 215             do_test( s );
 216         }
 217     };
 218
 219     class Set_InsDelFind_LF: public Set_InsDelFind
 220         , public ::testing::WithParamInterface<size_t>
 221     {
 222     public:
 223         template <class Set>
 224         void run_test()
 225         {
 226             s_nLoadFactor = GetParam();
 227             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 228             Set_InsDelFind::run_test<Set>();
 229         }
 230
 231         static std::vector<size_t> get_load_factors();
 232     };
 233
 234 } // namespace set