tests/unit/stack/stack_push.cpp

   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 "cppunit/thread.h"
  32 #include "stack/stack_type.h"
  33
  34 // Multi-threaded stack test for push operation
  35 namespace stack {
  36
  37 #define TEST_CASE( Q ) void Q()          { test_unbounded< Types<SimpleValue>::Q >(); }
  38 #define TEST_ELIMINATION( Q ) void Q()   { test_elimination< Types<SimpleValue>::Q >(); }
  39 #define TEST_BOUNDED( Q ) void Q()       { test_bounded< Types<SimpleValue>::Q >(); }
  40
  41     namespace {
  42         static size_t s_nThreadCount = 8;
  43         static size_t s_nStackSize = 10000000;
  44         static size_t s_nEliminationSize = 4;
  45
  46         struct SimpleValue {
  47             size_t      nNo;
  48             size_t      nThread;
  49
  50             SimpleValue(): nNo(0), nThread(0) {}
  51             SimpleValue( size_t n ): nNo(n), nThread(0) {}
  52             size_t getNo() const { return  nNo; }
  53         };
  54     }
  55
  56     class Stack_Push: public CppUnitMini::TestCase
  57     {
  58         template <class Stack>
  59         class Thread: public CppUnitMini::TestThread
  60         {
  61             virtual TestThread *    clone()
  62             {
  63                 return new Thread( *this );
  64             }
  65         public:
  66             Stack&              m_Stack;
  67             double              m_fTime;
  68             size_t              m_nStartItem;
  69             size_t              m_nEndItem;
  70             size_t              m_nPushError;
  71
  72         public:
  73             Thread( CppUnitMini::ThreadPool& pool, Stack& s )
  74                 : CppUnitMini::TestThread( pool )
  75                 , m_Stack( s )
  76             {}
  77             Thread( Thread& src )
  78                 : CppUnitMini::TestThread( src )
  79                 , m_Stack( src.m_Stack )
  80             {}
  81
  82             Stack_Push&  getTest()
  83             {
  84                 return reinterpret_cast<Stack_Push&>( m_Pool.m_Test );
  85             }
  86
  87             virtual void init()
  88             {
  89                 cds::threading::Manager::attachThread();
  90             }
  91             virtual void fini()
  92             {
  93                 cds::threading::Manager::detachThread();
  94             }
  95
  96             virtual void test()
  97             {
  98                 m_fTime = m_Timer.duration();
  99
 100                 m_nPushError = 0;
 101                 SimpleValue v;
 102                 v.nThread = m_nThreadNo;
 103                 for ( v.nNo = m_nStartItem; v.nNo < m_nEndItem; ++v.nNo ) {
 104                     if ( !m_Stack.push( v ))
 105                         ++m_nPushError;
 106                 }
 107
 108                 m_fTime = m_Timer.duration() - m_fTime;
 109             }
 110         };
 111
 112     protected:
 113         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 114             s_nThreadCount = cfg.getULong("ThreadCount", 8 );
 115             s_nStackSize = cfg.getULong("StackSize", 10000000 );
 116             s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
 117         }
 118
 119         template <class Stack>
 120         void analyze( CppUnitMini::ThreadPool& pool, Stack& testStack  )
 121         {
 122             size_t nThreadItems = s_nStackSize / s_nThreadCount;
 123             std::vector<size_t> aThread;
 124             aThread.resize(s_nThreadCount);
 125
 126             double fTime = 0;
 127             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 128                 Thread<Stack> * pThread = reinterpret_cast<Thread<Stack> *>(*it);
 129                 fTime += pThread->m_fTime;
 130                 if ( pThread->m_nPushError != 0 )
 131                     CPPUNIT_MSG("     ERROR: thread push error count=" << pThread->m_nPushError );
 132                 aThread[ pThread->m_nThreadNo] = pThread->m_nEndItem - 1;
 133             }
 134             CPPUNIT_MSG( "     Duration=" << (fTime / s_nThreadCount) );
 135             CPPUNIT_ASSERT( !testStack.empty() )
 136
 137             size_t * arr = new size_t[ s_nStackSize ];
 138             memset(arr, 0, sizeof(arr[0]) * s_nStackSize );
 139
 140             cds::OS::Timer      timer;
 141             CPPUNIT_MSG( "   Pop (single-threaded)..." );
 142             size_t nPopped = 0;
 143             SimpleValue val;
 144             while ( testStack.pop( val )) {
 145                 nPopped++;
 146                 ++arr[ val.getNo() ];
 147                 CPPUNIT_ASSERT( val.nThread < s_nThreadCount);
 148                 CPPUNIT_ASSERT( aThread[val.nThread] == val.nNo );
 149                 aThread[val.nThread]--;
 150             }
 151             CPPUNIT_MSG( "     Duration=" << timer.duration() );
 152
 153             size_t nTotalItems = nThreadItems * s_nThreadCount;
 154             size_t nError = 0;
 155             for ( size_t i = 0; i < nTotalItems; ++i ) {
 156                 if ( arr[i] != 1 ) {
 157                     CPPUNIT_MSG( "   ERROR: Item " << i << " has not been pushed" );
 158                     CPPUNIT_ASSERT( ++nError > 10 );
 159                 }
 160             }
 161
 162             delete [] arr;
 163         }
 164
 165         // Unbounded stack test
 166         template <class Stack>
 167         void test_unbounded()
 168         {
 169             Stack testStack;
 170             test( testStack );
 171         }
 172
 173         // Unbounded elimination stack test
 174         template <class Stack>
 175         void test_elimination()
 176         {
 177             Stack testStack( s_nEliminationSize );
 178             test( testStack );
 179             check_elimination_stat( testStack.statistics() );
 180         }
 181         void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
 182         {}
 183         void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
 184         {
 185             CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
 186         }
 187
 188         // Bounded stack test
 189         template <class Stack>
 190         void test_bounded()
 191         {
 192             Stack testStack( s_nStackSize );
 193             test( testStack );
 194         }
 195
 196         template <class Stack>
 197         void test( Stack& testStack )
 198         {
 199             CppUnitMini::ThreadPool pool( *this );
 200             pool.add( new Thread<Stack>( pool, testStack ), s_nThreadCount );
 201
 202             size_t nStart = 0;
 203             size_t nThreadItemCount = s_nStackSize / s_nThreadCount;
 204             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 205                 Thread<Stack> * pThread = reinterpret_cast<Thread<Stack> *>(*it);
 206                 pThread->m_nStartItem = nStart;
 207                 nStart += nThreadItemCount;
 208                 pThread->m_nEndItem = nStart;
 209             }
 210
 211             CPPUNIT_MSG( "   Push test, thread count=" << s_nThreadCount
 212                 << " items=" << (nThreadItemCount * s_nThreadCount)
 213                 << "...");
 214             pool.run();
 215
 216             analyze( pool, testStack );
 217             CPPUNIT_MSG( testStack.statistics() );
 218         }
 219
 220     protected:
 221 #   include "stack/stack_defs.h"
 222         CDSUNIT_DECLARE_TreiberStack
 223         CDSUNIT_DECLARE_EliminationStack
 224         CDSUNIT_DECLARE_FCStack
 225         CDSUNIT_DECLARE_FCDeque
 226         CDSUNIT_DECLARE_StdStack
 227
 228         CPPUNIT_TEST_SUITE(Stack_Push)
 229             CDSUNIT_TEST_TreiberStack
 230             CDSUNIT_TEST_EliminationStack
 231             CDSUNIT_TEST_FCStack
 232             CDSUNIT_TEST_FCDeque
 233             CDSUNIT_TEST_StdStack
 234         CPPUNIT_TEST_SUITE_END();
 235     };
 236 } // namespace stack
 237
 238 CPPUNIT_TEST_SUITE_REGISTRATION(stack::Stack_Push);