Здравствуйте, eao197, Вы писали:
E>Или небольшая история, подтверждающая известный афоризм о том, что любая сложная проблема имет очевидное, простое и красивое неправильное решение, на примере реализации теста производительности chameneos, в ходе которой в очередной раз проявились ужасы многопоточного программирования и еще раз довелось столкнуться с задачей, проверка решения которой гораздо важнее и сложнее, чем получение самого решения.
Занятная задачка. И занятные засады.
На всякий случай оригинальное условие:
* create differently coloured (blue, red, yellow), differently named, concurrent chameneos creatures
* each creature will repeatedly go to the meeting place and meet, or wait to meet, another chameneos "(at the request the caller does not know whether another chameneos is already present or not, neither if there will be one in some future)"
* both creatures will change colour to complement the colour of the chameneos that they met — don't use arithmetic to complement the colour, use if-else or switch/case or pattern-match
* write all the colour changes for blue red and yellow creatures, using the colour complement function
* for rendezvouses with an odd number of creatures (blue red yellow) and with an even number of creatures (blue red yellow red yellow blue red yellow red blue)
o write the colours the creatures start with
o after N meetings have taken place, for each creature write the number of creatures met and spell out the number of times the creature met a creature with the same name (should be zero)
o spell out the sum of the number of creatures met (should be 2N)
Решил сделать свой вариант решения (приведён ниже). Исчерпывающего тестирования я не проводил, но на первый взгляд работает.
Под Win32 у меня работает 8.85 секунды (прогон для 3 зверей + прогон для 10 зверей, каждый под 6'000'000 встреч). А под Linux получается 16.8. У меня подозрение на старое ядро и на слабую машину.
Версия eao197 при тех параметрах у меня работает 70 секунд.
Несмотря на элиминацию мьютексов получилось вроде даже проще... если никто не найдёт ошибок ... писал как раз с томо самого наскока
Алгоритм в creature::run() имхо достаточно прямолинейный — атомарно производится либо забор уже лежащей заявки, если она есть; либо кладём свою заявку, если завяки не лежит. Если положили свою заявку, значит ждём, пока её кто-нибудь обработает. Если взяли чужую заявку, значит обрабатываем её и нотифицируем ждущего. Нет никакой сложной логики блокирования/сигнализирования, которой присущи гонки, дедлоки и т.д.
Ожидание сделано на активном/пассивном спине (в зависимости от условий). Спин ожидание тут получается "то, что доктор прописал", как с т.з. производительности, так и с т.з. простоты имплементации.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <pthread.h>
#include <sched.h>
#include <sys/times.h>
template<bool smp>
long atomic_cas32(long volatile* dst, long cmp, long xchg)
{
long old;
__asm__ __volatile__ ("lock; cmpxchgl %2, %0"
: "=m" (*dst), "=a" (old)
: "r" (xchg), "m" (*dst), "a" (cmp));
return old;
}
template<>
long atomic_cas32<false>(long volatile* dst, long cmp, long xchg)
{
long old;
__asm__ __volatile__ ("lock; cmpxchgl %2, %0"
: "=m" (*dst), "=a" (old)
: "r" (xchg), "m" (*dst), "a" (cmp));
return old;
}
template<bool active_spin>
void yield()
{
sched_yield();
}
template<>
void yield<true>()
{
__asm__ __volatile__ ("pause");
}
typedef int color_t;
color_t const BLUE = 0;
color_t const RED = 1;
color_t const YELLOW = 2;
color_t complement(color_t const c1, color_t const c2)
{
switch (c1)
{
case BLUE:
switch (c2)
{
case BLUE: return BLUE;
case RED: return YELLOW;
case YELLOW: return RED;
}
break;
case RED:
switch (c2)
{
case BLUE: return YELLOW;
case RED: return RED;
case YELLOW: return BLUE;
}
break;
case YELLOW:
switch (c2)
{
case BLUE: return RED;
case RED: return BLUE;
case YELLOW: return YELLOW;
}
break;
}
assert(false);
return 0;
}
struct meeting_request
{
color_t volatile my_color_;
color_t volatile peer_color_;
int volatile completed_;
};
struct meeting_place
{
struct part
{
unsigned req_index_ : 4;
unsigned req_present_ : 1;
unsigned remaining_ : 27;
};
union
{
part part_;
long raw_;
};
};
class creature
{
public:
creature(color_t my, meeting_place& mp, meeting_request* mr, int index)
: meet_()
, my_color_(my)
, mp_(mp)
, mr_(mr)
, index_(index)
{
}
template<bool smp, bool active_spin>
void run()
{
meeting_request* my_req = &mr_[index_];
for (;;)
{
meeting_place cmp;
cmp.raw_ = mp_.raw_;
if (0 == cmp.part_.remaining_)
break;
if (cmp.part_.req_present_)
{
meeting_place const xchg = {0, 0, cmp.part_.remaining_ - 1};
meeting_place prev;
prev.raw_ = atomic_cas32<smp>(&mp_.raw_, cmp.raw_, xchg.raw_);
if (cmp.raw_ == prev.raw_)
{
meeting_request* req = &mr_[cmp.part_.req_index_];
color_t const peer_color = req->my_color_;
req->peer_color_ = my_color_;
req->completed_ = 1;
my_color_ = complement(my_color_, peer_color);
meet_ += 1;
}
}
else
{
my_req->completed_ = 0;
my_req->my_color_ = my_color_;
meeting_place const xchg = {index_, 1, cmp.part_.remaining_};
meeting_place prev;
prev.raw_ = atomic_cas32<smp>(&mp_.raw_, cmp.raw_, xchg.raw_);
if (cmp.raw_ == prev.raw_)
{
do yield<active_spin>();
while (0 == my_req->completed_);
my_color_ = complement(my_color_, my_req->peer_color_);
meet_ += 1;
}
}
}
}
int meet() const
{
return meet_;
}
private:
int meet_;
color_t my_color_;
meeting_place volatile& mp_;
meeting_request* mr_;
int index_;
};
template<bool smp, bool active_spin>
void* creature_thread(void* arg)
{
static_cast<creature*>(arg)->run<smp, active_spin>();
return 0;
}
template<int creature_count>
void run_test(int proc_count, int meet_count, color_t (&colors)[creature_count])
{
meeting_place mp = {0, 0, meet_count};
meeting_request mr [creature_count];
creature* group [creature_count] = {};
pthread_t threads [creature_count];
void*(*thread_f)(void*) = 0;
if (1 == proc_count)
thread_f = &creature_thread<false, false>;
else if (proc_count < creature_count)
thread_f = &creature_thread<true, false>;
else
thread_f = &creature_thread<true, true>;
for (int i = 0; i != creature_count; ++i)
{
group[i] = new creature(colors[i], mp, mr, i);
pthread_create(&threads[i], 0, thread_f, group[i]);
}
int meet = 0;
for (int i = 0; i != creature_count; ++i)
{
pthread_join(threads[i], 0);
meet += group[i]->meet();
delete group[i];
}
printf("%d\n", meet);
}
int main(int argc, char** argv)
{
clock_t const t1 = times(0);
int const proc_count = sysconf(_SC_NPROCESSORS_CONF);
int meet_count = 600;
if (2 == argc)
meet_count = atoi(argv[1]);
color_t colors1 [] = {BLUE, RED, YELLOW};
run_test(proc_count, meet_count, colors1);
color_t colors2 [] = {BLUE, RED, YELLOW, RED, YELLOW, BLUE, RED, YELLOW, RED, BLUE};
run_test(proc_count, meet_count, colors2);
clock_t const t2 = times(0);
printf("%d\n", (int)(t2 - t1));
}
Здравствуйте, eao197, Вы писали:
E>Или небольшая история, подтверждающая известный афоризм о том, что любая сложная проблема имет очевидное, простое и красивое неправильное решение, на примере реализации теста производительности chameneos, в ходе которой в очередной раз проявились ужасы многопоточного программирования и еще раз довелось столкнуться с задачей, проверка решения которой гораздо важнее и сложнее, чем получение самого решения.
Programs may use kernel threads, lightweight threads… cooperative threads… and other programs with custom schedulers will be listed as interesting alternative implementations. Briefly say what concurrency technique is used in the program header comment.
Можно ли использовать lightweight threads и cooperative threads?
Здравствуйте, remark, Вы писали:
R>Здравствуйте, eao197, Вы писали:
E>>Или небольшая история, подтверждающая известный афоризм о том, что любая сложная проблема имет очевидное, простое и красивое неправильное решение, на примере реализации теста производительности chameneos, в ходе которой в очередной раз проявились ужасы многопоточного программирования и еще раз довелось столкнуться с задачей, проверка решения которой гораздо важнее и сложнее, чем получение самого решения.
R>Занятная задачка. И занятные засады.
R>На всякий случай оригинальное условие: R>
R> * create differently coloured (blue, red, yellow), differently named, concurrent chameneos creatures
R> * each creature will repeatedly go to the meeting place and meet, or wait to meet, another chameneos "(at the request the caller does not know whether another chameneos is already present or not, neither if there will be one in some future)"
R> * both creatures will change colour to complement the colour of the chameneos that they met — don't use arithmetic to complement the colour, use if-else or switch/case or pattern-match
R> * write all the colour changes for blue red and yellow creatures, using the colour complement function
R> * for rendezvouses with an odd number of creatures (blue red yellow) and with an even number of creatures (blue red yellow red yellow blue red yellow red blue)
R> o write the colours the creatures start with
R> o after N meetings have taken place, for each creature write the number of creatures met and spell out the number of times the creature met a creature with the same name (should be zero)
R> o spell out the sum of the number of creatures met (should be 2N)
Просто хочу заметить, что сейчас используется несколько иной бенчмарк, под именем chameneos-new. Его условие несколько отличается от того бенчмарка, который делал я.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, eao197, Вы писали:
E>>>Или небольшая история, подтверждающая известный афоризм о том, что любая сложная проблема имет очевидное, простое и красивое неправильное решение, на примере реализации теста производительности chameneos, в ходе которой в очередной раз проявились ужасы многопоточного программирования и еще раз довелось столкнуться с задачей, проверка решения которой гораздо важнее и сложнее, чем получение самого решения.
R>>Занятная задачка. И занятные засады.
R>>На всякий случай оригинальное условие: R>>
R>> * create differently coloured (blue, red, yellow), differently named, concurrent chameneos creatures
R>> * each creature will repeatedly go to the meeting place and meet, or wait to meet, another chameneos "(at the request the caller does not know whether another chameneos is already present or not, neither if there will be one in some future)"
R>> * both creatures will change colour to complement the colour of the chameneos that they met — don't use arithmetic to complement the colour, use if-else or switch/case or pattern-match
R>> * write all the colour changes for blue red and yellow creatures, using the colour complement function
R>> * for rendezvouses with an odd number of creatures (blue red yellow) and with an even number of creatures (blue red yellow red yellow blue red yellow red blue)
R>> o write the colours the creatures start with
R>> o after N meetings have taken place, for each creature write the number of creatures met and spell out the number of times the creature met a creature with the same name (should be zero)
R>> o spell out the sum of the number of creatures met (should be 2N)
E>Просто хочу заметить, что сейчас используется несколько иной бенчмарк, под именем chameneos-new. Его условие несколько отличается от того бенчмарка, который делал я.
Насколько я вижу, алгоритм точно такой же. Поменялся формат вывода. Убрали конечный цвет. Надо запускать для 3, потом для 10 зверей. А так вроде алгоритм точно такой же. По крайней мере я твою программу подогнал под новые требования за пару минут (не считая "произнесения результатов" — имхо бред какой-то ).
К слову. По поводу "произнесения результатов" — это я не понял что за фишка и с чем связана. Но я не про это. Я про требование "don't use arithmetic to complement the colour, use if-else or switch/case or pattern-match". Они судя по всему плохо представляют, что происходит. Моя программа проводит в юзер-спейсе 7% времени, 93% времени — это переключение потоков. Это при том, что я не оптимизировал основной цикл (за исключением префикса lock). Они действительно думают, что способ вычисления цвета будет на что-то влиять?! Если на одну встречу по условию задачи требуется несколько вызовов примитивов синхронизации + обязательное переключение контекста. О каком способе вычисления цвета они говорят?! Ну это так к слову...
Спасибо.
Под Win32 есть легковесные потоки — Fibers. А под Linux сейчас что-нибудь подобное есть?
(по иронии судьбы фиберы в виндовс пришли как раз из юникс систем )
А то как то совсем не честно получается, т.к. на каждую встречу обязательно переключение контекста. Понятно, что переключение легковесного потока языка на порядок быстрее переключения ядерного потока.
Здравствуйте, remark, Вы писали:
R>А то как то совсем не честно получается, т.к. на каждую встречу обязательно переключение контекста. Понятно, что переключение легковесного потока языка на порядок быстрее переключения ядерного потока.
Возми Java и какой нибуть JVM с green threads. Этот например.
... << RSDN@Home 1.2.0 alpha 4 rev. 1031 on Windows Vista 6.0.6001.65536>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, remark, Вы писали:
R>>А то как то совсем не честно получается, т.к. на каждую встречу обязательно переключение контекста. Понятно, что переключение легковесного потока языка на порядок быстрее переключения ядерного потока.
AVK>Возми Java и какой нибуть JVM с green threads. Этот например.
А она сможет, если программа запускается на компьютере с одним процессором, убрать префикс lock перед cmpxchg (в атомарных операциях)?
Сколько там занимает переключение контекста между легковесными потоками? В WinXPSP2 на ядерных потоках занимает порядка 700 тактов.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, remark, Вы писали:
R>>А то как то совсем не честно получается, т.к. на каждую встречу обязательно переключение контекста. Понятно, что переключение легковесного потока языка на порядок быстрее переключения ядерного потока.
AVK>Возми Java и какой нибуть JVM с green threads. Этот например.
Кстати, а в D насколько я знаю есть возможность писать встроенный asm. Правильно?
А встроенные легковесные потоки есть?
Здравствуйте, remark, Вы писали:
R>А она сможет, если программа запускается на компьютере с одним процессором, убрать префикс lock перед cmpxchg (в атомарных операциях)? R>Сколько там занимает переключение контекста между легковесными потоками? В WinXPSP2 на ядерных потоках занимает порядка 700 тактов.
Возьми да попробуй.
... << RSDN@Home 1.2.0 alpha 4 rev. 1032 on Windows Vista 6.0.6001.65536>>
Здравствуйте, remark, Вы писали:
R>А она сможет, если программа запускается на компьютере с одним процессором, убрать префикс lock перед cmpxchg (в атомарных операциях)?
AFAIR на "однояйцевом" x86 проце lock вообще ничего не делает.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, remark, Вы писали:
R>>А она сможет, если программа запускается на компьютере с одним процессором, убрать префикс lock перед cmpxchg (в атомарных операциях)? CC>AFAIR на "однояйцевом" x86 проце lock вообще ничего не делает.
На Pentium4, которые у них используются она ничего не делает, кроме задержки на 100 тактов и полной очистки пайплайна...
На некоторых AMD она действительно была практически бесплатной, но конкретно о той модели, которая у них, затрудняюсь сказать.
Здравствуйте, remark, Вы писали:
R>>>А она сможет, если программа запускается на компьютере с одним процессором, убрать префикс lock перед cmpxchg (в атомарных операциях)? CC>>AFAIR на "однояйцевом" x86 проце lock вообще ничего не делает. R>На Pentium4, которые у них используются она ничего не делает, кроме задержки на 100 тактов и полной очистки пайплайна...
На одноядерном и без HT?
Речь веду про то, что на не-SMP х86 системе lock не делала вообще ничего.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, remark, Вы писали:
R>>Кстати, а в D насколько я знаю есть возможность писать встроенный asm. Правильно?
E>Что-то такое есть
Всё, что нужно, имеется.
R>>А встроенные легковесные потоки есть?
E>Встроенных нет, но в библиотеке Tango есть реализация фиберов (вроде как кроссплатформенная).
А Tango входит в стандартную поставку DMD? Можно ли её использовать в The Computer Language Benchmarks Game?
Моя версия на ядерных потоках под Win32 будет работает у них на компьютере 2.1 сек.
Если у меня будет асм и легкие потоки с временем переключения контекста, допустим, 100 тактов, то я могу написать реализацию, которая у них будет работать за 0.35 сек (350 мс). Это при том, что там сейчас самая быстрая — на Haskell GHC — 11.93 сек! Вздрючим Haskell!
Здравствуйте, remark, Вы писали:
R>>>А встроенные легковесные потоки есть?
E>>Встроенных нет, но в библиотеке Tango есть реализация фиберов (вроде как кроссплатформенная).
R>А Tango входит в стандартную поставку DMD? Можно ли её использовать в The Computer Language Benchmarks Game?
Не входит. Насколько я знаю, в TCLBG используется DMD без Tango, поэтому Tango использовать не получится.
Но, поскольку Tango -- это чистый OpenSource, то из ее исходников можно вытащить те фрагменты, которые тебе потребуются для реализации этого теста на фиберах.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, remark, Вы писали:
R>>>>А встроенные легковесные потоки есть?
E>>>Встроенных нет, но в библиотеке Tango есть реализация фиберов (вроде как кроссплатформенная).
R>>А Tango входит в стандартную поставку DMD? Можно ли её использовать в The Computer Language Benchmarks Game?
E>Не входит. Насколько я знаю, в TCLBG используется DMD без Tango, поэтому Tango использовать не получится.
E>Но, поскольку Tango -- это чистый OpenSource, то из ее исходников можно вытащить те фрагменты, которые тебе потребуются для реализации этого теста на фиберах.
Если я это вставлю в свою программу, то это будет считаться кастомным шедулером:
Programs may use kernel threads, lightweight threads… cooperative threads… and other programs with custom schedulers will be listed as interesting alternative implementations. Briefly say what concurrency technique is used in the program header comment.
з.ы. постом выше я немного наврал — 2.1 сек. это тест на 10^6 встреч, а полномасшабный тест на 2 х 6*10^6 этот работает 10.5 секунд
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, remark, Вы писали:
R>>>>А она сможет, если программа запускается на компьютере с одним процессором, убрать префикс lock перед cmpxchg (в атомарных операциях)? CC>>>AFAIR на "однояйцевом" x86 проце lock вообще ничего не делает. R>>На Pentium4, которые у них используются она ничего не делает, кроме задержки на 100 тактов и полной очистки пайплайна...
CC>На одноядерном и без HT? CC>Речь веду про то, что на не-SMP х86 системе lock не делала вообще ничего.
Да, именно на самом обычно одноядерном однопроцессорном без HT компьютере с Pentium4 lock стоит 100 тактов. Это далеко не бесплатно.
... писал как раз с томо самого наскока 
Ну это так к слову...
