A few details about std :: string

I recently became interested in implementing std :: string in libstdc ++. Not in connection with the adoption of the new standard, but to understand. Fortunately, the requirements for the string type have not changed much.

The main tool for code analysis is undoubtedly the method of peering, but in order to narrow the gaze and make the procedure more exciting, you can implement the “tracer” idiom for the line in the “C ++ Templates: The Complete Guide”. Tracing allows you to identify suspicious interesting operations on strings.

As you know, std :: string is an alias for

std::basic_string

and nothing prevents us from identifying

std::basic_string

. In X, you can define several static counters and iterate them in the constructor, destructor, and other methods. By performing various operations on such a string, it will be possible to trace the effectiveness of the applied algorithms in terms of the number of operations.
Also in g ++ for

std::string a(«entrails»); 

expression

std::cout << reinterpret_cast(*((void**)(&a))); 

will display the contents of the string. Those. std :: string - is, in fact, a pointer to char.
In general, these and other shocking details under the cut.

Structure

std :: string is declared as:

  typedef basic_string    string;

 basic_string

, in turn, is an alias for:

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

The definition of basic_string is done in the files c ++ / bits / basic_string.h c ++ / bits / basic_string.tcc.

If you remove all the methods of the class, it will remain
, which in turn are expressed in a single pointer. Moreover, the pointer does not indicate the beginning of the allocated piece of memory, but as shown in the figure, _M_p indicates the beginning of the _CharT array.
Such a tricky structure is achieved by dividing the initialization into two stages. Inside the std :: string constructor, the allocate () method of the allocator is first called, then construct (). Allocate () using malloc () allocates the necessary piece of memory, and construct () calls placement new with the desired offset relative to the beginning of the selected area. The offset is determined at the compilation stage, so destruct () and deallocate () have no problems calculating the source address.
As written in basic_string.h, such a construction procedure is implemented so that the variable std :: string is a pointer to an array of string elements. Then gdb is able to display the contents of std :: string.

The picture seems to be self-documenting, however, I note that _M_refcount takes 4 bytes, but is aligned to 8 (for x86-64). Lines 1) and 2) will occupy the same amount of memory. X is a tracer class, but more on that later. First, a few words about the static members of the std :: string class.
It would seem that npos needs no introduction. But ... this is not the maximum possible length of std :: string; it is only the maximum value of type std :: string :: size_type. The maximum length of the string is at least four less and it is determined by the static member:
_S_max_size;
Why it was chosen a quarter - I could not find out.
_S_terminal - the end of line character is initialized by the constructor without parameters when the program starts.

Reference counting

Now we come to a separate topic of link counting. Counting string references is mentioned in the standard, but is not a requirement.
The _S_empty_rep_storage variable is the memory block that all empty lines created in the program refer to.
The number of links is stored in the _M_refcount variable field.
_M_refcount:

• -1: the line has one link, increasing the number of links is not possible;
  
• 0: normal value. there is only one line with this content;
  
• n> 0: there are n + 1 rows with this content. (when working in a multi-threaded program, locks are required for such lines)
  

Despite the fact that _M_refcount with a value of -1 should prohibit "lazy" string construction, there is no method in the public interface std :: string that allows you to enable or disable link counting. There is a macro definition _GLIBCXX_FULLY_DYNAMIC_STRING that seems to be intended for this, but it didn’t work in my tests, I didn’t go deeper.

(Upd: _GLIBCXX_FULLY_DYNAMIC_STRING have nothing to do with refcounting. This is a simple optimization so as not to allocate memory for empty lines. You need to disable it if you have several instances of libstdc ++ in the process (this happens on Windows))

In general, these links simply transfer memory allocation from the call of the constructor to the moment of the first write to the line and sometimes make themselves felt when working in multi-threaded mode. Helgrind and drd give nontrivial hints about this.

Tracer

Now let's see how well the methods of the std :: string class implement their actions. And we will measure the quality of actions in the number of operations performed on line characters. To do this, we will use the tracer idiom. It is intended for debugging containers and is involved in creating a class of counting operations performed on it. By instantiating a container of such classes, one can easily calculate the number of comparison operations, for example, when sorting or when performing any other action on the container. Well, std :: string more or less falls under the definition of a container, so the string can be examined using this idiom. You can estimate which constructors, methods, algorithms are more effective in a particular situation. Actually, here is our
Structure X has one regular field of class char v; - its meaning. Two static ones are an array of counters and an array of names for these counters. Calls of constructors, destructors, assignments, comparisons (==, <) and conversions to / from char are counted. Only seven counters. The two static methods show and head are used to visualize the results. Show displays the values ​​of the counters and resets them. Head shows the names of the counters.
To calibrate the tracer, let's see how it counts operations in elementary situations:

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 yv;} (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

Because calibration is performed at the beginning of the application, the constructor of the static terminal symbol _S_terminal falls into this table. Its constructor is counted in the first line.
The following table shows the construction of a pair of arrays:

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

Now let's move on to the lines. Let's call our trace line like this

typedef std::basic_string xs;

The construction of empty lines, as expected, does not perform operations on characters.

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

The following table speaks for itself. It was embarrassing that when specifying the length (s2), the number of operations is much less than in the case of s1. Moreover, the strings constructed on the basis of s1 and s2 behaved differently. For s6, lazy design worked, for s5 it didn't. The filling constructor surprised me so much - additional copying and destructors came from somewhere. (Upd: they came from passing a class by value)

operation	ctor	copy	assgn	dtor	lss	eql	cast
{	0	0	0	0	0	0	0
xs s1 ((X *) "1234567890");	eleven	0	eleven	eleven	0	eleven	0
xs s2 ((X *) "1234567890", 7);	0	0	8	0	0	0	0
xs s3 (10, 'a');	1	3	eleven	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	eleven	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

Now a few basic operations. Unexpectedly, the result for resize was significantly worse than for 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

What can be learned from this? Well, firstly, to use reserve, not resize, to avoid assignments and filling constructors, maybe something else. The code works and gives a similar result for g ++ 4.7.2, intel 13.0.1, clang 3.2, which was checked here.
After leaving the scope of the string, destructors for characters are not called. Perhaps there other operations are skipped (for example, memcmp is used instead

operator>()

in the loop). But the string is not a full container. For strings, the tracer method provides a rough estimate of the number of operations. For clean containers, this rating should be stricter.

That’s almost all.
No one was hurt during the study. Sources were
this reference , files:
/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
and gdb.

PS.

As a postscript and illustration of the metaprogramming identity , I’ll add that our tracer can be used to estimate the cost of parsing a line in boost :: spirit. On the github, the source of the tracer is laid out, along with an example calc5.cpp from boost :: spirit.

Upd1:
Thanks to Khim for explaining the situation with _GLIBCXX_FULLY_DYNAMIC_STRING, with c ++ 11 lines and their implementation in libstdc ++.

After the directive is included in the code

#include 

,
override

typedef __gnu_cxx::__versa_string xs;

and
builds with the -std = gnu ++ 11 option, link counting has been disabled, as you can see in the table:

Upd2: According to the standard, basic_string can only operate with POD types. It turned out that X is not a POD type. (it is a “standard layout class”, but not a “trivially copyable class” because it has explicit constructors, destructor and assignment operators)
Therefore, the behavior of the basic_string class is undefined, and the whole post is a lie and a provocation. :)
Which is confirmed by the inability to compile examples using standard libraries other than gnu libstdc ++. (clang 3.2 c libc ++ 1.0 and msvc from vs2012)