Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 a std::vector<T>) which stores an unspecified number of elements of the same type T on the heap. Each element is allocated and deallocated via the constructor and destructor of T.

  • A type M that stores m elements on the heap (so M itself is a kind of container). However, the value of m is not known at compile time, so it cannot be used as a template parameter to M.

Problem:

  • If we try to use a type Container<M>, accessing the elements of M inside this container would require two pointer dereferences, which in general has worse performance than if all elements of M were laid out contiguously.

Non-ideal solution:

  • Create a separate class ContainerFixed<T> that manages the memory of T directly, if T 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).

share|improve this question
    
This question is related to stackoverflow.com/questions/4403055/… ... also, it seems more appropriate for StackOverflow. –  Heatsink Jul 13 '13 at 0:56
add comment

1 Answer

up vote 1 down vote accepted

I think you could more or less solve this by having an API similar to allocators, whereby a container could specify how to allocate its metadata and elements contiguously. That is, a container would provide an “unboxed mode” in which it would presumably be immutable, or at least of fixed size. You couldn’t allocate unboxed containers on the stack because their sizeof is not a compile-time constant, but you could use this API when constructing a nested container.

This would seem to work naturally for std::vector and std::array, but for std::list and std::deque (which is typically implemented as a linked list of fixed-size chunks) or tree structures such as std::map, it’s not necessarily clear what such “unboxing” would actually mean. Do you stand to gain from allocating all the nodes in the tree contiguously, but still traversing them with lots of pointer indirections? Without benchmarking it’s hard to say.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.