Re: [Fwd: basic_string<> - useless because of its poor performance]

[Loren James Rittle <rittle at latour dot rsch dot comm dot mot dot com>]

In article <3B455CEA.E140F72@softax.pl>,
Ryszard Kabatek <Ryszard.Kabatek@softax.pl> writes:

> The current implementation of basic_string is to slow to be useful.

Only if you fail to use reserve() wisely as suggested by Stroustrup... ;-)

I do basically agree that we should do something better than
per-character growth given what we generally know about malloc
implementations.  However, it is unclear that an exponential growth
policy is wise.

> size_type 
> get_new_capacity(size_type n,
>                  size_type max_len) 
[...]

> that will be called in _M_mutate and perhaps in other places (not in reserve).

I think _Rep::_S_create is the correct place to add the logic to
adjust the request size sent to allocator<>::allocate() and to retain
the adjusted __capacity.  I have made no attempt to add this logic in
using (what looked like) a hook point or add the correct autoconf
setup of the parameters (well, I have started to look at it).

Index: libstdc++-v3/include/bits/basic_string.tcc
===================================================================
RCS file: /cvs/gcc/egcs/libstdc++-v3/include/bits/basic_string.tcc,v
retrieving revision 1.5
diff -c -r1.5 basic_string.tcc
*** basic_string.tcc	2001/06/12 02:30:37	1.5
--- basic_string.tcc	2001/07/06 07:24:40
***************
*** 371,376 ****
--- 371,411 ----
        // terminating null char_type() element, plus enough for the
        // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
        size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ 
+       // The standard places no restriction on allocating more memory
+       // than is strictly needed within this layer at the moment or
+       // requested by an explicit application call to reserve().  Many
+       // malloc implementations perform quite poorly when an
+       // application attempts to allocate memory in a stepwise fashion
+       // growing each allocation size by only 1 char.  Additionally,
+       // it makes little sense to allocate less linear memory than the
+       // natural resolution size of a malloc implementation.
+       // Unfortunately, we need a somewhat low-level calculation here
+       // to get this right for any particular malloc() implementation.
+       // Fortunately, it is currently believed that autoconf tests can
+       // be written to learn all required parameters.
+ 
+       // This version assumes the malloc implementation prefers to
+       // align allocations over the size of a page to a page boundary
+       // and under the size of a page to a power of 2.
+       const size_t __pagesize = 4096; // This magic constant, from OS.
+       const size_t __malloc_header_size = 0; // This one, from malloc.
+       if ((__size + __malloc_header_size) > __pagesize)
+ 	{
+ 	  size_t __extra =
+ 	    (__pagesize - ((__size + __malloc_header_size) % __pagesize))
+ 	    % __pagesize;
+ 	  __capacity += __extra / sizeof(_CharT);
+ 	  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ 	}
+       else if (__size > 128) // This magic constant is from stl_alloc.h.
+ 	{
+ 	  size_t __extra =
+ 	    (256 - ((__size + __malloc_header_size) % 256)) % 256;
+ 	  __capacity += __extra / sizeof(_CharT);
+ 	  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ 	}
+ 
        // NB: Might throw, but no worries about a leak, mate: _Rep()
        // does not throw.
        void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);