Здравствуйте, Lexey, Вы писали:

L>

R>>    struct cell_t
R>>    {
R>>        std::atomic<size_t>     sequence_;
R>>        T                       data_;
R>>    };
L>

L>Вопрос: а не будет ли тут false sharing'а при такой структуре элемента очереди? Может в нее тоже стоит выравнивание до размера линии кэша добавить?

Не будет ли тут false sharing'а при каких обращениях к каким элементам?

Здравствуйте, remark, Вы писали:

vf>>Я еще не полностью разобрался с алгоритмом, но закрались подозрения: enqueue_pos_, sequence_, dequeue_pos_ постоянно увеличиваются (если я ничего не пропустил), правильно ли я понимаю, что в алгоритме есть ограничение на число операций enqueue, dequeue ведь size_t не бесконечен?

R>Ограничений нет, они просто переполнятся в 0, и это должно быть корректно обработано алгоритмом.

Мне кажется вот этом месте будет первое переполнение:

R> bool dequeue(T& data)
R> {
R> ...
R> // помечаем элемент как готовый для следующей записи
R> cell->>sequence_.store(pos + buffer_mask_ + 1, std::memory_order_release);
R> return true;
R> }

Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0
Тогда cell[].sequence должно выглядить примерно так, после записи нуля после переполнения:

[12] [13] [14] [15] [ 0] [ 9] [10] [11]
enqueue---------||
dequeue-------------------||

Но тогда, вот здесь при добавлении элемента:

 bool dequeue(T& data)
    {
..
        for (;;)
        {
...
            intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1); - будет всегда больше нуля
            if (dif == 0)
            {
            }
            else if (dif < 0)
                return false;
            // нас кто-то опередил
            // перезагружаем текущий элемент и начинаем сначала
            else /* if (dif > 0) */
                pos = dequeue_pos_.load(std::memory_order_relaxed);
        }
...
    }

Я тут немного понапутал с кусками кода, но думаю идея понятна. Вторым шагом после переполнения, конечно же должно идти добавление элемента.

Здравствуйте, remark, Вы писали:

R>Не будет ли тут false sharing'а при каких обращениях к каким элементам?

Как это видится мне:
Есть два потока на разных ядрах — один кладет, другой вынимает. Первый положил элемент A в очередь, второй начал его вынимать, первый в этот момент кладет следующий B. Поскольку A и B попадают в одну линию кэша, запись B инвалидирует кэш и A будет читаться из памяти. Фолз шаринг в чистом виде.

Здравствуйте, vf, Вы писали:

vf>Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0

Э... будет 16. Откуда переполнение? Какие-то проблемы с переполнением там могут замаячить разве что при размере контейнера > 2**31. Но для этого еще и понадобиться сопоставимое число потоков. :D

Здравствуйте, fddima, Вы писали:

R>>Там мы можем элементарно переместить последний элемент из цепочки на место удаляемого, а тут не может.
F> Ммм... не уверен, что можем, по крайней мере это не просто. Последний элемент в цепочке коллизий вполне может быть элементом на своём месте. Или элементом с предыдущих позиций. Имхо, проще метить как удалённый.

В Hopscotch авторы это делают. При удалениях они всегда "уплотняют" таблицу так что бы элементы находились ближе (желательнов той же кэш-линии), что и рассчётное значение.


R>>Любой разумный однопоточный алгоритм не будет делать периодические ресайзы, только что бы "почистить" неиспользуемые ячейки.
R>>Ну а уж как рекурсивные ресайзы связаны с открытой адресацией я совсем не вижу. Рекурсивный ресайз означает, что при поиске потоку потенциально надо пройти по цепочке из N старых таблиц, что бы найти самую последнюю (АФАИК).
F> Опять же, имхо, но реализация Клифа настолько не прозрачна... оптимизации все эти я думаю он сделал исходя из практики, а не каких-то аналитических заключений.

Это не оптимизации, это побочные эффекты чистого lock-free. В TBB или Hopscotch concurrent кэштаблицах такой фигни нет.

F>Без доступа к такому железу самому что-то подобное написать — нереально.

Именно. Он делал алгоритм именно под своё железо с бесплатным uncontented CAS, только там он быстро и работает. А если ты будешь делать на x86, то у тебя получится другой алгоритм.

Здравствуйте, vf, Вы писали:

vf>Я тут немного понапутал с кусками кода, но думаю идея понятна. Вторым шагом после переполнения, конечно же должно идти добавление элемента.

Я не могу понять на каком элементе и когда будут проблемы.

Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, vf, Вы писали:

vf>>Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0

L>Э... будет 16. Откуда переполнение? Какие-то проблемы с переполнением там могут замаячить разве что при размере контейнера > 2**31.

Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.

Здравствуйте, remark, Вы писали:

R>В Hopscotch авторы это делают. При удалениях они всегда "уплотняют" таблицу так что бы элементы находились ближе (желательнов той же кэш-линии), что и рассчётное значение.
Клёва.
Меня в своё время интересовала таблица без возможности удаления (атомизация объектов) — так что вопросом удаления не сильно был озабочен. Если удаление и происходит то только вместе со всей таблицей.

F>>Без доступа к такому железу самому что-то подобное написать — нереально.
R>Именно. Он делал алгоритм именно под своё железо с бесплатным uncontented CAS, только там он быстро и работает. А если ты будешь делать на x86, то у тебя получится другой алгоритм.
А можно по подробнее?
Для x86 я так понимаю ж ведь суть та же ж:
— читаем и проверям что прочитанные данные консистенты
— пишем через Interlocked (где нужно)

Здравствуйте, vf, Вы писали:

vf>Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.

Пусть у бабушки будет X, тогда это будет дедушка. Какое отношение твое "пусть" имеет к реальности? В алгоритме sequence number — это size_t. 2**32 на x86.

Здравствуйте, remark, Вы писали:

Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0

Пусть будет вот такое состояния массива cell[].sequence, на некотором шаге:

То есть, если я правильно понял, то enqueue_pos_ & buffer_mask_ показывает на элемент в который будет писать. Сейчас enqueue сделать нельзя, мы догнали хвост (dif меньше нуля).

[12] [13] [14] [15] [ 8] [ 9] [10] [11]
enqueue--------------||
dequeue--------------||

Делаем dequeue, произошло переполнение, записали 0 вместо 16.

[12] [13] [14] [15] [ 0] [ 9] [10] [11]
enqueue--------------||
dequeue-------------------||

Но и сейчас enqueue сделать нельзя, ошибка?

Здравствуйте, Lexey, Вы писали:

vf>>Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.

L>Пусть у бабушки будет X, тогда это будет дедушка. Какое отношение твое "пусть" имеет к реальности? В алгоритме sequence number — это size_t. 2**32 на x86.

2**4, 2**32 или 2**64 ничего принципиально не меняет, с 2**4 просто проще, т.к. не надо манипулировать числами типа 18446744073709551615.

Здравствуйте, vf, Вы писали:

vf>Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0

vf>Пусть будет вот такое состояния массива cell[].sequence, на некотором шаге:

vf>То есть, если я правильно понял, то enqueue_pos_ & buffer_mask_ показывает на элемент в который будет писать. Сейчас enqueue сделать нельзя, мы догнали хвост (dif меньше нуля).

vf>

vf>[12] [13] [14] [15] [ 8] [ 9] [10] [11]
vf>enqueue--------------||
vf>dequeue--------------||
vf>

vf>Делаем dequeue, произошло переполнение, записали 0 вместо 16.

vf>

vf>[12] [13] [14] [15] [ 0] [ 9] [10] [11]
vf>enqueue--------------||
vf>dequeue-------------------||
vf>

vf>Но и сейчас enqueue сделать нельзя, ошибка?

У нас же enqueue сейчас тоже равен 0. 0-0=0, значит можно добавлять.

Здравствуйте, Lexey, Вы писали:

vf>>Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.

L>Пусть у бабушки будет X, тогда это будет дедушка. Какое отношение твое "пусть" имеет к реальности? В алгоритме sequence number — это size_t. 2**32 на x86.

Отношение прямое, выше я написал:

vf>>"индексы" инкрементируются при каждой операции.

То есть связано не с кол-во элементов, а с кол-во операций.

Че за беспонтовые дое..ки я мог бы в примере использовать 0xffffffff, смысл не меняется, читать не удобно?!

Здравствуйте, remark, Вы писали:

R>У нас же enqueue сейчас тоже равен 0. 0-0=0, значит можно добавлять.

Они же все вместе переполняются. enqueue был равен 15, seq элемента был 15, положили в него элемент. Теперь seq переполнился в 0, и enqueue переполнился в 0.

Здравствуйте, remark, Вы писали:

R>Они же все вместе переполняются. enqueue был равен 15, seq элемента был 15, положили в него элемент. Теперь seq переполнился в 0, и enqueue переполнился в 0.

Да, спасибо.

Здравствуйте, vf, Вы писали:

vf>Че за беспонтовые дое..ки я мог бы в примере использовать 0xffffffff, смысл не меняется, читать не удобно?!

Это не дое..ки. Переполнение в твоей модели абсолютно безвредно с любым модулем. Но для малых модулей там возможны гораздо более интересные эффекты, которые практически невозможны для больших (и, снижая размерность, ты их фактически вносишь). Правда, при размере буфера, равном степени двойки (и, соответственно, при модуле равном степени двойки) они невозможны и для малых модулей. Кстати, из этих соображений assert лучше бы сделать нормальной проверкой, чтобы он работал не только в дебаге, но и в релизе.

Здравствуйте, Lexey, Вы писали:

vf>>Че за беспонтовые дое..ки я мог бы в примере использовать 0xffffffff, смысл не меняется, читать не удобно?!

L>Но для малых модулей там возможны гораздо более интересные эффекты, которые практически невозможны для больших (и, снижая размерность, ты их фактически вносишь). Правда, при размере буфера, равном степени двойки (и, соответственно, при модуле равном степени двойки) они невозможны и для малых модулей. Кстати, из этих соображений assert лучше бы сделать нормальной проверкой, чтобы он работал не только в дебаге, но и в релизе.

Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!

>Но для малых модулей там возможны гораздо более интересные эффекты, которые практически невозможны для больших (и, снижая размерность, ты их фактически вносишь)

Там нет таких случаев, если ты про ABA. Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...

Здравствуйте, remark, Вы писали:

Начну новую ветку чтобы не путать с другим неверным подозрением связаным с переполнением.

Чем больше разбираюсь тем больше мне алгоритм нра, он компактный, красивый, очень хорошо вписывается под мою задачу/требования. Есть большое желание его использовать.

Два попутных вопроса:
1. А кто автор алгоритма, Вы?
2. Нет ли c# версии? Я его конечно переписал на шарп, но где-то видать накосячил, не взлетело (хотя в одном потоке работает).

Основной вопрос:

Возможна ли следующая ситуация:

Вызвали конструктор, имеем пустую очередь, и инициализированый след. образом seq массив:

enqueue = 0 
dequeue = 0
<0> <1> <2> <3>....

Первый поток начинает добавлять элемент, инкрементировал enqueue, но не успел обновить seq[0] — заснул. Имеем след. картину:

enqueue = 1
dequeue = 0
<0> <1> <2> <3>....

Второй поток добавляет след.элемент, получаем ([2] — скобками показываю что даже данные положили):

enqueue = 2
dequeue = 0
<0> [2] <2> <3>....

Сейчас в очереди имеется один элемент, пытаемся его вытащить, во втором потоке, первый поток все еще спит.

dequeue = 0
seq[0] == 0

а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!

intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1);

Здравствуйте, Lexey, Вы писали:

L>Есть два потока на разных ядрах — один кладет, другой вынимает. Первый положил элемент A в очередь, второй начал его вынимать, первый в этот момент кладет следующий B. Поскольку A и B попадают в одну линию кэша, запись B инвалидирует кэш и A будет читаться из памяти. Фолз шаринг в чистом виде.

С одной стороны — да, с другой — нет.
То, как ты описываешь, действительно имеет место быть. Однако, если разнести все элементы очереди в разные кэш линии, то получим свои негативные моменты. Если поток кладёт в очередь несколько элементов, то теперь ему надо будет модифицировать несколько кэш линий. Аналогично для потока, который достаёт элементы. Ну и в целом, на Н элементов будет передаваться Н кэш линий в лучшем случае, при плотной же укладке элементов — Н/К линий.
Я думаю, что можно подобрать такие синтетические тесты, где будет лучше и один вариант и другой. Однако на своих тестах я обычно наблюдаю, что плотная укладка элементов получается лучше. Хотя в целом окончательный ответ ты можешь получить только попробовав оба варианта в твоей программе.