This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: vector<> can probably never grow to it's maximum size!
On Wed, 2004-10-20 at 15:21, Paolo Carlini wrote:
> Dhruv Matani wrote:
>
> >Actually, I think this would be useful after all. Consider the situation
> >where th vector already has 1.2GB of memory, and wishes to expand more.
> >Consider that the user does a push_back(). Now, the vector will try to
> >allocate 1.2*2=2.4GB of memory. Currently, I think Linux supports only
> >3GB data segment(heap) max.
> >
> >
> Why are you always considering only 32-bit machines?
No, sorry about the 3*1024*1024 part just ignore it. I have attached a
patch that removes the controversial part.
>
> >The push_back will throw even though it could have succeeded!
> >With the patched allocator, it will now try to allocate slightly more
> >than 1.2GB, and will succeed. Thus, we have presented a
> >function(push_back) from failing.
> >
> >
> The point is not that doesn't make sense not doubling the request in low
> memory (perhaps, you have to add limits, platform dependent...).
Don't consider the 3GB part. It is not part of the patch. I forgot to
remove it before making the patch :-)
> The
> point is
> that you do *not* detect that condition via the arithmetic overflow
> mechanism!
> In the case you present above, __old_len * 2 = 2.4 GB, which does *not*
> overflow 2^32 - 1. Therefore, your patch is flawed in any case.
The part which handles this case is within the
__mt_alloc::allocate(n,hint,hint_passer) overload.
Look at the case where __n*sizeof(_Tp) > 128. There is a series of try
catch which use the _M_at_least field of the hint_passer to detect if
the allocator can if the __n failed, allocate at least _M_at_least
objects. If so, then it will succeed.
>
> Also, about the *small* allocations, are you aware of the fact that the old
> SGI allocator had a 'reallocate' extension? Before devising newer, complex,
> things, shouldn't we learn from that?
Yes, I'm aware of it, but that allocator was primarily a malloc based
allocator which did something similar to ::realloc().
Here's a code snippet from the SGI style allocator:
static void* reallocate(void* __p, size_t /* old_sz */, size_t
__new_sz)
{
void* __result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
Which is part of the __malloc_alloc_template.
What I am trying to do for the __mt_alloc is NOT reallocate memory, but
reuse a memory region if it is already over-allocated(as in the case of
__mt_alloc because it uses bins of 2^N size).
Thus, the copying phase is not there! Also, copying would not work for
non-PODs.
Anyways, we will HAVE to dispatch on whether the allocator parameter is
std::allocator or not, because given the fact that we have added an
extra parameter to the allocate function(which is legal), we can use
that overload ONLY with std::allocator. Also, I have included added
protection wherein the overload works only if the base class of
std::allocator is __mt_alloc<> because __mt_alloc would support in-place
expansion for small objects since it over-allocated memory.
>
> Paolo.
--
-Dhruv Matani.
http://www.geocities.com/dhruvbird/
The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs
diff -Nrup cvs_libstdc++-v3/.cvsignore modified_libv3/.cvsignore
--- cvs_libstdc++-v3/.cvsignore 2004-02-06 04:49:53.000000000 +0530
+++ modified_libv3/.cvsignore 1970-01-01 05:30:00.000000000 +0530
@@ -1 +0,0 @@
-autom4te.cache
diff -Nrup cvs_libstdc++-v3/include/bits/allocator.h modified_libv3/include/bits/allocator.h
--- cvs_libstdc++-v3/include/bits/allocator.h 2004-06-25 11:40:42.000000000 +0530
+++ modified_libv3/include/bits/allocator.h 2004-10-20 08:22:49.000000000 +0530
@@ -48,6 +48,32 @@
#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H 1
+namespace __gnu_cxx
+{
+ template<typename _Tp>
+ struct _Hint_passer
+ {
+ size_t _M_at_least;
+ size_t _M_old_n;
+ _Tp* _M_old_p;
+ bool _M_used_this;
+ };
+
+ template<typename _Tp, typename _Ba>
+ struct _Alloc_dispatch
+ {
+ typename _Tp::pointer
+ allocate(_Tp& __alloc_ref, typename _Tp::size_type __n)
+ { return __alloc_ref.allocate(__n); }
+
+ typename _Tp::pointer
+ allocate(_Tp& __alloc_ref, typename _Tp::size_type __n,
+ const void* __hint,
+ _Hint_passer<typename _Tp::value_type>* __ph = 0)
+ { return __alloc_ref.allocate(__n, __hint); }
+ };
+}
+
// Define the base class to std::allocator.
#include <bits/c++allocator.h>
@@ -102,6 +128,17 @@ namespace std
~allocator() throw() { }
+ pointer allocate(size_type __n, const void* __hint,
+ __gnu_cxx::_Hint_passer<_Tp>* __ph = 0)
+ {
+ return ___glibcxx_base_allocator<_Tp>::allocate(__n, __hint, __ph);
+ }
+
+ pointer allocate(size_type __n)
+ {
+ return ___glibcxx_base_allocator<_Tp>::allocate(__n);
+ }
+
// Inherit everything else.
};
@@ -124,7 +161,7 @@ namespace std
#endif
// Undefine.
-#undef ___glibcxx_base_allocator
+ // #undef ___glibcxx_base_allocator
} // namespace std
#endif
diff -Nrup cvs_libstdc++-v3/include/bits/vector.tcc modified_libv3/include/bits/vector.tcc
--- cvs_libstdc++-v3/include/bits/vector.tcc 2004-08-23 17:48:26.000000000 +0530
+++ modified_libv3/include/bits/vector.tcc 2004-10-20 18:54:14.000000000 +0530
@@ -262,8 +262,41 @@ namespace _GLIBCXX_STD
else
{
const size_type __old_size = size();
- const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
- iterator __new_start(this->_M_allocate(__len));
+ size_type __len = __old_size != 0 ? 2 * __old_size : 1;
+
+ // However, 1 more element would suffice here!
+ __gnu_cxx::_Alloc_dispatch<allocator_type,
+ ___glibcxx_base_allocator<_Tp> > __ad;
+
+ __gnu_cxx::_Hint_passer<value_type> __hp;
+ __hp._M_at_least = __old_size + 1;
+ __hp._M_old_p = this->_M_impl._M_start;
+ __hp._M_old_n = __old_size;
+ __hp._M_used_this = false;
+ iterator __new_start(__ad.allocate(this->_M_impl, __len, 0, &__hp));
+
+ if (__new_start == iterator(this->_M_impl._M_start))
+ {
+ // No need to reallocate!
+ this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __hp._M_at_least;
+ // __hp._M_at_least now contains the new size(n).
+ this->get_allocator().construct(this->_M_impl._M_finish, __x);
+ ++(this->_M_impl._M_finish);
+ return;
+ }
+ else
+ {
+ // If control reaches here, only 2 things are possible:
+ // 1. The std::allocator is not being used.
+ // 2. std::alllocator is being used, but was unable to
+ // expand the block in place.
+ if (__hp._M_used_this) // std::allocator will always set
+ // this to true.
+ __len = __hp._M_at_least; // at_least always contains
+ // the memory returned.
+ }
+
+ // iterator __new_start(this->_M_allocate(__len));
iterator __new_finish(__new_start);
try
{
diff -Nrup cvs_libstdc++-v3/include/ext/mt_allocator.h modified_libv3/include/ext/mt_allocator.h
--- cvs_libstdc++-v3/include/ext/mt_allocator.h 2004-10-18 18:43:36.000000000 +0530
+++ modified_libv3/include/ext/mt_allocator.h 2004-10-20 08:26:54.000000000 +0530
@@ -663,6 +663,52 @@ namespace __gnu_cxx
pointer
allocate(size_type __n, const void* = 0);
+ // Added this function.
+ pointer
+ allocate(size_type __n, const void*, _Hint_passer<_Tp>* __ph)
+ {
+ if (!__ph)
+ return this->allocate(__n);
+
+ __ph->_M_used_this = true;
+ if (__ph->_M_at_least * sizeof(_Tp) <= 128)
+ {
+ __pool_type& __pool = this->_S_get_pool();
+ const size_t __which1 = __pool._M_get_binmap(__ph->_M_old_n * sizeof(_Tp));
+ const size_t __which2 = __pool._M_get_binmap(__ph->_M_at_least * sizeof(_Tp));
+ if (__which1 == __which2)
+ {
+ __ph->_M_at_least = (1 << (__which1 + 3)) / sizeof(_Tp);
+ return __ph->_M_old_p;
+ }
+ else
+ {
+ __ph->_M_at_least = __n;
+ return this->allocate(__n);
+ }
+ }
+ else
+ {
+ pointer p = 0;
+ try
+ {
+ p = allocate(__n);
+ __ph->_M_at_least = __n;
+ return p;
+ }
+ catch(...)
+ {
+ try
+ {
+ p = allocate(__ph->_M_at_least);
+ return p;
+ }
+ catch(...)
+ { throw std::bad_alloc(); }
+ }
+ }
+ }
+
void
deallocate(pointer __p, size_type __n);
@@ -750,6 +796,23 @@ namespace __gnu_cxx
operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
{ return false; }
+ // Forward declare std::allocator.
+ namespace std { template<typename> struct allocator; }
+
+ // Specialization for std::allocator.
+ template<typename _Tp1, typename _Tp2>
+ struct _Alloc_dispatch<std::allocator<_Tp1>, __gnu_cxx::__mt_alloc<_Tp2> >
+ {
+ typedef typename std::allocator<_Tp1>::pointer _Ptr_t;
+ typedef typename std::allocator<_Tp1>::value_type _Value_t;
+ typedef typename std::allocator<_Tp1>::size_type _Size_t;
+
+ _Ptr_t
+ allocate(std::allocator<_Tp1>& __alloc_ref, _Size_t __n,
+ const void* __hint = 0, _Hint_passer<_Value_t>* __ph = 0)
+ { return __alloc_ref.allocate(__n, __hint, __ph); }
+ };
+
#undef __default_policy
} // namespace __gnu_cxx