Нужен совет в оптимизации кода

@Vakarine · Регистрация: 15.09.2018

Нужно оптимизировать метод Deallocate, который переводит нужный указатель из allotted в exempted, и, если указателя нет, бросает ошибку. Я сделал через find, но есть ли способ сделать это быстрее?

C++

    void Deallocate(T* object) {//O(N)
        auto a = find(allotted.begin(), allotted.end(), object);//O(N)
        if (a != allotted.end()) {
            T* param = *a;
            exempted.push_back(param);          //O(1)
            allotted.erase(a);                  //O(end - a)
        }
        else {
            throw invalid_argument("");
        }
    }

Ниже весь код:

C++

template <class T>
class ObjectPool {
public:
    T* Allocate() {//O(1)
        if (exempted.begin() != exempted.end()) {       //O(1)
            T* param = exempted.front();//O(1)
            allotted.push_back(param);  //O(1)
            exempted.pop_front();       //O(1)
            return param;
        }
        else {
            T* param = new T;
            allotted.push_back(param);//O(1)
            return param;
        }
    }
 
    T* TryAllocate() {//O(1)
        if (exempted.begin() != exempted.end()) {           //O(1)
            T* param = exempted.front();    //O(1)
            allotted.push_back(param);      //O(1)
            exempted.pop_front();           //O(1)
            return param;
        }
        else {
            return nullptr;
        }
    }
 
    void Deallocate(T* object) {//O(N)
        auto a = find(allotted.begin(), allotted.end(), object);//O(N)
        if (a != allotted.end()) {
            T* param = *a;
            exempted.push_back(param);          //O(1)
            allotted.erase(a);                  //O(end - a)
        }
        else {
            throw invalid_argument("");
        }
    }
 
    ~ObjectPool() {
 
    }
 
private:
    deque<T*> allotted, exempted;
};

@JaponDemon · 19.09.2018, 00:07

Например, взять другой контейнер с быстрым поиском, вместо дека. map set или что там ещё есть .

Добавлено через 1 минуту
А если удалять без проверки существования например ?

C++

1	allotted.erase(a);

Добавлено через 42 секунды
А нет, там UB

An invalid position or range causes undefined behavior.

@Vakarine · 19.09.2018, 00:11 **[ТС]**

Я бы попытался использовать другой контейнер, но методы Allocate и TryAllocate должны возвращать объекты в порядке FIFO, т.е. множество exempted объектов должно представлять собой очередь: методы [Try]Allocate должны извлекать объекты из её начала, а метод Deallocate должен помещать объект в её конец. Так что, как мне кажется, дек там лучше всего подойдет(queue не взял потому что у него нет degin и end).

MrGluck · 19.09.2018, 14:36

Vakarine, можно кешировать указатели в каком-нибудь std::unordered_set. То есть дополнительно хранить их в контейнере, предназначенном для поиска.
Однако, в любом случае надо сначала определить, является ли данный участок кода слабым местом. Вы профилировали?

Добавлено через 2 минуты
Плюс можно производить деаллоцирование кучками, то есть сначала помечать их "флагом протухания" или помещать в специальный контейнер, а в свободное для процессора время начинать процесс очистки. Тут всё уже от архитектуры зависит. Но, в любом случае, такие действия должны быть оправданы. Если у вас небольшое количество данных, то разницы в микросекундах не принесут профита. Как говорил дедушка Кнут, "Преждевременная оптимизация - корень всех бед".

@rat0r · 19.09.2018, 17:21

boost::multi_index с sequenced и ordered индексами

@Vakarine · 19.09.2018, 17:41 **[ТС]**

MrGluck, Ну, там сложности я посчитал(в коде комментарии), и у Deallocate самая большая сложность, вот и предположил, что это он так время съедает.

@DrOffset · 19.09.2018, 18:42

Сообщение от Vakarine

есть ли способ сделать это быстрее?

Сделать интрузивный контейнер. Например список.
Тогда элемент сам будет знать своих соседей, и можно будет безопасно удалить его за O(1) без поиска вообще. Можно будет также совместить удаление и вставку в другой контейнер в одну операцию.

@Vakarine · 19.09.2018, 18:50 **[ТС]**

DrOffset, Список - это queue? Но там ведь нельзя найти нужный элемент т.к нету begin и end, да и из него не удалить элемент, который ты перенес в другой список, если он не первый.

@DrOffset · 19.09.2018, 18:53

Vakarine, queue - это очередь.
Список - это list. Но не тот, который std::, с ним будут те же проблемы с поиском. А сделать свой - интрузивный (тут вы берете и идете гуглить что это), или взять из boost::intrusive_containers.

@Vakarine · 19.09.2018, 18:57 **[ТС]**

Понятно, пойду пробовать, спасибо.

@DrOffset · 19.09.2018, 21:14

Vakarine,
С бустом примерчик быстро пишется (все умолчания оставил как были):

Кликните здесь для просмотра всего текста

C++

#include <boost/intrusive/list.hpp>
#include <stdexcept>
#include <iostream>
 
using namespace boost::intrusive;
 
template <class T>
class ObjectPool {
    struct IntrusiveNode
        : T, list_base_hook<>
    { };
 
public:
    T * Allocate() {//O(1)
        if (!exempted.empty()) {       //O(1)
            allotted.splice(allotted.end(), exempted, exempted.begin()); // O(1)
            return &allotted.back();
        }
        else {
            IntrusiveNode * param = new IntrusiveNode;
            allotted.push_back(*param); //O(1)
            return param;
        }
    }
 
    T* TryAllocate() {//O(1)
        if (!exempted.empty()) {           //O(1)
            allotted.splice(allotted.end(), exempted, exempted.begin());
            return &allotted.back();
        }
        else {
            return nullptr;
        }
    }
 
    void Deallocate(T * object) {//O(1)
        IntrusiveNode * node = static_cast<IntrusiveNode *>(object);
 
        if(object && node->is_linked())
        {
            auto a = allotted.iterator_to(*node); // O(1)
            exempted.splice(exempted.end(), allotted, a); // O(1)
        }
        else {
            throw std::invalid_argument("");
        }
    }
 
    ~ObjectPool() {
        std::cout << "Allotted: " << allotted.size() << std::endl;
        std::cout << "Exempted: " << exempted.size() << std::endl;
    }
 
private:
    list<IntrusiveNode> allotted, exempted;
};
 
class A {};
 
int main()
{
    ObjectPool<A> pool;
 
    A * p1 = pool.Allocate();
    pool.Deallocate(p1);
 
    A * p2 = pool.Allocate();
    pool.Deallocate(p2);
}

http://rextester.com/DIRJQ73151

@Vakarine 0 / 0 / 0 Регистрация: 15.09.2018 Сообщений: 14
	19.09.2018, 18:57 [ТС]	10
	Понятно, пойду пробовать, спасибо. 0

@Vakarine 0 / 0 / 0 Регистрация: 15.09.2018 Сообщений: 14
	19.09.2018, 00:11 [ТС]	3
	Я бы попытался использовать другой контейнер, но методы Allocate и TryAllocate должны возвращать объекты в порядке FIFO, т.е. множество exempted объектов должно представлять собой очередь: методы [Try]Allocate должны извлекать объекты из её начала, а метод Deallocate должен помещать объект в её конец. Так что, как мне кажется, дек там лучше всего подойдет(queue не взял потому что у него нет degin и end). 0

MrGluck Форумчанин 8183 / 5033 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	19.09.2018, 14:36	4
	Vakarine, можно кешировать указатели в каком-нибудь std::unordered_set. То есть дополнительно хранить их в контейнере, предназначенном для поиска. Однако, в любом случае надо сначала определить, является ли данный участок кода слабым местом. Вы профилировали? Добавлено через 2 минуты Плюс можно производить деаллоцирование кучками, то есть сначала помечать их "флагом протухания" или помещать в специальный контейнер, а в свободное для процессора время начинать процесс очистки. Тут всё уже от архитектуры зависит. Но, в любом случае, такие действия должны быть оправданы. Если у вас небольшое количество данных, то разницы в микросекундах не принесут профита. Как говорил дедушка Кнут, "Преждевременная оптимизация - корень всех бед". 0

@rat0r 285 / 176 / 21 Регистрация: 16.02.2018 Сообщений: 666
	19.09.2018, 17:21	5
	boost::multi_index с sequenced и ordered индексами 0

@Vakarine 0 / 0 / 0 Регистрация: 15.09.2018 Сообщений: 14
	19.09.2018, 17:41 [ТС]	6
	MrGluck, Ну, там сложности я посчитал(в коде комментарии), и у Deallocate самая большая сложность, вот и предположил, что это он так время съедает. 0

@DrOffset 15880 / 8643 / 2114 Регистрация: 30.01.2014 Сообщений: 14,871
	19.09.2018, 18:42	7
	Сообщение от Vakarine есть ли способ сделать это быстрее? Сделать интрузивный контейнер. Например список. Тогда элемент сам будет знать своих соседей, и можно будет безопасно удалить его за O(1) без поиска вообще. Можно будет также совместить удаление и вставку в другой контейнер в одну операцию. 0

@Vakarine 0 / 0 / 0 Регистрация: 15.09.2018 Сообщений: 14
	19.09.2018, 18:50 [ТС]	8
	DrOffset, Список - это queue? Но там ведь нельзя найти нужный элемент т.к нету begin и end, да и из него не удалить элемент, который ты перенес в другой список, если он не первый. 0

@DrOffset 15880 / 8643 / 2114 Регистрация: 30.01.2014 Сообщений: 14,871
	19.09.2018, 18:53	9
	Vakarine, queue - это очередь. Список - это list. Но не тот, который std::, с ним будут те же проблемы с поиском. А сделать свой - интрузивный (тут вы берете и идете гуглить что это), или взять из boost::intrusive_containers. 0

Опции темы

Нужен совет в оптимизации кода

Решение