[c++] Лишние копирования в операторах

Dmitriy82


 

class string

{

  char* value;

  ....

  friend string operator+(const string& a, const string& b);

}

string operator+(const string& a, const string& b)

{

  string result;

  result->~string; // удалить созданную конструктором по умолчанию пустую строку

  result.value=new char[...

  strcat(...

  return result;    // тут вызывается лишний конструктор копирования 

}

Другие подходы, которые приходят вголову, тоже не работают (например, нельзя возвращать ссылку на string вместо string, т.к. тогда строка будет создаваться локально и удалится по выходу из функции (этого нельзя избежать динамическим созданием строки - тогда непонятно кто будет её удалять.
Насколько я смог разобраться в засыпанном template<че-то там traits allocators и т.д.> коде стандартных библиотек, там тоже происходит это лишнее копирование.
Можно ли написать действительно эффективную библиотеку строк с классическим операторным синтаксисом?

a10063

помнится у меня когда-то была подобная проблема
обошелся глобальным распределителем объектов - правда, такое решение имеет ряд минусов...

mirt1971

Да можно конечно




#include <cstring>

#include <cstdio>

class detached_string

{

 public:

  detached_string( char* data, size_t length ) throw :

   d_data( data 

   d_length( length )

  {

  }

  

  char* release throw 

  {

   char* data = d_data;

   d_data = 0;

   

   return data;

  }

  

  size_t length const throw 

  {

   return d_length;

  }

  

  ~detached_string throw 

  {

   if ( d_data )//not necessary, but for understanding :)

   {

    delete d_data;

   }

  }

  

 private:

  char* d_data;

  size_t d_length;

};

class string

{

  friend detached_string operator+( const string& st1, const string& st2 );

 

 public:

  string:

   d_data( new char[1] )

  {

   d_data[0] = '\0';

   d_length = 0;

  }

  

  string( detached_string ds ):

   d_data( ds.release 

   d_length( ds.length )

  {

  }

  

  const string& operator= ( detached_string ds )

  {

   if ( d_data )

   {

    delete d_data;

   }

   

   d_data = ds.release;

   d_length = ds.length;

   

   return *this;

  }

  

  string( const char* d )

  {

   if ( d )

   {

    d_data = strdup( d );

    d_length = strlen( d_data );

   }

   else

   {

    d_data = new char[1];

    d_data[0] = '\0';

    d_length = 0;

   }

  }

  

  string( const char* d, size_t length )

  {

   if ( d )

   {

    d_data = strdup( d );

    d_length = length;

   }

   else

   {

    d_data = new char[1];

    d_data[0] = '\0';

    d_length = 0;

   }

  }

  

  

  ~string throw 

  {

   delete d_data;

  }

  

  const char* c_str const throw 

  {

   return d_data;

  }

  

  size_t length const throw 

  {

   return d_length;

  }

  

 private:

  char* d_data;

  size_t d_length;

};

detached_string operator+( const string& st1, const string& st2 )

{

 const size_t l = st1.d_length + st2.d_length;

 char* data = new char[ l + 1 ];

 data[l] = '\0';

 memcpy( data, st1.c_str st1.length );

 memcpy( data + st1.length st2.c_str st2.length );

 

 return detached_string( data, l );

}

int main

{

 string st1 = "qw";

 string st2 = "wq";

 

 string st3 = st1 + st2;

 

 printf( "%s\n", st3.c_str );

}

mirt1971

Да. Хочу отметить, мне кажется проблема эта несколько надумана. Все современные компиляторы в таких случаях способны убирать лишнее копирование. ИМХО.

Dmitriy82

Идея немного громоздкая, но в целом нормально. Сам бы ни за что не додумался.
А вот насчет того что компиляторы оптимизируют - похоже это не так.
Компилятор из студии 2003.net на программе


 

class MyString

{

public:

	MyString {}

	MyString(MyString& s) 

	{

		cout<<"copy constructor"<<endl;

		// perform time-consuming duplication of data

	}

	const MyString& operator=(const MyString& a) 

	{

		cout<<"assignment"<<endl; 

		// perform time-consuming duplication of data too

		return *this;

	}

	friend MyString operator+(const MyString& a ,const MyString& b);

};

MyString operator+(const MyString& a ,const MyString& b)

{

	cout<<"add"<<endl;

	MyString result;

	return result;

}

int main(int argc, char* argv[])

{

	MyString a,b,c;

	c=a+b;

	char ch; cin>>ch;

	return 0;

}

выдает в release:
add
copy constructor
assignment
Ещё, похоже проблему можно решить счетчиком ссылок
(т.е. при копировании увеличивать счетчик ссылок, а данные не дублировать,
а при модификации если ссылок больше 1 - создавать копию и изменять её
но это будет во время выполнения, а хотелось бы на этапе компиляции.

rosali

На самом деле, кажись, достаточно сделать так:


 

class string

{

  char* value;

  ....  

  friend string operator+(const string& a, const string& b);

  private:

  class __tag123{};

  string( __tag123, string & a, string & b)

  {

    //сюда ставится код для *this = a + b

  } 

}; 

string operator+(const string& a, const string& b)

{

  return( string( __tag123 a, b ) );

}

Насколько я помню, при




A f

{

  ...

  return(A(...;

}

копирующий конструктор не вызывается.

rosali

выдает в release:
add
copy constructor
assignment

С помощью cout-ов нельзя выяснить, что может оптимизатор. Оптимизатор же не изменяет семантику, ты его попросил печатать, он и печетает. Надо ассемблер смотреть...

freezer

а если будет
x=a+b+c+d;

a10063

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

bleyman

А че, есть разные взгляды на то, что называть копированием строки? Поделись =)

a10063

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

lenabarskaya

Оптимизатор же не изменяет семантику, ты его попросил печатать, он и печетает.

Ведь ты же не поленился сходить по сцылке, которую дал ?
А потом открыть стандарт языка (например, п. 12.8.5 - в том драфте, который у всех в локалке валяецо).

mirt1971

Конечно громоздкая. На самом деле вместо detached_string нужно std::pair< std::auto_ptr< char >, size_t >, просто я хотел чтобы было понятно.

mirt1971

ИМХО вполне имеет право. Я точно не помню, но вроде операция копирования должна соответствовать нашим представлениям об операции копирования(грубо говоря никаких counter). Правда я этого точно не помню, нужно смотреть стандарт.

rosali

x=a+b+c+d;

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

Надо, чтобы operator + возвращал не string а объект вспомогательного класса, имеющего оператор кастинга в string. Тогда второй плюс будет отличаться от первого, и пусть он возвращает объект _другого_ вспомогательного класса, и т.д. А реальное сложение строк будет происходить только в этом самом кастинге. Кстати, можно даже исхитриться сделать так, чтобы количество плюсов было неогранниченное. Для этого вспомогательные классы должны называться как-нибудь так:


 

Plus<string,string>;

Plus<Plus<string,string>,string>;

Plus<Plus<Plus<string,string>,string>,string>;

ну в общем идея надеюсь понятна, причем она действительно

доводится до работоспособного состояния.
PS. По-моему, эта дискуссия не имеет _никакого_ отношения к программированию. Также как, например, олимпиадные задачи не имеют никакого отношения к науке...

Marinavo_0507

> По-моему, эта дискуссия не имеет _никакого_ отношения к программированию.
Ну не сказал бы, что конкатенация строк - типа не нужно на практике.
Наоборот, очень распространённая операция, которая заслуживает удобной библиотеки.

a10063

кстати, а разве STL-ный string при копировании не создает псевдокопию, а реально данные копирует только при внесении изменений?
мне кажется, я про такую идею у страуструпа читал...
дело в том, что в этом случае эффект от лишнего копирования минимален

Dmitriy82

2
> Надо ассемблер смотреть...
Я попробовал. Оказывается msvc не может сделать оператор+ подставляющимся
(хотя он у меня описан inline и состоит из одной строчки - может что неправильно?)


 

class MyString

{

private:

	int *value;

public:

	MyString(int i=0)     : value(new int) { *value=i; }

	MyString(MyString& s) : value(new int) { *value=*s.value; }

	const MyString& operator=(const MyString& a) 

	{

		this->~MyString;

		value=new int;

		*value=*a.value;

		return *this;

	}

	~MyString

	{

		delete value;

	}

	friend inline MyString operator+(const MyString& a ,const MyString& b);

};

inline MyString operator+(const MyString& a ,const MyString& b)

{

	return MyString(*a.value+*b.value);

}

int main(int argc, char* argv[])

{

	MyString a,b,c;

	c=a+b;

	return 0;

}

Но ты был прав: в случае если значение возвращается в виде
return Конструктор(...) копирования не происходит.
А если поменять у меня оператор+ на




inline MyString operator+(const MyString& a ,const MyString& b)

{

  	MyString result(*a.value+*b.value);

	return result;

}

- копирует. Чудеса.
------------------
Насчет A=B+C+D.
Тут detached_string справляется вполне терпимо:
B+C создает detached_string, которое без копирования конвертируется
в string и складывается с D, образуя ещё один detached_string (а только
что описанный string уничтожается которые присваивается A без копирования,
но с уничтожением предыдущего значения.
Подозреваю, что, опираясь только на описанную операцию сложения, лучше
транслятор сделать просто не может. Хотя конечно нечто вроде шапровского
string builder'а конечно будет эффективнее - там другие алгоритмы, и память, к примеру,
может сразу выделяться с запасом.
------------
> По-моему, эта дискуссия не имеет _никакого_ отношения к программированию. Также как,
> например, олимпиадные задачи не имеют никакого отношения к науке...
К программированию конечно никакого - очевидно ведь, что я хочу в идеале.
Чтобы оператору+ по ссылке передавалоь место куда он должен записать результат.
Вопрос чисто кодерский - как это реализовать на cpp, сохранив привычную
форму a=b+c. Чтобы не пришлось писать
add(string& a,const string& b,const string& c);
и string::add(a,b,c).
-------------
:
>кстати, а разве STL-ный string при копировании не создает псевдокопию, а реально данные
>копирует только при внесении изменений?
>мне кажется, я про такую идею у страуструпа читал...
>дело в том, что в этом случае эффект от лишнего копирования минимален
Я писал, что счетчик ссылок решает эту проблему(возможно, наиболее эффективно,
т.к. он кроме этого предотвращает лишние копирования и в других случаях и почему
мне интересны другие решения.
Короче, тут я рассматриваю c++ как язык, который позволяет сделать все что угодно
в естественной для пользователя форме, но возможно посредством жутких
извратов в закрытой части(реализации).
>по мне вообще не надо писать класс строки - надо брать из STL
Для строк конечно я бы стал использовать STL. Но строки это был
просто самый простой естественный пример, который пришел мне в голову.
Другой пример - длинная арифметика, когда число хранится по разрядам
в массиве произвольной длины. А интересовало меня решение проблемы
в общем.

Dasar

> Чтобы оператору+ по ссылке передавалоь место куда он должен записать результат.




ostringsteram oss;

oss << "asfsdf" << "sfaf" << "123123";

или




class Cache

{

  ostringstream oss;

public:

  Cache& operator +  (string s)

  {

    oss << s;

    return *this;

  }

  operator string

  {

     return oss.getString;

  }

};

использование:




string v = Cache + a + b + c;

mirt1971

Если мне не изменяет склероз, последнее выражение может запросто отработать так: Cache + (a + b + c). А это не есть гут. Придется самому скобки расставлять.

Dasar

вроде не может
у Operator-а '+' - левый приоритет

Dasar

Если скобки ползают, то вот такие выражения перестают работать:




int i = MinInt + MaxInt + MaxInt

mirt1971

Вообще говоря перестают. Но по факту не перестают.

Marinavo_0507

А с чего бы им переставать работать?

mirt1971

Это зависит от реализации(машины). В большинстве случаев(арифметика в кольце не перестают.

rosali

Ну не сказал бы, что конкатенация строк - типа не нужно на практике.
Наоборот, очень распространённая операция, которая заслуживает удобной библиотеки.

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

Marinavo_0507

> То что написано в STL надо воспринимать как "лучший вариант", даже если не до конца понимаешь всех его прелестей
Какой-то пораженческий подход.
Я против.

freezer

а может так?


 

class stringsum: vector<const string&>

{

  size_t sz;

public:

    stringsum(const string& a, const string& b): vector<const string&>(2 sz(0)

   {

     (* this)[0]=a;

     (* this)[1]=b;

     sz=a.size+b.size;

   }

   stringsum(const stringsum& ss):vector<const string&>(ss.size ss.begin sz(ss.sz){}

   stringsum(const stringsum& ss, const string s):vector<const string&>(ss.size ss.begin sz(ss.sz+s.size{push_back(s);}

   void ToString(string& s)

   {

        s.resize(sz);

        char* p = const_cast<char*>(s.c_str;

        for(size_t i=0,n;i<size;p+=n, i++)

        {

            n=(*this)[i].size;

            strncpy(p, (*this)[i].c_str n);

        }

        *p=0;

   }

};

class faststring: public string

{

public:

// тут всяческие конструкторы и т.д.

   stringsum operator+(const string& s) {return stringsum(*this, s);}

   const stringsum& operator = (const stringsum& ss)

  {

      ss.ToString(*this);

      return ss;

  }

};

stringsum operator+(const stringsum& ss, const string& s)

{

   return stringsum(ss, s);

}

я это не проверял, так что если не заработает - не ругайте

Оставить комментарий