Строка GNU STL: здесь используется копирование при записи? - PullRequest
Новая
       6

Строка GNU STL: здесь используется копирование при записи?

14 голосов
/ 01 ноября 2010

(Отказ от ответственности: я не знаю, что стандарт C ++ может сказать по этому поводу ... Я знаю, я ужасен)

при работе с очень большими строками я заметил, что std :: string использует copy-on-write. Мне удалось написать наименьший цикл, который бы воспроизводил наблюдаемое поведение, а следующий, например, работает подозрительно быстро: 

#include <string>
using std::string;
int main(void) {
    string basestr(1024 * 1024 * 10, 'A');
    for (int i = 0; i < 100; i++) {
        string a_copy = basestr;
    }
}

при добавлении записи в тело цикла a_copy[1] = 'B'; фактическая копия, очевидно, имела место, и программа работала в течение 0,3 с вместо нескольких миллисекунд. 100 записей замедлили его примерно в 100 раз.

Но потом стало странно. Некоторые из моих строк не были записаны, только прочитаны, и это не отразилось на времени выполнения, которое было почти точно пропорционально количеству операций над строками. Немного покопавшись, я обнаружил, что простое чтение из строки все еще дает мне снижение производительности, поэтому я предположил, что строки GNU STL используют функцию копирования при чтении (?). 

#include <string>
using std::string;
int main(void) {
    string basestr(1024 * 1024 * 10, 'A');
    for (int i = 0; i < 100; i++) {
        string a_copy = basestr;
        a_copy[99]; // this also ran in 0.3s!
    }
}

Поработав некоторое время над своим открытием, я обнаружил, что чтение (с оператором []) из базовой строки также занимает 0,3 с для всей игрушечной программы. Действительно ли строки STL копируются при чтении или они вообще допускают копирование при записи? Я склонен думать, что оператор [] имеет некоторые гарантии против того, кто будет хранить ссылку, которую он возвращает, и позже будет писать в нее; это действительно так? Если нет, то что на самом деле происходит? Если кто-то может указать на какой-то соответствующий раздел в стандарте C ++, это также будет оценено.

Для справки я использую g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3 и GNU STL.

Ответы [ 3 ]

14 голосов
/ 01 ноября 2010

C ++ не различает operator[] для чтения и записи, а только operator[] для константного объекта и изменяемого (неконстантного) объекта. Поскольку a_copy является изменяемым, будет выбран изменяемый operator[], что приведет к принудительному копированию, поскольку этот оператор возвращает (изменяемую) ссылку.

Если важна эффективность, вы можете привести a_copy к const string, чтобы использовать const версию operator[], которая не будет копировать внутренний буфер. 

char f = static_cast<const string>(a_copy)[99];
13 голосов
/ 01 ноября 2010

Стандарт C ++ не запрещает или не предписывает копирование при записи или любые другие подробности реализации для std::string. При условии соблюдения требований семантики и сложности реализация может выбирать любую стратегию реализации по своему усмотрению.

Обратите внимание, что operator[] в строке, отличной от const, фактически является операцией «записи», поскольку она возвращает ссылку, которая может использоваться для изменения строки в любой точке вплоть до следующей операции, которая изменяет строку. Такая модификация не должна затрагивать копии.

Вы пытались профилировать один из этих двух? 

const string a_copy = basestr;
a_copy[99];

Или 

string a_copy = basestr;
const std::string& a_copy_ref = a_copy;
a_copy_ref[99];
2 голосов
/ 01 ноября 2010

Попробуйте этот код: 

#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

template<typename T>
void dump(std::ostream & ostr, const T & val)
{
    const unsigned char * cp = reinterpret_cast<const unsigned char *>(&val);
    for(int i=0; i<sizeof(T); i++)
        ostr
            << setw(2) << setfill('0') << hex << (int)cp[i] << ' ';
    ostr << endl;
}

int main(void) {
    string a = "hello world";
    string b = a;
    dump(cout,a);
    dump(cout,b);

    char c = b[0];

    dump(cout,a);
    dump(cout,b);
}

На GCC это вывод, который я получаю: 

3c 10 51 00
3c 10 51 00
3c 10 51 00
5c 10 51 00

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

...