Performance of boost::circular_buffer on the standard tests in my book is competitive with std::vector, and at least five times as fast as std::deque or std::list on the same tests. This is not surprising given the similarity between the implementation of circular_buffer and vector. I also performed tests to assess the performance of list, deque, and circular_buffer when used as a queue. As expected, the circular buffer outperformed list and deque.
Вопрос: кто-нибудь знает, собирается ли комитет C++ добавить кольцевой буфер в стандарт?
Здравствуйте, B0FEE664, Вы писали:
BFE>Мне нужен кольцевой буфер, в стандарте, как я понимаю, его нет, а boost не используют в конторе которую я консультирую. BFE>Соответственно опрос: BFE>В std библиотеку C++ следует добавить кольцевой буфер?
Не могу обосновать "железобетонно", но по моим ощущениям в этой задаче будет достаточно сложно добиться какого-то разумного баланса между полезностью и общностью. Иначе говоря, в самом общем виде, приемлемом для стандартной библиотеки, коэффициент полезного действия для отдельных прикладных случаев будет достаточно низким. Получится эдакий сферический конек в вакууме — прикольный, но бесполезный.
R>Не могу обосновать "железобетонно", но по моим ощущениям в этой задаче будет достаточно сложно добиться какого-то разумного баланса между полезностью и общностью. Иначе говоря, в самом общем виде, приемлемом для стандартной библиотеки, коэффициент полезного действия для отдельных прикладных случаев будет достаточно низким. Получится эдакий сферический конек в вакууме — прикольный, но бесполезный.
На мой взгляд boost::circular_buffer написан в самом общем виде (быть может даже излишне общем виде, я не уверен, что нужно иметь возможность менять емкость контейнера) и вполне пригоден для любого использования. Я его использовал и остался вполне доволен.
Я думаю тут такая же ситуация как с std::array — долгое время все использовали std::vector там, где хватило бы std::array'я. Так и сейчас можно использовать std::deque, вместо boost::circular_buffer, при этом сильно проигрывая в скорости.
BFE>Performance of boost::circular_buffer on the standard tests in my book is competitive with std::vector, and at least five times as fast as std::deque or std::list on the same tests. This is not surprising given the similarity between the implementation of circular_buffer and vector. I also performed tests to assess the performance of list, deque, and circular_buffer when used as a queue. As expected, the circular buffer outperformed list and deque.
BFE>Вопрос: кто-нибудь знает, собирается ли комитет C++ добавить кольцевой буфер в стандарт?
Чувак с тестами тупой совсем? Добавление/удаление в списке быстрее, а произвольный доступ быстрее в векторе/массиве/кольцевом буфере.
Можно ещё использовать разновидность реализации связного списка- закольцованный связный список.
Здравствуйте, B0FEE664, Вы писали:
BFE>Вопрос: кто-нибудь знает, собирается ли комитет C++ добавить кольцевой буфер в стандарт?
С одной стороны, применения для кольцевого буфера есть.
С другой стороны, субъективно, это не первый контейнер из буста, который можно было бы стандартизировать.
Не так часто он нужен. Так, не дочитав до конца, сначала подумал, что речь о spsc_queue.
В личном порядке приоритетов: flat_map / flat_set прежде всего, потом intrusive, потом static/small vector, interval_tree, дальше уже можно circular_buffer
Здравствуйте, Тёмчик, Вы писали:
Тё>Чувак с тестами тупой совсем?
Не-а.
Тё>Добавление/удаление в списке быстрее,
Добавление/удаление куда? В начало или в конец?
Вот, что говорит тест:
ring
vector
deque
list
.push_back() from vector[]
1218
4539
6711
6759
.push_back() from vector iterator
997
4724
6814
6635
same, but with reserve()
1412
.push_front() from vector[]
1265
6588
6878
.push_front() from vector iterator
1212
6738
6641
Тё>а произвольный доступ быстрее в векторе/массиве/кольцевом буфере.
Если вы хотите вставить элемент в список. то разве вам не придётся сначала дойти по списку до нужного места?
Тё>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список.
А смысл?
Здравствуйте, Тёмчик, Вы писали:
Тё>Чувак с тестами тупой совсем? Добавление/удаление в списке быстрее, а произвольный доступ быстрее в векторе/массиве/кольцевом буфере.
Добавление/удаление элемента в std::list со стандартным аллокатором это всегда new/delete с хождением на поклон к менеджеру памяти.
Тё>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список.
Можно, но зачем? Тут вам не Java, про локальность данных думать надо иногда.
Во всех случаях что я видел, использовался кольцевой буфер фиксированного размера, в качестве контейнера элементов очереди. И очень часто с размером степени 2, для быстрого вычисления индекса элемента.
Смысл тестов на вставку, сортировку и прочие операции с кольцевым буфером мне не ясен. Для очереди требуется 2 операции — добавить элемент в один конец и удалить с противоположного конца.
Здравствуйте, B0FEE664, Вы писали:
Тё>>Чувак с тестами тупой совсем? BFE>Не-а.
Тё>>Добавление/удаление в списке быстрее, BFE>Добавление/удаление куда? В начало или в конец? BFE>Вот, что говорит тест: BFE>
BFE>
BFE>
BFE>
ring
BFE>
vector
deque
list
BFE>
BFE>
BFE>
.push_back() from vector[]
1218
4539
6711
6759
BFE>
BFE>
BFE>
.push_back() from vector iterator
997
4724
6814
6635
BFE>
BFE>
BFE>
same, but with reserve()
1412
BFE>
BFE>
BFE>
.push_front() from vector[]
1265
6588
6878
BFE>
BFE>
BFE>
.push_front() from vector iterator
1212
6738
6641
BFE>
BFE>
Тё>>а произвольный доступ быстрее в векторе/массиве/кольцевом буфере. BFE>Если вы хотите вставить элемент в список. то разве вам не придётся сначала дойти по списку до нужного места?
Нет. У вас уже есть node.
Тё>>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список. BFE>А смысл?
А смысл тот же самый- закольцованный обход.
Здравствуйте, PM, Вы писали:
Тё>>Чувак с тестами тупой совсем? Добавление/удаление в списке быстрее, а произвольный доступ быстрее в векторе/массиве/кольцевом буфере.
PM>Добавление/удаление элемента в std::list со стандартным аллокатором это всегда new/delete с хождением на поклон к менеджеру памяти.
Нужно смотреть по ситуации.
Тё>>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список.
PM>Можно, но зачем? Тут вам не Java, про локальность данных думать надо иногда.
Так и подумайте.
PM>Во всех случаях что я видел, использовался кольцевой буфер фиксированного размера, в качестве контейнера элементов очереди. И очень часто с размером степени 2, для быстрого вычисления индекса элемента.
Не для вычисления индекса, а для выравнивания адреса элемента. Размер буфера делают кратным размеру страницы в page file.
PM>Смысл тестов на вставку, сортировку и прочие операции с кольцевым буфером мне не ясен. Для очереди требуется 2 операции — добавить элемент в один конец и удалить с противоположного конца.
Сам придумал, сам ответил
Только FIFO очередь не ограничивается, и могут потребоваться более другие структуры данных.
Здравствуйте, Тёмчик, Вы писали:
Тё>>>Чувак с тестами тупой совсем? Добавление/удаление в списке быстрее, а произвольный доступ быстрее в векторе/массиве/кольцевом буфере.
PM>>Добавление/удаление элемента в std::list со стандартным аллокатором это всегда new/delete с хождением на поклон к менеджеру памяти. Тё>Нужно смотреть по ситуации.
Нужно, я и даже подскажу где — в реализации std::list::push_back задуматься над смыслом __allocate_node
Тё>>>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список.
PM>>Можно, но зачем? Тут вам не Java, про локальность данных думать надо иногда. Тё>Так и подумайте.
PM>>Во всех случаях что я видел, использовался кольцевой буфер фиксированного размера, в качестве контейнера элементов очереди. И очень часто с размером степени 2, для быстрого вычисления индекса элемента. Тё>Не для вычисления индекса, а для выравнивания адреса элемента. Размер буфера делают кратным размеру страницы в page file.
мой день начинается с открытий! Что же делать разработчикам встраиваемого ПО, зачем там пользоваться буферами размера степени 2? Ведь на их железе может не быть MMU и страничной памяти.
PM>>Смысл тестов на вставку, сортировку и прочие операции с кольцевым буфером мне не ясен. Для очереди требуется 2 операции — добавить элемент в один конец и удалить с противоположного конца. Тё>Сам придумал, сам ответил Тё>Только FIFO очередь не ограничивается, и могут потребоваться более другие структуры данных.
Какие? Хотелось бы увидеть примеры из реальных проектов
Здравствуйте, Тёмчик, Вы писали:
BFE>>Если вы хотите вставить элемент в список. то разве вам не придётся сначала дойти по списку до нужного места? Тё>Нет. У вас уже есть node.
Откуда?
Тё>>>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список. BFE>>А смысл? Тё>А смысл тот же самый- закольцованный обход.
Зачем? В чём смысл иметь закольцованный обход?
Когда автор рассматривает вариант Array + index + length вот этот аргумент про кэширование слабоват:
The most common use for ring buffers is for it to be the intermediary between a concurrent reader and writer (be it two threads, to processes sharing memory, or a software process communicating with hardware). And for that, the index + size representation is kind of miserable. Both the reader and the writer will be writing to the length field, which is bad for caching.
Даже в коде с двумя индексами без модуля (unmasked у автора) оба индекса окажутся в одной кэш линии, которая целиком будет помечена испорченной при любой записи.
Здравствуйте, Тёмчик, Вы писали:
Тё>Чувак с тестами тупой совсем?
Это понятие относительное, смотря с кем сравнивать...
Тё>Добавление/удаление в списке быстрее, <…>/кольцевом буфере.
С фига ли это в списке, быстрее, чем в кольцевом буфере?
Тё>Можно ещё использовать разновидность реализации связного списка- закольцованный связный список.
1) обычно в основе std::list и так лежит закольцованный двусвязный список...
2) Зачем для кольцевого буффера закольцованный список? А как в нём с конца ходить?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
A> The most common use for ring buffers is for it to be the intermediary between a concurrent reader and writer (be it two threads, to processes sharing memory, or a software process communicating with hardware). And for that, the index + size representation is kind of miserable. Both the reader and the writer will be writing to the length field, which is bad for caching.
A>
A>Даже в коде с двумя индексами без модуля (unmasked у автора) оба индекса окажутся в одной кэш линии, которая целиком будет помечена испорченной при любой записи.
В примерах кода вообще нет никакого выравнивая индексов по разам кэш-диниям, это детали реализации на каком-то железе.
Мысль в том, что в случае Array + two indices модификация индексов read и write производится читателем и писателем независимо друг от друга:
Здравствуйте, PM, Вы писали:
PM>В примерах кода вообще нет никакого выравнивая индексов по разам кэш-диниям, это детали реализации на каком-то железе.
Это будет крайне вероятно практически на любом железе. За счет локальности. Индексы в соседних адресах живут.
PM>о чем и упоминается в цитате выше.
Это понятно. Я про то, что второй индекс скорее всего также жертвой cache trashing окажется и будет подгружаться не из кэша, а из основной памяти каждый раз, не смотря на то, что он не модифицировался — вся линия будет помечена "грязной". Нет смысла писать гораздо хуже понятный код для сомнительных выигрышей в производительности имхо, хотя, конечно, мерить надо.
Здравствуйте, andyp, Вы писали:
A>Это понятно. Я про то, что второй индекс скорее всего также жертвой cache trashing окажется и будет подгружаться не из кэша, а из основной памяти каждый раз, не смотря на то, что он не модифицировался — вся линия будет помечена "грязной". Нет смысла писать гораздо хуже понятный код для сомнительных выигрышей в производительности имхо, хотя, конечно, мерить надо.
Ээээ... Вы хотите сказать, что вместо того, чтобы завести два буфера и свапить указатели на них обычно используют один защищённый буфер? Это же в любом случае не быстро.
Здравствуйте, B0FEE664, Вы писали:
BFE>Ээээ... Вы хотите сказать, что вместо того, чтобы завести два буфера и свапить указатели на них обычно используют один защищённый буфер? Это же в любом случае не быстро.
Я хочу сказать, что при доступе из нескольких ядер вся структура памяти, описывающая буфер, попадет в одну кэш-линию. Поэтому всё равно, меняется только одно поле этой структуры при доступе (индекс) или оба (индекс и длина). Второе ядро в обоих случаях будет подтягивать всю структуру из основной памяти, а не из кэша, поэтому не важно, что в случае с двумя индексами при доступе меняется только один индекс, а в случае с индексом и длиной — оба поля.
Здравствуйте, andyp, Вы писали:
BFE>>Ээээ... Вы хотите сказать, что вместо того, чтобы завести два буфера и свапить указатели на них обычно используют один защищённый буфер? Это же в любом случае не быстро.
A>Я хочу сказать, что при доступе из нескольких ядер вся структура памяти, описывающая буфер, попадет в одну кэш-линию. Поэтому всё равно, меняется только одно поле этой структуры при доступе (индекс) или оба (индекс и длина). Второе ядро в обоих случаях будет подтягивать всю структуру из основной памяти, а не из кэша, поэтому не важно, что в случае с двумя индексами при доступе меняется только один индекс, а в случае с индексом и длиной — оба поля.
мой день начинается с открытий! Что же делать разработчикам встраиваемого ПО, зачем там пользоваться буферами размера степени 2? Ведь на их железе может не быть MMU и страничной памяти.
