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]

PATCH (mainline): First-order improve string<> allocation performance


> Loren I would appreciate it if you could corral this patch into CVS. It 
> seems to be based on your work and you seem to have a much better grip on 
> it than I. Does this sound possible?

Passed ``gmake clean all check'' with no regressions in the
libstdc++-v3 build directory on i386-*-freebsd4.4.  Paolo checked a
close version on i386-*-linux* (completely different malloc
implementation).  It is subtly different than the version I posted a
few months ago and contains the tuning done by Paolo Carlini and minor
generalization done to avoid having to do any configuration tests.
The code comment for this algorithm was updated to explain how/why it
is different than the exponential growth shaper.  I grant this
algorithm will rarely dominate the exponential growth shaper once it
is in.  But it will influence memory allocation size selection subtly.

2001-11-27  Loren J. Rittle  <ljrittle@acm.org>
            Paolo Carlini  <pcarlini@unitus.it>

        * include/bits/basic_string.tcc (basic_string::_Rep::_S_create):
        Enforce allocation size blocking policy to reduce
        fragmentation and enhance performance with common malloc
        implementations.

Index: include/bits/basic_string.tcc
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/basic_string.tcc,v
retrieving revision 1.9
diff -c -r1.9 basic_string.tcc
*** basic_string.tcc	2001/11/21 22:04:50	1.9
--- basic_string.tcc	2001/11/28 05:14:44
***************
*** 374,379 ****
--- 374,427 ----
        // 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 as
+       // 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 blocking size of the malloc implementation.
+       // Unfortunately, we would need a somewhat low-level calculation
+       // with tuned parameters to get this perfect for any particular
+       // malloc implementation.  Fortunately, generalizations about
+       // common features seen among implementations seems to suffice.
+       // This algorithm does not replace the need for an exponential
+       // growth shaper to meet library specification.  Note: THIS IS
+       // NOT THE CORRECT LOCATION FOR AN EXPONENTIAL GROWTH SHAPER
+       // (since this code affect initial allocation as well as
+       // reallocation).
+ 
+       // __pagesize need not match the actual VM page size for good
+       // results in practice, thus we pick a common value on the low
+       // side.  __malloc_header_size is an estimate of the amount of
+       // overhead per memory allocation (in practice seen N * sizeof
+       // (void*) where N is 0, 2 or 4).  According to folklore,
+       // picking this value on the high side is better than
+       // low-balling it (especially when this algorithm is used with
+       // malloc implementations that allocate memory blocks rounded up
+       // to a size which is a power of 2).
+       const size_t __pagesize = 4096; // must be 2^i * __subpagesize
+       const size_t __subpagesize = 128; // should be >> __malloc_header_size
+       const size_t __malloc_header_size = 4 * sizeof (void*);
+       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 > __subpagesize)
+ 	{
+ 	  size_t __extra =
+ 	    (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
+ 	    % __subpagesize;
+ 	  __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);


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