с++: Оптимизация работы с контейнерами ссылок

Question

стоит следующая задача:

в один вектор m_outputStatistics добавляются элементы (вектор растёт неограниченно)
во второй вектор m_statisticsLinks добавляются ссылки на добавленные элементы (длина вектора небольшая - в нем ссылки на актуальные элементы первого вектора с которыми и идет работа)
периодически в вектор m_outputStatistics добавляется новый элемент и соответственно в m_statisticsLinks ссылка на него, с этими элементами идет активная работа
периодически элементы "устаревают" и исключаются из m_statisticsLinks

Вопрос:

можно ли ускорить работу в такой системе (возможно мой код очень неоптимальный)?
вектор m_statisticsLinks постоянно просматривается, чтобы работать с элементами на который указывают ссылки из него и он же постоянно просматривается, чтобы удалить из него устаревшие ссылки -

сейчас приходится разбить данный алгоритм на 2 этапа - 1) работа со свежими элементами 2) удаление устаревших элементов -

оба действия по сути срабатывают на одну и ту же проверку и могут выполняться за 1 проход, но удаление в векторе при его проходе через for чревато,

может лучше использовать другой тип контейнера?

в задаче требуется не требуется произвольный доступ к элементу, поэтому возможно, что вместо std::vector лучше использовать что-то другое, типа std::list?

сделал следующий код:

using statistics_block_pr = std::pair<double, ICustomStatistics>;
using statistics_blocks_t = std::vector<statistics_block_pr>;

using statistics_links_t = std::vector<std::reference_wrapper<statistics_block_pr>>;

// параметры сбора данных
double                                  m_timeStep;         // временной шаг сбора данных
double                                  m_timeInterval;     // время сбора данных

std::function<ICustomStatistics(void)>  m_statistics;       // элемент статистики

// рабочие параметры
double                                  m_nextBlockTime;    // время формирования следующего блока со статистикой

statistics_links_t                      m_statisticsLinks;
statistics_blocks_t                     m_outputStatistics;

...

// добавить новые блоки статистики
while (packetData.timestamp >= m_nextBlockTime)
{
    // добавить блок статистики
    auto& link = m_outputStatistics.emplace_back(m_nextBlockTime, m_statistics());

    m_statisticsLinks.push_back(link);

    // определить следующее время создания нового блока статистики
    m_nextBlockTime += m_timeStep;
}

// проанализировать существующие блоки статистики
for (auto object : m_statisticsLinks)
{
    // проверить блок статистики на актуальность
    if (packetData.timestamp < object.get().first + m_timeInterval)
    {
        // обновить статистику
        object.get().second.add(packetData);
    }
}

// удалить старые блоки статистики
m_statisticsLinks.erase(std::remove_if(m_statisticsLinks.begin(), m_statisticsLinks.end(), [&packetData, timeInterval = m_timeInterval](const auto& object) {
    return (packetData.timestamp >= object.get().first + timeInterval);
    }), m_statisticsLinks.end());

Answer 1

При добавлении новых элементов в m_outputStatistics (даже если это один элемент) ссылки на элементы m_outputStatistics становятся недействительными, и m_statisticsLinks нужно обновлять целиком. На практике ссылки протухают при увеличении размера вектора в 1.5 или в 2 раза, в зависимости от реализации, но не стоит полагаться на это.

Чтобы избежать проблемы, m_outputStatistics должен быть вектором указателей, т.е. vector<unique_ptr<statistics_block_pr>>, или же списком list<statistics_block_pr> (но вам вряд ли нужен именно список). Создание объектов в динамической памяти по отдельности приведет к снижению локальности данных и, возможно, к фрагментации памяти. Если для вас это важно, для решения проблемы можно использовать сторонние аллокаторы, выделяющие память страницами и не освобождающие память до удаления аллокатора целиком, или же освобождающие память только при освобождении страницы целиком. Конкретные реализации не подскажу, их довольно много.

Если в m_outputStatistics осуществляется только добавление, но не удаление, подход с аллокаторами не самый эффективный, вместо этого лучше использовать list-подобый контейнер, содержащий данные блоками, что-то вроде

struct container{
    constexpt size_t block_size = 512;
    vector<vector<Item>> data;

    void push(Item item){
       if(data.empty() || data.back().size() == block_size ){
           data.emplace_back();
           data.back().reserve(block_size);
       }
       data.back().push_back(std::move(item));
    }
};

Естественно, в этом случае невозможен последовательный доступ по индексу, но на практике даже если реализовать доступ по индексу, структура будет не на много медленнее vector.

boost::stable_vector реализует подобный подход, но не могу сказать, насколько реализация лучше или хуже других.

БЛОГ НА HUSL

с++: Оптимизация работы с контейнерами ссылок

Ответы (1 шт):