Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, What, Вы писали:
W>>Как раз пункт 2.1 (который я цитировал) также гарантирует, что объект будет валидным. Если сначала записать сам объект (первая переменная), а потом положить указатель на него в очередь (вторая переменная внутри очереди), то, в момент, когда второй поток прочитает новое значение второй переменной (достанет из очереди указатель) первая переменная (содержимое объекта) будет уже иметь валидное знаечение, потому что она была записана раньше, а операции записи в разные адреса из одного потока не переставляются в x86. Так что конкретно в том коде автора темы барьеры доступа к памяти не нужны.
Pzz>При условии, что объект будет читаться в том же порядке, в котором он писался. Что является в нормальной жизни совершенно невыносимым требованием.
Нет. Достаточно что бы данные элемента читались после того, как будет считан из очереди сам указатель на эти данные.
Несмотря на всю абсурдность, были такие процессоры, которые могли это делать — читать данные по указателю до того как считан сам указатель
Pzz>Я, кстати, читал не white paper, а другой интеловский дукомент, и поэтому у меня сложилось несколько другое (более пессемистическое) впечатление. Посмотрите пункт 7.2.2, там прям картинка нарисована про то, как writes с разных процессоров могут быть reordered. Следует учесть так же, что на SMP машинке поток вполне может перескочить на соседний процессор как раз между инструкциями, так что даже запись в одно и то же место может приехать out of order, если специально не позаботиться об обратном. Хотя, конечно, в процессе перескакивания на соседний процессор наверняка хоть один барьер да встретится, так что эта возможность скорее гипотетическая. Но я, знаете ли, в таких вопросах пессемист
При миграции потока с одного процессора на другой *гарантированно* обязательно будет выполнен полный барьер памяти на том процессоре, с которого идёт миграция, и на том, на который идёт миграция. Плюс гарантируется, что любая запись с нового процессора будет видна не раньше любой записи со старого процессора.
Я думаю, что в POSIX это должно гарантироваться. В Win32 сложно сказать, где такую информацию можно искать, но уверен, что это в любом случае будет работать так и не сломается в будущем.
Здравствуйте, hexis, Вы писали:
H>Это при привой реализации потоков. При нормальной нет. Я вот не H>поленился, попробовал простенькую реализацию очередей сделанную из тех H>же соображений (правда получилось — один читатель, много писателей). H>Результат — неблокирующая выигрывает процентов на 15-20 (в основном за H>счет тормозов на InterlockedXXX операциях). И это вполне объяснимо — при H>взаимодействии 1:1 в указанных условиях можно обойтись без фактических H>блокировок. Вот код:
Подожди-подожи. Какие InterlockedXXX, если мы говорим об очереди без InterlockedXXX?!
Если ты используешь InterlockedXXX, то это естественно по скорости будет одинакого, т.к. мьютекс == InterlockedXXX.
H>Из отличий — я эксперементировал с неблокирующим аллокатором (иначе H>new/delete тоже занимаются сериализацией) и с разными мьютексами. По H>порядку снижения производительности: spin lock, моя реализация H>рекурсивного mutex с блокировками и win32 critical_section.
В реализации spin lock сколько операций InterlockedXXX на одну блокировку/разблокировку?
>> многопроцессорной машине выигрыш будет ещё существеннее + иметь >> последствия не только на голую скорость, но и на масштабиремость. >>
H>С масштабируемостью, ИМХО, совсем не очевидно — реализация-то рассчитана H>на взаимодействие 1:1. При таких условиях и блокирующие алгоритмы не H>будут деградировать.
Во-первых, на многопроцессорной машине, если у тебя мьютекс без спин-части, то существенно увеличивается вероятность блокирования.
Во-вторых, дело не только в увеличении конкуренции за один конкретный мьютекс, дело так же в увеличении давления на шину когерентности кэшей.
Здравствуйте, HaronK, Вы писали:
HK>Переписал реализацию очереди с учетом предложений в топике. HK>Из изменений: HK>1. Убрал флаг. Теперь его роль исполняет указатель на промежуточную цепочку. HK>2. Убрал new/delete. Операции создания и удаления возлагаются на потоки.
HK>Не знаю насколько замена флага на указатель безопасна, но в моих тестах этот код отрабатывал.
Это даже безопаснее, чем использование отдельного флага.
HK>Барьеры пока не добавлял, поскольку нет единого мнения нужны ли они вообще.
Конкретно в этой реализации на текущей модели памяти х86 барьеры памяти не нужны.
HK>Получилось меньше операций и по идее должно быть быстрее.
Мерить не пробовал?
HK>Не знаю правда как повлияет на быстродействие второй volatile.
Практически никак.
Только тут тебе volatile не поможет, т.к. пользовательские данные не volatile, следовательно обращения к ним могут перемещаться произвольно.
Тут тебе надо использовать _ReadWriteBarrier()
Здравствуйте, HaronK, Вы писали:
HK>Здравствуйте, remark, Вы писали:
R>>Второй момент, что очередь_один_производитель_один_потребитель значительно интереснее, чем кажется на первый взгляд. Во-первых, она имеет на порядок меньшие издержки и дружественность к SMP/multicore, чем все остальные типы очередей. Во-вторых, на основе этой очереди можно построить общее решение. Например, можно сделать полносвязанную систему из потоков, связанную такими очередями, где каждый поток может послать сообщение каждому. Либо можно построить систему, в которой один или несколько потоков выступают в роли посредников-маршрутизаторов, рядовые потоки связаны очередями с этимим посредниками и через них посылают/принимают сообщения от всех остальных потоков. R>>Такая система получается врожденно распределенной и как следствие — масштабируемой. Т.е. конкуренция на никакой очереди не растёт всё больше и больше с ростом числа процессоров/ядер.
HK>Я тоже думал о реализации варианта многие ко многим,а вот идея маршрутизатора интересна. Сейчас думаю над ее реализацией.
Тут палка о двух концах.
В полносвязанной системе получается, что каждому потоку надо опрашивать N-1 очередей, и отправлять в N-1 очередей.
С маршрутизаторами (с одним) получается, что каждому потоку надо опрашивать и отправлять в 1 очередь. Но зато увеличивается латентность доставки, т.к. сообщение должно пройти через 2 очереди. Плюс у маршрутизатора получается достаточно большой объём дополнительной работы. Плюс один дополнительный процессор "трогает" память сообщения, т.е. возрастает нагрузка на шину когерентности кэшей.
Я лично, когда думал над этим вопросом, склонился к полносвязанной системе. По крайней мере, пока число процессоров меньше сотни. Когда число процессоров перевалит за сотню, то опрашивать более сотни очередей становится очень накладно. Но и маршрутизатор имхо тут будет не очень хорошо себя вести. Скорее всего лучше будет некое гибридное решение.
А вот, например, Chris Thomasson (который делает appcore и vZOOM) склоняется к системе с маршрутизаторами. Хотя видимо он думает о NUMA системах, где будет один маршрутизатор на NUMA-узел, который обслуживает только процессоры данного узла. В таком контексте идея с маршрутизаторами звучит более разумно.
А если не секрет, ты чем занимаешься? Каким-то конкретным проектом? Или так, для себя?
Здравствуйте, HaronK, Вы писали:
HK>Переписал реализацию очереди с учетом предложений в топике. HK>Из изменений: HK>1. Убрал флаг. Теперь его роль исполняет указатель на промежуточную цепочку. HK>2. Убрал new/delete. Операции создания и удаления возлагаются на потоки.
HK>Не знаю насколько замена флага на указатель безопасна, но в моих тестах этот код отрабатывал. HK>Барьеры пока не добавлял, поскольку нет единого мнения нужны ли они вообще.
А почему ты не хочешь совсем убрать промежуточную очередь? И возможность "зависания" элементов в очереди?
Он работает по очень интересному принципу — фактически это кэш элементов, разделяемый между 2 потоками. При этом оба потока (производитель и потребитель) не используют никаких дорогих операций — мьютексов, InterlockedXXX, барьеров памяти и т.д.
Операция освобождения элемента сводится к одной записи в память (!)
Операция выделения элемента своидится к нескольким проверкам и нескольким записям в память.
Алокатор тоже можно сделать интрузивным, тогда стоимость добавления/изъятия из очереди практически стремится к нулю
И там же есть пример использования этого аллокатора с mpsc fifo очереди.
remark wrote: > > Здравствуйте, hexis, Вы писали: > > H>Это при привой реализации потоков. При нормальной нет. Я вот не > H>поленился, попробовал простенькую реализацию очередей сделанную из тех > H>же соображений (правда получилось — один читатель, много писателей). > H>Результат — неблокирующая выигрывает процентов на 15-20 (в основном за > H>счет тормозов на InterlockedXXX операциях). И это вполне объяснимо — при > H>взаимодействии 1:1 в указанных условиях можно обойтись без фактических > H>блокировок. Вот код: > > Подожди-подожи. Какие InterlockedXXX, если мы говорим об очереди без > InterlockedXXX?!
Они используются в моей реализации блокирующейся очереди. Все же должно
быть честно.
> Если ты используешь InterlockedXXX, то это естественно по скорости будет > одинакого, т.к. мьютекс == InterlockedXXX.
Так эти мьютексы потенциально блокирующиеся (при неудаче — без spin
зависают на семафоре). Кстати, если заставить реализацию переключать
потоки так, чтобы постоянно появились ожидания (я сделал 1 раз из
десяти), добавив sleep сразу после lock, время работы становится хуже в
два раза. И большего различия мне добиться не удалось.
Использование стандартных win32 mutex/sem, приводит к тому, что
блокирующая очередь работает в пять раз медленнее. Но это совсем не порядки.
Все проверки на однопроцессорной машине.
> > В реализации spin lock сколько операций InterlockedXXX на одну > блокировку/разблокировку?
По необходимости. В лучшем случае — одна. В мьютексе, в лучшем случае —
тоже одна.
> >>> многопроцессорной машине выигрыш будет ещё существеннее + иметь >>> последствия не только на голую скорость, но и на масштабиремость. >>> > > H>С масштабируемостью, ИМХО, совсем не очевидно — реализация-то рассчитана > H>на взаимодействие 1:1. При таких условиях и блокирующие алгоритмы не > H>будут деградировать. > > > Во-первых, на многопроцессорной машине, если у тебя мьютекс без > спин-части, то существенно увеличивается вероятность блокирования.
Это так, согласен. Точнее — больше шансов за то, что потоки будут
проходить по критической секции одновременно, за чем последует
переключение в режим ядра, что и будет основным тормозом — пока
переключился, пока опять квант выделят. В этом плане очень интересно
выглядят реализации потоков в userspace, так, что переключение в режим
ядра происходит буквально по необходимости — я когда-то
экспериментировал с такой реализаций под QNX 4 — прирост
производительности просто колоссальный по сравнению с потоками из ядра.
> Во-вторых, дело не только в увеличении конкуренции за один конкретный > мьютекс, дело так же в увеличении давления на шину когерентности кэшей. >
Есди я правильно тебя понимаю, то эта проблема в большей мере актуальна
для spin lock.
Posted via RSDN NNTP Server 2.1 beta
Re[12]: Неблокируемая очередь сообщений для двух потоков
Здравствуйте, hexis, Вы писали:
>> Подожди-подожи. Какие InterlockedXXX, если мы говорим об очереди без >> InterlockedXXX?!
H>Они используются в моей реализации блокирующейся очереди. Все же должно H>быть честно.
Опять не понятно. В примере на мьютексах, который ты привёл, — очередь не блокирующаяся. Зачем ты тогда делал на Interlocked блокирующуюся?
>> Если ты используешь InterlockedXXX, то это естественно по скорости будет >> одинакого, т.к. мьютекс == InterlockedXXX.
H>Так эти мьютексы потенциально блокирующиеся (при неудаче — без spin H>зависают на семафоре). Кстати, если заставить реализацию переключать H>потоки так, чтобы постоянно появились ожидания (я сделал 1 раз из H>десяти), добавив sleep сразу после lock, время работы становится хуже в H>два раза. И большего различия мне добиться не удалось. H>Использование стандартных win32 mutex/sem, приводит к тому, что H>блокирующая очередь работает в пять раз медленнее. Но это совсем не порядки. H>Все проверки на однопроцессорной машине.
Я и не говорил, что тут будет на порядки. Я говорил:
1. Между мьютексами и Interlocked на многопроцессорной машине будет на порядки
2. Между Interlocked и без Interlocked будет на порядки
>> В реализации spin lock сколько операций InterlockedXXX на одну >> блокировку/разблокировку?
H>По необходимости. В лучшем случае — одна. В мьютексе, в лучшем случае - H>тоже одна.
Ты придумал реализацию не спин мьютекса с одной Interlocked операцией?!
А ты можешь запостить. Насколько я заню, такого в мире ещё нет.
Здравствуйте, hexis, Вы писали:
>>>> многопроцессорной машине выигрыш будет ещё существеннее + иметь >>>> последствия не только на голую скорость, но и на масштабиремость. >>>> >> >> H>С масштабируемостью, ИМХО, совсем не очевидно — реализация-то рассчитана >> H>на взаимодействие 1:1. При таких условиях и блокирующие алгоритмы не >> H>будут деградировать. >> >> >> Во-первых, на многопроцессорной машине, если у тебя мьютекс без >> спин-части, то существенно увеличивается вероятность блокирования.
H>Это так, согласен. Точнее — больше шансов за то, что потоки будут H>проходить по критической секции одновременно, за чем последует H>переключение в режим ядра, что и будет основным тормозом — пока H>переключился, пока опять квант выделят. В этом плане очень интересно H>выглядят реализации потоков в userspace, так, что переключение в режим H>ядра происходит буквально по необходимости — я когда-то H>экспериментировал с такой реализаций под QNX 4 — прирост H>производительности просто колоссальный по сравнению с потоками из ядра.
Да, такие вещи есть. Но они так сказать очень частно применимы Т.е. надо делать обёртки для *всех* блокирующих вызовов. И использовать только их. Любой блокирующий вызов, если он всё таки будет, поломает систему. А если пользователю надо сделать блокирующий вызов из сторонней библиотеки...
Плюс надо оборачивать неблокирующие вызовы, что бы из них сделать видимость блокирующего...
Очень интересная реализация юзер-спейс кооперативного тридинга Capriccio: http://capriccio.cs.berkeley.edu/
Фактически они позволяют применять модель "поток на соединение" и при этом получать производительность евент-дривен систем. Т.е. можно создавать сотни тысяч потоков, и все операции шедулинга выполняются за O(1).
>> Во-вторых, дело не только в увеличении конкуренции за один конкретный >> мьютекс, дело так же в увеличении давления на шину когерентности кэшей. >>
H>Есди я правильно тебя понимаю, то эта проблема в большей мере актуальна H>для spin lock.
Нет, она актуальная для всего, что использует разделяемую память, когда один поток читает то, что записал другой. И особенно при использовании Interlocked операций.
remark wrote: > > Опять не понятно. В примере на мьютексах, который ты привёл, — очередь > не блокирующаяся. Зачем ты тогда делал на Interlocked блокирующуюся?
Не совсем так — можно сказать, она мало блокирующая, по сравнению с
типичной реализацией очередей — из-за своей специализации под конкретную
задачу. (NB: Что на самом деле — не так часто встречается. Возможно, это
и правильно: организовать взаимодействие потоков, без опыта — сложная
штука, и народ часто отскакивает на стандартные реализации, почерпнутые
из интернета)
Тут же в писателе требуется атомарность при выполнении операции "if
(whead != NULL) wtail->next = n;" Поэтому в читателе присвоение "whead =
NULL" и обложено блокировками, как это ни странно выглядит.
> Я и не говорил, что тут будет на порядки. Я говорил: > 1. Между мьютексами и Interlocked на *многопроцессорной* машине будет на > порядки > 2. Между Interlocked и *без* Interlocked будет на порядки
Вообще, разговор начался с того, что я предположил, что различие между
wait-free и блокируюшей реализацией будет минимальным, на что ты ответил:
На однопроцессорной машине она может быть лучше более чем на порядок.
На многопроцессорной машине выигрыш будет ещё существеннее + иметь
последствия не только на голую скорость, но и на масштабиремость.
Многопроцессорной у меня под руками нет, а на однопроцессорной, мой опыт
говорит о другом — что различия в скорости сильно нивелируются
псевдопараллельностью исполнения — в спин блокировках, например,
практически нет смысла — лучше сразу переключить контекст на следующую
задачу. Правда тут есть одна особенность — планировщик винды отдает
предпочтение потокам, добровольно сократившим свой квант, в итоге этот
поток *быстрее* получает управление обратно. А вот на ожидание на
объектах синхронизации, это правило, похоже не распространяется, или это
время нивелируется тем, что обращение к объекту синхронизации для
ожидания, требует переключение в режим ядра. То есть присутствует одно
дополнительное переключение контекста. Хотя, зачем я ТЕБЕ об этом
рассказываю???
> Ты придумал реализацию *не* спин мьютекса с одной Interlocked операцией?! > А ты можешь запостить. Насколько я заню, такого в мире ещё нет.
Думаю, ты просто неправильно меня понял, — я об оптимизации обычного
мьютекса, с отскоком для ожидания в операционку при неудаче. В типичных
ситуациях, когда конкуренция за ресурсы не столь велика, такой подход
позволяет существенно сократить количество обращений к ядру. Но, чтобы
недоразумений больше не возникало — вот текст:
class Mutex
{
public:
Mutex();
~Mutex();
bool try_lock();
void lock();
void unlock();
private:
DWORD owner;
DWORD count;
HANDLE hwait;
volatile LONG avail;
};
Mutex::Mutex()
{
owner = 0;
count = 0;
avail = 1;
hwait = CreateSemaphore(NULL, 0, LONG_MAX, NULL);
}
Mutex::~Mutex()
{
CloseHandle(hwait);
}
bool Mutex::try_lock()
{
DWORD cur = GetCurrentThreadId();
if (owner != cur) {
LONG p = CAS(&avail, 0, -1);
if (p != 0)
return false;
owner = cur;
}
count++;
return true;
}
void Mutex::lock()
{
DWORD cur = GetCurrentThreadId();
if (owner != cur) {
LONG p = InterlockedDecrement(&avail);
if (p < 0) {
WaitForSingleObject(hwait, INFINITE);
}
owner = cur;
}
count++;
}
void Mutex::unlock()
{
if (--count == 0) {
owner = 0;
if (InterlockedIncrement(&avail) < 1) {
ReleaseSemaphore(hwait, 1, NULL);
}
}
}
Posted via RSDN NNTP Server 2.1 beta
Re[15]: Неблокируемая очередь сообщений для двух потоков
Здравствуйте, remark, Вы писали:
R>А если не секрет, ты чем занимаешься? Каким-то конкретным проектом? Или так, для себя?
Если по работе, то мы делаем систему статистического анализа для немцев.
А задача с очередью возникла из игрового проекта, что мы делаем с друзьями. Наверное можно было использовать и обычные очереди с блокировками, только хотелось сделать, что-то свое, красивое.
Re[16]: Неблокируемая очередь сообщений для двух потоков
Здравствуйте, HaronK, Вы писали:
HK>Здравствуйте, remark, Вы писали:
R>>А если не секрет, ты чем занимаешься? Каким-то конкретным проектом? Или так, для себя?
HK>Если по работе, то мы делаем систему статистического анализа для немцев. HK>А задача с очередью возникла из игрового проекта, что мы делаем с друзьями. Наверное можно было использовать и обычные очереди с блокировками, только хотелось сделать, что-то свое, красивое.
Ок. Понятно.
Может тогда тебе будет интересно: Multi-Threaded Challenges in the Game Space — a Conversation with Tom Leonard of Valve Fame
Tom Leonard раскрывает секреты, что в Valve's Source Engine они экстенсивно используют lock-free технологии для построения моделей мира, шедулера и т.д. Это, так сказать, их ставка и конкурентное приемущество в multicore будущем.
(и вообще сайт интересный — много статей и интервью)
Здравствуйте, hexis, Вы писали:
H>remark wrote: >> >> Опять не понятно. В примере на мьютексах, который ты привёл, — очередь >> не блокирующаяся. Зачем ты тогда делал на Interlocked блокирующуюся?
H>Не совсем так — можно сказать, она мало блокирующая, по сравнению с H>типичной реализацией очередей — из-за своей специализации под конкретную H>задачу. (NB: Что на самом деле — не так часто встречается. Возможно, это H>и правильно: организовать взаимодействие потоков, без опыта — сложная H>штука, и народ часто отскакивает на стандартные реализации, почерпнутые H>из интернета)
H>Тут же в писателе требуется атомарность при выполнении операции "if H>(whead != NULL) wtail->next = n;" Поэтому в читателе присвоение "whead = H>NULL" и обложено блокировками, как это ни странно выглядит.
Под блокирующей я имел в виду, что надо блокироваться, когда вызывается dequeue(), но очередь пуста.
Я запутался. Если блокироваться на dequeue() не надо, то зачем в тесте lock-free очереди, ты использовал Interlocked инструкции? Ведь вот же у тебя есть реализация очереди, в которой нет Interlocked.
>> Я и не говорил, что тут будет на порядки. Я говорил: >> 1. Между мьютексами и Interlocked на *многопроцессорной* машине будет на >> порядки >> 2. Между Interlocked и *без* Interlocked будет на порядки
H>Вообще, разговор начался с того, что я предположил, что различие между H>wait-free и блокируюшей реализацией будет минимальным, на что ты ответил:
H>
На однопроцессорной машине она может быть лучше более чем на порядок.
H>На многопроцессорной машине выигрыш будет ещё существеннее + иметь
H>последствия не только на голую скорость, но и на масштабиремость.
Ну так я имел в виду вот ту очередь, которую ты запостил в первом посте. А ты говоришь, что ты тестировал какую-то другую очередь, в которой всё таки были Interlocked инструкции.
H>Многопроцессорной у меня под руками нет, а на однопроцессорной, мой опыт H>говорит о другом — что различия в скорости сильно нивелируются H>псевдопараллельностью исполнения — в спин блокировках, например, H>практически нет смысла — лучше сразу переключить контекст на следующую H>задачу. Правда тут есть одна особенность — планировщик винды отдает H>предпочтение потокам, добровольно сократившим свой квант, в итоге этот H>поток *быстрее* получает управление обратно. А вот на ожидание на H>объектах синхронизации, это правило, похоже не распространяется, или это H>время нивелируется тем, что обращение к объекту синхронизации для H>ожидания, требует переключение в режим ядра. То есть присутствует одно H>дополнительное переключение контекста. Хотя, зачем я ТЕБЕ об этом H>рассказываю???
>> Ты придумал реализацию *не* спин мьютекса с одной Interlocked операцией?! >> А ты можешь запостить. Насколько я заню, такого в мире ещё нет.
H>Думаю, ты просто неправильно меня понял, — я об оптимизации обычного H>мьютекса, с отскоком для ожидания в операционку при неудаче. В типичных H>ситуациях, когда конкуренция за ресурсы не столь велика, такой подход H>позволяет существенно сократить количество обращений к ядру. Но, чтобы H>недоразумений больше не возникало — вот текст:
Тут на lock()/unlock() приходится 2 Interlocked операции (CAS в lock() и InterlockedIncrement в unlock()).
Понятно, это стандартный мьютекс.
remark wrote: > > H>remark wrote: >>> >>> Опять не понятно. В примере на мьютексах, который ты привёл, — очередь >>> не блокирующаяся. Зачем ты тогда делал на Interlocked блокирующуюся? > > H>Не совсем так — можно сказать, она мало блокирующая, по сравнению с > H>типичной реализацией очередей — из-за своей специализации под конкретную > H>задачу. (NB: Что на самом деле — не так часто встречается. Возможно, это > H>и правильно: организовать взаимодействие потоков, без опыта — сложная > H>штука, и народ часто отскакивает на стандартные реализации, почерпнутые > H>из интернета) > > H>Тут же в писателе требуется атомарность при выполнении операции "if > H>(whead != NULL) wtail->next = n;" Поэтому в читателе присвоение "whead = > H>NULL" и обложено блокировками, как это ни странно выглядит. > > > Под блокирующей я имел в виду, что надо блокироваться, когда вызывается > dequeue(), но очередь пуста.
Так я исходил из исходной постановки задачи: взаимодействие 1:1,
читающая сторона не блокируется при отсутствии сообщения. Получилось
чуть больше (1:*) — но, как получилось. А сравнивать две принципиально
разные задачи — нет смысла.
> Я запутался. Если блокироваться на dequeue() не надо, то зачем в тесте > lock-free очереди, ты использовал Interlocked инструкции? Ведь вот же у > тебя есть реализация очереди, в которой нет Interlocked.
Да, похоже, мы малость запутались. Сначала было мое мнение, что при
нормальной реализации потоков (то-есть примитивов синхронизации) не
будет принципиальных различий в скорости между реализацией этой задаче в
стиле lock-free и lock-based. Меня смутило твое возражение относительно
однопроцессных машин и я решил проверить — так ли это. Для этого я и
написал простую очередь, использующую mutex и, после того, поигрался с
различными вариантами реализации mutex — страндартный win32 mutex,
CRITICAL_SECTION, spin lock и тот, что запостил в прошлый раз — отсюда и
появились InterlockedXXX. Сама реализация очереди при этом не менялась.
С другой стороны, если ты говоришь о dequeue()-блокирующей очереди, то
там вступают в силу совсем другие соображения и будет совсем другая
реализация.
> > Тут на lock()/unlock() приходится 2 Interlocked операции (CAS в lock() и > InterlockedIncrement в unlock()). > Понятно, это стандартный мьютекс. >
Теперь понятно, что ты имел в виду. Что сделаешь — я редко занимаюсь
этим, и не всегда понимаю терминологию. Если конкуренция не очень
высока, можно предположить такой, достаточно очевидный вариант (fair,
время разблокирования пропорционально кол-ву ожидающих потоков):
H>Да, похоже, мы малость запутались. Сначала было мое мнение, что при H>нормальной реализации потоков (то-есть примитивов синхронизации) не H>будет принципиальных различий в скорости между реализацией этой задаче в H>стиле lock-free и lock-based. Меня смутило твое возражение относительно H>однопроцессных машин и я решил проверить — так ли это. Для этого я и H>написал простую очередь, использующую mutex и, после того, поигрался с H>различными вариантами реализации mutex — страндартный win32 mutex, H>CRITICAL_SECTION, spin lock и тот, что запостил в прошлый раз — отсюда и H>появились InterlockedXXX. Сама реализация очереди при этом не менялась.
Хорошо. Т.е. ты сравнивал реализацию очереди, которую запостил в первом посте, с очередью, построенной на мьютексе (на различных реализациях). Я правильно понял?
И что, разница была всего 15%?
Сейчас займусь ясновидением: ты либо тестировал на Win2k, либо у тебя процессор AMD, либо и то и то?
hexis wrote: > > Если конкуренция не очень > высока, можно предположить такой, достаточно очевидный вариант (fair, > время разблокирования пропорционально кол-ву ожидающих потоков):
При unlock() можно связывать список обратно — в этом случае среднее
время на операцию разблокирования будет O(1), а не O(n) — за счет того,
что одна нитка будет готовить данные для других — то есть время
разблокирования будет различным. Семафоры для ожидания можно сделать
общими — один на мьютекс, но очередь все равно нужна.
Вот текст с обратным связыванием списка:
class Mutex
{
public:
Mutex();
~Mutex() {}
void lock();
bool try_lock();
void unlock();
static void attach_thread();
private:
struct mqitem
{
volatile struct mqitem * next;
struct mqitem * prior;
HANDLE hwait;
} e, * tail;
#ifdef RECURSIVE_MUTEX
volatile DWORD owner;
DWORD count;
#endif
static _declspec(thread) mqitem * thread_item;
};
_declspec(thread) Mutex::mqitem * Mutex::thread_item = NULL;
void Mutex::attach_thread()
{
if (thread_item == NULL) {
thread_item = new mqitem;
thread_item->hwait = CreateSemaphore(NULL, 0, LONG_MAX, NULL);
}
}
Mutex::Mutex()
{
e.next = NULL;
tail = NULL;
#ifdef RECURSIVE_MUTEX
owner = 0;
count = 0;
#endif
}
void Mutex::lock()
{
mqitem * p, * h;
DWORD cur = GetCurrentThreadId();
#ifdef RECURSIVE_MUTEX
if (owner != cur) {
#endif
assert( thread_item != NULL );
p = thread_item;
p->prior = NULL;
do {
h = (mqitem *)e.next;
p->next = h;
} while( _CAS_PTR((PVOID*)&e.next, (PVOID)h, (PVOID)p) != h );
if (h != NULL)
WaitForSingleObject(thread_item->hwait, INFINITE);
#ifdef RECURSIVE_MUTEX
#ifdef _DEBUG
assert(CAS(&owner, (DWORD)NULL, cur) == NULL);
#else
owner = cur;
#endif
}
count++;
#endif
}
bool Mutex::try_lock()
{
mqitem * p;
DWORD cur = GetCurrentThreadId();
#ifdef RECURSIVE_MUTEX
if (owner != cur) {
#endif
assert( thread_item != NULL );
if (e.next != NULL)
return false;
p = thread_item;
p->next = NULL;
if ( _CAS_PTR((PVOID*)&e.next, (PVOID)NULL, (PVOID)p) != NULL )
return false;
#ifdef RECURSIVE_MUTEX
#ifdef _DEBUG
assert(CAS(&owner, (DWORD)NULL, cur) == NULL);
#else
owner = cur;
#endif
}
count++;
#endif
return true;
}
void Mutex::unlock()
{
mqitem * o = thread_item;
mqitem * p = &e;
#ifdef RECURSIVE_MUTEX
assert(owner == GetCurrentThreadId());
if (--count == 0) {
#endif/* we know the tail sometimes */if (tail != &e) {
p = tail;
tail = p->prior;
} else {
/* scan the list to find the tail and update
* the list inverse. Anyway, if the unlock() time
* is sensetive, do not use in highly concurrent
* conditions
*/while(p->next != o) {
p->next->prior = p;
p = (mqitem *)p->next;
}
tail = p->prior;
}
#ifdef RECURSIVE_MUTEX
owner = NULL;
#endif
if (p != &e)
ReleaseSemaphore(p->hwait, 1, NULL);
p->next = NULL;
#ifdef RECURSIVE_MUTEX
}
#endif
}
Posted via RSDN NNTP Server 2.1 beta
Re[16]: Неблокируемая очередь сообщений для двух потоков
H>Теперь понятно, что ты имел в виду. Что сделаешь — я редко занимаюсь H>этим, и не всегда понимаю терминологию.
Обычно спин-мьютекс это очередь, которая основана на периодическом опросе. Есть спин с активным ожиданием, это когда простой цикл, и есть спин с пассивным ожиданием, это когда sleep(0). Но тем не менее это всё спин, т.к. оба варианта периодически опрашивают состояние, что бы понять когда им действовать.
Не-спин мьютекс, основывается не на опросе, а на чётком взимодействии между двумя потоками. Ожидающий просто блокируется в ядро, а тот, кто сейчас в мьютексе, при выходе должен нотифицировать первого. При этом тот, кто сейчас в мьютексе, должен 100-процентно определить, есть ли кто-то ожидающий или нет. Вот тут и начинаются проблемы. Тут начинается такая же гонка как и при попытке захватить мьютекс двумя потоками почти одновременно — им надо чётко решить, кто же из них первый, а кто будет ждать. Приянть такое чёткое и 100-процентно консистентное решение и позволяет InterlockedXXX. При выходе начинается такая же гонка, только между потоком выходящим из мьютекса и потоком входящим в мьютекс. Они должны чётко решить — либо (1) выход произошёл раньше, тогда второй может входить без ожидания, и первому не надо нотифицировать, либо (2) вход произошёл раньше, тогда первый должен нотифицировать второго, а второй блокироваться в ядре. Если при разблокировке мьютекса нет InterlockedXXX, то чётко и консистентно решить этот вопрос 2 потока не могут. Есть вероятность, что один поток примет решение (1), а второй (2), или наоборот. Если бы это можно было разрешить без InterlockedXXX, то аналогичную ситуацию можно было бы разрешить и при входе в мьютекс. Т.е. можно было бы сделать мьютекс вообще без InterlockedXXX. Что естественно не соотв. действительности.
H> Если конкуренция не очень H>высока, можно предположить такой, достаточно очевидный вариант (fair, H>время разблокирования пропорционально кол-ву ожидающих потоков):
К сожалению, это *почти* работающий вариант...
Тут есть гонка между выходящим потоком и одновременно входящим потоком. Т.е. выходящий поток может решить, что ещё никакой поток не пытался войти, т.е. ему не надо нотифицировать семафор, и в то же время одновременно входящий поток может решить, что мьютекс ещё занят и заблокироваться на семафоре. Как результат он "повиснет" на неопределённое время...
з.ы. вот это можно cоптимизировать:
/* we'd better not to have high concurrency on this mutex */while(p->next != o)
p = p->next;
В lock-free алгоритмах есть такой трюк как "prev hint". Линк next является как бы основным, а линк prev вспомогательным. При этом prev не обязан быть 100% правильным, но он является правильным в большинстве случаев. Это позволяет в большинстве случаев и использовать prev, а если он всё таки не правильный, то иметь какой-то запасной вариант. Вот пример модификации. За 100% не ручаюсь, но идея такая:
void Mutex::lock()
{
mqitem* p = thread_item;
mqitem* h;
do
{
h = (mqitem *)e.next;
p->next = h;
} while( _CAS_PTR((PVOID*)&e.next, (PVOID)h, (PVOID)p) != h );
if (p->next)
p->next->prev = p;
if (h != NULL)
WaitForSingleObject(thread_item->hwait, INFINITE);
}
void Mutex::unlock()
{
mqitem * o = thread_item;
volatile mqitem * p = queue;
if (o->prev->next == o)
{
// we're lucky
p = o->prev;
}
else
{
// back-offwhile(p->next != o)
p = p->next;
}if (p != &e)
ReleaseSemaphore(p->hwait, 1, NULL);
p->next = NULL;
}
remark wrote: > > > Здравствуйте, hexis, Вы писали: > > > H>Да, похоже, мы малость запутались. Сначала было мое мнение, что при > H>нормальной реализации потоков (то-есть примитивов синхронизации) не > H>будет принципиальных различий в скорости между реализацией этой задаче в > H>стиле lock-free и lock-based. Меня смутило твое возражение относительно > H>однопроцессных машин и я решил проверить — так ли это. Для этого я и > H>написал простую очередь, использующую mutex и, после того, поигрался с > H>различными вариантами реализации mutex — страндартный win32 mutex, > H>CRITICAL_SECTION, spin lock и тот, что запостил в прошлый раз — отсюда и > H>появились InterlockedXXX. Сама реализация очереди при этом не менялась. > > > Хорошо. Т.е. ты сравнивал реализацию очереди, которую запостил в первом > посте, с очередью, построенной на мьютексе (на различных реализациях). Я > правильно понял? > И что, разница была всего 15%? > Сейчас займусь ясновидением: ты либо тестировал на Win2k, либо у тебя > процессор AMD, либо и то и то? >
XP. Проц AMD. Что-то у них с lock? Я правда использовал cmpxchg без него
— потому, что для однопроцессорной машины он смысла не имеет. А 15% —
это в основном алгоритмическая разница — при этом обращений к ядру
практически не происходило. Можно сказать, что при этом реализация
работала в режиме lock-free. Не думаю, что другая операционка или проц
смогли бы замедлить это время, по отношению к любой другой lock-free
реализации. Худшее время, когда блокировки происходят постоянно, я тоже
написал — разница в два раза — тут я могу поверить во влияние проца и
операционки.
Posted via RSDN NNTP Server 2.1 beta
Re[17]: Неблокируемая очередь сообщений для двух потоков
Здравствуйте, hexis, Вы писали:
H>hexis wrote: >> >> Если конкуренция не очень >> высока, можно предположить такой, достаточно очевидный вариант (fair, >> время разблокирования пропорционально кол-ву ожидающих потоков):
H>При unlock() можно связывать список обратно — в этом случае среднее H>время на операцию разблокирования будет O(1), а не O(n) — за счет того, H>что одна нитка будет готовить данные для других — то есть время H>разблокирования будет различным. Семафоры для ожидания можно сделать H>общими — один на мьютекс, но очередь все равно нужна.
Да, такой трюк можно применить. Можно совместить его с prev hint, который я запостил в соседнем посте.
Но основную проблему это не решает — решение не рабочее...
