Welcome, everybody, to the 237th talk on allocators at CppCon 2017. (audience laughs) My name's Bob Steagall. I'm here on my own dime
representing myself, and I'd like to talk a little bit about how to write a custom allocator. I think you'll find by
the end of the talk, it's really more along
the lines of guidelines for how to write a custom allocator. There's so many different
things that you can do. It's hard to prescribe anything except what I think are some useful principles. I was walking back to my hotel a couple of evenings ago, and I happened to be walking along with John McFarlane, who gave a talk a couple of days ago. And he made probably the most cogent and profound observation about allocators, I think that I have ever heard. We've all heard heroic tales
of other people doing this. (audience laughs) That being said, what I'd like to do is
provide a little bit of useful background in understanding the modern allocator facilities. So, I'll try to get through the background stuff pretty quickly. And also, I should say
I've got a lot of slides. The slides are numbered,
so if you have questions, I'd ask you to please hold until the end, unless I've done something
really super egregiously wrong. So, what is an allocator and why would you wanna write your own? I think I'll try to
address that a little bit. I'd like to provide a
little bit of background, go under the surface a little bit to understand the original
allocator facilities. I'm going to spend a
fair bit of time trying to describe the modern
allocator facilities at a fairly shallow level. I think in order to
understand that the principles on the last couple of slides about how to write an allocator, it's necessary to understand a little bit of how the allocator
facilities themselves work. And I say facilities because there's no longer simply an allocator class. There's a whole set of
classes that work together to provide allocation services to the new standard
containers and other things. I'll spend a few slides talking about the modern allocators from
a container's perspective. As you write your allocator,
I think it's useful to understand how a container
will use your allocator. It's much more complex than
it used to be before C++11. And as I said, I'd like to
end with a few guidelines. I'd originally wanted to give
the talk over two sessions, but there wasn't enough
time in the program. So, I'm gonna end on guidelines instead of a lot of examples. So, let's talk about what an allocator is, or what the purpose of an allocator is. In the 4th edition of the
C++ programming language, Bjarne Stroustrup says
that the basic purpose is to provide a source of
memory for some given type, and a place to return that memory to once it's no longer needed. Earlier in the week, I'm stealing a quote from Alisdair here, an
allocator is a service that grants exclusive use of a
region of memory to a client. And the corollary to this
that I didn't put on the slide is that hopefully the client will be good and give that memory back at some point. So, what's a standard library allocator? Well, it's a kind of object that used by the standard library to manage memory. Usually, we see it as
an implementation detail of the standard containers,
as a template parameter. It's that thing off to the right that's got a default argument that nobody ever really
looks at or messes with, and just kind of pretends
it doesn't exist, because it can be painful
if you don't pretend. Allocators were invented
by Stepanov many years ago as part of the original STL. It was partly an attempt
to solve the problem of different sized pointer types on DOS, which was the dominant
operating system of the time. There was this funny
16-bit addressing model with segments and offsets,
but you could address more than 16 bits of memory. And consequently, there were pointers that had different sizes. And there was a desire to
abstract those weird things away from the compilers, or the containers. They didn't need to think
about that or be aware of it. After some review a long time
ago by the committee long ago, there was also a desire
to make the library itself more flexible and independent of these underlying pointer types. I think also there was a recognition that containers have special needs. They need an interface
that's more granular, a finer level of control than
the new and delete operators. They want to perform
allocation, construction, destruction, and deallocation as four separate and distinct things. And this is what the service
that allocators provide. Most importantly perhaps,
they separate allocation from construction, which is
different than the new operator. And they separate destruction
from deallocation, which is different than the
way the delete operator works. They encapsulate information
about the allocation strategy. And by that, I mean the algorithms by which the allocator
carves up blocks of memory into chunks, and hands
those chunks to its client. The containers don't need
to know what that is. They encapsulate information
about the addressing model. I just mentioned one
possible addressing model, that of near and far pointers under DOS. As it turns out in Modern C++, you can have addressing
models besides that which is provided by native pointers. And of course, it goes without saying that they hide memory management and address model details
from the containers. The containers don't need
to know about these things. They just have a very simple interface that they use to get the
memory that they need to construct objects, destroy objects, and give the memory back. And if we're lucky, a
well-written allocator will support reuse and you can use it across container types,
if that's suitable. So, why would you wanna
write your own allocator? It seems like a lot of
work, and actually it is. Well, the reason that's
most often given is you want to get higher
performance in some way. You might desire to implement some sort of stack-based allocator. You have a container, you
don't wanna go to the heap. Perhaps you only need a fixed
limited amount of memory and you know you're never
gonna need more than that. Maybe you want to somehow
exploit locality of reference with data that's also on the stack. You may want to have a heap, whether it's on the stack or not, that
is dedicated exclusively to a particular container. I'm never gonna share
elements with anybody else. I'm never gonna swap
elements with anybody else. Maybe you're doing some
sort of embedded thing, and you've got a linked list of stuff, and you're never gonna share it, or delete it, or move it, or swap it. So, maybe that's
something that makes sense for your application. You might want to have
per-thread allocation. Perhaps you're doing
something where your memory that you allocate is only gonna be used by containers in their respective threads. And memory that's allocated in one thread is never gonna be deallocated
in another thread. Or maybe you wanna write an allocator that doesn't have the overhead of locking and unlocking like you would with a multi-threaded allocator. You might wanna do some sort of pooled or slab-based allocation strategy, which might be appropriate
if your allocation pattern is one in which you have a set of sizes. All of the chunks that you allocate fall into one of a small set of sizes. And you can have pools that
allocate from a certain size, or slabs that allocate
from a certain size. Perhaps you think that you can get some better performance that way. You could try to implement
an arena allocation strategy, where you are building up some data, some data structures, and
you're gonna allocate everything from an arena and everything that points to everything else exists
inside of that arena, everything is constructed
inside of that arena. Maybe there are no system
resources here that you have to worry about giving back to the OS. And when you're done,
to destroy everything, you just flush the arena. You don't have to destroy the elements. You just let the arena go
and everything winks out. Maybe, which could be
potentially more practical, you wanna write a debug allocator. You have some memory allocation thing that you're trying to debug. Or you want to instrument your allocation. You want to measure how many allocations of what size you're doing. Or perhaps you have a test allocator where you want to simulate some sort of error conditions that can only occur when you're trying to allocate something. And closer to my heart, I'm interested in the idea of relocatable data. Building data structures in such a way that they are address independent. For example, building data
structures in shared memories such that those data structures
can be correctly accessed by different processes
in which the segments of shared memory are mapped to different addresses in those processes. Or you might try to do something, what I call a self-contained heap, where you build a structure
in a sequence of bytes, and you wanna do a socket send of those bytes to somebody else. So, when they get those bytes, they wanna be able to use it without any sort of fancy deserialization. It so happens I have a couple of pictures of this, which I'm proud that I made and I'm gonna reuse very quickly. Shared memory data structures. Imagine you have two processes, P1 and P2, and I've got some segments in shared memory, S1 through 32. And inside those shared memory segments, I'm making something here which is supposed to look like a binary tree, with the root being in S1 there. In process P1, the operating
system has mapped all of those segments into a set of addresses. In process P2, each of those
segments has been mapped into a different address. And yet, I wanna be able to use that tree in both processes without any special serialization
or deserialization. I want to abstract that addressing model and hide it in a fancy pointer type. And I want my containers just to work without needing to know about it. A second application that is
of the self-contained heap or self-contained DOM. Imagine for a second this is represent some document object model. Maybe it's a very simple thing that I've stuck in a red-black tree. Maybe it's some strings or something. Well, I can imagine
creating a data structure where on the left there,
you've got three things which comprise the essence
of my tree structure, and they are placement constructed into the beginning of some buffer, and there's a heap behind,
a tail buffer so to speak. My allocator points into that buffer, and I have pointers
inside the data structure which point to my
left-most node and my root. I would like to be able
to traverse that tree, no matter what address
this buffer lies at. I should be able to take buffer, memcpy it to a totally different
address and use that tree. With Modern C++ allocators
and the facilities that support fancy pointers,
or synthetic pointers, or pointer-like types,
whatever they're called, you can do this. And I've given a couple of talks on that. This is not the subject of the talk today. So, I wanna give a very
quick history of allocators, because I think there's some
important background here. So, let's take a quick look back in time. The old picture was very simple, containers were parameterized
in term of an allocator. And they used the services
of that allocator directly. The containers were free
to assume in C++98 and 03 that a pointer was a T star. A const pointer was a T const star. A void pointer was a void star, and so on and so forth down the list. They were also free to
assume that any two instances of a given allocator
template compared equal. They were also free to
assume that any two instances of an allocator were interchangeable. And by that, what I mean is the little code snippet you see on the last line. In old school allocators,
you could allocate some bytes from allocator instance
b and deallocate them in allocator instance b. In fact, allocator a
and b didn't even need to be of the same type. You could have an allocator of int that you could allocate some bytes from, and you could deallocate it
with an allocator of double. So, the old allocator was
actually a pretty simple beast, very straightforward. There was a set of typedefs at the top which provided definitions that
were used by the containers. The attempt to abstract these details that I talked about before. There was this funny
thing called a rebinder, and I'll come back to that
in a couple of minutes. There were four important functions. There were a few other functions, but I'm concentrating on
the important ones here. Allocate and deallocate,
construct and destroy, which performed the four services that I talked about before, allocation, construction, destruction,
and deallocation. And finally, there were
the comparison operators. So, allocation and deallocation
are almost trivial. The standard required them,
or said that they should occur by using operator new for allocation, and global operator
delete for deallocation. Construction and destruction services are likewise very simple. They use placement new for construction, and directly invoke an object's
destructor for destruction. An interesting thing to notice here, and this is part of the standard. I copied this stuff out of
an old copy of the standard. Is that these member
functions actually work in terms of this typedef pointer, p. Now, point the type pointer is a T star, but they chose to use the typedef here in the signature of the member function. I've never quite understood
why they did that because pointer was
required to be a T star. Finally, comparisons under
this model are trivial. All instances of the
old default allocator, and even the new default
allocator, are required to always compare equal for all instances. Let's go back for a minute
to this strange rebind thing. What does it do? Its purpose is to transform
an allocator specialization of one type, one template argument, into an allocator specialization of a different template argument. So, before we had template type aliases, the way we did this was
by defining a small struct that had a member that we would use to do that type transformation. So, here's a quick example
of what that would look like. Suppose that we were implementing a list. Well, the template signature of list is it's parameterized
by the element type T and an allocator of T. But in a linked list,
you don't allocate Ts, you allocate list nodes of T. I never need to allocate a T, I need to allocate a list node. So, what the rebinder
did was provide a way to transform the type, allocator of T, into allocator of list node of T. And so, in the highlighted
text along the top there, you can see the egregious syntax that's required to make that happen. So, you could then create
this new allocator type from that, extract the type of the node, the pointer to the node,
which is what you wanted, and then maybe you would
have some member function that allocated a node and
constructed an element into that node as part of the allocation. And that's reflected
by the little function that you see at the bottom. So, there was some consequences resulting from these allocator requirements. Because pointers were
always assumed to be T star, that meant that there was no
support for fancy pointers, or pointer-like types, or anything that could address shared memory or create a self-contained heap. Because implementations
assume that instances were always equal and interchangeable, that meant your containers could not be used with stateful allocators. If you had an allocator that
needed to maintain some state, like the thread id that I'm operating in, or the container to which I
belong, you couldn't do that. So, there were a lot
of interesting problems that you couldn't solve
with those allocators. And also, in a corollary problem, scoped allocation was tricky. Consider the case where you wanted to create a nested hierarchy of stuff. Perhaps you wanna create
a map that maps strings to vector of list of strings. Well, it's kind of tricky to
set all of the templates up, all of the allocator types up so that everything allocates
from the same allocator, from the same instance
of the same allocator. And perhaps you would wanna do that because you managed to create some sort of stateful arena allocator. So, it was kind of tricky
to make that work correctly in the old standard, although
it was not impossible. So, I'd like to wade ankle
deep into the new things. So, to a large extent, this
talk is about plumbing. As an allocator author,
you need to know how to connect the plumbing
from your allocator to the plumbing that expected
by the standard containers. Now, when you first dig in to
the new standard allocation, it kind of looks like
the picture on the left. That's what I felt when I first
started learning about it. But after a while, you come to realize it's a little more orderly than that, and it's really closer to
the picture on the right. There is method to the madness
underneath the surface. So, with C++11, there are a
lot of changes in the standard to address the shortcomings
of the old school allocators. And this is a non-exhaustive
list of different places in the standard that
requirements were added that provide these new capabilities. And they're not all in one place, they're spread all over the place. And the numbers keep changing. So, what I've done, if you
wanna look these things up, is provide the tags by
which these requirements are found in the standard. They're the bits that are italicized. So, we have things that define
what a nullablepointer is, the basis of a pointer-like type. We have a requirement that defines what an allocator is conceptually and its relationship to
the allocator traits. We have a thing that describes something called pointer traits, which
is used by allocator traits that we'll come to in a few minutes. We have allocator
traits, probably the star of the whole show, which
describes a uniform interface to allocator types that
are used by the containers. We have this thing called
a scoped allocator adapter that's described in the
allocator.adaptor section, which helps setting up those nested hierarchies of standard containers, and supports a deep
propagation of allocators. And then we have another
very important section, the general container requirements, which defines what an
allocator-aware container is. And this allocator awareness is the key, in my mind, one of the most important if not the most important difference between allocators in Modern C++ and containers in Modern C++, and the allocators and
containers in old school C++. So, this is a picture of the
model that I have in my head. I don't claim that it's correct, but it's the way I visualize thing. And this is sort of a
bastardization of UML, the dotted arrow means the word, uses. So, working upward on the diagram, the standard containers now
get all of their information about memory from the
allocator traits template. The allocator traits
template is the interface, the wrapper to any kind of allocator that you might wanna use. Now, the allocator traits
template builds a picture of the storage services that are provided by the allocator itself,
and it also uses services of the pointer traits
to transform information that it gets from the allocator into other pieces of information
that it finds useful. It presents this picture
to the standard containers through its public interface. And we'll see what that
public interface is in a couple of minutes. So, the allocator, this is
the piece that you write, this is the thing that provides, at a minimum,
allocation-deallocation services. There's a very small number of things that a minimal allocator has to provide in order to work with
a standard container. There is a larger number of things that you can override to
customize its behavior. And as I said earlier, the
pointer traits template is used to transform information received from the allocator for the
purposes of allocator traits. As you can guess, it's
a way of transforming type information about pointers that's provided by the allocator to pointers that the container might need. For example, a pointer of T star to a pointer of list node of T star. So, you heard me mention
allocator awareness a couple of moments ago,
and what does that mean? Well, pedantically speaking,
it means fulfilling the requirements that you'll find in Table 86 of the recent draft standard. And I think the standard
that will be adopted here, or has been voted in and
we'll see published soon. There's a large number
of these requirements, I'm not gonna reproduce them here. I'm just gonna say, "If
you're really interested, "go look at this table." But in general, allocator awareness means doing something that makes
sense when a container uses an allocator that is
not the default allocator. And in the case of Modern C++, this means being able to
support synthetic pointers for addressing operations, having nontraditional addressing models, having allocators that can contain state, having allocators that can be non-equal and non-interchangeable, or allocators that can have non-trivial
copy, move, and swap semantics. The old school allocator
was completely stateless. As I said, every instance
of that allocator was in a sense equal to every other instance. You don't have to do that anymore. You have a lot more
power at your fingertips. So, I mentioned on this
slide the word, propagate, having to do with copy,
move, and swap semantics. So now, I'd like to talk a little bit about quickly what propagation
means, allocator propagation. Say that three times fast. So, there are two kinds of propagation, lateral propagation and deep propagation. At least that's the terminology
that's in common usage. So, lateral propagation
refers to what happens to a container's allocator
during the process of copy construction, move construction, copy assignment, move assignment, or swap. Deep propagation refers to the process of nesting the allocator type and instance of the outermost container
in a container hierarchy down into the innermost container. Consider again the
previous example of a map that map strings to
vector of list of strings. And you wanna pass the
same allocator instance down to all of those
guys so they can allocate from the same arena. The scoped allocator adapter was designed to help with exactly this situation. I'm not gonna say much more about that because it's not really super relevant to this conversation today. So, the focus today is going
to be on lateral propagation. So, of course, there are consequences. For library implementers, they really had their work cut out for 'em. Containers now had to be
rewritten to perform all of their operations using the
allocator traits template. They had to support non-equal allocators. Over the years, they started
to support non-equal allocators but now they're required to. They had to support lateral propagation in copy, move, and swap operations. And they also included a new set of constructors called the
allocator extended constructors to support deep propagation. Again, I'm not gonna
really mention those today. On a lighter note,
containers no longer used these nested typedefs called reference or const reference that you saw in the old school default allocator. Allocator traits construct
uses perfect forwarding, avoiding a possible
inefficiency that occurred with the old school construct
of the old default allocator. And interestingly enough,
I pointed this out before, construct and destroy as
part of allocator traits now have T star in their signature instead of the pointer type alias. So, if you actually, if you have a if you have a pointer,
some synthetic pointer to some type, you have to
provide a conversion operator to the native pointer of that type if you wanna use
allocator traits construct to construct an instance
using that pointer. For library users, life got easier. If somebody has a library with
a stateful allocator in it, and you think it works, it
should be pretty easy to use. It's relatively safe
and straightforward now to do scoped allocation with
nested container hierarchies. Some mutating container
operations may lose their noexcept guarantee,
depending on the implementation. For allocator implementers,
it was kind of a mixed bag. Part of it was easier and
part of it's more difficult. Certainly, some of the
verbiage was removed. There's no need to implement
construct and destroy, or have reference or
const reference typedefs. And really, the work
that you need to do is in thinking about what properties and services that you wanna specify, or that you wanna override the ones that are provided by allocator traits. And that's actually the hard work, deciding for my new allocator, how am I gonna specify copy, move, or swap operations if it's stateful? How am I gonna represent
pointers if I wanna use some sort of nontraditional memory addressing model? So, let's take a quick partial look at what the containers expect. Here's a phony container
which has a signature that's at the top of the container that's kind of similar to
most of the containers. There's a typedef for value type. There's value type, which is required. There's a typedef called allocator type. There's a typedef now
for allocator traits, which is a specialization
of allocator traits in terms of the allocator type. Then there are these typedefs for pointer, const pointer, size type,
and difference type. And now, these are expressed in terms of the equivalent type
from allocator traits. Allocator traits is providing information to the container, which the container is going to use internally. And down at the bottom,
the containers still use these typedefs reference
and const reference, but they don't get them
from the allocator anymore, they implement them themselves. So now, let's jump knee
deep into allocator traits. As I said, this is sort of the wiring that holds it all together. And I'd like to talk about
the important public parts of the allocator traits interface. As I said, it provides a uniform interface to allocators that's
used by the containers. It attempts to get
information from an allocator and normalize it in a way
that the container can use. If there is some bit of
information that is required by a container that's not
provided by your allocator, the allocator traits
will very cleverly pick what it thinks is a
reasonable default for it. It supplies a lot of boilerplate that had to be part of the old school allocators, and it's also backwardly
compatible with those allocators. It allows you to customize behavior by creating non-default
properties and functions. So, let's look at the top
half of the traits right now. You can see that several
of these things are here. By the way, I should say
what you're gonna see for the next few slides is not real C++, it's sort of a C++-ish
pseudocode to convey the example. A lot of these things that happen underneath the surface are
very scary metaprogramming and they will take a talk unto themselves, a talk that Alisdair gave three years ago on how to make allocators work. So, from the perspective of the container, the things that required
by your allocator, your allocator has to provide value type as a nested typedef. Then there's a bunch of
things that are inferred. And by inferred, if your allocator does not provide values for these things, or types for these
things, these are things that allocator traits will
make something up for you. The bottom half that I
wanna show here has to do with the services that are provided. Now, we've got allocate
and deallocate again, there's a second allocate overload. There are functions here,
construct and destroy, as before. You'll notice that construct
uses a template parameter pack and perfect forwarding so that the case of the default allocation doesn't, the case of constructing a vector of default constructed elements
is maximally efficient. One thing I wanna point out that's a part of propagation is this weird function at the bottom of the traits called select on container
copy construction. And we'll get to what that
is in a couple of minutes. So, for the various traits types, the types that are inferred,
how does this happen? Well, what I've tried to create here is effectively for each of these traits that the allocator traits expresses, I've tried to represent
the logic, or the priority, the set of priorities that
the allocator traits uses when deciding what these
things ought to be. So, for example, let's
look at pointer at the top. If your allocator alloc provides a pointer typedef, it will be used. Otherwise, allocator traits
will make the pointer its pointer typedef be value type star. Likewise, for void pointer,
if your allocator provides a typedef for void pointer,
that's what will be used. Otherwise, allocator traits
will use the rebinder from pointer traits to find out what is the correct void pointer type that goes with the type
pointer that in which your, the type pointer that
goes with value type. And I'm not gonna go over all of these, but hopefully, that will
be clear what I mean. Likewise, there are these
four nested typedefs having to do with
propagation, or three having to do with propagation and one
having to do with comparison. And again, it's the
same sort of thing here. If an allocator provides a
typedef for one of these, which has to be either std false type or std true type, that will be used. Otherwise, the default value for these propagation traits is to be false. In other words, the default action for an allocator is to not propagate on copy assignment, or
move assignment, or swap. For is always equal, this is a trait which lets the container know
whether two instance of an allocator type are always equal. If it knows at compile time
that it's always equal, there are some optimizations
that it can do in its code. Otherwise, allocator traits looks to see, is this allocator an empty object? And if it's an empty object, it assumes that they are always equal. - [Alisdair] Bob. Yes. - [Alisdair] I believe
those are actually values rather than types when you
put the example up there. Otherwise it's-- Did I get that wrong? - [Alisdair] I think so. Okay. - [Man] No, it's type. - [Alisdair] It conveys
the same information. - [Man] It's always equal as a type. Okay. - [Man] False type and true type. There are false type and true type, right? Okay. The allocator traits
also defines this thing, another rebinder, a thing
to rebind allocators, and it looks to see if there is a rebinder that's specified by the allocator. Otherwise, if your allocator is a template which has an element type as
its first template argument, and some zero more arguments, template arguments
afterwards, it will use that. It will use that as the rebound type. And if that doesn't
exist, or is not the case, then it's an ill-formed nested type. And then there are another rebinder which rebinds the allocator
traits themselves. In terms of the services, allocator traits will define the first load of allocate and also deallocate. And it defines these in terms of calling the corresponding allocate and deallocate functions
of your allocator. Those are member functions that your allocator's required to provide. The second overload of allocate
is chosen at compile time. If your allocator provides
the second overload, it will be used, otherwise,
the default will be to use the first overload. Likewise, with construct,
if your allocator provides a construct member
function, it will be used. Otherwise, placement new will be used. With destroy, if your allocator provides a destroy member function,
that will be used. Otherwise, the object type
will be destroyed directly by invoking its destructor. There is similar logic for max size, which is not really interesting. But the select on
container copy construction is kind of interesting. This is a mechanism by which an allocator at one time tells a container at copy construction time whether or not it should make a copy of an allocator. And we'll see an example
of how that's used. The logic is to look and
see, does your allocator define it's member function? If not, it's just gonna
return the argument. Now, I'd like to take a couple of minutes and look at the pointer traits helper. So, what does it do? Well, it describes the properties of pointers and pointer-like types. It also provides the types of
differences between pointers. If you have a non-standard pointer which is being used to
implement iterators, and you want your iterator differences to work correctly, that depends on taking the difference of the pointers upon which those iterators might be based. So, the idea is to, besides
pointer differences, is to provide the pointed-to type. So, given the type T
star, give me the type T. Given the type fancy pointer
of T, give me the type T. So, given some pointer type, give me the type to
which that thing points. They're also used to
provide a transformation from one pointer type
to another pointer type. They will have a rebinder, as well. Given the type T star,
get me the type U star. Given the type fancy pointer of T, give me fancy pointer of U. And T and U don't have
to be different types. They can be cv-qualified
differences of the same type. And I'd like to say just a couple of words about pointer-like
types, what the standard calls pointer-like types. I call them fancy pointers
or synthetic pointers. They're only mentioned four times in the recent draft standard. And the only real substance behind them is in the requirements for NullablePointer. And you can see those requirements in tabular form in Table 28. A NullablePointer is something that must satisfy several common requirements, EqualityComparable, DefaultConstructible, CopyConstructible,
CopyAssignable, and Destructible. They have to have swappable lvalues. I have to be able to
swap two of these things. If I default initialize it, I'm allowed to create an indeterminate result. Using that may result
in undefined behavior. If I value initialize it, I'm required to create a value that
represents a null result. Now, in standard, this idea of null result is not really defined. Construction and assignment
from a null pointer must also produce a null result. And I will say I don't
have it on the slide there, that if a pointer-like type contains a null result, then comparing it directly with the nullptr must return true. So, in effect it represents nullptr, but it doesn't have to
exactly have to be nullptr. These types have to be
contextually convertible to bool, so you can use typical if p syntax. And there are a set of
fundamental operations, which I'm not gonna list here, but which are in this Table 28, in which a synthetic pointer
may not throw exceptions. So, let's go back and look
quickly at pointer traits. This is a little bit of text which I've cribbed from the standard. These are relatively simple traits. There is a primary template
which is undefined, at least in the standard. There is a partial
specialization for T star. And so, given this partial specialization, there's a type pointer, which is T star. It's easy to get the
element type, which is T. The default difference type
for two T stars is ptrdiff t. There's a rebinder, which here unlike the old school allocators
is parameterized typedef that allows one to take a T
star and from it get a U star. And there's this function that's required that takes a reference
to the element type T and turns it into a pointer. In this case, a T star, but something which is this type pointer. And the default example in the standard is to use std addressof. Now, it's also possible
that you wanna have some sort of synthetic
or fancy pointer type. And so, confirming
implementations also provides this other partial specialization. So here, the nested type
pointer is actually equal to the type of the template argument. And I'm sort of trying to
show the same thing here, the sequence of steps
that this template takes to deduce what the typedef ought to be. So, for example, element type. If your typeptr defines a nested type element type, that's it. If ptr is a class template which has at least one argument, the type of that first argument is
the type of the element. If neither of those things happen, then a specialization or instantiation
of this is ill-formed. Likewise, with difference type, it looks to see is there
a nested difference type in your pointer type, if
not, it's a prtdiff t. And it also looks to see
does your pointer type have a rebinder, and if
it does, it uses that. Otherwise, it looks to see is
your pointer type a template, and it rebinds it by creating
a pointer type specialization with a different first argument. There is likewise the pointer to function which takes a reference. And the idea here is to
turn it into a pointer of your synthetic pointer type. This may or may not actually
be well-defined at runtime. If you could, for example, have
a set of synthetic pointers who only have meaning when pointing to things inside a
relatively small buffer. And that buffer may be very
far away from your stack. And if you have something
that's on your stack, and you use this function to get a pointer to that thing on the stack,
which is very far away and out of range for that buffer over which that pointer has meaning, that pointer will not have meaning. And probably computed at one time, but it's probably an error. So, we've looked at allocator
traits and pointer traits, so let's look at allocators themselves. Here's an example taken from
the text of the standard itself of a minimal allocator interface. This is the minimum amount
of work you have to do to create a standard conforming allocator. You have to provide a
nested value type alias. You provide a constructor
which may take some parameters. You have to have a converting constructor from allocators of a different type. You have to provide the allocate and deallocate member functions. And you'll also have to
provide compares equal and compares not equal operators. Very straightforward, very simple to use. This is a stateless allocator,
there's no member data. Any specialization can be constructed from any other specialization. Now, notice that if we
think about this in terms, what is allocator traits
gonna think about this? Allocator traits is gonna be parameterized in terms of this, and it's gonna have to return some type
information to the container. Well, we're interested in
the propagation traits. And the propagation traits
are by default all false. So, when this thing is parameterized or specialized by allocator traits, and that's presented to the container, the container is going to think that this does not propagate
on copy assignment. It does not propagate on move assignment. It does not propagate on swap. And because it's empty though, the allocator traits is going to believe that all instances of
this thing compare equal. The default allocator is
slightly more complex. It's basically the same idea. The real differences here are the fact that there is a default constructor, and that the propagate on
container move assignment and is always equal nested typedefs are actually defined here. The is always equal is defined true type, I think to ensure that
it's deliberately specified that all instances of
this allocator is true. And propagate on move assignment is true, so that containers can
maintain the no except property on move assignment. Likewise with the old school allocator, the implementation is
quite straightforward. Allocate calls global operator new, deallocate calls global operator delete. Notice I don't have construct
and destroy functions because those are provided
by allocator traits. Likewise, the equals and not
equals comparison operators return true and false respectively, indicating that all instances of this type always compare equal. That's not the whole story. There's a new kid in town. Starting with C++17 as part
of the std pmr namespace, there are now these new things called polymorphic memory resources, and I personally think
that this is a good idea. They provide the ability to
tailor the allocation behavior of a container at runtime
through dynamic polymorphism, rather than at compile time
through static polymorphism with different template types. The way they work, very simply
is that client allocator... the client allocator
types stores a pointer to a base class memory resource. And to actually create a memory resource, something that allocates memory, you derive your new type
from this base class and you implement a very small
number of member functions. In this particular case, there
is no lateral propagation. Alisdair said it very well on Monday. When you do this, when you use PMR and you instantiate an allocator, an allocator sticks for
life of the container. It doesn't get swapped, it
doesn't get propagated out. You create a container with
a PMR-based memory resource, that resource sticks with
the container for life. So, what's this base class look like? Well, it's pretty straightforward. There is this max align nested integer which tells the size of alignment. There are these public
functions for allocator and deallocate which are
required by allocator traits. There's a runtime function for is equal. And then the actual dirty
work is done behind the scenes by these private virtual functions that you would override in a derived class to actually provide these services. For example, in the
standard there is a PMR called monotonic buffer resource. It's publicly derived
from memory resource. It's got far more constructors
than I have listed here. I wanted to keep it all on one slide. There's a couple of
additional member functions. Of interest here is the fact
that the copy constructor and the copy assignment
operator have been deleted. Copying cannot be done, and by extension, moving cannot be done. And that goes along,
that confirms the idea or is in coincidence with the idea that these things do not propagate. They stick for life with the container. In this particular case, you can see that for this type, the do
allocate, do deallocate, and do is equal functions
are actually overridden and implemented in this type. And that's how you provide that behavior. There are a couple of more of these. There's a synchronized,
what's it called, Alisdair, synchronized memory buffer,
unsynchronized memory buffer? There is the general buffer,
the global memory buffer. There's more than
monotonic buffer resource. Pools, thank you, pools. Synchronized memory pool,
unsynchronized memory pool. So, to work with the memory resources, there is now in the PMR namespace, this allocator type that's designed to work specifically with these resources, the polymorphic allocator. And as an example of how
one might implement that, you can see that I've stored
in the private section here, a pointer to my memory resource. And I have my second constructor there as one that takes a
pointer to that resource. And what this means is that this resource has to be instantiated if
you want it to work nicely, have a longer lifetime than the allocator, which means having a longer
lifetime than the container. The memory resource has to have a lifetime that is a superset of the
lifetime of the allocators and containers that use that resource. Also, in this case, this
allocator, the allocator, the copy semantics and by extension, move semantics are deleted. They take on the default values for the propagation
traits, nothing propagates. Because this is not an empty class, and because this does
not specifically create the is always equal trait,
allocator traits will deduce that not all instances of this are equal. And so, there will actually
be a runtime comparison to determine, are two resources equal? And that will be handled by this member function, do is equal. And in the examples that I've seen, really it determines if
two resources are equal by looking at the value of
the pointer in the allocator. If both things point to the same resource, then the allocator is equal. The standard also provides some
type aliases, basic strings. I've listed a few of 'em
here, deques and sets, which you can use to create containers that use the PMR resources. I'm running low on time here. So, I'd like to talk very briefly, I'll probably skate through
these next slides very quickly. A question was raised the other day about, how do I write a container,
and how do I make my containers do the right thing with the
new allocator resources? And so, what I'm going to attempt to do, or what I've attempted to
do in the next set of slides in this section, is provide
a sort of pseudocode outline of how you would write
your default constructor, copy constructor, move constructor, copy assignment operator,
move assignment operator, and swap member function. And this is not real
C++ code, but hopefully, it will give you the idea
of how these things work. So, this is a repeat
of the previous slide, this is the top half
of my phony container. Here are the important special functions and the swap function. Here, for purposes of exposition is how I'm implementing my phony container. I've got something that I'm just calling my implementation data. I've got an instance of my allocator type. And for the purposes of
my outline functions, I've got two helper
functions, assign from, and clear and delete memory. Just so I don't have to
write lots of extra code. So, for copy construction, in the first copy constructor, I'm copy constructing another container and I don't have an allocator argument. This is where that funny
select on copy construction function comes from, and
this is where it's used. So really, the logic here is unless the allocator, m alloc, has a member function that returns itself or it returns a temporary, I am going to copy the
allocator that's part of other. So, what that means is,
I'm either going to copy from the allocator in the other, or it's going to be some temporary object because it doesn't propagate. I probably didn't explain
that very well, but maybe I'll come back to it. The second copy constructor
is very straightforward. I'm just going to assign
for my other implementation and I'm gonna copy construct my allocator. Move construction is actually
pretty straightforward. In the first, I'm going to
move from my implementation and I'm gonna move from
my other allocator, which may be trivial or maybe copying. In the second move constructor, I'm going to move from my implementation. Because I've provided a const
reference to the allocator, I'm going to have to
copy construct from that. Copy assignment is a
little more difficult, and this is where this is more
pseudocode than real code. And by the way, this
pseudocode was generated by looking at the class
std vector from Clang 4.0. It's much more complex code in there, but it's very well written. And Howard Hannett had a post
on stack overflow a couple of years ago and said, "If
you really wanna understand "this stuff, look at std vector in Clang," and that's what I did. So, I recommend looking at that code. Start with std vector and
look at the other containers if you wanna understand it. So, I wanna see, all right,
is my propagation trait true? If it's true and my allocator is different than the other allocator, I
wanna deallocate my memory. I wanna assign the other
allocator to my allocator. And then I wanna assign my elements. If my allocator doesn't propagate, I don't need to do that
stuff with the allocator. I'm just gonna assign
from the other elements. Pretty straightforward. Move assignment is trickier though. Move assignment and swap
are probably the trickiest. So here, if... if I propagate on move assignment, in other words, true type is the value of the traits list, the nested trait. Then I wanna clear my memory. I wanna move my allocator from my source. I wanna move my
implementation from my source. And then I'm done. If my allocator trait says that
allocators are always equal, or this allocator happens to compare equal to the allocator from the right-hand side, well, I'm still gonna clear
and deallocate my memory that's holding my elements right now. But I am just going to
move my implementation from the other container. I don't need to do anything
with the allocator, because I know that the
allocators are equal. Finally, if neither of
those conditions hold, then I'm just going to do a, effectively, a move assignment. And here is a case where you may lose the no throw guarantee,
even though I'm moving elements from the old container
into the new container. I may need to allocator memory, and an exception may be
generated in that case. Alisdair. (man speaking off microphone) Is it intentional-- (man speaking off microphone) Yes. Swap is also tricky. If propagate is set true, then
I can swap my implementation, I can swap my allocator. If my allocator traits say my
allocators are always equal, either by the value of the traits type or some runtime boolean test, then I'll just swap my implementation, there's no need to swap the allocators. However, if my allocators do not propagate or they are not equal,
then attempting to swap in that circumstance
is undefined behavior. Why is it undefined behavior? It's undefined behavior
because the standard requires all iterators to remain
valid after a swap. Now, in the last bottom
of the if ladder there, I may have to allocate elements. In which case, the
iterators to my old elements may no longer be valid, depending on what is the type of the container. All right, I'm getting
very close to the end here. Finally, I'd like to share in
the next two or three slides, some guidelines for how to think, or questions to ask yourself if you try to write your own allocator. So, design decisions. First thing you wanna think
about is the plumbing question, the big plumbing question. Do you need to write a
traditional allocator with all of that stuff in it, or do you wanna create
a new memory resource and just reuse the PMR? These days, I would recommend
start with PMR first. It's a lot easier, it's a lot simpler. Structural management for your allocator. In any case, you need to think
about the addressing model, the storage model, the addressing model, how do you dereference data? The storage model, where am I
going to get my memory from? Is it S-break, is it SHEMAT,
is it some other function? What's my big source of raw memory? The pointer interface, am
I using natural pointers or some sort of synthetic pointer that implements my addressing model? In the case of PMR, addressing model and pointer interface,
they're fixed for you. They are T star, there's no
real decision to make there. Your allocation strategy,
how are you gonna carve up big segments of bytes into little chunks that are used by your containers? Concurrency management. If you're gonna write an allocator that is gonna be used in a
multi-threaded application, you need to think about thread safety. If you're writing an allocator for a database engine
or something like that, you might even need to think
about transaction safety, keeping transaction logs
so that you can commit and roll back and do
transaction-safe allocation. So, if you're really like pain and you wanna build a
traditional allocator, I strongly recommend review the minimal and default allocator interfaces, and read the sections in the standards, those requirements that I
listed several slides ago. And decide how to specify the properties and functionalities that you want. Now, I haven't mentioned this
and I'm only gonna say it very quickly, you can
put all of that stuff in the allocator itself,
in your custom allocator. You're also allowed to
partially specialize allocator traits and pointer traits. I don't recommend doing that. I recommend put everything
in your allocator. You need to decide as I mentioned before, synthetic pointers or ordinary pointers. Do I need a self-contained
heap or shared memory, in which case you're gonna
wanna write a synthetic pointer, or can I get by with ordinary pointers because I don't care about that? If they're synthetic, don't forget to write a rebinder in your pointer type. If they're synthetic, you have to define that to pointer member
function, and you have to think very hard
about the implementation of that function, like I said. If your synthetic pointer is such that it can consistently
cover the entirety of the address space, then it's easy. If the semantic of your
synthetic pointer is such that it's only applicable
over a small part of your address space,
then you need to think about what to do if you
wanna take a pointer to something that's not
part of that little segment. What does that mean? You gotta decide that for yourself. Do specify the rebinder
for your allocator. Do specify your allocator's
nested value type. Actually, you have to do that. If the instances always compare equal, then define the nested type
alias and set it to true type. That'll buy you a little
bit of speed at runtime, because the containers will
make compile time decisions about what to do. If the instances do not
propagate on copy construction, define a select on copy
construction member function as part of your allocator that
returns a temporary value. That temporary value is
what will be propagated into the containers allocator. If you want your instances to
propagate on copy assignment, then define the nested
type alias as true type. Same thing for move assignment
and the same thing for swap. You need to think about what the semantic of your allocator is,
and does copying, moving, and swapping instances of the
allocator, does it make sense? If it does, set these things true. It's hard to think of cases where it does, they're probably fairly
rare, but if they do, you need to think about
it and do the right thing. If you're going the PMR root, which I recommend starting out with, the real question you have to answer is, which base class do I wanna work with? You can always start with memory resource. There are the others that are
derived from memory resource. Perhaps you want to
override their behavior, although their member
functions may be set final. I don't remember. But it's easy enough
to create something new from memory resource,
and create some sort of, not create, but test different
allocation strategies for your application. And not worry about synthetic
pointers or propagation traits or any of the other stuff you have to worry about with
traditional allocators. Yes, I'm running over. Okay, well, anyways,
thank you for attending. Sorry I ran over. (applauding)
