I wish to seek interest in generalising, extending and documenting a simple but useful library I use personally. 'box' is a simple class which provides an almost standard C++ container on top of a pre-allocated block of memory or range of iterators. For raw memory this container is a perfect implementation of vector, except for the constructors. It is possible for the underlying objects to be already constructed, or have the container handle construction and destruction. Simple usages: box<int> b1(malloc(sizeof(int) * 10), 10); // makes an empty container of size 10. assert(b1.size() = 0); assert(b1.max_size() == 10); b1.resize(10, 1); // Fills the container with 1s. b1.push_back(1); // throws std::length_error box<int> b2(alloca(sizeof(int) * 10), 10); // makes an empty container on the stack of size 10. void get_things(b2); // passing 'alloca'ed boxes to functions avoid heap allocation. A number of macros exist for automating the creation of containers with 'alloca'ed memory. Further, a simple alternative implementation of alloca which uses a parallel stack is provided. Common use cases: 1) Use 'alloca'ed memory to make a container on the stack. 2) In general allow the use of C++ container idioms (push_back, resize) while maintaining fully controlled, clear memory management. Design decisions: 1) Box has no copy constructor or assignment, and will have no move constructor either, as it seems difficult to give any definition without too many 'gotchas'. 2) Box does not attempt to implement complex memory management, 3) In general box aims to be as simple as possible, sticking with fixed size containers and no container copying. Possible Qs (with I hope correct answers) Q) Why is this not just boost::range? A) The container starts empty, and can be inserted into. Q) Why not implement this as an allocator to give to vector/list? 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. 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. Current state: box is currently in usage in a number of projects, based on a heavily-hacked SGI vector implementation. As a library the code would probably be rewritten, and also of course carefully documented. Chris
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
Some remarks and questions : passed as a template parameters ?
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
In particular, getting correct behaviour for the copy constructors of the container is difficult, and it is not
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. possible to give a correct
definition of max_size, which is more important for small-sized containers. Why exactly ?
2008/8/7 joel falcou <joel.falcou@u-psud.fr>:
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
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).
Nice trick ! So I think this cover my worry on this subejct :)
a) Implementations of std::vector behave badly in tight memory
circumstances. <snip> I wonder if some of the STL container and/or assorted algorithm doesn't need a somewhat modern clean-up/rewrite or are they that much "holy" that we shouldn't/couldn't provide proper alternatives with backward compatible interface.
b) When you have a container which holds few elements, it is nice to be able to check how many things it can hold. <snip> That's indeed a problem
2008/8/7 joel falcou <joel.falcou@u-psud.fr>:
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).
Nice trick ! So I think this cover my worry on this subejct :)
a) Implementations of std::vector behave badly in tight memory
circumstances. <snip>
I wonder if some of the STL container and/or assorted algorithm doesn't need a somewhat modern clean-up/rewrite or are they that much "holy" that we shouldn't/couldn't provide proper alternatives with backward compatibl interface.
Certainly I personally feel allocators were a mistake. They seem to be designed to badly cover a number of poorly defined use cases, but often not the use cases I often want. Howard previously worked on an extension to allocators which would have fixed the majority of these problems, in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html . However, this tragically seems to have died on the vine as C++0x approaches. Chris
b) When you have a container which holds few elements, it is nice to be able to check how many things it can hold. <snip> That's indeed a problem
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
on Thu Aug 07 2008, "Chris Jefferson" <chris-AT-bubblescope.net> wrote:
Howard previously worked on an extension to allocators which would have fixed the majority of these problems, in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html . However, this tragically seems to have died on the vine as C++0x approaches.
Regardless, a great many allocator upgrades are going into C++0x. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Hi,
From: Chris Jefferson
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; } };
You may consider reusing boost::mpl::int_, which does exactly the same. Best regards, Robert
participants (4)
-
Chris Jefferson -
David Abrahams -
joel falcou -
Robert Kawulak