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

[Dhruv Matani]

On Mon, 2004-10-18 at 20:41, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >2. You must have noticed that __mt_alloc<> allocates more memory than
> >required at times. We can take advantage of this fact, and include
> >support for this functionality within __mt_alloc::allocate(n, hint)
> >itself!
> >  
> >
> Even not considering the fundamental problem with the type of hint (see my
> other message), 

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.
Also, the vector's code need not change much to incorporate such
changes.

> I think there is something weird in your reasoning: when
> vector wants to grow and calls allocator::allocate(n), aither n is <~ 
> 128 bytes,
> and a pool is involved, or the request is passed directly to ::operator new.
> Therefore, mt_alloc either issues to the OS a *very* small memory 
> request - to
> refill one of its pools, of order 4K - or just returns what ::operator 
> new returns.
> In low memory, only the latter requests are problematic, and there is 
> nothing
> pool-allocation-specific in that: you just want to deal gracefully with an
> ::operator new that throws. An interesting topic, admittedly, but you 
> don't need
> the second argument of allocate for that!!!

Yes, these are 2 separate issues, but I hastily clubbed them into one.
Clearing things out might help.

Issue1: About operator new failing with a large request.
Issue2: Allocators such as mt_alloc<> already having some spare memory
which can be re-used not causing the vector to copy the data.

Now, the place where these 2 issues merge is the fact that container
using the allocator needs to be aware of the fact that the allocator
might give me lesser memory than required if it throws bad_alloc.

What we need is a way of distinguishing between these various cases
where the exception is thrown. This can be done using the hint
parameter.

Thinking more about it, I guess the exception part is not required at
all. Now we have the following scenario. The allocate(n, hint) overload
for mt_alloc<> works as follows.

It takes as it's 1st argument the new size required. The second argument
is non-zero is the address of the following struct:

struct hint_passer
{
  size_t at_least_these_many_n_are_required;
  pointer old_pointer;
  size_t old_n;
};

Now, the allocator can internally find out how many n were given to
old_pointer last time around. If it is <=
at_least_these_many_n_are_required, then just return the old_pointer,
and set at_least_these_many_n_are_required to the total size of the
block(new n).

Now, the user should call deallocate with this new n.


At the container side, this is roughly what happens:

vector::get_more_memory(new_size, at_least_size)
{
  hint_passer h;
  h.at_least_these_many_n_are_required = at_least_size;
  h.old_pointer = _M_start;
  h.old_n = this->capacity();

  pointer p = get_allocator().allocate(new_size, &h);
  if (p == _M_start)
  {
    _M_end_of_storage = _M_start + h.at_least_these_many_n_are_required;
    return;
  }

// Normal stuff.
}

std::allocator will just ignore the hint, and __mt_alloc will take the
correct action! Doesn't this look exciting?

How to merge Issues 1 and 2?
This should be quite clear now. What we do is make __mt_alloc<> do some
work for the case where bytes > 128.

mt_alloc::allocate(n, hint)
{
  if (n <= 128)
    ...
  else
  {
if (hint != 0)
{
    pointer p = 0;
    try
    { p = ::operator new(n); return p; }
    catch(bad_alloc&)
    {
      try
      {p = ::operator // Also set the other members if this is a success
           new((cast)hint->at_least_these_many_bytes_required);
       return p; }
      catch(bad_alloc&) { throw; }
    }
}
  }
}



> 
> Anyway, in thinking about these topics, be careful with the exponential grow
> guarantee in the standard (I know you are already aware of that, but, to be
> sure... ;) If allocator::allocate keeps on throwing, heaven knows why, 
> therefore
> vector doesn't obtain the amount of memory that really needs to grow 
> quickly,
> and *catches* the exceptions retrying with a smaller request, *the user 
> of the
> program* cannot see that something is going wrong, instead he sees only 
> a non
> conforming vector, growing too slowly.

I don't think that the problem of the vector growing too slowly will
occur with the code given above. After all these changes affect the
vector only when its memory consumption is <= 128 bytes.

> 
> 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