Комментарии 21
Ваша статья — это перевод или пересказ той статьи, на которую вы дали ссылку?
Более того, парни из memsql сами же её и перевели и писали на хабр: habrahabr.ru/post/174369 Ваша статья абсолютно идентична по смыслу с ней.
В третьих, в коде у парней я нашёл минимум одну ошибку в реализации lock-free (указатель на next_node зачем-то атомарный) и ещё пару непоняток в коде. Ещё после той статьи им отписал, не знаю, исправили или нет.
Более того, парни из memsql сами же её и перевели и писали на хабр: habrahabr.ru/post/174369 Ваша статья абсолютно идентична по смыслу с ней.
В третьих, в коде у парней я нашёл минимум одну ошибку в реализации lock-free (указатель на next_node зачем-то атомарный) и ещё пару непоняток в коде. Ещё после той статьи им отписал, не знаю, исправили или нет.
Немного расмышлений на тему:
1. Чтобы два потока могли одновременно работать с одной структурой без всяких локов cas-ов и прочего непотребства, то вносимые ими изменения не должны пересекаться вообще. Грубо говоря, у структуры должно быть по отдельной точке редактирования на каждый поток.
2. Простейшая структура имеющая 2 независимые точки изменения — очередь. Один поток пишет данные в хвост, второй срезает их с макушки. Единственное условие их непересечения — в очереди всегда должен быть как минимум один элемент — этого легко добиться.
3. Стек имеет лишь одну точку редактирования — вершину стека. Соответственно с ним может беспроблемно работать лишь один поток. Поэтому назначаем один поток арбитром, который единолично управляет стеком, а общение с остальными потоками организуем через очереди (2).
4. Очередь со множеством писателей реализуется, через множество очередей с одни писателем в каждой. Читатель при этом по разным стратегиям может выбирать сообщения из этих очередей.
5. Очередь со множеством читателей организуется аналогично стеку (3) через отдельный поток-балансировщик — он срезает сообщение с макушки общей очереди и добавляет в хвост очереди подходящего читателя.
Какие тут могут быть подводные камни? Есть некоторое пенальти на перекладывание между очередями, но оно хорошо масштабируется, в отличие от крутящихся в бесконечном цикле CAS или попыток взять блокировку.
1. Чтобы два потока могли одновременно работать с одной структурой без всяких локов cas-ов и прочего непотребства, то вносимые ими изменения не должны пересекаться вообще. Грубо говоря, у структуры должно быть по отдельной точке редактирования на каждый поток.
2. Простейшая структура имеющая 2 независимые точки изменения — очередь. Один поток пишет данные в хвост, второй срезает их с макушки. Единственное условие их непересечения — в очереди всегда должен быть как минимум один элемент — этого легко добиться.
3. Стек имеет лишь одну точку редактирования — вершину стека. Соответственно с ним может беспроблемно работать лишь один поток. Поэтому назначаем один поток арбитром, который единолично управляет стеком, а общение с остальными потоками организуем через очереди (2).
4. Очередь со множеством писателей реализуется, через множество очередей с одни писателем в каждой. Читатель при этом по разным стратегиям может выбирать сообщения из этих очередей.
5. Очередь со множеством читателей организуется аналогично стеку (3) через отдельный поток-балансировщик — он срезает сообщение с макушки общей очереди и добавляет в хвост очереди подходящего читателя.
Какие тут могут быть подводные камни? Есть некоторое пенальти на перекладывание между очередями, но оно хорошо масштабируется, в отличие от крутящихся в бесконечном цикле CAS или попыток взять блокировку.
А вы, батенька, оптимист =)
В любой структуре данных, даже в очереди, бывают следующие случаи:
1) несколько потоков пишут или читают в/из очереди одновременно (это уже не входит в вашу концепцию)
2) очередь содержит 0 или 1 элемент, в данном случае при чтении/записи доступ идёт к одному и тому же элементу: head == tail
все эти случаи тоже нуждаются в грамотной обработке. Это возможно только с помощью локов, или тех же самых атомарных доступов.
Ну и плюс ваш подход съедает нехилое количество инструкций только на арбитраж.
В любой структуре данных, даже в очереди, бывают следующие случаи:
1) несколько потоков пишут или читают в/из очереди одновременно (это уже не входит в вашу концепцию)
2) очередь содержит 0 или 1 элемент, в данном случае при чтении/записи доступ идёт к одному и тому же элементу: head == tail
все эти случаи тоже нуждаются в грамотной обработке. Это возможно только с помощью локов, или тех же самых атомарных доступов.
Ну и плюс ваш подход съедает нехилое количество инструкций только на арбитраж.
Читайте внимательнее
1) Очередь изначально поддерживает только 2 потока: 1 читатель и 1 писатель. Как сделать много писателей автор описал в п.4
2) Обеспечить наличие фейкового элемента в очереди думаю не очень сложно
Насчет технических деталей не знаю не реализовывал, но концепция выглядит довольно стройной.
1) Очередь изначально поддерживает только 2 потока: 1 читатель и 1 писатель. Как сделать много писателей автор описал в п.4
2) Обеспечить наличие фейкового элемента в очереди думаю не очень сложно
Насчет технических деталей не знаю не реализовывал, но концепция выглядит довольно стройной.
Прошу прощения, действительно проблема 1 неактуальна. Но остаётся всё же 2 и 3. Оверхед на поддержку очередей с лихвой перекроет любой возможный прирост быстродействия. Не представляю, как вы собираетесь решать проблему пустой очереди с помощью фейкового элемента.
Очень просто, пишущий поток завершает серию сообщений пустым сообщением, а читающий игнорирует пустые сообщения и никогда не удаляет последнее. Пример кода: https://gist.github.com/nin-jin/111f32935da5c758a1c8 правда тут используется сборщик мусора и передаются только строки.
Насчёт быстродействия надо тестировать, но реализация, как можно заметить довольно тривиальная.
Насчёт быстродействия надо тестировать, но реализация, как можно заметить довольно тривиальная.
Я тут запилил реализацию по лучше: https://github.com/nin-jin/go.d
Вместо односвязного списка c пустыми в перемешку с нормальными сообщениями, тут буфер фиксированного размера и пара указателей — на голову и хвост. Читающий поток перемещает голову, пишущий — хвост. При этом гарантируется, что хвост никогда не обгонит голову. Если буфер переполнен, то пишущий поток блокируется, если буфер пустой, то блокируется читающий.
Правда пока без статической типизации каналов — сообщения сейчас можно передавать любого типа.
В сравнении со стандартной реализацией на мьютексах (https://github.com/D-Programming-Language/phobos/blob/master/std/concurrency.d) получается в ~4.5 раза быстрее при двух писателях и одном читателе и в ~8 раз при 100 писателях и одно читателе. Насчёт нескольких читателей — ещё не реализовал :-)
Вместо односвязного списка c пустыми в перемешку с нормальными сообщениями, тут буфер фиксированного размера и пара указателей — на голову и хвост. Читающий поток перемещает голову, пишущий — хвост. При этом гарантируется, что хвост никогда не обгонит голову. Если буфер переполнен, то пишущий поток блокируется, если буфер пустой, то блокируется читающий.
Правда пока без статической типизации каналов — сообщения сейчас можно передавать любого типа.
В сравнении со стандартной реализацией на мьютексах (https://github.com/D-Programming-Language/phobos/blob/master/std/concurrency.d) получается в ~4.5 раза быстрее при двух писателях и одном читателе и в ~8 раз при 100 писателях и одно читателе. Насчёт нескольких читателей — ещё не реализовал :-)
А это получается не то же самое, что и модель акторов?
Эксперименты пока показывают следующие результаты по очередям с несколькими читателями:
1. Через балансировщик всё равно получается медленней. Пока не разобрался можно ли сделать сравнимо по скорости со мьютексами.
2. Если один из читателей затупил на одном из сообщений, то следующие в его очереди будут ждать пока он отвиснет, вместо того, чтобы быть обработанными другим читателем. Решить это можно путём уменьшения размера очереди читателя до 1, но тогда закончив с одним сообщением ему придётся засыпать в ожидании балансировщика, вместо того, чтобы взяться за следующее.
3. Тем не менее, когда нужно просто посылать сообщения между потоками, то решение без блокировок показывает до 10 крат преимущество по скорости (https://github.com/nin-jin/go.d).
1. Через балансировщик всё равно получается медленней. Пока не разобрался можно ли сделать сравнимо по скорости со мьютексами.
2. Если один из читателей затупил на одном из сообщений, то следующие в его очереди будут ждать пока он отвиснет, вместо того, чтобы быть обработанными другим читателем. Решить это можно путём уменьшения размера очереди читателя до 1, но тогда закончив с одним сообщением ему придётся засыпать в ожидании балансировщика, вместо того, чтобы взяться за следующее.
3. Тем не менее, когда нужно просто посылать сообщения между потоками, то решение без блокировок показывает до 10 крат преимущество по скорости (https://github.com/nin-jin/go.d).
Очень прошу прощения, но «безлоковый» сначала прочитал как «бестолковый». Прочитав «Холивар на тему бестолковых алгоритмов», понял что что-то пошло не так…
А RCU подойдет для решения этой же проблемы?
Когда-то также интересовался этой темой. Даже написал свою реализацию lock-free очереди (GitHub, StackExchange).
Идея там простая: есть 2 потока, один пишет в очередь, другой из нее читает. Внутри очереди есть 2 подочереди — одна для писателя, другая для читателя. Когда читатель вычитывает свою подочередь, он забирает подочередь писателя, а писатель начинает новую.
В базовам варианте (один читатель, один писатель) для синхронизации используется единственная atomic переменная.
Для продакшина нужна будет дополнительная обработка, но идея, я думаю, должна быть работоспособной.
Идея там простая: есть 2 потока, один пишет в очередь, другой из нее читает. Внутри очереди есть 2 подочереди — одна для писателя, другая для читателя. Когда читатель вычитывает свою подочередь, он забирает подочередь писателя, а писатель начинает новую.
В базовам варианте (один читатель, один писатель) для синхронизации используется единственная atomic переменная.
Для продакшина нужна будет дополнительная обработка, но идея, я думаю, должна быть работоспособной.
Кажется кто-то пишет научную работу.
malloc/free должно быть тоже lock-free. Но стандартные malloc/free такими не являются. Более того, такой вызов — это же уход в kernel space, и он не может быть быстрым. То есть, кардинально повысить производительность не выйдет, потому что значительную часть сьест malloc. Но выход есть. Тут должен быть специальный lock-free malloc.
Конечно, это все на уровне догадок. Реально чтоб сравнить, надо мерять как оно будет в конкретных числах.
Конечно, это все на уровне догадок. Реально чтоб сравнить, надо мерять как оно будет в конкретных числах.
Реальные конкретные числа, замеры, указаны в конце статьи =)
Озвученный в статье подход даёт почти 30% прироста в сравнении с чистым lock-free или чистым спинлоком.
Озвученный в статье подход даёт почти 30% прироста в сравнении с чистым lock-free или чистым спинлоком.
Ну это понятно. Тут интересней, сколько процентов времени сжирается внутри malloc.
Я тут еще подумал. Ведь стек — достаточно специфичная штука для многопоточной работы. Если у нас есть схема, когда в одном потоке в стек что-то кладется, а в другом снимается — фактически порядок съема обратным не будет, из за того что push и pop в разных потоках чередуются по-разному. И если в стек будет ложиться и приниматься по 1 записи — оно будет работать как очередь. Если же у нас в потоке-потребителе получится reverse ordered, это будет означать, что у нас на самом деле было не многопоточное выполнение, а последовательное выполнение двух задач в разных потоках. Реально же, на таком длительном тесте, стек будет работать почти как unordered collection.
Но. Если нас устраивает последовательное выполнение, то эффективней выполнить задачи в одном потоке — это более cache-frendly. А если нас устраивает unordered, то может лучше не стек? Если потоки действительно одновременно пишут и читают вершину, там же на вершине на этой будет false sharing (в данном случае наверное даже true sharing). Время будет съедаться на миграцию кэшлайна между ядрами, можно словить 1000 кратную просадку производительности.
Вобщем, достаточно искуственный пример. И тесты, (предположу, что в них скорей всего нет оценки степени «разупорядоченности») неясно что меряют. Набор различных эффектов, проявивших себя в различной мере, и наложенных друг на друга случайным образом.
Можете добавить в тесты следующую фишку: Через стек передаем последовательный набор чисел: 1,2,3,4,5,6..., Снимаются эти числа (когда снимаем в том же потоке) в обратной последовательности. На снимающей стороне мы смотрим, действительно ли последовательность съема обратная. Если происходит скачок по отношению к предыдущему снятому значению в сторону увеличения — значит потоком-производителем была засунута новая порция данных. Мы заводим счетчик таких событий.
И дальше мы говорим, мол всего элементов было столько-то, а конкуррентных вставок было столько-то, и отношение этих величин такое-то.
И когда мы сравниваем реализацию с мутексами с реализацией на cas-ах и спинлоках, то сравнивать имеет смысл прогоны теста, с оглядкой на отношение этих величин. Потому, что ОС, когда она обрабатывает мутексы, то может будить потоки по-разному.
И потом еще надо прогнать сначала push а потом pop этих элементов в одном потоке. Причем, прогнать в двух вариантах:
1 — сначала push всех, потом pop всех. (элементов должны быть сотни мб)
2 — push и pop порциями размером не более 64 байт (чтоб гарантированно работать в одном кэшлайне), вершина стека должна быть выровненной по 64 байтам.
И тут сравнивать время обработки с многопоточным временем обработки. Неисключено, что по варианту 2 будет выигрыш.
а потом прогоните через разные многопоточные очереди такой же обьем данных. И сравние. Это крректно потому, что мы выше решили, что стек может дать как ordered так и unordered данные на принимающей стороне. Нормальная очередь будет более cache-frendly, по идее должно получится существенно быстрей.
Но. Если нас устраивает последовательное выполнение, то эффективней выполнить задачи в одном потоке — это более cache-frendly. А если нас устраивает unordered, то может лучше не стек? Если потоки действительно одновременно пишут и читают вершину, там же на вершине на этой будет false sharing (в данном случае наверное даже true sharing). Время будет съедаться на миграцию кэшлайна между ядрами, можно словить 1000 кратную просадку производительности.
Вобщем, достаточно искуственный пример. И тесты, (предположу, что в них скорей всего нет оценки степени «разупорядоченности») неясно что меряют. Набор различных эффектов, проявивших себя в различной мере, и наложенных друг на друга случайным образом.
Можете добавить в тесты следующую фишку: Через стек передаем последовательный набор чисел: 1,2,3,4,5,6..., Снимаются эти числа (когда снимаем в том же потоке) в обратной последовательности. На снимающей стороне мы смотрим, действительно ли последовательность съема обратная. Если происходит скачок по отношению к предыдущему снятому значению в сторону увеличения — значит потоком-производителем была засунута новая порция данных. Мы заводим счетчик таких событий.
И дальше мы говорим, мол всего элементов было столько-то, а конкуррентных вставок было столько-то, и отношение этих величин такое-то.
И когда мы сравниваем реализацию с мутексами с реализацией на cas-ах и спинлоках, то сравнивать имеет смысл прогоны теста, с оглядкой на отношение этих величин. Потому, что ОС, когда она обрабатывает мутексы, то может будить потоки по-разному.
И потом еще надо прогнать сначала push а потом pop этих элементов в одном потоке. Причем, прогнать в двух вариантах:
1 — сначала push всех, потом pop всех. (элементов должны быть сотни мб)
2 — push и pop порциями размером не более 64 байт (чтоб гарантированно работать в одном кэшлайне), вершина стека должна быть выровненной по 64 байтам.
И тут сравнивать время обработки с многопоточным временем обработки. Неисключено, что по варианту 2 будет выигрыш.
а потом прогоните через разные многопоточные очереди такой же обьем данных. И сравние. Это крректно потому, что мы выше решили, что стек может дать как ordered так и unordered данные на принимающей стороне. Нормальная очередь будет более cache-frendly, по идее должно получится существенно быстрей.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lock-free алгоритмы и реализация стека