Умные указатели и попытка избавиться от лишнего копирования - C/C++

Здравствуйте, Andy the Toad, Вы писали:

Ш>>3) Шаблоны выражений.
ATT>Можно чуть поподробнее указать направление?
здесь

Ш>>4) Компилятор с RVO.
ATT>Что такое RVO? К MSVC++ с Билдером это отношение имеет? А gcc?

здесь

MaximE wrote:

[]

> Те реализации шаблонов выражений с которыми я знаком (boost::lambda, boost::phoenix) и которые я сам писал (), не разрешаются в вызов подобной ф-ции. Они разрешаются в вызов ф-ции, которая принимает объект выражения, построенной компилятором из твоего выражения с перегруженными операторами.

... которые я сам писал (http://cvs.sourceforge.net/viewcvs.py/conststring/const_string/boost/boost/const_string/concatenation.hpp?rev=1.6&view=auto)

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

Шахтер wrote:

> Здравствуйте, MaximE, Вы писали:
>
> ME>Andy the Toad wrote:
>
> ME>[]
>
>>> Господа гуру — те, кто сумел дочитать все это до конца, подскажите, есть ли более изящное решение этой проблемы, свободное от указанных недостатков? Что здесь можно изменить или подправить или вообще переписать? Хотелось бы иметь хорошую общую идею, потому что классов, ждущих реализации по подобному принципу у меня уже как минимум четыре наберется.
>
> ME>Используй технику expression templates, ссылку тебе дал korzhik (http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html). Эта техника предназначена конкретно для решения твоей проблемы.
>
> Это не совсем точное утверждение. Основное назначение expression template -- вовсе не экономия на копировании, а возможность преобразования выражений типа
>
>

> Vector<double> v1,v2,v3;
>
> double c1=...,c2=...;
>
> v3 = c1 * v1 + c2 * v2;
>

>
> в вызов оптимизированной функции, которая сделает составную операцию разом.

Твое утверждение также далеко от истины.

Это техника для передачи выражений как аргументов ф-ций (кстати, именно это и написано в начале по вышеприведенной ссылке). Основное назначение — избежать промежуточные вычисления и создание временных объектов.

>

> void vector_mul_add_and_set(Vector<double> &result,double c1,const Vector<double> &v1,double c2,const Vector<double> &v2);
>

Те реализации шаблонов выражений с которыми я знаком (boost::lambda, boost::phoenix) и которые я сам писал (), не разрешаются в вызов подобной ф-ции. Они разрешаются в вызов ф-ции, которая принимает объект выражения, построенной компилятором из твоего выражения с перегруженными операторами.

> Надо ещё заметить, что полноценная реализация такой библиотеки -- занятие далеко не тривиальное. Кроме того, необходим хороший C++ компилятор.

Не сказал бы. Вот минимальный пример набранный за 15 мин., который, я думаю, даже на убогой шестерке будет работать. Ф-ция eval как раз и является ф-цией, которая принимает объект выражения и вычисляет его:

#include <iostream>

template<class T>
T const& eval(T const& t) { return t; }

template<class Model>
struct expr_concept {};

template<class T>
struct value_expr : expr_concept<value_expr<T> >
{
     typedef T type;
     T const& t_;
     value_expr(T const& t) : t_(t) {}
     friend T const& eval(value_expr const& self) { return eval(self.t_); }
     friend std::ostream& operator<<(std::ostream& s, value_expr const& self)
     { return s << self.t_; }
};

template<class T>
value_expr<T> val(T const& t) { return value_expr<T>(t); }

template<class T, class L, class R>
struct plus_expr : expr_concept<plus_expr<T, L, R> >
{
     typedef T type;
     L const& l_;
     R const& r_;
     plus_expr(L const& l, R const& r) : l_(l), r_(r) {}
     friend T eval(plus_expr const& self) { return eval(self.l_) + eval(self.r_); }
     friend std::ostream& operator<<(std::ostream& s, plus_expr const& self)
     { return s << '(' << self.l_ << " + " << self.r_ << ')'; }
};

template<class T, class L, class R>
struct mult_expr : expr_concept<mult_expr<T, L, R> >
{
     typedef T type;
     L const& l_;
     R const& r_;
     mult_expr(L const& l, R const& r) : l_(l), r_(r) {}
     friend T eval(mult_expr const& self) { return eval(self.l_) * eval(self.r_); }
     friend std::ostream& operator<<(std::ostream& s, mult_expr const& self)
     { return s << self.l_ << " * " << self.r_; }
};

template<class Model, class T>
plus_expr<typename Model::type, Model, T> operator+(expr_concept<Model> const& l, T const& r)
{
     return plus_expr<typename Model::type, Model, T>(static_cast<Model const&>(l), r);
}

template<class Model, class T>
mult_expr<typename Model::type, Model, T> operator*(expr_concept<Model> const& l, T const& r)
{
     return mult_expr<typename Model::type, Model, T>(static_cast<Model const&>(l), r);
}

int main()
{
     std::cout
         << (val(1) + val(2) * 3 + val(4) * 5 * 6 * 7 + 8 + 9) << " = "
         << eval(val(1) + val(2) * 3 + val(4) * 5 * 6 * 7 + 8 + 9) << std::endl
         ;
}

[max@my exp]$ scons
scons: Reading SConscript files ...
scons: done reading SConscript files.
scons: Building targets ...
g++ -fmessage-length=0 -ggdb -c -o exp.o exp.cpp
g++ -o exp exp.o
scons: done building targets.
[max@my exp]$ ./exp
((((1 + 2 * 3) + 4 * 5 * 6 * 7) + 8) + 9) = 864

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

Здравствуйте, Вадим Никулин, Вы писали:

ВН>Здравствуйте, Andy the Toad, Вы писали:

ВН>

ATT>>inline TMatrix operator * (TMatrix m1, const TMatrix &m2) // У первого аргумента убрать ссылку, у второго прибавить const
ATT>>{
ATT>> m1.Data *= m2->Data; //упрощенный вид реализации умножения
ATT>> return m1;
ATT>>}
ATT>>//--------------
ATT>>
ВН>

ВН>В этом случае у компилятора гораздо больше возможностей для оптимизации.

В общем случае спорное утверждение.
Про детали реализации бинарных операторов можно почитать здесь

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, korzhik, Вы писали:

Ш>>>>4) Компилятор с RVO.
ATT>>>Что такое RVO? К MSVC++ с Билдером это отношение имеет? А gcc?

K>>здесь

E>Интересно, а на практике кто-нибудь идею Mojo применяет? Или видел где-нибудь применение?
Не применяю, не видел.
если заинтерисовался, то вот ещё ссылка

Господа гуру от C++, помогите пожалуйста копнуть глубже в казалось бы тривиальную проблему — не сочтите за труд дочитать до конца. Есть желание реализовать некий класс, занимающий в памяти место, большее чем sizeof(int), однако у которого перегружены операторы, долженствующие возвращать сам экземпляр класса, а не указатель или ссылку на него. Пусть это будет TMatrix:

class TMatrix
{
    ...
public:
    friend TMatrix operator * (TMatrix &m1, TMatrix &m2);
    ...
};

Автоматически приходим к идее некоего "умного указателя", или точнее "ведущего указателя", когда сам массив данных выделяется динамически, а класс-обертка TMatrix содержит в себе указатель на этот массив. Тогда для реализации подержки операций вроде:

TMatrix m,m1,m2;

    m = m1 * m2;

нужно оформить наш класс например так:

struct TMatrixData{
    double a[4][4];
};
//--------------
class TMatrix
{
private:
    TMatrixData *Data;
public:
    TMatrix(){
        Data = new TMatrixData;
    };
    TMatrix(TMatrix &m){
        Data = new TMatrixData;
        memcpy(Data,m.Data,sizeof(*Data));
    }
    ~TMatrix(){
        delete Data;
    }
    TMatrix &operator = (TMatrix &m){
        memcpy(Data,m.Data,sizeof(*Data));
        return *this;
    }
    friend TMatrix operator * (const TMatrix &m1, const TMatrix &m2);
    ...
};
//--------------
inline TMatrix operator * (TMatrix &m1, TMatrix &m2)
{
TMatrix m; //(1)

    Data = m1->Data * m2->Data; //упрощенный вид реализации умножения

    return m; //(2)
}
//--------------

В точке (2) компилятор (как MSVC++ 6.0, так и C++ Builder 5) разворачивает код таким образом:

TMatrix rm = m;
m->~TMatrix();
return rm;

т.е. сначала вызывает copy-конструктор для некоего временного объекта, удаляет наш экземпляр m, созданный в точке (1) и возвращает из функции этот временный объект.
Зачем мне этот лишний вызов memcpy? Почему нельзя, чтобы код вида:

m = m1 * m2 * m3;

разворачивался так:

TempData1 = new TMatrixData;      //Data некоего временного объекта TMatrix
TempData1 = m1->Data * m2->Data;  //упрощенный вид реализации умножения
TempData2 = new TMatrixData;      //Data другого временного объекта TMatrix
TempData2 = TempData1 * m3->Data; //упрощенный вид реализации умножения
m->Data   = TempData2;
delete TempData1;
//TempData2 не удаляется, т.к. каким-то образом сигнализируется, что к нему был приравнен m->Data.

Т.е. хотелось бы избавиться от двух вызовов memcpy — одного явного, в операторе =, а другого неявного, в точке (2)
Если еще не надоело читать, то посмотрите мой подход к этой проблеме:

struct TMatrixData{
    double a[4][4];
    bool IsTemp;
};
//--------------
class TMatrix
{
private:
    TMatrixData *Data;
    TMatrix(TMatrixData *d){
        Data = d;
    };
public:
    TMatrix(){
        Data = new TMatrixData;
        Data->IsTemp = false;
    };
    TMatrix(TMatrix &m){
        if(m.Data->IsTemp){
            Data = m.Data;
            m.Data = NULL; //(1)
        }
        else{
            Data = new TMatrixData;
            memcpy(Data->a,m.Data->a,sizeof(*Data->a));
        }
        Data->IsTemp = false;
    }
    ~TMatrix(){
        if(Data) delete Data;
    }
    TMatrix &operator = (TMatrix &m){
        if(m.Data->IsTemp){
            if(Data) delete Data;
            Data = m.Data;
            m.Data = NULL; //(2)
            Data->IsTemp = false;
        }
        else{
            if(!Data){
                Data = new TMatrixData;
                Data->IsTemp = false;
            }
            memcpy(Data->a,m.Data->a,sizeof(*Data->a));
        }
        return *this;
    }
    friend TMatrix operator * (const TMatrix &m1, const TMatrix &m2);
    ...
};
//--------------
inline TMatrix operator * (TMatrix &m1, TMatrix &m2)
{
TMatrixData *d;

    d = new TMatrixData;
    d->IsTemp = true;

    d = m1->Data * m2->Data; //упрощенный вид реализации умножения

    if(m1.Data->IsTemp){ //(3)
        delete m1.Data;
        m1.Data = NULL;
    }
    if(m2.Data->IsTemp){ //(4)
        delete m2.Data;
        m2.Data = NULL;
    }

    return TMatrix(d);
}
//--------------

Т.е. во время умножения создается временный объект, который затем уничтожается в последующем вызове оператора * или переприсваивается в операторе =.
Есть несколько неудобств:
1) В точках (3) и (4) приходится явно отслеживать удаление m1.Data и m2.Data. Если набор операторов работы с объектом большой, то даже при оформлении этого момента в какую-либо функцию будет зря загромождаться код. Но это не так важно, тем более у меня сейчас возникла одна мысль — не зря ли я это делаю, но оставим это, ибо есть неудобство 2 и 3:
2) В точках (1) и (2) приходится модифицировать аргумент функции, поэтому этот аргумент нельзя объявить как const, а это плохо, потому что C++ Builder, будь он неладен, не понимает таких copy-конструкторов и операторов присваивания — в выражениях вида m = m1 * m2 он не понимает, что TMatrix нужно преобразовать к TMatrix&
3) Если мы где-нибудь в середине кода запишем TMatrix m = m1 * m2, то код развернется во всего один вызов оператора *, а объект m будет иметь Data->IsTemp == true, т.е. мы поимеем ссылку на временный объект, который не задумывался быть видимым для программиста. При первом же использовании его в операторах он примет значение NULL — понятно, чем это чревато.

Господа гуру — те, кто сумел дочитать все это до конца, подскажите, есть ли более изящное решение этой проблемы, свободное от указанных недостатков? Что здесь можно изменить или подправить или вообще переписать? Хотелось бы иметь хорошую общую идею, потому что классов, ждущих реализации по подобному принципу у меня уже как минимум четыре наберется.

Здравствуйте, Andy the Toad, Вы писали: ...

1) Счетчики ссылок + Copy on Write.
2) Счетчики ссылок + немутабельность + билдеры.
3) Шаблоны выражений.
4) Компилятор с RVO.

Короче, на эту тему можно не одну статью написать.

... << RSDN@Home 1.1.3 stable >>

Здравствуйте, Шахтер, Вы писали:

Ш>1) Счетчики ссылок + Copy on Write.
Как бы отследить этот on Write не трогая on Read...
Ш>2) Счетчики ссылок + немутабельность + билдеры.
Ш>3) Шаблоны выражений.
Можно чуть поподробнее указать направление?
Ш>4) Компилятор с RVO.
Что такое RVO? К MSVC++ с Билдером это отношение имеет? А gcc?
Ш>Короче, на эту тему можно не одну статью написать.

А где б почитать?

Здравствуйте, Andy the Toad, Вы писали:

ATT>inline TMatrix operator * (TMatrix m1, const TMatrix &m2) // У первого аргумента убрать ссылку, у второго прибавить const
ATT>{
ATT> m1.Data *= m2->Data; //упрощенный вид реализации умножения
ATT> return m1;
ATT>}
ATT>//--------------
ATT>

В этом случае у компилятора гораздо больше возможностей для оптимизации. Есть, конечно, и небольшие минусы. Например, возможность написать a+b=c, но я считаю, что этим можно пожертвовать.
И еще один момент. Ты ведь смотришь все это под релизом, правда?

Здравствуйте, Вадим Никулин, Вы писали:

ВН>И еще один момент. Ты ведь смотришь все это под релизом, правда?

Нет, под дебагом.
В релиз я пока не углубляюсь по той простой причине, что понадеявшись на оптимизирующие возможности компилятора я получу разное поведение на разных компиляторах. Хотелось бы самому поучавствовать в процессе формирования результирующего кода, тем более что я чувствую, что сам принцип пока еще не до конца отточен. Если компайлеру вдруг удастся удалить пару машинных тактов из экзешника — что ж, тем лучше. Мне нужна работа этих классов по крайней мере на двух компайлерах, а если завтра я вдруг захочу использовать эти классы под Линем?
Я не прав?

Andy the Toad wrote:

[]

> Господа гуру — те, кто сумел дочитать все это до конца, подскажите, есть ли более изящное решение этой проблемы, свободное от указанных недостатков? Что здесь можно изменить или подправить или вообще переписать? Хотелось бы иметь хорошую общую идею, потому что классов, ждущих реализации по подобному принципу у меня уже как минимум четыре наберется.

Используй технику expression templates, ссылку тебе дал korzhik (http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html). Эта техника предназначена конкретно для решения твоей проблемы.

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

Очень похожая ситуация разбирается в книге Страуструпа. И тоже на примере матрицы.
22.4.7 Временные массивы, копирование и циклы.

Здравствуйте, Andy the Toad, Вы писали:

ATT>Здравствуйте, Шахтер, Вы писали:

Ш>>1) Счетчики ссылок + Copy on Write.
ATT>Как бы отследить этот on Write не трогая on Read...

Грамотно расставить константность

Если объект имеет операторы неконстантного доступа (например, operator[], operator* и т.п.), которые можно использовать двояко (читать и изменять), то можно возвращать не простую неконстантную ссылку, а "умную ссылку" — адаптер, который различает чтение и запись.

class Object
{
public:
  Value const& at(int index) const;
  Value      & at(int index); // неконстантный доступ - выполняет copy on write

  const Value& operator[](int index) const // константный доступ - только чтение
  {
    return at(index);
  }

  SmartRef operator[](int index) // двоякий
  {
    return SmartRef(this,index);
  }

  class SmartRef
  {
    Object* host;
    int index;

    friend class Object;
    SmartRef(Object* h, int i) : host(h), index(i) {}
  public:
    operator Value const& () const { return ((const Object*)host)->at(index); }
    operator Value&       () const { return host->at(index); } // если кому-то потребовалась неконстантная ссылка
    Value& operator=(const Value& v) const { return host->at(index) = v; }
    // и ещё можно определить всякие операторы...
  };
};

Здравствуйте, MaximE, Вы писали:

ME>Andy the Toad wrote:

ME>[]

>> Господа гуру — те, кто сумел дочитать все это до конца, подскажите, есть ли более изящное решение этой проблемы, свободное от указанных недостатков? Что здесь можно изменить или подправить или вообще переписать? Хотелось бы иметь хорошую общую идею, потому что классов, ждущих реализации по подобному принципу у меня уже как минимум четыре наберется.

ME>Используй технику expression templates, ссылку тебе дал korzhik (http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html). Эта техника предназначена конкретно для решения твоей проблемы.

ME>--
ME>Maxim Yegorushkin

Это не совсем точное утверждение. Основное назначение expression template -- вовсе не экономия на копировании, а возможность преобразования выражений типа

Vector<double> v1,v2,v3;

double c1=...,c2=...;

v3 = c1 * v1 + c2 * v2;

в вызов оптимизированной функции, которая сделает составную операцию разом.

void vector_mul_add_and_set(Vector<double> &result,double c1,const Vector<double> &v1,double c2,const Vector<double> &v2);

Надо ещё заметить, что полноценная реализация такой библиотеки -- занятие далеко не тривиальное. Кроме того, необходим хороший C++ компилятор.

... << RSDN@Home 1.1.3 stable >>

Здравствуйте, korzhik, Вы писали:

Ш>>>4) Компилятор с RVO.
ATT>>Что такое RVO? К MSVC++ с Билдером это отношение имеет? А gcc?

K>здесь

Интересно, а на практике кто-нибудь идею Mojo применяет? Или видел где-нибудь применение?

... << RSDN@Home 1.1.4 beta 4 rev. 303>>

Здравствуйте, MaximE, Вы писали:

ME>MaximE wrote:

ME>[]

>> Те реализации шаблонов выражений с которыми я знаком (boost::lambda, boost::phoenix) и которые я сам писал (), не разрешаются в вызов подобной ф-ции. Они разрешаются в вызов ф-ции, которая принимает объект выражения, построенной компилятором из твоего выражения с перегруженными операторами.

ME>... которые я сам писал (http://cvs.sourceforge.net/viewcvs.py/conststring/const_string/boost/boost/const_string/concatenation.hpp?rev=1.6&view=auto)

Ты кстати доки с тестами случайно не доделал?

korzhik wrote:

> ME>... которые я сам писал (http://cvs.sourceforge.net/viewcvs.py/conststring/const_string/boost/boost/const_string/concatenation.hpp?rev=1.6&view=auto)
>
> Ты кстати доки с тестами случайно не доделал?

Юнит-тесты там были изначально.

Дока есть такая http://conststring.sf.net/, все не собирусь дописать. (хотя дописывать там особо и нечего).

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

	От:	korzhik
	Дата:	29.03.05 05:01
	Оценка:	17 (2)

	От:	MaximE
	Дата:	30.03.05 07:57
	Оценка:	8 (1)

	От:	MaximE
	Дата:	30.03.05 07:54
	Оценка:	7 (1)

	От:	korzhik
	Дата:	29.03.05 07:12
	Оценка:	3 (1)

	От:	korzhik
	Дата:	30.03.05 17:08
	Оценка:	1 (1)

От:	Вадим Никулин	Здесь
Дата:	29.03.05 06:08
Оценка:

От:	Хитрик Денис	RSDN
Дата:	29.03.05 08:03
Оценка:

От:	eao197	http://eao197.blogspot.com
Дата:	30.03.05 07:12
Оценка: