Lock-free структуры данных. Очередной трактат

[datacompboy]

Монументальный труд. А вот прочитать про то почему код и теория разошлись для стека интересно. Может, всё-таки поднапрячься и родить? :)

[khizmax]

Спасибо
Про стек и реализацию elimination back-off: там не код с теорией разошлись, там получилась классическая проблема реализации псевдокода на C++. В псевдокоде elimination back-off полагается, что дескриптор операции (push или pop) нам уже откуда-то дан и мы с ним работаем, и не рассматриваются вопросы порождения этого дескриптора и времени его жизни. Ясно, что каждый поток может в каждый момент времени иметь только один дескриптор, поэтому хочется разместить их на стеке, не делать new/delete. Но потоки должны встретиться — обменяться содержимым дескрипторов. И тут начинаются гонки…
В общем, я полторы недели пытался оживить псевдокод, получил не очень хорошие результаты — как по производительности, так и по стабильности, — плюнул на чистое lock-free и реализовал lock-based вариант (на spin-lock'ах) со всеми плюшками: дескрипторы размещаются на стеке, если произошла аннигиляция — тут же выводим пассивный (ожидающий) поток из спячки и пр. Получилось намного легче того, что описано в статье.

[youROCK]

Не могли бы вы пожалуйста протестить ещё вот эту программку на своем сервере? У меня получается 0,5 сек при одном консьюмере и одном продьюсере, поэтому я выставил не 10 млн, а 100 млн в качестве количества событий.

У меня получаются вот какие цифры (нужно разделить на 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 её не реализует «из коробки».

[khizmax]

Есть другой путь — скачать libcds, скомпилить и прогнать те же тесты на своей машине. Перед этим посмотреть, что тест внутри делает, чтобы мерить примерно в равных условиях. Исходник теста внутри libcds — tests/unit/queue/reader_writer_mt.cpp

[khizmax]

Упс, забыл…
Запуск теста: cdsu-queue -t=Queue_ReaderWriter
Настройки теста находятся в файле test.conf, секция [Queue_ReaderWriter]

[xnike]

А у вас «Наивная стандартная очередь» написана не корректно: при последовательном добавлении нескольких Node, а потом забирания из очереди только первый элемент будет не NULL.

Запуск кода на gcc подтвердил.

[khizmax]

Oops! Действительно — перепутано направление списка. Краснею…
Плюсую, спасибо!

[Master_Dante]

Я реализовал неблокирующие очередь и стек на связанных сегментах(массивах одного размера), проблема с узким горлом там не такая острая так как используется неблокирующий add.