VPF::оптимизация эмуляции стека векторов

varnie

Дата 30.8.2008, 09:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 27.9.2007

Репутация: 0
Всего: 0

здравствуйте.
имеется класс для эмулирования работы со стеком:

Код


class CValue;
typedef boost::shared_ptr<CValue> CValuePtr;

class CStack {

    class CData;
    typedef boost::shared_ptr< CData> CDataPtr;
    
    class CData {
        friend class CStack;
        
        std::size_t _count;
        std::vector< CValuePtr, boost::fast_pool_allocator<CValuePtr> > _params;        
    public:
        CData():_count(0) {
            _params.push_back( CValuePtr());
        }
        CData(const CData &other): _count(other._count), _params(other._params){  }
        ~CData() { }
    private:
    
        const CValue &getValue(const std::size_t index) const {
            return *(_params[index]);
        }
        
        void setValue(const std::size_t index, const CValue &v) {
            _params[index].reset(new CValue(v) );
        }
       
        CData* clone()  {
            return new CData(*this);
        }
    };
private:
   
    std::stack< CData * > _data;
    CData *_pTop;
public:
    CStack() {
        _data.push(_pTop = new CData);
    }
    ~CStack(){  _data.pop(); delete _pTop;  assert(_data.empty()); }
    void push() {
         _data.push(_pTop = _pTop->clone());
    }
    void pop() {
      _data.pop();
      delete _pTop;
      _pTop = _data.top();
    }
    const CValue &getValue(const std::size_t index) const {
        return _pTop->getValue(index);
    }
    void setValue(const std::size_t index, const CValue &v) {
        _pTop->setValue(index, v);
    }

/*
  //вариант номер 2
  std::stack< CData * > _data;
  
public:
    CStack() {
        _data.push(new CData);
    }
    ~CStack(){ pop(); std::cout << "size=" << _data.size() << std::endl; if (!_data.empty()){ std::cout <<  "smth wrong"; } }
    void push() {
         _data.push( _data.top()->clone());
    }
    void pop() {
       delete _data.top();
      _data.pop();
    }
    const CValue &getValue(const std::size_t index) const {
        return _data.top()->getValue(index);
    }
    void setValue(const std::size_t index, const CValue &v) {
        _data.top()->setValue(index, v);
    }
    void setValueByIndex(const std::size_t index, const CValue &indexPos, const CValue &v) {
        _data.top()->setValueByIndex(index, indexPos, v);
    }
*/
};

хочется оптимизировать по времени исполения.

интересно то, что закомменченный вариант номер 2, в котором при кажд. увеличении стека запоминается указатель на его вершину для того, чтобы при многочисленных CStack::setValue, CStack::getValue нам не приходилось каждый раз обращаться к _data.top(), работает медленнее. от чего такое может быть?? или же это и есть случай преждевременной оптимизации, которая есть зло?

если есть другой подход к решению проблемы -- был бы рад о нем услышать. спасибо.

JackYF

Дата 30.8.2008, 09:34 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(varnie @ 30.8.2008, 08:06

)

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

Судя по коду, это вариант №1. Ничего не перепутал?

--------------------

Пожаловаться на меня как модератора можно здесь.

varnie

Дата 30.8.2008, 09:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 27.9.2007

Репутация: 0
Всего: 0

Цитата(JackYF @ 30.8.2008, 12:34)

Цитата(varnie @ 30.8.2008, 08:06

)

Судя по коду, это вариант №1. Ничего не перепутал?

упс. да, вы правы. я опечаталса выше.

JackYF

Дата 30.8.2008, 15:13 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Вопрос ещё в силе? Какой из вариантов работает медленнее?

--------------------

Пожаловаться на меня как модератора можно здесь.

varnie

Дата 30.8.2008, 16:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 27.9.2007

Репутация: 0
Всего: 0

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

JackYF

Дата 30.8.2008, 18:31 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(varnie @ 30.8.2008, 08:06

)

работает медленнее

Тогда давай подробнее, а, собственно, на каких функциях и в каком порядке он работает медленее?

--------------------

Пожаловаться на меня как модератора можно здесь.

varnie

Дата 30.8.2008, 20:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 27.9.2007

Репутация: 0
Всего: 0

JackYF,
ну вот есть у меня эта реализация стека. при кажд. заходе в некоторый блок (а-ля эмуляция вызова функции) мы делаем stack::push, далее отрабатывает этот блок, использующий в десятках своих мест stack::getValue и stack::setValue. причем, stack::setValue вызывается всего неск раз (для того чтобы занести нек. параметры в стек), а stack::getValue вызывается в разы больше (для многочисленных получений значений параметров из текущего стека). ну вот. а по выходу из этого обрабатываемого блока мы делаем stack::pop.

именно поэтому я и прикинул, что по-идее быстрее будет если мы при кажд увеличении/уменьшении стека будем запоминать указатель на его верхушку, а далее в getValue/setValue работать с стеком через этот указатель. но что-то эту скорость я неособо вижу) точнее, вообще не вижу.

как вариант, была мысль раскручивать стек и освобождать память только один раз, в деструкторе моего стэка, но это не применимо в том случае, если наш т.н. блок действий будет исполняться бесконечно и многократно вызывать др блоки (следовательно, вызывается Stack::push и мы быстро сожрем всю память, не возвращая ее после кажд выхода из блока, что не есть хорошо).

mes

Дата 31.8.2008, 02:08 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(varnie @ 30.8.2008, 20:01

)

именно поэтому я и прикинул, что по-идее быстрее будет если мы при кажд увеличении/уменьшении стека будем запоминать указатель на его верхушку, а далее в getValue/setValue работать с стеком через этот указатель. но что-то эту скорость я неособо вижу) точнее, вообще не вижу.

т.е Вы считаете что замена _data.top() на _pTop даст значительный прирост в скорости ?
В релизе при включенной оптимизации компилятор и так автоматически выкидывает все такие лишние вызовы..

Раз 20 прочитал что Вы написали, но полного смысла не уловил, чего Вы пытаетесь добиться

--------------------

http://opendots.net

jonie

Дата 31.8.2008, 09:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 15
Всего: 118

с памятью работать не так надо, лдя скорости... почитайте про quickheap на rsdn.ru ...

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »