ring.cpp

   1 /*
   2  * The Computer Language Benchmarks Game
   3  * http://shootout.alioth.debian.org/
   4  * Contributed by Premysl Hruby
   5  * convert to C++ by The Anh Tran
   6  * Some optimisation by Pauli Nieminen
   7  */
   8
   9 #ifndef __USE_GNU
  10 #define __USE_GNU
  11 #endif
  12
  13 #include <unistd.h>
  14 #include <pthread.h>
  15 #include <sched.h>
  16 #include <cstdio>
  17 #include <cstdlib>
  18 #include <limits.h>
  19 #include <sys/sysinfo.h>
  20 #include <cstdint>
  21
  22 typedef unsigned int uint;
  23
  24 const uint16_t NUM_THREADS   = 503;
  25 const uint STACK_SIZE   = PTHREAD_STACK_MIN;
  26
  27 // hw_concurrency should be <cores in use>-1
  28 // a core is reserved for new threads initializing
  29 const uint16_t hw_concurrency = 3;
  30 #define real_hw_concurrency 4
  31
  32 class mutex_t {
  33         pthread_mutex_t mutex_;
  34 public:
  35         mutex_t() : mutex_(PTHREAD_MUTEX_INITIALIZER)
  36         {
  37         }
  38
  39         void lock()
  40         {
  41         pthread_mutex_lock( &mutex_ );
  42         }
  43
  44         void unlock()
  45         {
  46                 pthread_mutex_unlock( &mutex_ );
  47         }
  48 };
  49
  50 template <class F>
  51 void* threadStarter(void *param)
  52 {
  53         F* func = reinterpret_cast<F*>(param);
  54         (*func)();
  55         return 0;
  56 }
  57
  58 #include <cassert>
  59
  60 class thread {
  61         thread(const thread&);
  62         thread& operator=(const thread&);
  63 public:
  64         thread() {}
  65
  66         template <class F>
  67         void createThread(F& func,
  68                         pthread_t& id,
  69                         pthread_attr_t& attr)
  70         {
  71                 pthread_create(&id, &attr, &threadStarter<F>,static_cast<void*>(&func));
  72         }
  73
  74         static void join(pthread_t& id)
  75         {
  76                 pthread_join(id, 0);
  77         }
  78
  79 };
  80
  81 class barrier_t {
  82         pthread_barrier_t barrier;
  83         public:
  84         barrier_t()
  85         {
  86                 pthread_barrier_init(&barrier, 0, 2);
  87         }
  88
  89         void wait()
  90         {
  91                 pthread_barrier_wait(&barrier);
  92         }
  93
  94 };
  95
  96 uint   token = 1000;
  97
  98 barrier_t               main_barrier;
  99 mutex_t      mutex[NUM_THREADS];
 100 char            stacks   [NUM_THREADS][STACK_SIZE];
 101
 102 #if real_hw_concurrency > 1 || real_hw_concurrency == 0
 103 cpu_set_t cpu_set_free;
 104 cpu_set_t cpu_set_restrict;
 105 #endif
 106
 107 void init_cpu_set()
 108 {
 109 #if real_hw_concurrency > 1 || real_hw_concurrency == 0
 110         CPU_ZERO(&cpu_set_restrict);
 111         CPU_SET(0,&cpu_set_restrict);
 112         // Run free thread everywhere else except first cpu
 113         sched_getaffinity(getpid(), sizeof(cpu_set_t), &cpu_set_free);
 114         if (real_hw_concurrency == 0)
 115         {
 116                 if (hw_concurrency < get_nprocs())
 117                         CPU_CLR(0, &cpu_set_free);
 118         } else {
 119                 if (hw_concurrency < real_hw_concurrency )
 120                         CPU_CLR(0, &cpu_set_free);
 121         }
 122 #endif
 123 }
 124
 125 class thread_func {
 126
 127         uint16_t id;
 128         public:
 129         static thread threads[NUM_THREADS];
 130         static thread_func functions[NUM_THREADS];
 131
 132         void set_id(uint16_t new_id) {
 133                 id = new_id;
 134         }
 135
 136         void operator()()
 137         {
 138                 if (hw_concurrency > 1
 139                         && (id + 1) < hw_concurrency)
 140                 {
 141                         {
 142                                 const uint16_t start = (NUM_THREADS*(id+1))/hw_concurrency;
 143                                 const uint16_t end = (NUM_THREADS*(id+2))/hw_concurrency;
 144                                 thread_func::createThreads(start, end);
 145                         }
 146 #if real_hw_concurrency > 1 || real_hw_concurrency == 0
 147                         pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpu_set_restrict);
 148 #endif
 149                 }
 150                 mutex_t &mutex_this_node = mutex[id];
 151                 mutex_t &mutex_next_node = mutex[(id +1)%NUM_THREADS];
 152
 153                 while (true)
 154                 {
 155                         mutex_this_node.lock();
 156                         if ( token > 0 )
 157                         {
 158                                 token--;
 159                                 mutex_next_node.unlock();
 160                         }
 161                         else
 162                         {
 163                                 printf("%d\n", id+1 );
 164                                 exit(0);
 165                         }
 166                 }
 167         }
 168
 169         static void createThreads(uint16_t start, const uint16_t& end)
 170         {
 171                 pthread_attr_t stack_attr;
 172                 pthread_attr_init(&stack_attr);
 173                 if (1 < hw_concurrency
 174                         && (start+1) < hw_concurrency)
 175                 {
 176 #if real_hw_concurrency > 1 || real_hw_concurrency == 0
 177                         pthread_attr_setaffinity_np(&stack_attr, sizeof(cpu_set_t), &cpu_set_free);
 178 #endif
 179                         if (hw_concurrency-1 < end)
 180                                 docreateThreads(start, hw_concurrency-1, stack_attr);
 181                         else
 182                                 docreateThreads(start, end, stack_attr);
 183
 184                 }
 185 #if real_hw_concurrency > 1 || real_hw_concurrency == 0
 186                 pthread_attr_setaffinity_np(&stack_attr, sizeof(cpu_set_t), &cpu_set_restrict);
 187 #endif
 188                 docreateThreads(start, end, stack_attr);
 189
 190         }
 191
 192 private:
 193         static void docreateThreads(uint16_t& start, const uint16_t& end, pthread_attr_t& stack_attr)
 194         {
 195                 pthread_t id;
 196                 for (; start < end; ++start)
 197                 {
 198                         // lock all mutexs
 199                         mutex[start].lock();
 200                         // manual set stack space & stack size for each thread
 201                         // to reduce memory usage
 202                         pthread_attr_setstack( &stack_attr, &(stacks[start]), STACK_SIZE );
 203                         functions[start].set_id(start);
 204
 205                         // create thread using specified stackspace
 206                         threads[start].createThread(functions[start], id, stack_attr);
 207                 }
 208
 209         }
 210
 211 };
 212
 213 thread thread_func::threads[NUM_THREADS];
 214 thread_func thread_func::functions[NUM_THREADS];
 215
 216 int main(int argc, char** args)
 217 {
 218         if (argc >= 2)
 219                 token = atoi(args[1]);
 220
 221         {
 222                 init_cpu_set();
 223                 const uint16_t start = 0;
 224                 const uint16_t end = NUM_THREADS/hw_concurrency;
 225                 thread_func::createThreads(start, end);
 226         }
 227         // start game
 228         mutex[0].unlock();
 229
 230         // wait for result
 231         main_barrier.wait();
 232
 233         return 0;
 234 }