References


This page references source code implementations as well as other memory allocation related readings.

Working implementation of the malloc v2 proposal: http://github.com/ned14/nedmalloc

nedmalloc.h specifying the malloc v2 proposal along with a policy driven STL allocator class: http://github.com/ned14/nedmalloc/blob/master/nedmalloc.h

Related standard change proposals:

  1. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html (Improving STL allocators by Ion Gaztañaga. Aimed at reducing memory wastage). A slightly later revision is available from http://www.drivehq.com/web/igaztanaga/allocplus/.
  2. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html (The Electronic Arts slightly modified STL for games applications. STL compatible except for std::allocator<> which it replaces)
  3. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1850.pdf (Towards a Better Allocator Model by Pablo Halpern. Points out that a container’s allocator type is inseperable from that of the container i.e. two identical STL container types are incommensurate if their allocator is different, yet C++ happily lets you FUBAR everything without warning).

Relation of the above to this proposal:

  1. These proposals appear to be aimed at increasing the complexity of the allocator API in order to reduce memory wastage. This proposal doesn’t care about memory wastage, rather it is aimed at reducing memory bandwidth usage which is a far more pressing concern.
  2. Lots of good stuff in this proposal. However, much of it is down to poor STL implementation quality as evidenced by the fact that their STL is ABI compliant with the ISO one except when it comes to std::allocator<>. Much of the rest of their issues stem from poor compiler optimisation which was a problem with pre-v3.4 GCCs, or the lack of move construction and other optimisations enabled by rvalue references. As for their specific concerns with std::allocator<>, I refer to the next section below.
  3. I completely agree that how std::allocator<> has been done is fairly woeful, and I don’t think anyone who has looked at it can think highly of it. However, it turned out this way due to the early STL allocator work by Stepanov being unacceptably abstracted from reality at such a low level at that time, so you got the “STL allocator lite” we see today. See section below.

The Original Stepanov C++ STL allocator design:

Quoting from Wikipedia’s history of the development of STL allocators:

Alexander Stepanov and Meng Lee presented the Standard Template Library to the C++ standards committee in March 1994.[1] The library received preliminary approval, although a few issues were raised. In particular, Stepanov was requested to make the library containers independent of the underlying memory model,[2] which led to the creation of allocators. Consequently, all of the STL container interfaces had to be rewritten to accept allocators.

In adapting STL to be included in the C++ Standard Library, Stepanov worked closely with several members of the standards committee, including Andrew Koenig and Bjarne Stroustrup, who observed that custom allocators could potentially be used to implement persistent storage STL containers, which Stepanov at the time considered an “important and interesting insight”.[2]

From the point of view of portability, all the machine-specific things which relate to the notion of address, pointer, and so on, are encapsulated within a tiny, well-understood mechanism.—Alex Stepanov, designer of the Standard Template Library

The original allocator proposal incorporated some language features that had not yet been accepted by the committee, namely the ability to use template arguments that are themselves templates. Since these features could not be compiled by any existing compiler, there was, according to Stepanov, “an enormous demand on Bjarne [Stroustrup]’s and Andy [Koenig]’s time trying to verify that we were using these non-implemented features correctly.”[2] Where the library had previously used pointer and reference types directly, it would now only refer to the types defined by the allocator. Stepanov later described allocators as follows: “A nice feature of STL is that the only place that mentions the machine-related types (…) is encapsulated within roughly 16 lines of code.”[2]

While Stepanov had originally intended allocators to completely encapsulate the memory model, the standards committee realized that this approach would lead to unacceptable efficiency degradations.[3][4] To remedy this, additional wording was added to the allocator requirements. In particular, container implementations may assume that the allocator’s type definitions for pointers and related integral types are equivalent to those provided by the default allocator, and that all instances of a given allocator type always compare equal,[5][6] effectively contradicting the original design goals for allocators.[4]

Stepanov later commented that, while allocators “are not such a bad ideas in theory (…) [u]nfortunately they cannot work in practice”. He observed that to make allocators really useful, a change to the core language with regards to references was necessary.[7]

Things are different today – we now have template template type arguments as well as rvalues and variadic templates. These ought to allow the implementation of most of the original 1994 STL allocator design including the rather cool and extremely useful idea of persistent state. I’d personally propose that rather than N1850, N2045 or N2271 – if you’re going to introduce breaking changes, you might as well go the whole hog.

The other thing I would add is that it is rather useful to implement the STL allocator class as a policy driven class i.e. one supplies an arbitrary number of template parameters which are used to incorporate the allocator instance. This lets you work around the lack of state in most cases by letting you do dirty things like supply a pointer to a state structure as one of the template policies (yes this is dirty, nasty and wrong. But it works), or even more evilly you can supply a pointer to a function which is upcalled in certain circumstances.

Personally, my own criteria for STL feature inclusion are:

  1. Does it standardise usage for a really, really, really common use case? If so include.
  2. Can the desired functionality be implemented in any other way using existing features (even if ugly)? If so reject.
  3. Does it provide a standard API for desirable non-portable platform features otherwise unusable? If so include.
  4. Otherwise it belongs in the Boost libraries as a third party addon. Or elsewhere again. Not in an international standard.

On the basis of these criteria I don’t think that most of the prior proposals listed above are utterly necessary as almost all of them come down to quality of implementation problems, language problems since fixed or solutions (if ugly) are already available. In case you disagree with my assessment, do consider how adding policies to std::allocator<> does indeed allow reasonably workarounds for a huge chunk of the problems with the existing STL allocator design.

However, to reiterate, I’d like to see the original Stepanov STL allocator intention returned. I think that in the process of doing that one might well find almost all these problems fixed anyway.

4 Comments

  1. Posted September 29, 2010 at 4:47 pm | Permalink | Reply

    To me, the original Stepanov STL allocator was a stateful allocator which formalized pointer and reference abstractions. I feel like I’m missing something critical here…?

    Among the problems I see with the existing STL allocator design are:
    – implementations must assume allocators are stateless
    – allocations cannot be arbitrarily aligned
    – blocks cannot be expanded or contracted, and there’s no way to determine the “real” size of an allocated block

    I don’t see how “adding policies to std::allocator” provides any kind of workarounds for the above issues. I’m not actually 100% sure what these policies you’re referring to are. Are you imagining something like

    template < class Buffer, Buffer* BufferPointer > struct my_allocator;

    and then feeding my_allocator’s template parameters with a pointer to some global buffer struct? I wouldn’t really classify this as a workaround (it’s arguably the correct approach if, indeed, you intend to allocator from some global structure), and it’s certainly reasonable until you actually want your allocation source to be runtime-dependent. And this is only an attempted workaround for the lack of state in allocators. I don’t see how policies can enable you to more efficiently deal with block sizes. Aligned allocation can be hacked in by over-allocating, but that is certainly a subpar solution.

    – Jeff

    • Posted October 1, 2010 at 11:58 pm | Permalink | Reply

      I fixed your missing < and > for you.

      The original Stepanov STL allocator design performed a complete abstraction of the memory model, so std::list performed all of its dealings with memory via its allocator. The theory was – at that time – that you could cope with a segmented rather than virtualised linear memory design because std::allocator would tell the compiler the appropriate machine-specific markup to describe whether some memory access was near segment or far. Equally, there was no reason why the same memory accesses could not be entirely on disk e.g. via a memory mapped file. Or more interestingly for the future, one could implement a transactional memory model where operations can be rolled back.

      The reason they dropped this – according to Stepanov (http://www.stlport.org/resources/StepanovUSA.html) – is because:

      vector a(…);
      vector b(…);

      you cannot now say:
      find(a.begin(), a.end(), b[1]);

      … because b[1] returns a alloc2::reference which may or may not be the int& required by find(). And C++ did not at that time allow you to provide type conversions apart from “to a base class” for object references, just for objects. One could I suppose return an object with an implicit converter to the requisite reference type, but I’d doubt that was feasible back then in pre-metaprogramming days.

      Regarding template policies, I’d refer you to http://en.wikipedia.org/wiki/Policy-based_design. In the case of nedmalloc’s policy driven STL allocator, one might do:

      typedef vector<SSEVectorType, nedallocator<SSEVectorType,
      nedpolicy::align<16>::policy,
      nedpolicy::zero<>::policy,
      nedpolicy::typeIsPOD<true>::policy
      > > SSEvector2Type;
      SSEvector2Type SSEvector2(5);

      Fairly intuitively one is specifying an alignment of 16, always bit zeroed contents and that the type is POD (which means that nedallocator::reallocate() is allowed to relocate the storage). You can specify as many or as few policies as you like, and usually in any order. This is what I mean by saying that one can encapsulate much of the need for instance state in the type itself.

      Regarding STL allocators at all, they are a fundamentally borked design – but far more than the arbitrary restrictions placed on them by the ISO spec. In my opinion, I would have ALL the STL container classes policy driven and one of those policies would be the storage model, and a different and quite separate policy would be the allocation strategy employed (after all, the two are quite separate and don’t actually have much to do with one another). Yet another set of policies again would handle how to convert between different instances and dissimilar policied types of the container.

      However, such a design would have to live for years in the Boost libraries before standing a chance of acceptance into the ISO standard. And in the end, especially given the difficulties in attracting funding to develop the STL at all back in the day, I would very much doubt that sufficient funding for such a project could be attracted now.

      Niall

      • Posted October 4, 2010 at 9:49 am | Permalink

        > I fixed your missing for you.

        Thanks.

        > The original Stepanov STL allocator design performed a complete abstraction of
        > the memory model, so std::list performed all of its dealings with memory via
        > its allocator. The theory was – at that time – that you could cope with a
        > segmented rather than virtualised linear memory design because std::allocator
        > would tell the compiler the appropriate machine-specific markup to describe
        > whether some memory access was near segment or far. Equally, there was no
        > reason why the same memory accesses could not be entirely on disk e.g. via a
        > memory mapped file. Or more interestingly for the future, one could implement
        > a transactional memory model where operations can be rolled back.
        >
        > The reason they dropped this – according to Stepanov
        > (http://www.stlport.org/resources/StepanovUSA.html) – is because:
        >
        > vector a(…);
        > vector b(…);
        >
        > you cannot now say:
        > find(a.begin(), a.end(), b[1]);
        >
        > … because b[1] returns a alloc2::reference which may or may not be the int&
        > required by find(). And C++ did not at that time allow you to provide type
        > conversions apart from “to a base class” for object references, just for
        > objects. One could I suppose return an object with an implicit converter to
        > the requisite reference type, but I’d doubt that was feasible back then in
        > pre-metaprogramming days.

        …but should be feasible now, correct? What are the *present* technical
        obstacles standing in the way of proposing a “Stepanov allocator” ?

        > Regarding template policies,
        […]
        > Fairly intuitively one is specifying an alignment of 16, always bit zeroed
        > contents and that the type is POD (which means that nedallocator::reallocate()
        > is allowed to relocate the storage). You can specify as many or as few
        > policies as you like, and usually in any order. This is what I mean by saying
        > that one can encapsulate much of the need for instance state in the type
        > itself.

        I have been under the impression that one of the basic uses of instance state is
        to specify *where* an allocator should obtain its memory from, which is what I
        thought you were alluding to.

        > Regarding STL allocators at all, they are a fundamentally borked design – but
        > far more than the arbitrary restrictions placed on them by the ISO spec. In my
        > opinion, I would have ALL the STL container classes policy driven and one of
        > those policies would be the storage model, and a different and quite separate
        > policy would be the allocation strategy employed (after all, the two are quite
        > separate and don’t actually have much to do with one another). Yet another set
        > of policies again would handle how to convert between different instances and
        > dissimilar policied types of the container.

        I don’t think it’s technically a problem to combine the storage model policy and
        the allocation strategy policy, as (I suppose) is done now, similar to how one
        could just as easily combine the hashing policy and equality comparison policy
        in a hash table. I think it *is* technically a problem that all allocator
        instances of the same type may be assumed to be equal.

        I don’t think “adding policies” solves very many of the problems at all with the
        current STL allocator. I think what’s desired (by some) at this point is an
        extension of the API to better communicate memory usage: expansion and
        contraction of blocks, determination of the actual allocated block size, and a
        separation of array and node allocation (to name a few).

        – Jeff

      • Posted October 7, 2010 at 3:56 pm | Permalink

        > > … because b[1] returns a alloc2::reference which may or may not be the int&
        > > required by find(). And C++ did not at that time allow you to provide type
        > > conversions apart from “to a base class” for object references, just for
        > > objects. One could I suppose return an object with an implicit converter to
        > > the requisite reference type, but I’d doubt that was feasible back then in
        > > pre-metaprogramming days.
        >
        > …but should be feasible now, correct? What are the *present* technical
        > obstacles standing in the way of proposing a “Stepanov allocator” ?

        Technical obstacles: none to my knowledge, apart from some code breakage with existing usage of the STL.

        There would be huge cultural obstacles though. And the biggest one of all: insufficient people thinking it broken enough to require fixing.

        > > Fairly intuitively one is specifying an alignment of 16, always bit zeroed
        > > contents and that the type is POD (which means that nedallocator::reallocate()
        > > is allowed to relocate the storage). You can specify as many or as few
        > > policies as you like, and usually in any order. This is what I mean by saying
        > > that one can encapsulate much of the need for instance state in the type
        > > itself.
        >
        > I have been under the impression that one of the basic uses of instance state is
        > to specify *where* an allocator should obtain its memory from, which is what I
        > thought you were alluding to.

        Sure, that would be the most common use requirement for most people. However, as I said later, one is trying to wrap two quite separate policy settings in one std::allocator which isn’t very good at either in the default ISO design.

        > I don’t think it’s technically a problem to combine the storage model policy and
        > the allocation strategy policy, as (I suppose) is done now, similar to how one
        > could just as easily combine the hashing policy and equality comparison policy
        > in a hash table. I think it *is* technically a problem that all allocator
        > instances of the same type may be assumed to be equal.

        Sure, but I am very sure that those requirements were added for very good reasons at the time they were added. On average, the decisions made to date in the development of ISO C++ have been remarkably good and sometimes amazingly prescient given the then state of compiler quality.

        My point is that given how these restrictions were added, just coming along and saying “undo them!” is highly unlikely to be successful. Besides, I and you and pretty much everyone else would say that std::allocator is the wrong way to implement what we want to implement. So why mend something which is fundamentally broken when a proper choice ought to be the correct implementation in the first place?

        > I don’t think “adding policies” solves very many of the problems at all with the
        > current STL allocator. I think what’s desired (by some) at this point is an
        > extension of the API to better communicate memory usage: expansion and
        > contraction of blocks, determination of the actual allocated block size, and a
        > separation of array and node allocation (to name a few).

        That isn’t what I said actually – I said that adding policies to the *container* *classes* themselves is the right way to implement this functionality (and while you’re at it, a whole load of other functionality too). In fact, things like std::vector and std::list and all the others should simply be a predefined assembly of policies i.e. convenience templates which stand for a certain default set of policies.

        One then you see could assemble any arbitrary STL container by combining whatever policies you want, mixing in bits of your own code via mixing in your own policies. One thus arrives back at the original Stepanov intent of completely generic algorithms which assemble and optimise themselves based on the structure of type relations in the assembly.

        Niall

Post a Comment

Required fields are marked *

*
*

%d bloggers like this: