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!
Hi,
I attaching a patch to implement my ideas on Issue2:
"Issue2: Allocators such as mt_alloc<> already having some spare memory
which can be re-used not causing the vector to copy the data."
I would like to know what your take is on this, and should it be
implemented?
Also attached is a test-case. std::allocator with the base allocator as
__mt_alloc<> enables the optimization.
-Dhruv.
On Tue, 2004-10-19 at 00:41, Paolo Carlini wrote:
> Dhruv Matani wrote:
>
> >As I have explained earlier, but forgot to mention this:
> >
> >We may force the user to pass a non-const memory region's address to
> >allocate(n, hint) if hint is non-zero. This is possible because the
> >__mt_alloc<> is after all an extension, and we can demand such things.
> >
> >
> You can't in the current framework, since __mt_alloc is used as-is to
> implement
> std::allocator, in particular std::allocator::allocate (with the correct
> const void*
> type). You would need an additional wrapper around __mt_alloc.
>
> >Issue1: About operator new failing with a large request.
> >
> >
> This one (the only one that you mentioned at the beginning of this thread,
> by the way ;) you can't really fix by catching the exceptions thrown by
> ::operator new, I think. Here we are considering any possible size, and
> my previous comment about vector grow unduly limited stand.
>
> >Issue2: Allocators such as mt_alloc<> already having some spare memory
> >which can be re-used not causing the vector to copy the data.
> >
> >
> This is a completely new issue.
>
> >std::allocator will just ignore the hint, and __mt_alloc will take the
> >correct action! Doesn't this look exciting?
> >
> >
> Well, something is troubling me *a lot*: our std::vector is not supposed
> to be
> used only with the bunch of allocators that we are providing, but with *any*
> standard conforming allocator. You would pass to those allocators an
> hint not
> correct wrt to the standard requirements: Table 31 says, about it
>
> "a value of type T::const_pointer obtained by calling Y::allocate or
> else 0"
>
> More comments later...
> 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
#include <vector>
// #define ALLOC_ std::allocator
#define ALLOC_ __gnu_cxx::__mt_alloc
using namespace std;
struct one
{
char c;
};
int main()
{
int ctr = 0;
int x = 2000000;
while (x--)
{
std::vector<one, ALLOC_<one> > ov(65);
for (int i = 0; i < 60; ++i)
{
one o;
ov.push_back(o);
}
++ctr;
}
}
diff -Nrup -x'.cvs*' 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 -x'.cvs*' 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 08:26:21.000000000 +0530
@@ -262,8 +262,48 @@ 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;
+
+ if (__len < __old_size) // Bummer!
+ {
+ size_type __threshold = 3*1024*1024; // 3GB?
+ __threshold *= 1024;
+ __len = __threshold;
+ }
+
+ // 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 -x'.cvs*' 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