К примеру Hierarchy Occlusion Culling, обход SceneGraph для поиска объектов являющихся RenderTarget'ами вода, зеркала и т.д. Постепенно проводиться оптимизация движка. В частности замер профайлером работу отдельных функций. На данный момент есть частое добавление объектов в динамический массив в каждом кадре. Как для от рисовки в текстуру теней так и для поиска видимых объектов. Для этого использовался ранее обычный std::vector с заранее вызванным std::vector::reserve. Почитав пост известного всем IronPeter'а Банановые шкурки, я подумал что сам метод std::vector::push_back уж очень универсален, там есть проверка на текущий размер с выделением памяти при необходимости и много других вызовов. К примеру std::vector::operator [] очень быстрый, но лишен универсальности, к примеру проверка выхода за диапазон, для этого есть std::vector::at. Иногда возникает вопрос, почему разработчик STL Александр Степанов не добавил быструю реализацию push_back, назвав ее к примеру fast_push_back?
Для некоторых частных специфических задач, требующих минимальной загрузки CPU, проверять выход за пределы не нужно вообще, к примеру как в этом случае - быстрое добавление данных с инкрементом указателя, который смещается к концу масса, причем размер массива уже известен.
Поэтому я написал свою довольно простую реализацию FastArray унаследовав с защищенным доступом от std::vector. Реализация выглядит так:
#ifndef __FASTARRAY_H__ #define __FASTARRAY_H__ #include "exceptions.h" #include <cassert> #include <vector> // Fast Dynamic Array template<typename T> class FastArray : protected std::vector<T> { private: typedef std::vector<T> BaseClass; T* last; public: typedef T* iterator; typedef const T* const_iterator; void resize(size_t count) { BaseClass::resize(count); last = &*BaseClass::end(); } void reserve(size_t count) { BaseClass::reserve(count); last = &*BaseClass::end(); } const_iterator end() const { return last; } iterator end() { return last; } const_iterator begin() const { return &*BaseClass::begin(); } iterator begin() { return &*BaseClass::begin(); } T& back() { assert(last && "NULL Pointer"); assert(!empty() && "Empty Array"); return *(last - 1); } const T& back() const { assert(last && "NULL Pointer"); assert(!empty() && "Empty Array"); return *(last - 1); } T& front() { assert(!empty() && "Empty Array"); BaseClass::front(); } const T& front() const { assert(!empty() && "Empty Array"); return BaseClass::front(); } bool empty() const { return &BaseClass::front() == last; } size_t size() const { assert(last >= &*begin() && "Out of Range"); return static_cast<size_t>(last - &*begin()); } size_t capacity() const { return BaseClass::capacity(); } void pop_back() { assert(last && "NULL Pointer"); assert(last >= &*begin() && "Out of Range"); --last; } void push_back(const T& val) { assert(last && "NULL Pointer"); *(last++) = val; } T& operator [] (size_t index) { assert(&*begin() + index < last && "Out of Range"); return *(begin() + index); } const T& operator [] (size_t index) const { assert(&*begin() + index < last && "Out of Range"); return *(begin() + index); } void clear() { last = &*begin(); } FastArray(size_t count, const T& val = T()) : BaseClass(count, val), last(&BaseClass::back()) { } FastArray() : last(&BaseClass::back()) { } ~FastArray() { } }; #endif |
Такая реализация обеспечивает быстрое добавление в конец и очистку массива, так-же работу с итераторами. Единственным минусом является небезопасное добавление, если число элементов превышает длину массива.
9 комментариев:
интересно, а как на счет цифер. Что дало на практике уменьшение проверок добавления через push_back?
В push_back не только проверки, метод insert довольно объемный. Цифры пока не проверял. Нужно сделать еще усреднение по времени встроенного профайлера, потом сделать замер. На синтетических тестах своя реализация быстрей.
И чем это отличается от boost::array, например?
А от stl контейнеров нельзя наследоваться нельзя, ибо их деструкторы невиртуальны.
boost::array не содержит push_back, и требует задания размера массива. Для задачи нужно добавлять по 1 элементу, размер массива не известен.
Насчет наследования, утечек памяти нету. Виртуальный конструктор не нужен, потому что я не использую объект данного класса, созданный через оператор new. Ведь в таком случае при удалении оператором по delete указателю на базовый класс, деструктор наследника вызван не будет. У меня иная ситуация.
правильно сделал!
я делал правда немного не так.
у меня два вида их:
template <typename T>
class feArray : public std::vector<T, _feMyStlAllocator<T> >
{ public: };
и второй - нагло списанный у Crytek (из FarCry SDK) их FastArra, всеми своими методами имитирующий std::vector но действующий немного не так:
MY_INLINE void push_back( const_reference p )
{
if ( m_NumElems >= m_NumAlloc )
{
FE_ASSERT( &p < m_pElements || &p >= ( m_pElements + m_NumAlloc ) );
m_NumAlloc = m_NumElems * 2 + 8;
m_pElements = (T*)my_realloc( m_pElements, m_NumAlloc * sizeof( T ) );
FE_ASSERT( m_pElements );
}
m_pElements[m_NumElems++] = p;
}
тоесть при достижении границы, память доаллоцируется и пока не достигли границы никаких аллокаций.
а так как у мну правило стараться заранее юзать reserve(), то и границу достигаем не часто. Пока доволен :)
Про наследование написано правильно, от STL контейнеров наследовать нельзя. Это ты сейчас нее используешь указатели на базовый класс, а кто даст гарантию, что через полгода ты не захочешь их использовать ?
Согласен, возможно наследование не совсем гибко, но тут очень специфический случай. Но от std::vector нужно только забота по работе с памятью и все. Как контейнер в качестве базового класса для данной задачи он идеальный кандидат. В этой ситуации даже сделав агрегирования std::vector вместо наследования от него, не поможет, если нужно будет сменить контейнер. Возможен еще вариант сделать его как параметр шаблона. В любом случае данное решение меня устраивает.
std::vector[int] v;
v.resize(100);
char * p = &v[0];
p[30] = 0; // никаких проверок никакого лишнего кода
выделил память 1 раз и делай что хочешь - поэтому никаких функций типа fast_push_back и нет - они просто не нужны.
Такая реализация неудобна.
Нужны методы push_back, size, empty,
pop_back, нужны итераторы.
Отправить комментарий