M>А queue, по идее, при постановке в хвост будет лазать в кучу за элементом, и при забирании с носа — отдавать в кучу элемент.
Это если явно попросишь сделать очередь поверх списка, то да, будут походы в аллокатор.
Но по умолчанию она делается поверх deque и тут возможны варианты.
Во-первых, deque обычно делается поверх списка блоков. И аллокатор вызывается для блоков. Чем меньше элемент, тем больше их влезет в блок, тем реже вызывается аллокатор.
Во-вторых, список блоков тоже не обязательно реализуется как список.
Например, я использую libc++ и там это их split_buffer. Который также умеет двигать элементы при исчерпании capacity. Только в отличии от твоего предложения, там двигаются не сами элементы, а указатели (нет зависимости от размера, не нужно вызывать конструкторы/декструкторы), и указатели не на элементы, а на блоки (которых, как помним, кратно меньше чем элементов).
M>По идее, это можно оптимизировать. Вопрос, как с этим в основных реализациях std?
Ну в той же libc++ сделан и другой разумный шаг: если при push_back исчерпалось back_capacity, но есть достаточный front_capacity, то надо взять первый свободный блок и переподклеить его в конец — это обмен пары указателей, а не поход в аллокатор.
В результате std::deque<T> (а с ним и std::queue<T>) может работать как циклический буфер, если количество элементов в нём примерно стабилизировалось. Например, как в подобном коде:
Только первые итерации аллоцируют память, а последующие переиспользуют освободившуюся после удаления.
Разумеется, всё описанное — implementation defined. В других STL реализация может быть хуже, а может быть и ещё лучше.
Но так как никто специально не вносит пессимизаций, то от реализации стандартной библиотеки можно ожидать, что она намеренно не делает совсем уж неоптимальные вещи даже если они формально подходят под букву стандарта.
M>ЗЫ В принципе, что-то существенное по отношению к остальному коду не выгадаю
Tсли и остальной код написан в стиле "добавим pop_front для vector", то, действительно, такие тонкие оптимизации уже не помогут
А так, надо исходить из правила profile first!
Если этого не сделал, и не замерил производительность на своём сценарии, то не нужно заниматься предварительной оптимизацией. А надо использовать стандартные механизмы.
У них понятная семантика и поэтому даже если они будут тормозить, то их проще будет на что-то заменить потом, когда прижмёт.
Плюс проблемы с производительностью можно решить и тем, что переключится на современную реализацию stl и взять современный аллокатор. А не продолжать использовать старьё 20-летней давности, которое включено по умолчанию из-за обратной совместимости (правда этот совет работает только если тебе не нужно поддерживать бинарную совместимость с таким старьём ).
Здравствуйте, Marty, Вы писали:
M>Вектор при выталкивании с носа будет целиком перемещаться
Так ты не перемещай. Храни отдельный счётчик "сколько сняли с носа".
Когда покажется, что дофига пустого места вначале — уже уплотняй. Критерий сам придумай, чтоб амортизированное О(1) было. А так я чаще забиваю на уплотнения, памяти хватает.
Нужно сделать очередь, в хвост кладём, с носа забираем. Типы — примитивные.
Вектор при выталкивании с носа будет целиком перемещаться, что не очень хорошо, но в случае примитивных типом и не слишком большого размера — 100-200, например — это будет скорее всего memcpy с небольшим объемом памяти. А queue, по идее, при постановке в хвост будет лазать в кучу за элементом, и при забирании с носа — отдавать в кучу элемент. По идее, это можно оптимизировать. Вопрос, как с этим в основных реализациях std?
Если нетривиальные типы — то дека скорее всего будет оптимальнее сразу, а на примитивах — небольшой вектор (до какого-то размера) может быть шустрее.
ЗЫ В принципе, что-то существенное по отношению к остальному коду не выгадаю, но вот просто интересно
M>Нужно сделать очередь, в хвост кладём, с носа забираем. Типы — примитивные.
Почему не взять стандартную? M>Вектор при выталкивании с носа будет целиком перемещаться, что не очень хорошо, но в случае примитивных типом и не слишком большого размера — 100-200, например — это будет скорее всего memcpy с небольшим объемом памяти. А queue, по идее, при постановке в хвост будет лазать в кучу за элементом, и при забирании с носа — отдавать в кучу элемент. По идее, это можно оптимизировать. Вопрос, как с этим в основных реализациях std?
Даже в нашем "заборостроительном" институте любой 2-курсник понимает, что вектор для реализации очереди — плохая идея...
В STL стандартная очередь реализуется на деке или на списке.
В тех кодах, что я видел, по умолчанию параметром шаблона был дек. M>Если нетривиальные типы — то дека скорее всего будет оптимальнее сразу, а на примитивах — небольшой вектор (до какого-то размера) может быть шустрее.
Вот оно и сделано.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Что оптимальнее для FIFO - queue или vector?
Здравствуйте, LaptevVV, Вы писали:
LVV>Даже в нашем "заборостроительном" институте любой 2-курсник понимает, что вектор для реализации очереди — плохая идея...
А теперь уменьшаем размер очереди до пары десятков элементов, и собераем это под микроконтроллер
LVV>В STL стандартная очередь реализуется на деке или на списке.
Других вариантов-то не особо.
LVV>В тех кодах, что я видел, по умолчанию параметром шаблона был дек.
А это не по стандарту вообще так?
M>>Если нетривиальные типы — то дека скорее всего будет оптимальнее сразу, а на примитивах — небольшой вектор (до какого-то размера) может быть шустрее. LVV>Вот оно и сделано.
Здравствуйте, LaptevVV, Вы писали:
M>>А я-то говорю про примитивные типы LVV>Ну и сделай кольцевой буфер на 100 элементов. LVV>Гарантия от переполнения есть?
Не много не понял, чья гарантия?
Ну а так — да, максимальное число элементов фиксировано.
Здравствуйте, T4r4sB, Вы писали:
M>>Вектор при выталкивании с носа будет целиком перемещаться
TB>Так ты не перемещай. Храни отдельный счётчик "сколько сняли с носа". TB>Когда покажется, что дофига пустого места вначале — уже уплотняй. Критерий сам придумай, чтоб амортизированное О(1) было. А так я чаще забиваю на уплотнения, памяти хватает.
M>>>Нужно сделать очередь, в хвост кладём, с носа забираем. Типы — примитивные. LVV>>Почему не взять стандартную? _NN>В MSVC крайне не рекомендуется. _NN>Очень высокие накладные расходы и в ближайшем будущем это не изменится. _NN>https://github.com/microsoft/STL/issues/147
Да в с этим я согласен.
Если нужна скорость, да еще и с памятью вопросы — надо делать самому.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Что оптимальнее для FIFO - queue или vector?
Усложняю задачу — надо не просто класть в хвост и забирать с морды, но и пробежаться по элементам.
queue — не даёт пробежаться
deque — плохая реализация в MSVC
ring_buffer — хорош, только нет реализации в стандартной библитеке
vector — в принципе, если уплотнять морду не каждый раз, то ничего
Есть новые варианты?
Ну и раскрою карты в руки, что мне нужно:
а) я назвал это request balancer — есть лимит на количество запросов к сервису; при этом хочется, если лимит не исчерпан, отправлять запросы максимально быстро. Поэтому самый тупой вариант, когда просто считаем допустимый рейт и с вычисленным интервалом извлекаем из очереди запросы, и отправляем сервису — не катит. Я не знаю, как у сервера сделано — может, он тупо на нулевой секунде сбрасывает счётчик, а может у него скользящее окно. Я решил у себя сделать скользящее окно — если сервис тупо сбрасывает счетчик, моё окно всё равно должно работать, по идее.
Суть идеи такова — при отправке (если разрешено) кладем в очередь штамп времени (мс). Как определить, что можно отправлять — смотрим голову, если она старше заданного интервала от текущего момента — извлекаем. И так до тех пор, пока в голове не обнаруживаются штамп посвежее. Затем смотрим размер — если меньше лимита — можно отправлять запрос.
Но возможно, можно как-то иначе сделать. Может и готовое кто знает?
б) bandwidth meter — измеряем пропускную способность. Почти тоже самое, только есть какое-то число payload — например, число байт данных в посылке. При поклаже payload'а в хвост прицепляем к нему штамп времени, с носа выбираем старое — потом пробежаться, посчитать суммарную загрузку
Хочется сделать это одинаково, например, в виде второго варианта, и в первом случае использовать просто без нагрузки
M>>А теперь уменьшаем размер очереди до пары десятков элементов, и собераем это под микроконтроллер AN>Кольцевой буфер на std::array или обычном массиве фиксированной длины. И подумать, что делать если буфер заполнен полностью.
Можно на обычном массиве нефиксированной длины — отращивать при заполнении. А если погуглить можно найти откуда скопипастить. А если программист без комплексов (а топикстартер именно такой), то можно просто заюзать буст — https://www.boost.org/doc/libs/1_61_0/doc/html/circular_buffer.html
Как много веселых ребят, и все делают велосипед...
Re[5]: Что оптимальнее для FIFO - queue или vector?
Здравствуйте, ononim, Вы писали:
M>>>А теперь уменьшаем размер очереди до пары десятков элементов, и собераем это под микроконтроллер AN>>Кольцевой буфер на std::array или обычном массиве фиксированной длины. И подумать, что делать если буфер заполнен полностью. O>Можно на обычном массиве нефиксированной длины — отращивать при заполнении.
У микроконтроллеров обычно ресурсы сильно ограничены.
O>А если погуглить можно найти откуда скопипастить. А если программист без комплексов (а топикстартер именно такой), то можно просто заюзать буст — https://www.boost.org/doc/libs/1_61_0/doc/html/circular_buffer.html
А ещё лучше взять std::deque, которая реализована как связанный список массивов.
Re[5]: Что оптимальнее для FIFO - queue или vector?
Здравствуйте, ononim, Вы писали:
M>>>А теперь уменьшаем размер очереди до пары десятков элементов, и собераем это под микроконтроллер AN>>Кольцевой буфер на std::array или обычном массиве фиксированной длины. И подумать, что делать если буфер заполнен полностью. O>Можно на обычном массиве нефиксированной длины — отращивать при заполнении. А если погуглить можно найти откуда скопипастить. А если программист без комплексов (а топикстартер именно такой), то можно просто заюзать буст — https://www.boost.org/doc/libs/1_61_0/doc/html/circular_buffer.html
Ну, я очень закомплексованый, на самом деле. И свой циркулярный буфер уже написал
На самом деле, написал просто ради интереса изначально. Как-то перелистывал книгу Уоренна про трюки, и пришла в голову пара идей, в результате которых и получился static_circular_buffer — static — потому, что capacity один раз задаётся, и потом не меняется. В принципе, если очень надо, можно будет приделать расширение, но пока и нынешний вариант под микроконтроллер хорошо зашел. Кстати, вроде бы получилось даже вполне лок-фри, если один читатель и один писатель — как раз данные из прерываний возвращать
AN>У микроконтроллеров обычно ресурсы сильно ограничены.
Ну, в конкретном случае я не под контроллер пишу, но вообще, так как я на работе этим занимаюсь, то любое решение осматриваю и на предмет применимости в МК
O>>А если погуглить можно найти откуда скопипастить. А если программист без комплексов (а топикстартер именно такой), то можно просто заюзать буст — https://www.boost.org/doc/libs/1_61_0/doc/html/circular_buffer.html
AN>А ещё лучше взять std::deque, которая реализована как связанный список массивов.
Здравствуйте, Marty, Вы писали:
M>нынешний вариант под микроконтроллер хорошо зашел. Кстати, вроде бы получилось даже вполне лок-фри, если один читатель и один писатель
А какой memory ordering использовался для записи и чтения?
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Re[7]: Что оптимальнее для FIFO - queue или vector?
Здравствуйте, AndrewJD, Вы писали:
M>>нынешний вариант под микроконтроллер хорошо зашел. Кстати, вроде бы получилось даже вполне лок-фри, если один читатель и один писатель AJD>А какой memory ordering использовался для записи и чтения?
Здравствуйте, Marty, Вы писали:
M>>>нынешний вариант под микроконтроллер хорошо зашел. Кстати, вроде бы получилось даже вполне лок-фри, если один читатель и один писатель AJD>>А какой memory ordering использовался для записи и чтения?
M>Не совсем понял вопроса, если честно.
Один читатель и один писатель сами по себе не гарантируют безопасный лок-фри. В общем случае С++ требует использование атомиков с соотвествующим memory ordering. Для x86-64 это будет и так рабоать, но для других процов и возможно твоего контролера это не так.
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Re[9]: Что оптимальнее для FIFO - queue или vector?
M>>>>нынешний вариант под микроконтроллер хорошо зашел. Кстати, вроде бы получилось даже вполне лок-фри, если один читатель и один писатель AJD>>>А какой memory ordering использовался для записи и чтения?
M>>Не совсем понял вопроса, если честно.
AJD>Один читатель и один писатель сами по себе не гарантируют безопасный лок-фри. В общем случае С++ требует использование атомиков с соотвествующим memory ordering. Для x86-64 это будет и так рабоать, но для других процов и возможно твоего контролера это не так.
Я оставил возможность пользователю самому расставить барьеры памяти. Это раз. Во вторых, я конечно не изучал глубоко, но полагаю, в STM32 при возникновении прерываний это все само собой делается. Но вообще надо бы копнуть, да
).
