Pull to refresh

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

Reading time 10 min
Views 74K
Недавно заинтересовался реализацией 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;
цитата из c++/bits/basic_string.tcc
  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 вроде бы предназначенное для этого, но в моих тестах оно не заработало, глубже разбираться я не стал.

(Upd: _GLIBCXX_FULLY_DYNAMIC_STRING никакого отношения к refcounting'у не имеют. Это простая оптимизация для того, чтобы не выделять память для пустых строк. Отключать её нужно в тех случаях когда у вас несколько экземпляров libstdc++ в процессе (так бывает на Windows) )

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

Трассер
Посмотрим теперь насколько хорошо методы класса std::string реализуют свои действия. А измерять качество действий будем в количестве операций проводимых над символами строки. Для этого будем использовать идиому «трассер». Она предназначается для отладки контейнеров и заклюается в создании класса подсчитывающего операции производимые над ним. Инстанцируя контейнер таких классов легко можно подсчитать количество оперций сравнения например при сортировке или при выполнении любого другого действия над контейнером. Ну а std::string более или менее подпадает под определение контейнера, соответственно строку можно исследовать с помощью этой идиомы. Можно прикинуть какие конструкторы, методы, алгоритмы более эффективны в тех или иных ситуация. Собственно, вот наш
трассер X
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 показывает имена счетчиков.
Для калибровки трассера посмотрим как он подсчитывает операции в элементарных ситуациях:
operation ctor copy assgn dtor lss eql cast
{ 1 0 0 0 0 0 0
X a; 1 0 0 0 0 0 0
a = '1'; 0 0 1 0 0 0 0
X b = a; 0 1 0 0 0 0 0
X c(a); 0 1 0 0 0 0 0
c('e'); 0 0 0 0 0 0 1
c = b; 0 0 1 0 0 0 0
(c=b)='e'; 0 0 2 0 0 0 0
a < b; 0 0 0 0 1 0 0
a == b; 0 0 0 0 0 1 0
[](X y)->X{return y.v;}(b); 1 1 0 2 0 0 0
a = [](X y)->X{return y;}(b); 0 2 1 2 0 0 0
} 0 0 0 3 0 0 0
Код калибровки трассера
        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;");
        #if __cplusplus > 199711L
       [](X y)->X{return y.v;}(b);
       X::show("[](X y)->X{return y.v;}(b);");
        a = [](X y)->X{return y;}(b);
        X::show("a = [](X y)->X{return y;}(b);");
        #endif
}
        X::show("}");

Т.к. калибровка выполняется в начале приложения, то в эту таблицу попадает конструктор статического терминального символа _S_terminal. Его конструктор посчитан в первой строке.
В следующей таблице показано конструирование пары массивов:
operation ctor copy assgn dtor lss eql cast
{ 0 0 0 0 0 0 0
X a[10]; 10 0 0 0 0 0 0
std::copy(ch,ch+10,a); 0 0 10 0 0 0 0
X b[10] = {'o'}; 10 0 0 0 0 0 0
std::copy(a,a+10,b); 0 0 10 0 0 0 0
} 0 0 0 20 0 0 0
Код для массивов X
{
        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;

Конструирование пустых строк, как и ожидалось, не производит операций над символами.
operation ctor copy assgn dtor lss eql cast
{ 0 0 0 0 0 0 0
const xs s1; 0 0 0 0 0 0 0
xs s2(s1); 0 0 0 0 0 0 0
xs s3 = s1; 0 0 0 0 0 0 0
} 0 0 0 0 0 0 0
Код для конструкторов пустых строк
{
        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 — нет. Заполняющий конструктор так вообще удивил — откуда-то взялись дополнительные копирования и деструкторы. (Upd: они взялись из передачи класса по значению)
operation ctor copy assgn dtor lss eql cast
{ 0 0 0 0 0 0 0
xs s1((X*)«1234567890»); 11 0 11 11 0 11 0
xs s2((X*)«1234567890»,7); 0 0 8 0 0 0 0
xs s3(10,'a'); 1 3 11 4 0 0 0
xs s4(s1.begin(), s1.begin()+7); 0 0 8 0 0 0 0
xs s5(s2); 0 0 0 0 0 0 0
s5[0]='a'; 0 0 9 0 0 0 0
xs s6(s1); 0 0 11 0 0 0 0
s6[0]='a'; 0 0 1 0 0 0 0
xs s7(s1,1,5); 0 0 6 0 0 0 0
xs s8=[]()->xs{xs a((X*)«ololo»);return a;}(); 6 0 6 6 0 6 0
Теперь несколько базовых операций. Неожиданно, результат для resize получился значительно хуже чем для reserve:
operation ctor copy assgn dtor lss eql cast
int a = s1.size(); 0 0 0 0 0 0 0
s1.resize(100); 1 3 102 4 0 0 0
s2.reserve(100); 0 0 8 0 0 0 0
s1.erase(); 0 0 1 0 0 0 0
Тут еще несколько избранных операций
operation ctor copy assgn dtor lss eql cast
s1.insert(0,s2); 0 0 8 0 0 0 0
s1.insert(0,s2,2,4); 0 0 5 0 0 0 0
s3 = s1; 0 0 0 0 0 0 0
s3 == s1; 0 0 0 0 2 0 0
s2 != s1; 0 0 0 0 1 0 0
s1 > s2; 0 0 0 0 2 0 0
equal(s1.begin(),s1.end(),s2.begin()); 0 0 0 0 0 1 0
mismatch(s1.begin(),s1.end(),s2.begin()); 0 0 0 0 0 1 0
copy(s1.begin(),s1.end(),out_it); 0 0 0 0 0 0 11
std::sort(s1.begin(),s1.end()); 0 10 24 10 29 0 0
std::swap(s1,s2); 0 0 0 0 0 0 0
s3 = s1 + s2; 0 0 20 0 0 0 0
s1 + s2; 0 0 20 0 0 0 0
s3 += s1; 0 0 27 0 0 0 0
s3.substr(10); 0 0 16 0 0 0 0
s4 = s3.substr(10); 0 0 16 0 0 0 0
s4 = s3.find(s2); 1 3 2 4 26 8 0
} 0 0 0 0 0 0 0

И их код
{
	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.

Upd1:
Спасибо хабражителю Khim за разъяснение ситуации с _GLIBCXX_FULLY_DYNAMIC_STRING, cо строками c++11 и их реализацией в libstdc++.

После включения в код директивы
#include <ext/vstring.h>
,
переопределения
typedef __gnu_cxx::__versa_string<X> xs;
и
сборки с опцией -std=gnu++11 подсчет ссылок отключился, что и видно в таблице:
Результаты для __gnu_cxx::__versa_string<X>
operation ctor copy assgn dtor lss eql cast
{ 0 0 0 0 0 0 0
const xs s1; 1 0 1 1 0 0 0
xs s2(s1); 1 0 1 1 0 0 0
xs s3 = s1; 1 0 1 1 0 0 0
} 0 0 0 0 0 0 0
operation ctor copy assgn dtor lss eql cast
{ 0 0 0 0 0 0 0
xs s1((X*)«1234567890»); 12 0 11 12 0 11 0
xs s2((X*)«1234567890»,7); 1 0 8 1 0 0 0
xs s3(10,'a'); 2 4 11 6 0 0 0
xs s4(s1.begin(), s1.begin()+7); 1 0 8 1 0 0 0
xs s5(s2); 1 0 8 1 0 0 0
s5[0]='a'; 0 0 1 0 0 0 0
xs s6(s1); 1 0 11 1 0 0 0
s6[0]='a'; 0 0 1 0 0 0 0
xs s7(s1,1,5); 1 0 6 1 0 0 0
xs s8=[]()->xs{xs a((X*)«lol»);return a;}(); 7 0 6 7 0 6 0
xs s9((X*)«1234567890»); 12 0 11 12 0 11 0
X n = s9[0]; 0 1 0 0 0 0 0
int a = s1.size(); 0 0 0 0 0 0 0
s1.resize(100); 2 4 101 6 0 0 0
s2.reserve(100); 0 0 8 0 0 0 0
s1.erase(); 1 0 1 1 0 0 0
s1.insert(0,s2); 1 0 8 1 0 0 0
s1.insert(0,s2,2,4); 1 0 5 1 0 0 0
s3 = s1; 0 0 0 0 0 0 0
s3 == s1; 0 0 0 0 2 0 0
s2 != s1; 0 0 0 0 1 0 0
s1 > s2; 0 0 0 0 2 0 0
equal(s1.begin(),s1.end(),s2.begin()); 0 0 0 0 0 1 0
mismatch(s1.begin(),s1.end(),s2.begin()); 0 0 0 0 0 1 0
copy(s1.begin(),s1.end(),out_it); 0 0 0 0 0 0 11
std::sort(s1.begin(),s1.end()); 0 10 24 10 29 0 0
std::swap(s1,s2); 0 0 32 0 0 0 0
s3 = s1 + s2; 3 0 38 3 0 0 0
s1 + s2; 3 0 22 3 0 0 0
s3 += s1; 1 0 8 1 0 0 0
s3.substr(10); 1 0 16 1 0 0 0
s4 = s3.substr(10); 17 0 64 17 0 0 0
s4 = s3.find(s2); 2 3 2 5 26 8 0
} 0 0 0 1 0 0 0



Upd2: Согласно стандарту basic_string может оперировать только с POD типами. Оказалось, что X не является POD типом. (он «standard layout class», но не «trivially copyable class» т.к. имеет явные конструкторы, деструктор и операторы присвоения)
Поэтому поведение класса basic_string является неопределенным, а весь это пост — ложь и провокация. :)
Что и подтвеждается невозможностью скомпилировать примеры с использованием стандартных библиотек отличных от gnu libstdc++. (clang 3.2 c libc++ 1.0 и msvc из vs2012)
Tags:
Hubs:
+33
Comments 23
Comments Comments 23

Articles