source code
/* The Computer Language Benchmarks Game
http://benchmarksgame.alioth.debian.org/
Based on original C contribution by Alex Burlyga.
Based on thread pool + request queue in Java contribution by Michael Barker.
Based on single atomic ops, and pthread affinity in C contribution by Dmitry Vyukov.
Based on C++ contribution by Andrew Moon.
Contributed by The Anh Tran.
This entry creates N kernel threads. All threads will wait inside
boost::asio::io_service queue object. If there is a request posted to io_service
queue, a thread will be dispatched to handle it.
Each creature will submit "i want to go to meeting place" request to io_service.
Atomic compare-and-set is used to change meeting place state.
*/
#include <fstream>
#include <iostream>
#include <string>
#include <map>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <memory.h>
#include <pthread.h>
#include <sched.h>
#include <boost/xpressive/xpressive_static.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/format.hpp>
#include <boost/asio.hpp>
#include <boost/thread.hpp>
#include <boost/bind.hpp>
#include <boost/smart_ptr.hpp>
#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH
typedef unsigned int uint;
typedef boost::asio::io_service QUEUE_T;
#define CPU_INFO_STR "/proc/cpuinfo"
#define L2_ALIGN __attribute__((aligned(16)))
enum COLOR { BLUE = 0, RED = 1, YELLOW = 2 };
COLOR
operator ^ (COLOR c1, COLOR c2)
{
switch (c1) // game rule
{
case BLUE: switch (c2)
{
case BLUE: return BLUE;
case RED: return YELLOW;
case YELLOW: return RED;
}
case RED: switch (c2)
{
case BLUE: return YELLOW;
case RED: return RED;
case YELLOW: return BLUE;
}
case YELLOW: switch (c2)
{
case BLUE: return RED;
case RED: return BLUE;
case YELLOW: return YELLOW;
}
}
assert(false);
return BLUE;
}
std::ostream&
operator << (std::ostream &os, COLOR c)
{
static char const * ColorName[3] = {"blue", "red", "yellow"};
os << ColorName[c];
return os;
}
std::string
SpellNumber(uint n)
{
static char const* NumberStr[] =
{
"zero ", "one ", "two ", "three ", "four ",
"five ", "six ", "seven ", "eight ", "nine "
};
std::string num;
while ( n >= 10 )
{
uint m = n % 10;
n /= 10;
num.insert(0, NumberStr[m]);
}
num.insert(0, NumberStr[n]);
return num;
}
/* Place where a creature meet another.
stage_exchange stores 2 informations:
_ how many meeting times to go. 28 bit from bit 0 -> 27.
_ is there any creature waiting. 4 highest bit, 28 -> 31
*/
struct MeetingPlace
{
private:
L2_ALIGN
uint volatile state_exchange_;
public:
MeetingPlace(uint N) : state_exchange_(N) { }
/*
State_exchange = 32 bit
4 bit MSB: id of creature which is waiting. Can support up to 15 creatures.
28 bit: counter of how many meeting times that needs to run
*/
int EnterMeetingRoom( uint cr_id ) // id starts from 1.
{
while (true)
{
uint old_state = state_exchange_;
uint meeting_left = old_state & 0x0FFFFFFF;
if (meeting_left > 0)
{
uint cr_waiting = old_state >> 28;
uint new_state;
if (cr_waiting == 0) // no one inside, me is 1st
new_state = meeting_left | (cr_id << 28);
else // there is a creature waiting
new_state = meeting_left -1;
if (__sync_bool_compare_and_swap(&state_exchange_, old_state, new_state))
return cr_waiting;
}
else
return -1;
}
}
};
struct Creature
{
QUEUE_T* p_queue_;
MeetingPlace* p_meetingplace_;
Creature* p_cr_list_;
COLOR color_;
uint count_;
uint id_; // creature id start from 1
uint same_count_;
Creature() : color_(BLUE), count_(0), id_(0), same_count_(0) {}
void
Start( MeetingPlace* mp, COLOR color , uint id,
QUEUE_T* queue, Creature* pcrl)
{
color_ = color;
id_ = id +1;
p_queue_ = queue;
p_meetingplace_ = mp;
p_cr_list_ = pcrl;
// post "go to meeting place" request
p_queue_->post(boost::bind(&Creature::PlayGame, this));
}
// request granted, meeting action executes here
void
PlayGame()
{
int other_cr_id = p_meetingplace_->EnterMeetingRoom(id_);
// meeting_place returns other creature?
if (other_cr_id > 0)
SayHello( p_cr_list_[other_cr_id -1] );
// if me is the 1st one entering meeting_place, do nothing.
// 2nd arrival creature will submit next meeting request for me.
}
void
SayHello(Creature &other)
{
if (__builtin_expect(id_ == other.id_, false))
{
++same_count_;
++other.same_count_;
}
++count_;
++other.count_;
COLOR new_color = this->color_ ^ other.color_;
other.color_ = color_ = new_color;
// submit another meeting request, for current creature + other creature.
p_queue_->post(boost::bind(&Creature::PlayGame, this));
p_queue_->post(boost::bind(&Creature::PlayGame, &other));
}
} L2_ALIGN;
template <int ncolor>
struct Game
{
MeetingPlace mplace;
QUEUE_T queue;
Creature cr_list[ncolor]; // list of all creatures
std::ostringstream game_output;
boost::thread_group cr_thread_group; // 1 standard OS thread for each creature
Game(uint n, COLOR const (&color)[ncolor], cpu_set_t * aff = 0)
: mplace(n)
{
boost::format fmt("%1% ");
// print initial color of each creature
for (int i = 0; i < ncolor; ++i)
{
game_output << (fmt % (color[i]) );
cr_list[i].Start( &mplace, color[i], i, &queue, cr_list );
}
game_output << std::endl;
// Create N kernel threads. All threads will wait inside boost::asio::io_service
// queue object. If there is a request posted to io_service queue, a thread
// will be dispatched to handle it.
for (int i = 0; i < ncolor; ++i)
{
boost::thread* t = cr_thread_group.create_thread(boost::bind(&QUEUE_T::run, &queue));
if(aff != 0)
pthread_setaffinity_np(t->native_handle(), sizeof(cpu_set_t), aff);
}
}
std::string
WaitAndGetResult()
{
// wait until meeting times = 0
cr_thread_group.join_all();
uint total = 0;
boost::format fmt("%1% %2%\n");
// print meeting times of each creature
for (int i = 0; i < ncolor; i++)
{
total += cr_list[i].count_;
game_output << (fmt
% cr_list[i].count_
% SpellNumber(cr_list[i].same_count_) );
}
// print total meeting times
fmt = boost::format(" %1%\n\n");
game_output << (fmt % SpellNumber(total));
return game_output.str();
}
};
void
PrintColors()
{
boost::format fmt("%1% + %2% -> %3%\n");
for (int c1 = BLUE; c1 <= YELLOW; ++c1)
{
for (int c2 = BLUE; c2 <= YELLOW; ++c2)
std::cout << (fmt % (COLOR)c1 % (COLOR)c2 % ((COLOR)c1 ^ (COLOR)c2));
}
std::cout << std::endl;
}
// Detect multi / single thread benchmark
int
GetThreadCount()
{
cpu_set_t cs;
CPU_ZERO(&cs);
sched_getaffinity(0, sizeof(cs), &cs);
int count = 0;
for (int i = 0; i < 16; ++i)
{
if (CPU_ISSET(i, &cs))
++count;
}
return count;
}
// Parse /proc/cpuinfo
// Return a list of cpu cores sharing 1 L2 cache
std::auto_ptr<std::vector<cpu_set_t> >
GetAffinityList()
{
std::ifstream file(CPU_INFO_STR);
std::istreambuf_iterator<char> is(file), ise;
// load file to vector<char>
std::vector<char> buf;
std::copy(is, ise, std::back_inserter(buf));
file.close();
// map processors to L2 cache unit
typedef std::map<int, cpu_set_t> MAP_T;
MAP_T l2_set;
{
using namespace boost::xpressive;
namespace bx = boost::xpressive;
typedef std::vector<char>::iterator VI_T;
typedef bx::basic_regex<VI_T> RE_T;
typedef bx::regex_iterator<VI_T> IRE_T;
RE_T re(
as_xpr("processor") >> +(_s|':') >> (s1 = +_d)
>> -+(~_n|_n)
>> "apicid" >> +(_s|':') >> (s2 = +_d) );
IRE_T it(buf.begin(), buf.end(), re), it_end;
for (; it != it_end; ++it)
{
int core = boost::lexical_cast<int>( (*it)[1].str() );
int apic = boost::lexical_cast<int>( (*it)[2].str() );
// q6600 has 4 cores, 2 cores share 1 L2 cache
// 2 cores + 1 L2 = 1 package
int package = apic >> 1;
CPU_SET(core, &(l2_set[package]));
}
}
std::auto_ptr<std::vector<cpu_set_t> > aff(new std::vector<cpu_set_t>);
typedef MAP_T::value_type VT;
foreach ( VT &i, l2_set )
aff->push_back(i.second);
return aff;
}
int
main(int argc, char** argv)
{
PrintColors();
COLOR const r1[] = { BLUE, RED, YELLOW };
COLOR const r2[] = { BLUE, RED, YELLOW, RED, YELLOW, BLUE, RED, YELLOW, RED, BLUE };
int n = (argc >= 2) ? boost::lexical_cast<int>(argv[1]) : 600;
if (GetThreadCount() > 1)
{
std::auto_ptr<std::vector<cpu_set_t> > affset( GetAffinityList() );
Game<3> cg1( n, r1, &((*affset)[0]) );
Game<10> cg2( n, r2, &((*affset)[1]) );
std::cout << cg1.WaitAndGetResult();
std::cout << cg2.WaitAndGetResult();
}
else
{
Game<3> cg1( n, r1 );
std::cout << cg1.WaitAndGetResult();
Game<10> cg2( n, r2 );
std::cout << cg2.WaitAndGetResult();
}
return 0;
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
g++ (Ubuntu 7.2.0-8ubuntu3) 7.2.0
Mon, 30 Oct 2017 18:49:54 GMT
MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=native -pthread chameneosredux.c++ -o chameneosredux.c++.o && \
/usr/bin/g++ chameneosredux.c++.o -o chameneosredux.gpp_run -lboost_thread -lboost_system -lpthread
chameneosredux.c++:323:6: warning: ‘template<class> class std::auto_ptr’ is deprecated [-Wdeprecated-declarations]
std::auto_ptr<std::vector<cpu_set_t> >
^~~~~~~~
In file included from /usr/include/c++/7/memory:80:0,
from /usr/include/boost/config/no_tr1/memory.hpp:21,
from /usr/include/boost/smart_ptr/shared_ptr.hpp:23,
from /usr/include/boost/shared_ptr.hpp:17,
from /usr/include/boost/xpressive/detail/detail_fwd.hpp:23,
from /usr/include/boost/xpressive/regex_primitives.hpp:21,
from /usr/include/boost/xpressive/xpressive_static.hpp:24,
from chameneosredux.c++:33:
/usr/include/c++/7/bits/unique_ptr.h:51:28: note: declared here
template<typename> class auto_ptr;
^~~~~~~~
chameneosredux.c++: In function ‘std::auto_ptr<std::vector<cpu_set_t> > GetAffinityList()’:
chameneosredux.c++:367:9: warning: ‘template<class> class std::auto_ptr’ is deprecated [-Wdeprecated-declarations]
std::auto_ptr<std::vector<cpu_set_t> > aff(new std::vector<cpu_set_t>);
^~~~~~~~
In file included from /usr/include/c++/7/memory:80:0,
from /usr/include/boost/config/no_tr1/memory.hpp:21,
from /usr/include/boost/smart_ptr/shared_ptr.hpp:23,
from /usr/include/boost/shared_ptr.hpp:17,
from /usr/include/boost/xpressive/detail/detail_fwd.hpp:23,
from /usr/include/boost/xpressive/regex_primitives.hpp:21,
from /usr/include/boost/xpressive/xpressive_static.hpp:24,
from chameneosredux.c++:33:
/usr/include/c++/7/bits/unique_ptr.h:51:28: note: declared here
template<typename> class auto_ptr;
^~~~~~~~
chameneosredux.c++: In function ‘int main(int, char**)’:
chameneosredux.c++:389:12: warning: ‘template<class> class std::auto_ptr’ is deprecated [-Wdeprecated-declarations]
std::auto_ptr<std::vector<cpu_set_t> > affset( GetAffinityList() );
^~~~~~~~
In file included from /usr/include/c++/7/memory:80:0,
from /usr/include/boost/config/no_tr1/memory.hpp:21,
from /usr/include/boost/smart_ptr/shared_ptr.hpp:23,
from /usr/include/boost/shared_ptr.hpp:17,
from /usr/include/boost/xpressive/detail/detail_fwd.hpp:23,
from /usr/include/boost/xpressive/regex_primitives.hpp:21,
from /usr/include/boost/xpressive/xpressive_static.hpp:24,
from chameneosredux.c++:33:
/usr/include/c++/7/bits/unique_ptr.h:51:28: note: declared here
template<typename> class auto_ptr;
^~~~~~~~
rm chameneosredux.c++
14.99s to complete and log all make actions
COMMAND LINE:
./chameneosredux.gpp_run 6000000
PROGRAM OUTPUT:
blue + blue -> blue
blue + red -> yellow
blue + yellow -> red
red + blue -> yellow
red + red -> red
red + yellow -> blue
yellow + blue -> red
yellow + red -> blue
yellow + yellow -> yellow
blue red yellow
4014022 zero
3972724 zero
4013254 zero
one two zero zero zero zero zero zero
blue red yellow red yellow blue red yellow red blue
1246228 zero
1197984 zero
1285528 zero
1229433 zero
1181656 zero
1094422 zero
1208217 zero
1186895 zero
1186909 zero
1182728 zero
one two zero zero zero zero zero zero