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 have attached a patch that modifies the files:
allocator.h
vector.tcc
mt_allocator.h
And tries to explain more concretely what I'm trying to achieve and also
shows that it's do able in current C++.
Also, attached is a test case which shows that you get 2 times the speed
with the patch than without the patch. To enable the speedup, define
ALLOC_ to std::allocator, and to disable it, use ALLOC_
__gnu_cxx::mt_alloc
So, this is definitely do able with the present situation.
This is a very rough patch that just about compiles and works, and is
not something to be comitted. The organization is very bad, and vector
and the allocator use global types defined in the .cpp file.
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
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-19 16:53:46.000000000 +0530
@@ -102,6 +102,16 @@ namespace std
~allocator() throw() { }
+ pointer allocate(size_type n, const void* hint = 0, 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 hint);
+// }
+
// Inherit everything else.
};
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-19 19:10:17.000000000 +0530
@@ -262,8 +262,50 @@ 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;
+ }
+
+ // fprintf(stderr, "Come here %d %d\n", __old_size, __len);
+
+ // However, 1 more element would suffice here!
+ alloc_dispatch<allocator_type> ad(static_cast<allocator_type&>(this->_M_impl));
+ hint_passer<value_type> h;
+ h.at_least = __old_size + 1;
+ h.old_p = this->_M_impl._M_start;
+ h.old_n = __old_size;
+ h.used_this = false;
+ iterator __new_start(ad.allocate(__len, 0, &h));
+
+ if (__new_start == iterator(this->_M_impl._M_start))
+ {
+ // fprintf(stderr, "Do not reallocate now!\n");
+
+ // No need to reallocate!
+ this->_M_impl._M_end_of_storage = this->_M_impl._M_start + h.at_least;
+ // h.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 (h.used_this) // std::allocator will always set this
+ // to true.
+ __len = h.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-19 19:09:28.000000000 +0530
@@ -663,6 +663,62 @@ 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)
+ {
+ // fprintf(stderr, "ph == %x", ph);
+
+ if (!ph)
+ return this->allocate(__n);
+
+ ph->used_this = true;
+ // fprintf(stderr, "at_least: %d", ph->at_least*sizeof(_Tp));
+
+ if (ph->at_least * sizeof(_Tp) <= 128)
+ {
+ __pool_type& __pool = this->_S_get_pool();
+ const size_t __which1 = __pool._M_get_binmap(ph->old_n * sizeof(_Tp));
+ const size_t __which2 = __pool._M_get_binmap(ph->at_least * sizeof(_Tp));
+ // fprintf(stderr, "pools: %d %d\n", __which1, __which2);
+
+ if (__which1 == __which2)
+ {
+ // fprintf(stderr, "Here: %d %d\n", ph->old_n*sizeof(_Tp), __which1);
+ // ph->at_least;
+ // What do do here??? I want to get the maximum for a
+ // particular bin.
+ ph->at_least = (1 << (__which1 + 3)) / sizeof(_Tp);
+ return ph->old_p;
+ }
+ else
+ {
+ ph->at_least = __n;
+ return this->allocate(__n);
+ }
+ }
+ else
+ {
+ pointer p = 0;
+ try
+ {
+ p = allocate(__n);
+ ph->at_least = __n;
+ return p;
+ }
+ catch(...)
+ {
+ try
+ {
+ p = allocate(ph->at_least);
+ return p;
+ }
+ catch(...)
+ { throw std::bad_alloc(); }
+ }
+ }
+ }
+
void
deallocate(pointer __p, size_type __n);
#include <stddef.h>
#include <stdio.h>
// Forward declare std::allocator.
namespace std
{
template <typename T>
struct allocator;
}
template <class T>
struct hint_passer
{
size_t at_least;
T* old_p;
size_t old_n;
bool used_this;
};
template <class T>
struct alloc_dispatch
{
T& tref;
alloc_dispatch(T& _tref) : tref(_tref)
{ }
typename T::pointer
allocate(typename T::size_type n, const void* hint = 0,
hint_passer<typename T::value_type>* ph = 0)
{ return tref.allocate(n, hint); }
};
// Specialization for std::allocator.
template <class T>
struct alloc_dispatch<std::allocator<T> >
{
typedef typename std::allocator<T>::reference reff_t;
typedef typename std::allocator<T>::pointer ptr_t;
typedef typename std::allocator<T>::value_type value_t;
std::allocator<T>& tref;
alloc_dispatch(std::allocator<T>& _tref) : tref(_tref)
{ }
ptr_t
allocate(size_t n, const void* hint = 0, hint_passer<value_t>* ph = 0)
{ return tref.allocate(n, hint, ph); }
};
#include <iostream>
#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 = 1000000;
while (x--)
{
std::vector<one, ALLOC_<one> > ov(65);
for (int i = 0; i < 50; ++i)
{
one o;
o.c = i;
ov.push_back(o);
}
++ctr;
}
}