tests/unit/alloc/larson.cpp

   1 //$$CDS-header$$
   2
   3 // Larson allocator test
   4
   5 #include "alloc/michael_allocator.h"
   6 #include "alloc/random_gen.h"
   7
   8 #include <cds/os/timer.h>
   9 #include <cds/os/topology.h>
  10
  11 #include "cppunit/thread.h"
  12
  13 namespace memory {
  14
  15     static size_t s_nMaxThreadCount = 32;
  16     static unsigned int s_nMinBlockSize = 8;
  17     static unsigned int s_nMaxBlockSize = 1024;
  18     static size_t s_nBlocksPerThread = 1000;
  19     static size_t s_nPassCount = 100000;
  20
  21     static size_t s_nPassPerThread;
  22
  23
  24 #    define TEST_ALLOC(X, CLASS)    void X() { test< CLASS >(false)    ; }
  25 #    define TEST_ALLOC_STAT(X, CLASS)    void X() { test< CLASS >(true)    ; }
  26
  27     /*
  28         In this test, initially one thread allocates and frees random
  29         sized blocks (s_nMinBlockSize to s_nMaxBlockSize bytes) in random order, then an
  30         equal number of blocks (s_nBlocksPerThread) is handed over to each of the
  31         remaining threads. In the parallel phase, each thread randomly selects a block and
  32         frees it, then allocates a new random-sized block in its place.
  33         The benchmark measures the duration of s_nPassCount free/malloc pairs
  34         during the parallel phase. Larson captures the robustness of malloc\92s latency
  35         and scalability under irregular allocation patterns with respect to block-size
  36         and order of deallocation over a long period of time.
  37     */
  38     class Larson: public CppUnitMini::TestCase
  39     {
  40         typedef char ** thread_data;
  41
  42         thread_data *   m_aThreadData;
  43
  44
  45         template <class ALLOC>
  46         class Thread: public CppUnitMini::TestThread
  47         {
  48             ALLOC&      m_Alloc;
  49             typedef typename ALLOC::value_type value_type;
  50
  51             virtual Thread *    clone()
  52             {
  53                 return new Thread( *this );
  54             }
  55
  56             randomGen<size_t>   m_rndGen;
  57         public:
  58             thread_data     m_arr;
  59
  60         public:
  61             Thread( CppUnitMini::ThreadPool& pool, ALLOC& a )
  62                 : CppUnitMini::TestThread( pool )
  63                 , m_Alloc( a )
  64             {}
  65             Thread( Thread& src )
  66                 : CppUnitMini::TestThread( src )
  67                 , m_Alloc( src.m_Alloc )
  68             {}
  69
  70             Larson&  getTest()
  71             {
  72                 return reinterpret_cast<Larson&>( m_Pool.m_Test );
  73             }
  74
  75             virtual void init() { cds::threading::Manager::attachThread()   ; }
  76             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  77
  78             virtual void test()
  79             {
  80                 for ( size_t nPass = 0; nPass < s_nPassPerThread; ++nPass ) {
  81                     size_t nItem = m_rndGen( size_t(1), s_nBlocksPerThread ) - 1;
  82                     m_Alloc.deallocate( reinterpret_cast<value_type *>(m_arr[nItem]), 1 );
  83                     m_arr[nItem] = reinterpret_cast<char *>(m_Alloc.allocate( m_rndGen( s_nMinBlockSize, s_nMaxBlockSize ), nullptr ));
  84                     CPPUNIT_ASSERT( (reinterpret_cast<cds::uptr_atomic_t>(m_arr[nItem]) & (ALLOC::alignment - 1)) == 0 );
  85                 }
  86             }
  87         };
  88
  89         template <class ALLOC>
  90         void test( size_t nThreadCount )
  91         {
  92             ALLOC alloc;
  93
  94             CPPUNIT_MSG( "Thread count=" << nThreadCount );
  95             CPPUNIT_MSG("Initialize data..." );
  96
  97             randomGen<unsigned int> rndGen;
  98
  99             s_nPassPerThread = s_nPassCount / nThreadCount;
 100
 101             size_t nThread;
 102             m_aThreadData = new thread_data[ nThreadCount ];
 103             for ( nThread = 0; nThread < nThreadCount; ++nThread ) {
 104                 thread_data thData
 105                     = m_aThreadData[nThread]
 106                     = new char *[ s_nBlocksPerThread ];
 107                     for ( size_t i = 0; i < s_nBlocksPerThread; ++i ) {
 108                         thData[i] = reinterpret_cast<char *>(alloc.allocate( rndGen( s_nMinBlockSize, s_nMaxBlockSize ), nullptr ));
 109                         CPPUNIT_ASSERT( (reinterpret_cast<cds::uptr_atomic_t>(thData[i]) & (ALLOC::alignment - 1)) == 0 );
 110                     }
 111             }
 112             CPPUNIT_MSG("Initializatin done" );
 113
 114             CppUnitMini::ThreadPool pool( *this );
 115             pool.add( new Thread<ALLOC>( pool, alloc ), nThreadCount );
 116             nThread = 0;
 117             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it )
 118                 static_cast<Thread<ALLOC> *>(*it)->m_arr = m_aThreadData[nThread++];
 119
 120             cds::OS::Timer    timer;
 121             pool.run();
 122             CPPUNIT_MSG( "  Duration=" << pool.avgDuration() );
 123
 124             for ( nThread = 0; nThread < nThreadCount; ++nThread ) {
 125                 thread_data thData = m_aThreadData[nThread];
 126                 for ( size_t i = 0; i < s_nBlocksPerThread; ++i ) {
 127                     alloc.deallocate( reinterpret_cast<typename ALLOC::value_type *>(thData[i]), 1 );
 128                 }
 129                 delete [] thData;
 130             }
 131             delete [] m_aThreadData;
 132         }
 133
 134         template <class ALLOC>
 135         void test( bool bStat )
 136         {
 137             CPPUNIT_MSG( "Block size=" << s_nMinBlockSize << "-" << s_nMaxBlockSize
 138                 << ", block count per thread=" << s_nBlocksPerThread << ", pass count=" << s_nPassCount );
 139
 140             for ( size_t nThreadCount = 2; nThreadCount <= s_nMaxThreadCount; nThreadCount *= 2 ) {
 141                 summary_stat stBegin;
 142                 if ( bStat )
 143                     ALLOC::stat(stBegin);
 144
 145                 test<ALLOC>( nThreadCount );
 146
 147                 summary_stat    stEnd;
 148                 if ( bStat ) {
 149                     ALLOC::stat( stEnd );
 150
 151                     std::cout << "\nStatistics:\n"
 152                         << stEnd
 153 ;
 154                     stEnd -= stBegin;
 155                     std::cout << "\nDelta statistics:\n"
 156                         << stEnd
 157 ;
 158                 }
 159             }
 160         }
 161
 162         void setUpParams( const CppUnitMini::TestCfg& cfg )
 163         {
 164             s_nPassCount = cfg.getULong( "PassCount", 100000 );
 165             s_nMinBlockSize = cfg.getUInt( "MinBlockSize", 8 );
 166             s_nMaxBlockSize = cfg.getUInt( "MaxBlockSize", 1024 );
 167             s_nBlocksPerThread = cfg.getUInt( "BlocksPerThread", 10000 );
 168             s_nMaxThreadCount = cfg.getUInt( "MaxThreadCount", 32 );
 169             if ( s_nMaxThreadCount == 0 )
 170                 s_nMaxThreadCount = cds::OS::topology::processor_count() * 2;
 171             if ( s_nMaxThreadCount < 2 )
 172                 s_nMaxThreadCount = 2;
 173             if ( s_nPassCount < s_nBlocksPerThread )
 174                 s_nBlocksPerThread = s_nPassCount;
 175         }
 176
 177         typedef MichaelAlignHeap_Stat<int, 64>      t_MichaelAlignHeap_Stat;
 178         typedef MichaelAlignHeap_NoStat<int,64>     t_MichaelAlignHeap_NoStat;
 179         typedef system_aligned_allocator<int, 64>   t_system_aligned_allocator;
 180
 181         TEST_ALLOC_STAT( michael_heap_stat,      MichaelHeap_Stat<int> )
 182         TEST_ALLOC( michael_heap_nostat,    MichaelHeap_NoStat<int> )
 183         TEST_ALLOC( std_alloc,              std_allocator<int> )
 184
 185         TEST_ALLOC_STAT( michael_alignheap_stat,     t_MichaelAlignHeap_Stat )
 186         TEST_ALLOC( michael_alignheap_nostat,   t_MichaelAlignHeap_NoStat )
 187         TEST_ALLOC( system_aligned_alloc,       t_system_aligned_allocator )
 188
 189         CPPUNIT_TEST_SUITE( Larson )
 190             CPPUNIT_TEST( michael_heap_stat )
 191             CPPUNIT_TEST( michael_heap_nostat )
 192             CPPUNIT_TEST( std_alloc )
 193
 194             CPPUNIT_TEST( system_aligned_alloc )
 195             CPPUNIT_TEST( michael_alignheap_stat )
 196             CPPUNIT_TEST( michael_alignheap_nostat )
 197
 198         CPPUNIT_TEST_SUITE_END();
 199     };
 200
 201 }   // namespace memory
 202 CPPUNIT_TEST_SUITE_REGISTRATION( memory::Larson );