Re: [boost] Library proposal: box

From: Chris Jefferson (chris_at_[hidden])
Date: 2008-08-07 05:02:04

2008/8/7 joel falcou <joel.falcou_at_[hidden]>:
>
>
> Some remarks and questions :
>
>> 3) In general box aims to be
> as simple as possible, sticking
>> with fixed size containers and
> no container copying.
> Then why not enforcing this by having the size
> passed as a template parameters ?

Because, like many buffers, in practice I find the maximum size is
often a run-time constant. It is possible to get most of the benefits
of a compile-time parameter constant with a compiletime_int (see end
of e-mail).

>> A) Allocators are a
> complex and often misunderstood type, and it is
>> not felt it
> makes things easier for users to give a different allocator to
>>
> vector as opposed to defining a new class.
> I don't think exposing
> such low level behavior (alloca calls and such) is a good
> call
> either. An allocator definition helper class is maybe best suited then.
> What if i want a std::list or some other complex data structure using
> alloca ?
> I will still be forced to write an allocator and not using
> box.
>
>> In particular, getting correct behaviour for the copy
> constructors of
>> the container is difficult, and it is not
> possible to give a correct
>> definition of max_size, which is more
> important for small-sized
>> containers.
> Why exactly ?

I'll split this question into two parts.

1) Why not use allocators? (This connects also with the next question).

a) Implementations of std::vector behave badly in tight memory
circumstances. They always double the amount of memory they use on a
resize operation, and also want to allocate a new block and copy their
data, even if the existing block they have can be extended. Therefore
users would have to do something like:

std::vector<int, magic_allocator_that_takes_seven_ints> v;
v.reserve(7);

To use all their memory.

b) When you have a container which holds few elements, it is nice to
be able to check how many things it can hold. I define a box to have
capacity == max_size == maximum allowed size. In a std::vector there
is no way of setting either of these values, as max_size is generally
set to size_t(-1) / size_t(sizeof(T)) and capacity varies. As in (a),
it never gets to the right value.

c) We probably want to make using the copy constructor and copy assign
of box a compile-time error, because they shouldn't be used. However,
there is in fact no way of forbidding this at all, because when the
allocator gets a memory request from the std::vector, it might be a
resize request or a copy request. Therefore there is no way of
stopping our allocator becoming a full "pool allocator".

2) Hiding alloca.

It is true we should hide alloca well from users. This can be done
through the careful use of helper macros. Unfortunately it's not
possible to hide alloca inside a constructor of function call, because
of course the stack room it provided will be destroyed when it exits.
I have implemented myself a simple "alternative stack", which makes
largeish heap allocations and then provides a FIFO "malloc"
alternative that provides memory. This is purposefully very simple,
erroring if any deallocations are performed out of order and providing
no opportunity for resizing allocations.

Now a brief diversion, the compiletime_int trick, which may or may not
be well known.

The compiletime_int class looks like:

template<int i>
struct compiletime_int
{ operator int() const { return i; } };

Then given a class which looks like:

template<typename Type, typename Size = size_t>
struct box;

If Size is actually defined to be a particular compiletime_int, and
the Size parameter is placed in a compressed_pair, then my tests show
the code exactly as fast and almost as small as if Size had been an
size_t template parameter in the first place.

Chris