vector<> can probably never grow to it's maximum size!

[Dhruv Matani]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch_beta_vector_allocator_20102004_dhruv
Type: text/x-patch
Size: 6056 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20041020/7a6e17fe/attachment.bin>