Комментарии 8
Монументальный труд. А вот прочитать про то почему код и теория разошлись для стека интересно. Может, всё-таки поднапрячься и родить? :)
Спасибо
Про стек и реализацию elimination back-off: там не код с теорией разошлись, там получилась классическая проблема реализации псевдокода на C++. В псевдокоде elimination back-off полагается, что дескриптор операции (push или pop) нам уже откуда-то дан и мы с ним работаем, и не рассматриваются вопросы порождения этого дескриптора и времени его жизни. Ясно, что каждый поток может в каждый момент времени иметь только один дескриптор, поэтому хочется разместить их на стеке, не делать new/delete. Но потоки должны встретиться — обменяться содержимым дескрипторов. И тут начинаются гонки…
В общем, я полторы недели пытался оживить псевдокод, получил не очень хорошие результаты — как по производительности, так и по стабильности, — плюнул на чистое lock-free и реализовал lock-based вариант (на spin-lock'ах) со всеми плюшками: дескрипторы размещаются на стеке, если произошла аннигиляция — тут же выводим пассивный (ожидающий) поток из спячки и пр. Получилось намного легче того, что описано в статье.
Про стек и реализацию elimination back-off: там не код с теорией разошлись, там получилась классическая проблема реализации псевдокода на C++. В псевдокоде elimination back-off полагается, что дескриптор операции (push или pop) нам уже откуда-то дан и мы с ним работаем, и не рассматриваются вопросы порождения этого дескриптора и времени его жизни. Ясно, что каждый поток может в каждый момент времени иметь только один дескриптор, поэтому хочется разместить их на стеке, не делать new/delete. Но потоки должны встретиться — обменяться содержимым дескрипторов. И тут начинаются гонки…
В общем, я полторы недели пытался оживить псевдокод, получил не очень хорошие результаты — как по производительности, так и по стабильности, — плюнул на чистое lock-free и реализовал lock-based вариант (на spin-lock'ах) со всеми плюшками: дескрипторы размещаются на стеке, если произошла аннигиляция — тут же выводим пассивный (ожидающий) поток из спячки и пр. Получилось намного легче того, что описано в статье.
Не могли бы вы пожалуйста протестить ещё вот эту программку на своем сервере? У меня получается 0,5 сек при одном консьюмере и одном продьюсере, поэтому я выставил не 10 млн, а 100 млн в качестве количества событий.
У меня получаются вот какие цифры (нужно разделить на 10, чтобы получить цифру для 10 млн):
2 потока — 8.6 sec
4 потока — 10.1 sec
8 потоков — 14.6 sec
Исходный текст программы на go (в качестве первого аргумента принимает число N — одновременных писателей и читателей):
К сожалению, сравнение получается нечестное из-за того, что Go не поддерживает (насколько мне известно) unbounded-очереди, но в моих тестах скорость значительно выше того, что указано в статье.
Ну и, конечно же, если каждому потоку дать по своей очереди, то время начинает падать линейно, чего, я если, честно, и ожидал от статьи… Видимо, линейное увеличение скорости разгребания очереди возможно только в случае unfair очереди, вот только почему-то даже Go её не реализует «из коробки».
У меня получаются вот какие цифры (нужно разделить на 10, чтобы получить цифру для 10 млн):
2 потока — 8.6 sec
4 потока — 10.1 sec
8 потоков — 14.6 sec
Исходный текст программы на go (в качестве первого аргумента принимает число N — одновременных писателей и читателей):
Скрытый текст
package main
import (
"fmt"
"os"
"runtime"
"strconv"
)
const (
NUMELEM = 1e8
)
func main() {
megaqueue := make(chan int, 1000)
n, _ := strconv.Atoi(os.Args[1])
maxIdx := NUMELEM / n
runtime.GOMAXPROCS(n * 2)
endChan := make(chan int, n)
for i := 0; i < n; i++ {
go func() {
for j := 0; j < maxIdx; j++ {
megaqueue <- 1
}
}()
go func() {
j := 0
for ; j < maxIdx; j++ {
<-megaqueue
}
endChan <- j - 1
}()
}
total := 0
for i := 0; i < n; i++ {
total += <-endChan
}
fmt.Println(NUMELEM, " vs. ", total)
}
К сожалению, сравнение получается нечестное из-за того, что Go не поддерживает (насколько мне известно) unbounded-очереди, но в моих тестах скорость значительно выше того, что указано в статье.
Ну и, конечно же, если каждому потоку дать по своей очереди, то время начинает падать линейно, чего, я если, честно, и ожидал от статьи… Видимо, линейное увеличение скорости разгребания очереди возможно только в случае unfair очереди, вот только почему-то даже Go её не реализует «из коробки».
Есть другой путь — скачать libcds, скомпилить и прогнать те же тесты на своей машине. Перед этим посмотреть, что тест внутри делает, чтобы мерить примерно в равных условиях. Исходник теста внутри libcds —
tests/unit/queue/reader_writer_mt.cppУпс, забыл…
Запуск теста:
Настройки теста находятся в файле test.conf, секция
Запуск теста:
cdsu-queue -t=Queue_ReaderWriterНастройки теста находятся в файле test.conf, секция
[Queue_ReaderWriter]
А у вас «Наивная стандартная очередь» написана не корректно: при последовательном добавлении нескольких Node, а потом забирания из очереди только первый элемент будет не NULL.
Запуск кода на gcc подтвердил.
Запуск кода на gcc подтвердил.
Я реализовал неблокирующие очередь и стек на связанных сегментах(массивах одного размера), проблема с узким горлом там не такая острая так как используется неблокирующий add.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lock-free структуры данных. Очередной трактат