This is not strictly related to C++ but its type system serves to illustrate the problem well.
Assume:
We have a generic template
Container<T>
(such as astd::vector<T>
) which stores an unspecified number of elements of the same typeT
on the heap. Each element is allocated and deallocated via the constructor and destructor ofT
.A type
M
that storesm
elements on the heap (soM
itself is a kind of container). However, the value ofm
is not known at compile time, so it cannot be used as a template parameter toM
.
Problem:
- If we try to use a type
Container<M>
, accessing the elements ofM
inside this container would require two pointer dereferences, which in general has worse performance than if all elements ofM
were laid out contiguously.
Non-ideal solution:
- Create a separate class
ContainerFixed<T>
that manages the memory ofT
directly, ifT
is assumed to have the same size throughout the container.T
would also have to exchange information about its storage with the containing class. However, if we implement another kind of container, then we have to repeat this process again.
The problem arises because the container class is oblivious of the storage requirements of T
so it defers the allocation to T
itself; if the container had known that T
only requires a fixed (though not known at compile time) number of elements then this issue could have been avoided.
Now I feel as though that if there was some way to communicate to the container that M
has a definite size m
(as in M<m>
, which is not legal in C++), then from the type signature of Container<M<m> >
one can potentially deduce that a faster allocation scheme is possible. (It's a bit like dependent types, in a way.) That is, any Container1<Container2<m> >
can be allocated more efficiently as a "flattened" container.
What would be a more general solution to this problem? I don't think this is something that can be easily solved in C++ (feel free to prove me wrong), so I would certainly like to hear if this is something that other languages can solve in a much simpler way (perhaps with more sophisticated type systems).