This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: sso tradeoffs


Hi again,

after some good hours of sleep, I'm ready for some, hopefully
meaningful, comments. Actually, I'm not 100% sure that it's the right
time for that: the philosophy of ext/vstring.h is that of giving the
users a wide choice of different trade-offs and then stabilize to a new
default standard implementation only just in time for the next ABI
version. That's why I encourage you to consider in any case this ext
string stuff your playground, and, if you want, improve also the
existing code (I'm going to do a bit of that, anyway).

> I am for the first time today poking around the extension short 
> string implementation.  I wanted to explore some of the design 
> tradeoffs that we currently have.
>
> The class layout currently looks like:
>
> Allocator - space optimized
> CharT*
> size
> union {
> CharT buf[16],
> capacity
> }
>
> This gives a 6 word size for string (CharT is char).
>
> This is a respectable design, and according to Effective STL, very 
> similar, if not a little better (imho) than implementation "D" from  ESTL.

As I already told you I was not aware of that nice summary. The story
went that with Nathan (and Benjamin: he always favoured a versatile
approach) we wanted a short string optimized string to play with. In
fact Nathan suggested something more similar to your design but I really
disliked slowness (a conditional, right?) in the indexing and wanted
something really, really, really clean wrt casts and memory tricks. I
was aware that our would never be a super optimized production thing, on
the other hand. Nathan also suggested to spare the memory of the
capacity when the short string is used and that's why you see one less
word than implementation "D" ;)

> The short/long flag is a check to see if the CharT* references the 
> internal buffer or not.
>
> Advantages:
>
> 1.  Very fast iterator creation (simply return the CharT*).
> 2.  Very fast indexing (index off of the CharT*).
> 3.  Decent internal buffer size before switching to long strings.
>
> Disadvantages (compared to what I'll show below):
>
> 1.  Significantly more complicated/slower swap (and thus move assign).
> 2.  Slower move construction.
> 3.  Slightly slower default ctor.

Indeed. Something I *really* like of your design and I believe *must*
characterize our eventual new standard implementation, is that it scales
well to 64-bit and that, of course, is move-semantics aware, which of
course we are already pursuing all over the board, even in a simulated
form for 4.2.

On the other hand, I'm nervous about the indexing thing. But it's just a
part of the big issue. Of course it's also a much more complex design
(e.g., you mention the need for specializations), but this is expected
for a real modern solution.

> The capacity for the short string shrinks as sizeof(CharT) grows 
> (from this rationale).  Here is a summary, sizeof is in bytes:
>
> 32 bit machine:
> sizeof(CharT)     sizeof(basic_string<CharT>)   short_capacity      
> min_cap
>     1                       12                        10               11
>     2                       12                         4                5
>     4                       12                         1                2
>
> 64 bit machine:
> sizeof(CharT)     sizeof(basic_string<CharT>)   short_capacity      
> min_cap
>     1                       24                        22               23
>     2                       24                        10               11
>     4                       24                         4                5
>
> A first reaction is that these internal capacities are awfully small 
> (I had the same reaction).  But...

In my opinion, the capacity scales well on 64-bit machines and this is
very cool. I have a different issue in mind, which has to do with the
different treatment reserved to char vs wchar_t. This is something that
makes me very nervous too, because if I look to the real world
applications of wchar_t, I don't think we have any reason to believe
that statistically wchar_r strings are much shorter. I have in mind of
course our C++ model, which is, by an large: internazionalization == in
memory wchar_t. Therefore, I cannot see which favor we can do to the
users allowing for 1 + 1 wchar_t (4 + 5 wchar_t). Do you have actual
statistics, maybe? From some talks with KDE people very much into memory
problems due to strings, I gather that, well, 1 + 1 (or 4 + 5) strings
are not going to help much. Why don't we renounce completely to sso for
large sizeof(CharT) in favour of sizeof(string)? I mean, we keep only
'\'0', of course. I think we should not discard this option too early.
Another element of this issue, is the performance of the memory
allocator, of course. I don't find it mentioned too often. From actual
experience with pooled memory allocators (consider even the legacy
HP/SGI one, if you want), I'm pretty sure that allocating memory from a
pool can be much, much faster that a real new. I think we should also
evaluate the various designs vs dynamic memory allocation (performance),
and if necessary, for v7 we should work at the same time, and
consistently, on memory allocation.

> One of the big differences between the two designs is the self-
> referential nature of the CharT* pointer:  pointing into itself in 
> one design, and being a completely different pointer in the other.  
> Each favors different things:  one favors indexing and iterator 
> creation, the other favors swap/move, and to a lesser extent default 
> ctor.

Exactly. I think we should definitely explore these trade-offs further
and collect some real world data, hopefully: honestly, I'm missing real
world data supporting my wild strong feeling that indexing should be
fast, for example. Another idea I have, probably we can compensate for
that rewriting the various string utility functions in the light of it,
quite a bit of work, but can be worth it. On the other hand, I'm afraid
users of the string class in their applications can tend to indicize
liberally as-if they had a char array... Personally, certainly I did
that, in the past ;) but again, I'm missing serious statistics...

Paolo.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]