Вы, вероятно, захотите поместить указатели в свою очередь, а не копировать данные в/из самого общего кольца. то есть полезная нагрузка кольцевого буфера - это просто указатель.
Семантика освобождения/получения заботится о том, чтобы данные были там, когда вы разыменовываете указатель, полученный из очереди. Но тогда у вас возникает проблема с освобождением памяти: как производитель узнает, когда потребитель закончил использование буфера, чтобы он мог использовать его повторно?
Если можно передать право собственности на буфер, то все в порядке. Может быть, потребитель может использовать буфер для чего-то другого, например, добавить его в локальный свободный список или, возможно, использовать его для чего-то, что он производит.
Чтобы узнать следующее, см. анализ очереди MPMC без блокировки на основе кольцевого буфера в Гарантии выполнения без блокировки< /а>. Я представляю себе модификации, которые сделают его пригодным для ваших целей.
Он имеет индекс чтения и индекс записи, а каждый узел кольцевого буфера имеет счетчик последовательности, который позволяет ему определять, что пишущие догоняют читающих (очередь заполнена) по сравнению с читающими, догоняющими писателей (очередь пуста), не создавая конкуренции. между читателями и писателями. (IIRC, читатели читают индекс записи или наоборот, но нет общих данных, которые изменяются как читателями, так и писателями.)
Если существует разумная верхняя граница размера буфера, вы могли бы иметь общие буферы фиксированного размера, связанные с каждым узлом в кольцевом буфере. Например, 1 КБ или 4 КБ. Тогда вам не понадобится полезная нагрузка в кольцевом буфере; индекс был бы интересной вещью.
Если выделение памяти не имеет большого значения (только кеш-память), даже буферы размером 64 КБ или 1 МБ будут в основном хороши, даже если вы обычно используете только младшие 400 байтов каждого. Части буфера, которые не используются, просто останутся холодными в кеше. Если вы используете огромные страницы размером 2 МБ, буферы меньшего размера являются хорошей идеей, чтобы уменьшить нагрузку на TLB: вы хотите, чтобы несколько буферов покрывались одной и той же записью TLB.
Но вам нужно будет запросить буфер перед записью в него и закончить запись в него до завершения второго шага добавления записи в очередь. Вы, вероятно, не хотите делать больше, чем просто memcpy
, потому что частично завершенная запись блокирует чтение, если она становится самой старой записью в очереди до ее завершения. Возможно, вы могли бы выполнить предварительную запись буфера ( с prefetchw
в Broadwell или новее), прежде чем пытаться его заявить, чтобы сократить время между тем, как вы (потенциально) блокируете очередь. Но если за писателей мало разногласий, это может не иметь значения. И если существует высокая конкуренция, поэтому вам (почти) не всегда удается заявить права на первый пробуемый вами буфер, предварительная выборка записи в неправильном буфере замедлит работу программы чтения или записи, которой он принадлежит. Может быть, обычная предварительная выборка была бы хороша.
Если буферы привязаны непосредственно к записям очереди, возможно, вам следует просто поместить их в очередь в очередь, если библиотека MPMC позволяет использовать пользовательский код чтения, который считывает длину и копирует столько байтов, вместо того, чтобы всегда копировать весь гигантский массив.
Тогда каждая запись управления очередью, которую просматривают производители/потребители, будет находиться в отдельной строке кэша, поэтому между двумя производителями, требующими смежных записей, не будет конкуренции.
Если вам нужны действительно большие буферы, потому что ваша верхняя граница составляет около 1 МБ или что-то в этом роде, повторные попытки из-за конкуренции приведут к касанию большего количества записей TLB, поэтому более компактный кольцевой буфер с отдельными большими буферами может быть лучшей идеей.
Читатель, затребовавший буфер на полпути, не блокирует другие читатели. Он блокирует очередь только в том случае, если она циклически повторяется, а производитель застревает в ожидании. Таким образом, вы определенно можете заставить своих читателей использовать данные на месте в очереди, если она достаточно велика и читатели быстры. Но чем больше вы делаете во время частично завершенного чтения, тем больше шансов, что вы заснете и в конечном итоге заблокируете очередь.
Это гораздо более серьезное дело для производителей, особенно если очередь обычно (почти) пуста: потребители подходят к вновь написанным записям почти сразу после их создания. Вот почему вы можете захотеть выполнить предварительную выборку данных, которые вы собираетесь копировать, и/или самого общего буфера перед запуском производителя.
400 байт — это всего 12,5 циклов фиксации 32 байтов за такт в кэше L1d (например, Intel Haswell/Skylake), так что это действительно мало по сравнению с межъядерными задержками или временем вам нужно дождаться RFO в кэш-памяти. Таким образом, минимальное время между тем, когда производитель делает заявку на узел видимой во всем мире, и моментом, когда вы завершаете эту заявку, чтобы читатели могли ее прочитать (и более поздние записи), по-прежнему очень мало. Блокировка очереди на долгое время надеюсь избежать.
Такое количество данных помещается даже в регистры YMM 13, так что теоретически компилятор может фактически загрузить данные в регистры до того, как запросить запись в буфер, и просто сохранить их. Возможно, вы могли бы сделать это вручную с помощью встроенных функций с полностью развернутым циклом. (Вы не можете проиндексировать регистровый файл, поэтому он должен быть полностью развернут или всегда хранить 408 байт или что-то еще.)
Или 7 регистров ZMM с AVX512, но вы, вероятно, не хотите использовать 512-битные загрузки/сохранения, если вы не используете другие 512-битные инструкции, из-за влияния на тактовую частоту max-turbo и отключения порта 1 для вектор АЛУ упс. (Я предполагаю, что это все еще происходит с векторной загрузкой/сохранением, но, если нам повезет, некоторые из этих эффектов происходят только с 512-битными операциями ALU...)
person
Peter Cordes
schedule
17.08.2018