First draft of string exponential alloc
Paolo Carlini
pcarlini@unitus.it
Tue Nov 20 20:00:00 GMT 2001
Hi all,
the following is a first rough draft of the exponential shaping patch that me and Loren we
are currently preparing.
As is, it already bootstraps and passes make check.
The first benchmark results are *good* in every testcase we have tried, much better than
those of the previous string patch in many circumstances, never worse.
But, please, give it a try!
Cheers,
Paolo.
P.S. Here in Italy it is time to go to bed...
diff -urN gcc-vanilla/libstdc++-v3/include/bits/basic_string.h
gcc/libstdc++-v3/include/bits/basic_string.h
--- gcc-vanilla/libstdc++-v3/include/bits/basic_string.h Fri Nov 2 18:38:10 2001
+++ gcc/libstdc++-v3/include/bits/basic_string.h Thu Nov 22 22:42:52 2001
@@ -197,21 +197,6 @@
_CharT*
_M_clone(const _Alloc&, size_type __res = 0);
-#if _GLIBCPP_ALLOC_CONTROL
- // These function pointers allow you to modify the allocation
- // policy used by the string classes. By default they expand by
- // powers of two, but this may be excessive for space-critical
- // applications.
-
- // Returns true if ALLOCATED is too much larger than LENGTH
- static bool (*_S_excess_slop) (size_t __length, size_t __allocated);
-
- inline static bool
- __default_excess(size_t, size_t);
-#else
- inline static bool
- _S_excess_slop(size_t, size_t);
-#endif
};
// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
diff -urN gcc-vanilla/libstdc++-v3/include/bits/basic_string.tcc
gcc/libstdc++-v3/include/bits/basic_string.tcc
--- gcc-vanilla/libstdc++-v3/include/bits/basic_string.tcc Thu Nov 22 00:54:51 2001
+++ gcc/libstdc++-v3/include/bits/basic_string.tcc Tue Nov 27 23:24:25 2001
@@ -271,7 +271,7 @@
_M_mutate(size_type __pos, size_type __len1, size_type __len2)
{
size_type __old_size = this->size();
- const size_type __new_size = __old_size + __len2 - __len1;
+ size_type __new_size = __old_size + __len2 - __len1;
const _CharT* __src = _M_data() + __pos + __len1;
const size_type __how_much = __old_size - __pos - __len1;
@@ -279,6 +279,8 @@
{
// Must reallocate.
allocator_type __a = get_allocator();
+ if (__new_size > capacity())
+ __new_size *= 2;
_Rep* __r = _Rep::_S_create(__new_size, __a);
try
{
@@ -302,8 +304,8 @@
traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
}
_M_rep()->_M_set_sharable();
- _M_rep()->_M_length = __new_size;
- _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
+ _M_rep()->_M_length = __old_size + __len2 - __len1;
+ _M_data()[__old_size + __len2 - __len1] = _Rep::_S_terminal; // grrr. (per 21.3.4)
// You cannot leave those LWG people alone for a second.
}
@@ -349,13 +351,6 @@
}
}
-#ifdef _GLIBCPP_ALLOC_CONTROL
- template<typename _CharT, typename _Traits, typename _Alloc>
- bool (*basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_excess_slop)
- (size_t, size_t) =
- basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_default_excess;
-#endif
-
template<typename _CharT, typename _Traits, typename _Alloc>
typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
basic_string<_CharT, _Traits, _Alloc>::_Rep::
@@ -374,6 +369,37 @@
// 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.
+
+ // 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 = 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 > 128)
+ {
+ 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);
@@ -389,7 +415,11 @@
basic_string<_CharT, _Traits, _Alloc>::_Rep::
_M_clone(const _Alloc& __alloc, size_type __res)
{
- _Rep* __r = _Rep::_S_create(_M_length + __res, __alloc);
+ _Rep* __r;
+ if (__res == 0)
+ __r = _Rep::_S_create(_M_length, __alloc);
+ else
+ __r = _Rep::_S_create((_M_length + __res)*2, __alloc);
if (_M_length)
{
try
@@ -402,19 +432,6 @@
}
__r->_M_length = _M_length;
return __r->_M_refdata();
- }
-
- template<typename _CharT, typename _Traits, typename _Alloc>
- inline bool
-#ifdef _GLIBCPP_ALLOC_CONTROL
- basic_string<_CharT, _Traits, _Alloc>::_Rep::
- _S_default_excess(size_t __s, size_t __r)
-#else
- basic_string<_CharT, _Traits, _Alloc>::_Rep::
- _S_excess_slop(size_t __s, size_t __r)
-#endif
- {
- return 2 * (__s <= 16 ? 16 : __s) < __r;
}
template<typename _CharT, typename _Traits, typename _Alloc>
diff -urN gcc-vanilla/libstdc++-v3/include/bits/c++config
gcc/libstdc++-v3/include/bits/c++config
--- gcc-vanilla/libstdc++-v3/include/bits/c++config Thu Nov 22 13:25:14 2001
+++ gcc/libstdc++-v3/include/bits/c++config Fri Nov 23 01:09:38 2001
@@ -55,10 +55,6 @@
// Use corrected code from the committee library group's issues list.
#define _GLIBCPP_RESOLVE_LIB_DEFECTS 1
-// Define this to permit user-level control of the expansion of string
-// buffers (via a fn pointer), see basic_string.* for more.
-//#define _GLIBCPP_ALLOC_CONTROL
-
// Map gthr.h abstraction to that required for STL. Do not key off of
// __GTHREADS at this point since we haven't seen the correct symbol
// yet, instead setup so that include/bits/stl_threads.h will know to
More information about the Libstdc++
mailing list