суббота, 2 мая 2009 г.

FastArray

Сейчас очень много сделано в движке. Есть некоторые недоделанные реализации чего либо.
К примеру 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 комментариев:

Neill комментирует...

интересно, а как на счет цифер. Что дало на практике уменьшение проверок добавления через push_back?

Andrey комментирует...

В push_back не только проверки, метод insert довольно объемный. Цифры пока не проверял. Нужно сделать еще усреднение по времени встроенного профайлера, потом сделать замер. На синтетических тестах своя реализация быстрей.

Анонимный комментирует...

И чем это отличается от boost::array, например?
А от stl контейнеров нельзя наследоваться нельзя, ибо их деструкторы невиртуальны.

Andrey комментирует...

boost::array не содержит push_back, и требует задания размера массива. Для задачи нужно добавлять по 1 элементу, размер массива не известен.
Насчет наследования, утечек памяти нету. Виртуальный конструктор не нужен, потому что я не использую объект данного класса, созданный через оператор new. Ведь в таком случае при удалении оператором по delete указателю на базовый класс, деструктор наследника вызван не будет. У меня иная ситуация.

iOrange комментирует...

правильно сделал!
я делал правда немного не так.
у меня два вида их:
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 контейнеров наследовать нельзя. Это ты сейчас нее используешь указатели на базовый класс, а кто даст гарантию, что через полгода ты не захочешь их использовать ?

Andrey комментирует...

Согласен, возможно наследование не совсем гибко, но тут очень специфический случай. Но от std::vector нужно только забота по работе с памятью и все. Как контейнер в качестве базового класса для данной задачи он идеальный кандидат. В этой ситуации даже сделав агрегирования std::vector вместо наследования от него, не поможет, если нужно будет сменить контейнер. Возможен еще вариант сделать его как параметр шаблона. В любом случае данное решение меня устраивает.

Анонимный комментирует...

std::vector[int] v;
v.resize(100);
char * p = &v[0];
p[30] = 0; // никаких проверок никакого лишнего кода

выделил память 1 раз и делай что хочешь - поэтому никаких функций типа fast_push_back и нет - они просто не нужны.

Andrey комментирует...

Такая реализация неудобна.
Нужны методы push_back, size, empty,
pop_back, нужны итераторы.