3 // Larson allocator test
5 #include "alloc/michael_allocator.h"
6 #include "alloc/random_gen.h"
8 #include <cds/os/timer.h>
9 #include <cds/os/topology.h>
11 #include "cppunit/thread.h"
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;
21 static size_t s_nPassPerThread;
24 # define TEST_ALLOC(X, CLASS) void X() { test< CLASS >(false) ; }
25 # define TEST_ALLOC_STAT(X, CLASS) void X() { test< CLASS >(true) ; }
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.
38 class Larson: public CppUnitMini::TestCase
40 typedef char ** thread_data;
42 thread_data * m_aThreadData;
45 template <class ALLOC>
46 class Thread: public CppUnitMini::TestThread
49 typedef typename ALLOC::value_type value_type;
51 virtual Thread * clone()
53 return new Thread( *this );
56 randomGen<size_t> m_rndGen;
61 Thread( CppUnitMini::ThreadPool& pool, ALLOC& a )
62 : CppUnitMini::TestThread( pool )
66 : CppUnitMini::TestThread( src )
67 , m_Alloc( src.m_Alloc )
72 return reinterpret_cast<Larson&>( m_Pool.m_Test );
75 virtual void init() { cds::threading::Manager::attachThread() ; }
76 virtual void fini() { cds::threading::Manager::detachThread() ; }
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 );
89 template <class ALLOC>
90 void test( size_t nThreadCount )
94 CPPUNIT_MSG( "Thread count=" << nThreadCount );
95 CPPUNIT_MSG("Initialize data..." );
97 randomGen<unsigned int> rndGen;
99 s_nPassPerThread = s_nPassCount / nThreadCount;
102 m_aThreadData = new thread_data[ nThreadCount ];
103 for ( nThread = 0; nThread < nThreadCount; ++nThread ) {
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 );
112 CPPUNIT_MSG("Initializatin done" );
114 CppUnitMini::ThreadPool pool( *this );
115 pool.add( new Thread<ALLOC>( pool, alloc ), nThreadCount );
117 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it )
118 static_cast<Thread<ALLOC> *>(*it)->m_arr = m_aThreadData[nThread++];
120 cds::OS::Timer timer;
122 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
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 );
131 delete [] m_aThreadData;
134 template <class ALLOC>
135 void test( bool bStat )
137 CPPUNIT_MSG( "Block size=" << s_nMinBlockSize << "-" << s_nMaxBlockSize
138 << ", block count per thread=" << s_nBlocksPerThread << ", pass count=" << s_nPassCount );
140 for ( size_t nThreadCount = 2; nThreadCount <= s_nMaxThreadCount; nThreadCount *= 2 ) {
141 summary_stat stBegin;
143 ALLOC::stat(stBegin);
145 test<ALLOC>( nThreadCount );
149 ALLOC::stat( stEnd );
151 std::cout << "\nStatistics:\n"
155 std::cout << "\nDelta statistics:\n"
162 void setUpParams( const CppUnitMini::TestCfg& cfg )
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;
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;
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> )
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 )
189 CPPUNIT_TEST_SUITE( Larson )
190 CPPUNIT_TEST( michael_heap_stat )
191 CPPUNIT_TEST( michael_heap_nostat )
192 CPPUNIT_TEST( std_alloc )
194 CPPUNIT_TEST( system_aligned_alloc )
195 CPPUNIT_TEST( michael_alignheap_stat )
196 CPPUNIT_TEST( michael_alignheap_nostat )
198 CPPUNIT_TEST_SUITE_END();
201 } // namespace memory
202 CPPUNIT_TEST_SUITE_REGISTRATION( memory::Larson );