Несколько подробностей об std::string

Недавно заинтересовался реализацией std::string в libstdc++. Не в связи с принятием нового стандарта, а чтобы разобраться. Благо требования к строковму типу почти не изменились.

Основным средством для анализа кода несомненно является метод пристального вглядывания, но чтобы сузить область вглядывывания и сделать процедуру более захватывающей можно реализовать для строки идиому «трассер» подсмотренную в «C++ Templates: The Complete Guide». Трассировка позволяет выявлять подозрительные интересные операции над строками.

Как известно, std::string это псевдоним для std::basic_string<char> и нам ничего не мешает определить std::basic_string<X>. В X можно определить несколько статических счетчиков и итерировать их в конструкторе, деструкторе и остальных методах. Выполняя разные операции над такой строкой можно будет проследить эффективность применяемых алгоритмов в терминах количества операций.
Кроме того, в g++ для std::string a(«entrails»); выражение
std::cout << reinterpret_cast<char*>(*((void**)(&a)));
выведет содержимое строки. Т.е. std::string — является, по сути, указателем на char.
Вобщем, эти и другие шокирующие поднобности под катом.

Структура

std::string декларируется как:

  typedef basic_string<char>    string;

basic_string<char>, в свою очередь, является псевдонимом для:

template<typename _CharT, typename _Traits = char_traits<_CharT>, typename _Alloc = allocator<_CharT> >  class basic_string; 

Определение basic_string выполнено в файлах c++/bits/basic_string.h c++/bits/basic_string.tcc.

Если убрать все методы класса, то останется

template<typename _CharT, typename _Traits, typename _Alloc>
class basic_string{
public:
     static const size_type    npos = static_cast<size_type>(-1);
private:
    struct _Rep_base{
        size_type            _M_length;  //по умолчанию инстанцируется в size_t
        size_type            _M_capacity;
        _Atomic_word   _M_refcount;
    };
    struct Rep:_Rep_base{
        static const size_type         _S_max_size; //(((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4
        static const _CharT            _S_terminal;   //терминальный символ. Инициализируется величиной _CharT()
        static size_type                    _S_empty_rep_storage[]; // Массив заполняемый нулями длиной (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /sizeof(size_type)
    };

    struct _Alloc_hider : _Alloc{    
        _Alloc_hider(_CharT* __dat, const _Alloc& __a) : _Alloc(__a), _M_p(__dat) { } 
       _CharT* _M_p; // указатель на массив символов. 
      };  
      mutable _Alloc_hider      _M_dataplus; //единственный не статический член класса string
};

, что в свою очередь выраждаются в единственный указатель. Причем указатель указывает не на начало выделенного куска памяти, а как показано на рисунке, _M_p указывает на начало массива _CharT.
Такая хитрая структура достигается за счет разделения инициализации на два этапа. Внутри конструктора std::string сначала вызывается метод allocate() аллокатора, затем construct(). Allocate() с помощью malloc() выделяет необходимый кусок памяти, а construct() вызывает placement new с нужным смещением относительно начала выделенной области. Смещение определяется на этапе компиляции, поэтому destruct() и deallocate() не имеют проблем с вычислением исходного адреса.
Как написано в basic_string.h, такая процедура конструирования реализована для того чтобы переменная std::string являлась указателем на массив элементов строки. Тогда gdb способен показывать содержимое std::string.

Картинка вроде бы получилась самодокументируемая, однако замечу, что _M_refcount занимает 4 байта, но выравнивается до 8(для x86-64). Строки 1) и 2) будут занимать одинаковый объем памяти. X — это класс трассера, но об этом позже. Сначала несколько слов о статических членах класса std::string.
Казалось бы npos в представлении не нуждается. Но… это не максимальная возможная длина std::string это лишь максимальное значение типа std::string::size_type. Максимальная длина строки как минимум в четверо меньше и она определяется статическим членом:
_S_max_size;

  template<typename _CharT, typename _Traits, typename _Alloc>
    const typename basic_string<_CharT, _Traits, _Alloc>::size_type
    basic_string<_CharT, _Traits, _Alloc>::
    _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;

Почему выбрана именно четверть — мне выяснить так и не удалось.
_S_terminal — символ конца строки он инициализируется конструктором без параметров при запуске программы.

Подсчет ссылок

Теперь мы подошли к отдельной теме подсчета ссылок. Подсчет ссылок на строку упоминается в стандарте, но не является его требованием.
Переменная _S_empty_rep_storage является тем блоком памяти на который ссылаются все пустые строки создаваемые в программе.
Количество ссылок хранится в поле переменной _M_refcount.
_M_refcount:

• -1: строка имеет одну ссылку, увеличение количества ссылок не возможно;
• 0: нормальное значение. существует только одна строка с таким содержанием;
• n>0: существуют n+1 строк с таким содержанием. (при работе в многопоточной программе для таких строк требуются блокировки)

Не смотря на то, что _M_refcount при значении -1 должен запрещать «ленивое» конструирование строки, в публичном интерфейсе std::string нет метода позволяющего включать или выключать подсчет ссылок. Существует макроопределение _GLIBCXX_FULLY_DYNAMIC_STRING вроде бы предназначенное для этого, но в моих тестах оно не заработало, глубже разбираться я не стал. В целом эти ссылки просто переносят выделение памяти с вызова констркутора к моменту первой записи в строку и иногда дают о себе знать при работе в мультипоточном режиме. Helgrind и drd выдают нетривиальные подсказки по этому поводу.

Трассер

Посмотрим теперь насколько хорошо методы класса std::string реализуют свои действия. А измерять качество действий будем в количестве операций проводимых над символами строки. Для этого будем использовать идиому «трассер». Она предназначается для отладки контейнеров и заклюается в создании класса подсчитывающего операции производимые над ним. Инстанцируя контейнер таких классов легко можно подсчитать количество оперций сравнения например при сортировке или при выполнении любого другого действия над контейнером. Ну а std::string более или менее подпадает под определение контейнера, соответственно строку можно исследовать с помощью этой идиомы. Можно прикинуть какие конструкторы, методы, алгоритмы более эффективны в тех или иных ситуация. Собственно, вот наш

struct X{
        char v; //value

        X():v(){ X::c[ctor]++; };
        X(char x):v(x){ X::c[ctor]++; };
        X(X const& x):v(x.v) { X::c[copy]++; };
        ~X(){ X::c[dtor]++; };

        X& operator=(X const& x) { X::c[assgn]++; v=x.v; return *this; };
        X& operator=(char x) { X::c[assgn]++; v = x;   return *this; };
        X& operator()(char x) { X::c[cast]++; v = x;   return *this; };// X a = X('c');
        operator char() const { X::c[cast]++; return v; };             // char x = a;
        bool operator==( X const & x) const { X::c[eql]++; return v == x.v; };
        bool operator==( char x) const { X::c[eql]++; return v == x; };
        bool operator<( X const& x) const { X::c[lss]++; return v < x.v; };    
        bool operator<( int x) const { X::c[lss]++; return v < x; };    //for boost


        enum { ctor=0, copy, assgn, dtor, lss, eql, cast, last };    
        static int c[]; //counters
        static ::std::string n[]; //names of the counters
        static void show(const ::std::string &title, const ::std::string& end);
        static void head(const ::std::string &header);
};

Структура X имеет одно регулярное поле класса char v; — его значение. Два статических — массив счетчиков и массив имен для этих счетчиков. Подсчитываются вызовы конструкторов, деструкторов, присваиваний, сравнений(==,<) и преобразований к/от char. Всего семь счетчиков. Два статических метода show и head предназначены для визуализации результатов. Show выводит значения счетчиков и обнуляет их. Head показывает имена счетчиков.
Для калибровки трассера посмотрим как он подсчитывает операции в элементарных ситуациях:

        X::head();
        X::show("{");
{       //single operations
        X a;
        X::show("X a;");
        a = '1';
        X::show("a = '1';");
        X b = a;
        X::show("X b = a;");
        X c(a);
        X::show("X c(a);");
        c('e');
        X::show("c('e');");
        c = b;
        X::show("c = b;");
        (c = b) = 'e';
        X::show("(c=b)='e';");
        c < b;
        X::show("a < b;");
        a == b;
        X::show("a == b;");
}
        X::show("}");

Т.к. калибровка выполняется в начале приложения, то в эту таблицу попадает конструктор статического терминального символа _S_terminal. Его конструктор посчитан в первой строке.
В следующей таблице показано конструирование пары массивов:

{
        X::show("{");
        X a[10];
        X::show("X a[10];");
        std::copy(ch,ch+10,a);
        X::show("std::copy(ch,ch+10,a);");
        X b[10] = { 'o' };
        X::show("X b[10] = {'o'};");
        std::copy(a,a+10,b);
        X::show("std::copy(a,a+10,b);");
}
        X::show("}");

Теперь перейдем к строкам. Назовем нашу трасситуемую строку так typedef std::basic_string<X> xs;
Конструирование пустых строк, как и ожидалось, не производит операций над символами.

{
        X::head();
        X::show("{");
        const xs s1; 
        X::show("const xs s1;");
        xs s2(s1);
        X::show("xs s2(s1);");
        xs s3 = s1; 
        X::show("xs s3 = s1;");
}
        X::show("}");

Следующая таблица говорит сама за себя. Смутило, что при указании длины(s2) количество операций значительно меньше чем в случае s1. Более того строки конструируемые на основе s1 и s2 повели себя разным образом. Для s6 ленивое конструирование сработало, для s5 — нет. Заполняющий конструктор так вообще удивил — откуда-то взялись дополнительные копирования и деструкторы.

Теперь несколько базовых операций. Неожиданно, результат для resize получился значительно хуже чем для reserve:

{
	X::head();
	X::show("{");
	xs s1((X*)"1234567890");
	X::show("xs s1((X*)"1234567890");");
	xs s2((X*)"1234567890",7);
	X::show("xs s2((X*)"1234567890",7);");
	xs s3(10,'a');
	X::show("xs s3(10,'a');");
	xs s4(s1.begin(), s1.begin()+7);
	X::show("xs s4(s1.begin(), s1.begin()+7);");
	xs s5(s2);
	X::show("xs s5(s2);");
	s5[0]='a';
	X::show("s5[0]='a';");
	xs s6(s1);
	X::show("xs s6(s1);");
	s6[0]='a';
	X::show("s6[0]='a';");
	xs s7(s1,1,5);
	X::show("xs s7(s1,1,5);");
	#if __cplusplus > 199711L
	xs s8 = []()->xs{xs a((X*)"ololo");return a;}();
	X::show("xs s8=[]()->xs{xs a((X*)"lol");return a;}();");
	#endif
//----------------------------------------------------------------

	int a = s1.size();
	X::show("int a = s1.size();");
	s1.resize(100);
	X::show("s1.resize(100);");
	s2.reserve(100);
	X::show("s2.reserve(100);");
	s1.erase();
	X::show("s1.erase();");
	s1.insert(0,s2);
	X::show("s1.insert(0,s2);");
	s1.insert(0,s2,2,4);
	X::show("s1.insert(0,s2,2,4);");

//----------------------------------------------------------------

	X::show("s3 = s1;");
	s3 == s1;	
	X::show("s3 == s1;");
	s2 != s1;
	X::show("s2 != s1;");
	s1 > s2;
	X::show("s1 > s2;");

        std::equal(s1.begin(),s1.end(),s2.begin());
        X::show("equal(s1.begin(),s1.end(),s2.begin());");
        std::mismatch(s1.begin(),s1.end(),s2.begin());
        X::show("mismatch(s1.begin(),s1.end(),s2.begin());");
        
        std::copy(s1.begin(),s1.end(),out_it);
        std::cout << std::endl; 
        X::show("copy(s1.begin(),s1.end(),out_it);");
        
        std::sort(s1.begin(),s1.end());
        X::show("std::sort(s1.begin(),s1.end());");
        std::swap(s1,s2);
        X::show("std::swap(s1,s2);");
        s3 = s1 + s2;
        X::show("s3 = s1 + s2;");
        s1 + s2;        
        X::show("s1 + s2;");
        s3 += s1;       
        X::show("s3 += s1;");
        s3.substr(10);  
        X::show("s3.substr(10);");
        s4 = s3.substr(10);     
        X::show("s4 = s3.substr(10);");
        s4 = s3.find(s2);
        X::show("s4 = s3.find(s2);");
}
	X::show("}");

Что из этого можно вынести? Ну во первых использовать reserve, а не resize, избегать присвоений и заполняющих конструкторов, воможно, что-то еще. Код работает и дает сходный результат для g++ 4.7.2, intel 13.0.1, clang 3.2, что было проверено здесь
После выхода из области видимости строки деструкторы для символов не вызываются. Возможно там и другие операции пропускаются (например используется memcmp вместо operator>() в цикле). Но и строка это не полноценный контейнер. Для строк метод трассеров позволяет получить приблизительную оценку количества операций. Для чистых контейнеров эта оценка должна быть строже.

Вот, почти все.
Во время исследования никто не пострадал. Источниками были
этот референс, файлы:
/usr/include/c++/4.7.2/strings
/usr/include/c++/4.7.2/bits/stringfwd.h
/usr/include/c++/4.7.2./bits/basic_string.h
/usr/include/c++/4.7.2./bits/basic_string.tcc
и gdb.

PS.

В качестве постскриптума и иллюстрации тожества метапрограммирования добавлю, что наш трассер можно использовать для оценки затрат на разбор строки в boost::spirit. На гитхабе выложен исходник трассера вместе с примером calc5.cpp из boost::spirit.

Автор: korisk

Источник