Pull to refresh

Comments 37

А где собственно lock-free очередь? Без неё пост явно не полный, и не даёт ответа на воспрос — на сколько lock-free очередь быстрее обычной (не lock free).
В таком случае — правильно ли я понимаю что разницы практически нет (и там и там около 400нс если слушать в бесконечном цикле без слипов)?
Да, именно так и получается, можно сказать основной вывод в этом и состоит.
А почему вы думаете, что lock-free очередь должна быть быстрее? Есть ситуации когда lock-free алгоритмы могут себя вести куда менее эффективно. Синтетика тут может показать совершенно иные результаты, нежели будет в реальной жизни.
Обычно lock-free алгоритмы используют с целью улучшения производительности. Или же есть какой-то другой смысл в их использовании?
UFO landed and left these words here
Нет, что вы, не-lock-free вовсе не означает deadlock. В общем случае термин lock-free означает что вставка/удаление из очереди происходят без использования мьютексов или других средств синхронизации. В идеале, wait-free algorithms, происходят за конечное число инструкций.
Всем рекомендую почитать вот эту блестящую серию постов.
UFO landed and left these words here
пожалуйста, вот псевдокод (я игнорирую для наглядности инициализацию и случаи пустой очереди, кроме того он страдает известной ABA проблемой):
struct node { node* next; };

struct queue
{
    node *head, *tail;

// это пример wait-free алгоритма, операция завершается 
//    за известное заранее число инструкций
    void put(node* n) {
        n->next=0;
        atomic_swap(tail, n);
        if(n) n->next=tail;
    }

// это lock-free, но не wait-free алгоритм,
//   мы крутимся в цикле пока операция не пройдет успешно
    node* get() {
        for(;;) {
            node *n=head;
            if(atomic_compare_and_swap(head, n, n->next))
                return n;
        }
    }
};

В общем случае используются атомарные операции, конкретно atomic_swap(a,b) — атомарно обменивает местами значения аргументов, и atomic_compare_and_swap(target, compare, new_value) — атомарно проверяет что target == compare и, если да, присваивает target=new_value, возвращает bool = успех операции.
UFO landed and left these words here
Я извиняюсь, не понял сразу вопроса.
Не-lock-free алгоритм по определению использует блокирующие операции, но не входит в состояние deadlock, не путайте lock и deadlock.
UFO landed and left these words here
я рассматриваю spinlock просто как один из вариантов блокировки, вы же сами написали:
Spin locks and other algorithms with busy-wait loops are not lock-free
UFO landed and left these words here
wiki
Без блокировок (англ. lock-free)
Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
UFO landed and left these words here
Как вы себе это представляете? dead-lock-и возникают в именно что сложных ситуациях — нельзя просто так взять и заменить mutex-ы в существующих сложных объектах на некий lock-free алгоритм. lock-free структуры поставляются именно в виде готовых к употреблению структур. Это то-же самое, что и отказаться от mutex-ов в пользу оберток над структурами, защищающими все операции над этими структурами mutex-ом — но в таких случаях логика простая, и dead-lock-ов не возникает.
Давайте все-таки уточним: deadlock не возникает сам по себе, его создаем мы сами тем что криво пишем алгоритм.
Правильно написанный алгоритм никогда не испытывает deadlock, и симметрично, lock-free алгоритм не является средством deadlock избежать.
UFO landed and left these words here
Если код разросся до такого состояния, что существует куча логики с использованием блокировок в непонятных ситуациях, тогда lock-free алгоритмы точно не помогут такому коду, т.к. эти алгоритмы в разы сложнее алгоритмов с блокировками.
Я бы рекомендовал придерживаться нескольких правил, чтобы избежать взаимных блокировок:
1) мьютекс должен блокировать доступ к данным, а не код (если это возможно)
2) никогда не вызывайте внешний код из под блокировки (коллбеки и т.п.)
3) в идеале lock/unlock должны происходить в одной функции (RAII)
Да, обычно, но дело в том, что сами по себе lock-free алгоритмы при слишком высокой нагрузке могут стать менее эффективны. Из-за слишком частых холостых проходов. И если в синтетике нагрузить с большой кучи физических ядер, то просесть может очень сильно. В итоге смотреть есть смысл только уже в конкретных решениях.
Из-за слишком частых холостых проходов.
Это не особо актуально для очередей с одним входом и одним выходом.
Да, да, все локальные для данного потока переменные размещаются в thread local storage и никакими силами нельзя заставить другой поток увидеть их адрес.

Для этого используются ключевые слова shared (разрешён только синхронный совместный доступ) и __gshared (как в C++, делай что хочешь).

Если залезть под капот (разумеется я не мог не заглянуть), увидим что код совершенно обычный — односвязные списки защищенные мьютексами.
Там ещё и сообщения полиморфные, то есть можно послать что угодно кому угодно, а тому придётся разгребать. Лучше всего для обмена сообщениями между потоками подходят каналы, как в go. Вот моя реализация неблокирующих каналов на D. Там, правда, используется экспоненциальное засыпание, а не блокирующая переменная, и не хватает мультиплексирования волокон, которые позволяют вместо засыпания, заняться потоку чем-то полезным.
Все правильно, только пост все таки не о коде, а о сравнении быстродействия стандартных механизмов, в том числе в D.
Ну так сравните в том числе и с неблокирующей реализацией на D:

import std.stdio, std.datetime, jin.go;

struct Tick { long start; }
struct Ask {}

enum N = 1000000;

void main() {

	auto ticks = new Queue!Tick;
	auto asks = new Queue!Ask;

	start!f( ticks , asks );

	foreach( i ; 0 .. N ) {
		ticks.push!Tick( MonoTime.currTime.ticks );
		asks.take;
	}
}

void f( Queue!Tick ticks , Queue!Ask asks ) {
	foreach( i ; 0 .. N ) {
		auto m  = ticks.take.start;
		writeln( MonoTime.currTime.ticks - m );
		asks.push!Ask();
	}
}


Кроме того, на сколько я понял, вы собирали дебажные версии, а не релизные, что даёт свой вклад.

сравнил)
У вас похоже где-то засыпание происходит, если вы не против, я в коде поковыряюсь немного.
Ну да, я же написал, что экспоненциальное засыпание :-) Думаю если добавиь перед засыпанием спинлок, то это сильно ускорит в этом тесте. А реализация на файберах (в один поток) думаю вообще всех уделает. Буду рад, если покопаетесь :-)
И вообщем-то мы приходим к тому, что lock-free имеет смысл только во всяких системах с какими-то нереально-огромными потоками данных, ну типа магистральных роутеров или чего-то такого. В обычной программе, обрабатывающей какие-то смешные миллиарды сообщений в день — эти изыски не будут иметь особого влияния в виду экономии пары секунд процессорного времени за сутки.
Можно узнать ваше мнение о nanomsg? Он решает схожие задачи и насколько успешно?
Честно скажу, про nanomsg от вас услышал, но я тут почитал немножко.
Вообще говоря, это библиотека другого уровня и главная ее цель — общий интерфейс для семейства различных протоколов. А насчет быстродействия, интуиция мне подсказывает что должно быть порядка 100 мкс, по крайней мере это та цель к которой я бы стремился. Я кстати когда-то мерил ZeroMQ, давно уже, цифр не помню, но помню что подтормаживало сильно, был разочарован.
А как достигается разрешение радикально выше 100 нс при измерении? ЕМНИП, HPET работает на 14 или 18 МГц и разрешения выше 55нс получить проблематично без использования левых таймеров. Мне, например, на .NET/Win32 интервал менее 300нс стандартными средствами не удалось замерять.
на моей машине:

iBolit# cat /sys/devices/system/clocksource/clocksource0/available_clocksource 
tsc hpet acpi_pm 
iBolit# cat /sys/devices/system/clocksource/clocksource0/current_clocksource
tsc

и разрешение TSC у меня как раз равно 1нс, TSC как правило сильно выигрывает у HPET. Конечно остается проблема точности вызова самой функции, но я это тоже мерил (в статью не вошло за недостатком места) и оцениваю точность измерения в 20 нс.
Ну я последовал рекомендации на MSDN: "We strongly discourage using the RDTSC or RDTSCP processor instruction to directly query the TSC because you won't get reliable results on some versions of Windows, across live migrations of virtual machines, and on hardware systems without invariant or tightly synchronized TSCs."
И кстати на Linux машинах тоже не использовал его, т.к. при graceful синхронизации по ntp только hpet нормальные timestamp давал в момент "движения" времени.
Ну у меня же измеряются короткие интервалы для которых дрейф TSC несущественен, а абсолютное время и ntp вообще не нужны.
Ну у меня интервалы не более 60 микросекунд в общем, просто метка путешествует через 3 процесса. Вобщем как я и думал, в D вопрос кросс-процессорного профилирования тоже нормально не решен. Ну как и нигде вобщем.
Only those users with full accounts are able to leave comments. Log in, please.