Быстрый бассейн распределителя для игры в C++


Я реализовал следующий бассейн распределитель в C++:

template <typename T>
struct pool {
private:
    struct node {
        node*   next;
        T       element;
    };

private:
    std::vector<node*>  m_Chunks;
    node*               m_Head          = nullptr;
    uint64              m_MaxElements   = 0;
    bool                m_Resizable;

public:
    pool(pool const&)               = delete;
    pool& operator=(pool const&)    = delete;

    pool(uint64 nElems, bool resiz = false)
        : m_Resizable{ resiz } {
        m_Head = alloc_chunk(nElems);
    }

    pool(pool&& o) 
        : m_Chunks{ std::move(o.m_Chunks) }, m_Head{ o.m_Head },
        m_MaxElements{ o.m_MaxElements }, m_Resizable{ o.m_Resizable } {
    }

    pool& operator=(pool&& o) {
        for (auto n : m_Chunks) {
            std::free(n);
        }
        m_Chunks        = std::move(o.m_Chunks);
        m_Head          = o.m_Head;
        m_MaxElements   = o.m_MaxElements;
        m_Resizable     = o.m_Resizable;
        return *this;
    }

    ~pool() {
        for (auto n : m_Chunks) {
            std::free(n);
        }
    }

    operator bool() const {
        return m_Chunks.size();
    }

    T* alloc() {
        if (!m_Head) {
            if (m_Resizable) {
                m_Head = alloc_chunk(m_MaxElements);
                if (!m_Head) {
                    return nullptr;
                }
            }
            else {
                return nullptr;
            }
        }
        auto h = m_Head;
        m_Head = m_Head->next;
        return &h->element;
    }

    void free(T* ptr) {
        if (!ptr) {
            return;
        }
        uint8* mem_raw = reinterpret_cast<uint8*>(ptr);
        mem_raw -= offsetof(node, element);
        node* mem_head = reinterpret_cast<node*>(mem_raw);
        mem_head->next = m_Head;
        m_Head = mem_head;
    }

private:
    node* alloc_chunk(uint64 num) {
        uint64 alloc_sz = sizeof(node) * num;
        node* mem = reinterpret_cast<node*>(std::malloc(alloc_sz));
        if (!mem) {
            return nullptr;
        }
        m_Chunks.push_back(mem);
        node* it = mem;
        for (uint64 i = 1; i < num; ++i, ++it) {
            it->next = it + 1;
        }
        it->next = nullptr;

        m_MaxElements += num;
        return mem;
    }
};

Это реализация хорошо/правильно? Я могу сделать код более высокого качества-то? Я написал небольшой тест, стресс-тесты, и вроде бы ОК, производительность от 5 до 10 раз лучше, чем оператор по умолчанию новые.

Есть современные элементы с++ я могу использовать? Я выучил C++11 и 14 в этом году в колледж, и я пытался использовать мои знания. Я знаю, что это должно означать, что я должен сделать исключение-безопасный, но игры, как правило, не использовать исключения (вот почему я включил оператор bool для минимальной проверки ошибок), поэтому я решил не.

Редактировать: тестовый код, который я использовал

template <typename FN>
void measure_exec(const char* name, FN f) {
    auto start = std::chrono::steady_clock::now();
    f();
    auto t = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start);
    std::cout << name << " took " << t.count() << "ms." << std::endl;
}

struct message {
    int     id;
    double  timestamp;
};

int main(void) {
    std::srand(std::time(nullptr));
    std::vector<message*> control;
    std::vector<message*> test;
    measure_exec("Pool", [&]{
        mem::pool<message> pool{ 32, true };
        for (uint64 i = 0; i < 200000; ++i) {
            if (i % 15) {
                // Allocate
                int r_id = std::rand();
                double r_time = double(std::rand()) / std::rand();

                auto t = pool.alloc();
                t->id = r_id;
                t->timestamp = r_time;
                test.push_back(t);
            }
            else if (control.size()) {
                // Delete
                uint64 idx = std::rand() % control.size();
                test.erase(test.begin() + idx);
            }
        }
    });
    measure_exec("New", [&]{
        for (uint64 i = 0; i < 200000; ++i) {
            if (i % 15) {
                // Allocate
                int r_id = std::rand();
                double r_time = double(std::rand()) / std::rand();

                control.push_back(new message{ r_id, r_time });
            }
            else if (control.size()) {
                // Delete
                uint64 idx = std::rand() % control.size();
                control.erase(control.begin() + idx);
            }
        }
    });
    std::cin.get();
    return 0;
}

Обратите внимание, что я не ничего подобного испытанное прежде, этот метод испытания был полный выстрел в темноте. Я знаю, что из-за рандома оно может быть несправедливым, но повторный анализ дал аналогичные результаты. Да я знаю, я не свободной памяти но я не думаю, что это важно, что много.



Комментарии
1 ответ

Комментарий на тестирование

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

template <typename T>
struct pool
{
private:
node* m_head = nullptr;
node* m_tail = nullptr;
std::size_t m_max = 0;
bool m_resize= false;

public:
pool(pool const&) = delete;
pool& operator=(pool const&) = delete;
pool(uint64 nElems, bool resiz = false)
: m_max(nElems)
, m_resize(resiz) {
allocBlock();
}
pool(pool&& o) nothrow {
swap(o);
}
pool& operator=(pool&& o) nothrow {
swap(o);
return *this;
}
void swap(pool& other) nothrow {
using std::swap;
swap(m_head, other.m_head);
swap(m_tail, other.m_tail);
swap(m_max, other.m_max);
swap(m_resize, other.m_resize);
}
operator bool() const {
return m_head != m_tail;
}

T* alloc() {
if ((m_head == m_tail) && m_resizable) {
allocBlock();
}
return m_head == m_tail ? nullptr : m_head++;
}

void free(T* ptr) {}

private:
void allocBlock() {
uint64 alloc_sz = sizeof(T) * m_max;
m_head = m_tail = reinterpret_cast<T*>(std::malloc(alloc_sz));
if (m_head == nullptr) {
throw std::bad_alloc;
}
m_tail += m_max;
}
};

Комментарий Код

Следует отметить перемещении оператора noexcept.

    pool(pool&& o)  // Why is this not noexcept here.

Они должны быть noexcept в любом случае хорошо, чтобы язык полиции, что для вас (он прекращается, если она на самом деле бросает). Также он может помочь, если вы используете ваш бассейн со стандартной библиотеки, так как она позволяет некоторые оптимизации.

Уверены, что ваш объект является недействительным после переезда. И не вызовет никаких проблем, если правильно использовать.

    pool(pool&& o) 
: m_Chunks{ std::move(o.m_Chunks) }, m_Head{ o.m_Head },
m_MaxElements{ o.m_MaxElements }, m_Resizable{ o.m_Resizable } {
}

Но я думаю, что это может вызвать проблемы при неправильном использовании. В m_Head указатель по-прежнему указывает на цепочку элементов. Таким образом, вы можете случайно использовать это и создать реальные проблемы для остальных распределителя, который просто взял собственности на память.

Стандартный способ реализовать это, используя своп(). Смотри мой выше реализации. Такой ручки ситуации, как это в безопасный способ.

Же комментарии по поводу перемещения оператора присваивания.

Но это выглядит странно.

    pool& operator=(pool&& o) {
for (auto n : m_Chunks) {
std::free(n);
}

Ты свободна вся память. Но голова все точки в этой цепи и может быть использован повторно. Я думаю, что это наверняка ошибка. Движение не должно быть освобождения памяти.

Это странно.

    operator bool() const {
return m_Chunks.size();
}

Я бы сделал это возвратит true, если есть свободная память. Не если мы когда-нибудь успешно выделенной памяти. Но я не читал стандартный распределитель документации. Так что может быть то, что вы хотите (хотя я сомневаюсь).

Почему ты используешь uint8?

        uint8* mem_raw = reinterpret_cast<uint8*>(ptr);

Если этого не будет char*. Вызов offsetof() возвращает смещение в байтах. Чар по определению укладывается в 1 байт, таким образом, char* это 1 байт адресный диапазон. Также стандарт содержит специальные свойства для char* что других целочисленных типов нет.

Также uint8 тип не является стандартным, хотя std::uint8_t является стандартным. Но это не должна быть определена. Если он определен, то это ровно 8 бит, но если это не доступно, типа не доступен.

Комментарии о тестирование код.

Не дают вектор, чтобы расширить.

std::vector<message*> control;
std::vector<message*> test;

В противном случае ваш тестируете код менеджера памяти. Которая очень сложна, и даст вам разные результаты (потому что память все готово покопался в предыдущем тесте).

Поэтому предварительно выделить размер векторов (так они не перераспределять во время теста).

control.reserve(2000000);
test.reserve(2000000);

Это способ небольшой тест.

    for (uint64 i = 0; i < 200000; ++i) {

Оба этих счетчиков будет готово в мгновение ока. Вы хотите, чтобы тест, который длиться пару секунд получить реальную информацию.

У вас не работает конструктор.

            // Allocation but no construction
auto t = pool.alloc();
// Allocation and construction.
new message{ r_id, r_time };

Вы могли бы использовать оператор new, чтобы сделать их более похожими. Но лично я бы переопределить оператор new/delete, в результате чего он использует свой бассейн.

Время испытания будет преобладать этот вызов.

            uint64 idx = std::rand() % control.size();
test.erase(test.begin() + idx);

Вы заставляете двигаться все итераторы в векторе. А не стирая его просто освободить память и установить указатель на nullptr. Это будет гораздо лучше, испытания.

Вы должны использовать точно такой же код для обоих тестов. Единственная разница должна быть аллокатор используется. Вы должны иметь один тест, который использует пользовательский аллокатор. А второй тест использует аллокатор, который просто называет новый/удалить под капотом.

template<typename T>
class normal
{
public:
T* alloc() {return reinterpret_cast<T*>(new char[sizeof(T)]);}
void free(T* ptr) {delete [] reinterpret_cast<char*>(ptr);}
};
int main(void)
{
std::size_t testSize = 200'000'000;
std::vector<message*> control;
std::vector<message*> test;

control.reserve(testSize);
test.reserve(testSize);

measure_exec("Pool", [&]{mem::pool<message> pool{ 32, true }; runtTest(testSize, test, pool);});

measure_exec("New", [&]{mem::normal<message> pool;runtTest(testSize, control, pool);});
std::cin.get();
}

6
ответ дан 6 февраля 2018 в 11:02 Источник Поделиться