Ever want to generate a unique typeID from a type? You can by using templates!
Eventually we will want something of the form:
ASSERT(typeID(TypeA) != typeID(TypeB))
But first lets start with something a little simpler:
ASSERT(typeID<float>() == typeID<float>()) and
ASSERT(typeID<char>() != typeID<int>())
The trick here is to take an address of a singleton pointer of a specific type. The pointer doesn't actually point to anything, it's just there to generate a unique number.
Let's define a template function:
template<typename T>
size_t typeID() {
static const T* type_id;
return reinterpret_cast<size_t>(&type_id);
}
Let's see what this is doing. First only one function will used after the C++ source has been linked. Our singleton is the static const T* type_id pointer. The location of this pointer in memory is what is important since it is unique. Uniqueness is important since we can use it test for equality. Equal types will produce equal type ids'.
To make this slightly more useful, we are going to want to deduce the type id automatically by the type of an input value. So let's overload the typeID function with one that deduces the type based on the argument.
template<typename T>
size_t typeID(const T& t) {
return typeID<T>();
}
Now this allows us to do things like:
int a;
bool b;
ASSERT(typeID(a) != typeID(b));
Note that what this solution does not due is determine the subtype from a base type reference. For that you would want to store the typeID during construction of the object. Also, because the typeID() function is created by the compiler, libraries that are not linked together (aka dynamic linked libraries) will produce different typeid's. The type id can (and probably will) change whenever the project has been rebuilt.
Wednesday, June 4, 2008
Monday, March 10, 2008
assigned_ptr: A smarter smart pointer for managing memory fragmentation
The smart_ptr library in C++ is quite useful for managing the lifespan of objects. It's as close as C++ gets for generic garbage collection. In this post I introduce a new smart_ptr, "assigned_ptr", which results in one less memory heap allocation and can attach custom memory allocation to an object without overriding that object's new/delete operator.
There are 2 basic types of smart pointers that are practical and recommended for use
1. scoped_ptr<T>
2. shared_ptr<T>
Both of these should be used whenever you're managing memory from the heap. The shared_ptr construct is a nice to use however it requires that there are an additional allocation from the Heap for it's shared counter.
Here's an ascii diagram of what's happening:
Notice that all the shared_counter* and T* both have to be pointers, while the shared_ptr's are usually allocated on the stack or in a container. Shared_counter is allocated on the heap and this is a performance penalty since shared_ptr is now responsible for allocating and deallocating two objects from the Heap. Besides the performance cost of heap allocation, there is also the cost of fragmenting the heap for shared_counter that can have affect memory performance for the whole application.
There is a reason why we live with this cost: weak_ptr, which is like shared_ptr except that it only prevents the shared_counter from being deallocated instead of both that and the object pointed to.
So using shared_ptr we live with the cost of the shared_counter because we might need a weak_ptr, but what kind of savings could we get if this weren't the case?
Enter assigned_ptr. It works just like shared_ptr except that:
1) it doesn't maintain a separate shared_counter in the heap
2) can't own an external pointer
3) can manage the allocation of an object without necessitating overriding the object's new/delete operator.
The trick here, is that the shared_counter and the object can be allocated on the same block of memory! This pattern matches the intrustive shared_ptr except that by design we are not coupling the implementation with the class.
this ascii diagram shows what this looks like:
All of the assigned_ptr's now point to the same shared_mem_block* which contains both the counter and the templated object. Both the object and the counter are constructed using the in-place new operator.
Here's the code that implements this:
Notice that we use a static allocator to allocated the block of memory that the T object is constructed on. By default, we pass all the memory allocations to malloc and free. Overriding this is simple, we simply provide a template specialization for the allocator of a specific type and we get "plug-in" memory pools for that type. Here's a simple example of providing a pooled memory allocation for floats:
There are 2 basic types of smart pointers that are practical and recommended for use
1. scoped_ptr<T>
2. shared_ptr<T>
Both of these should be used whenever you're managing memory from the heap. The shared_ptr construct is a nice to use however it requires that there are an additional allocation from the Heap for it's shared counter.
Here's an ascii diagram of what's happening:
shared_ptrshared_ptr shared_ptr
\ | /
\ | /
\ | /
\ | /
\ | /
shared_counter* - - - - weak_ptr
|
|
|
|
|
T*
Notice that all the shared_counter* and T* both have to be pointers, while the shared_ptr
There is a reason why we live with this cost: weak_ptr
So using shared_ptr
Enter assigned_ptr
1) it doesn't maintain a separate shared_counter in the heap
2) can't own an external pointer
3) can manage the allocation of an object without necessitating overriding the object's new/delete operator.
The trick here, is that the shared_counter and the object can be allocated on the same block of memory! This pattern matches the intrustive shared_ptr except that by design we are not coupling the implementation with the class.
this ascii diagram shows what this looks like:
assigned_ptr assigned_ptr assigned_ptr
\ | /
\ | /
\ | /
\ | /
\ | /
shared_mem_block*
+--------------+
| counter |
| T Obj |
+--------------+
All of the assigned_ptr's now point to the same shared_mem_block* which contains both the counter and the templated object. Both the object and the counter are constructed using the in-place new operator.
Here's the code that implements this:
#ifndef _ASSIGNED_PTR_H_
#define _ASSIGNED_PTR_H_
#include <new>
//mem_allocator, by default it will forward to delete/new
template<typename T>
class mem_allocator {
public:
static char* Alloc() {
return new char[sizeof(assigned_ptr_BASE::mem_header) + sizeof(T)];
}
static void Free(void* ptr) {
delete[] ptr;
}
};
class assigned_ptr_BASE {
protected:
struct mem_header {
size_t shared_count;
(void)(*Destructor)(void*);
(void)(*Deallocator)(void*); //static function for a typed mem deallocator
};
};
template<typename T>
class assigned_ptr : public assigned_ptr_BASE {
friend class mem_allocator<T>;
static void TDestructor(void* aThisPtr) {
reinterpret_cast<T*>(aThisPtr)->~T();
}
static void TDeallocator(void* mem_header) {
mem_allocator<T>::Free(mem_header);
}
public:
// ctor
assigned_ptr() {
buff = mem_allocator<T>::Alloc();
T* t = get();
new(t)T();
mem_header *mem_hdr = get_mem_hdr();
mem_hdr->shared_count = 1;
mem_hdr->Destructor = &TDestructor;
mem_hdr->Deallocator = &TDeallocator;
}
//cctor
assigned_ptr(assigned_ptr& other) {
buff = other.buff;
mem_header *mem_hdr = buff->get_mem_hdr();
mem_hdr->shared_count++;
}
//dtor
~assigned_ptr() {
unref();
}
template<typename U>
void adopt(assigned_ptr<U>& u_ptr) {
//if U* can't be casted to T* then we will fail right here
T* t = u_ptr.get();
(void)(t); //prevent compiler warning for above
unref();
//to do: think of a better way to implement this....
buff = reinterpret_cast<char*>(t) - sizeof(mem_header);
ref();
}
template<typename U>
assigned_ptr<T>& operator=(assigned_ptr<U>& u_ptr) {
adopt(u_ptr);
return *this;
}
T& operator*() {
T &t = *get();
return t;
}
T* get() {
return
reinterpret_cast<T*>(
buff + sizeof(mem_header));
}
void unref() {
if(buff){
mem_header *mem_hdr = get_mem_hdr();
mem_hdr->shared_count--;
if(0 == mem_hdr->shared_count) {
T* t = get();
mem_hdr->Destructor(t);
mem_hdr->Deallocator(mem_hdr);
}
buff = NULL;
}
}
private:
void ref() {
mem_header *mem_hdr = get_mem_hdr();
mem_hdr->shared_count++;
}
T& operator->() {
return *get();
}
private:
assigned_ptr_BASE::mem_header* get_mem_hdr() {
return reinterpret_cast<mem_header*>(
buff);
}
char* buff;
};
#endif //_ASSIGNED_PTR_H_
Notice that we use a static allocator to allocated the block of memory that the T object is constructed on. By default, we pass all the memory allocations to malloc and free. Overriding this is simple, we simply provide a template specialization for the allocator of a specific type and we get "plug-in" memory pools for that type. Here's a simple example of providing a pooled memory allocation for floats:
template<>
class Allocator<float> {
MemPool<
sizeof(floats) + sizeof(assigned_ptr_counter),
100> mMemPool; //assume a memory pool class with Alloc() and Free()
static char* Alloc() {
return mMemPool.Alloc();
}
static void Free(void* ptr) {
mMemPool.Free(ptr);
}
}
Friday, March 7, 2008
Using templates to bind static functions to named class member functions
Member Function signatures in C++ are messed up. Seriously messed up. Don't believe me, read about what one author had to do to create the FastDelegate and you'll get a sense of the idea. To get around this limitation in C++, we can use a template trick to bind a class members function to a static template function.
Remember that a templated function will actually be converted to a real function at compile time. This means that we can treat it just like any other function, pass it to other functions, store the address of it in array etc etc...
You can even do things that you probably didn't think you could do, such as create a static function to a class's constructor and destructor!
How to do this is simple, here's a snippit of a template function that will construct an object using the class's default constructor (note that we assume the memory has already been allocated):
Now we can call this like so:
A non-contrived example is using constructors and destructors to implement custom memory allocators that support non-trivial data types.
Remember that any functions called by a class has a "this" pointer passed as an implicit argument. So whenever we bind a static template function to a class function we will always need to pass in a "this" pointer.
For example:
The call to Foo can really be thought of as this:
So any static template function that binds to a member function is going to need a "this" pointer.
Following our example, lets bind the static function SomeObjectFoo to SomeObject::Foo().
Pretty simple huh? Let's generalize this to all Objects that have a Foo() member function.
Okay this is getting better, now we can use templates to accept any class that has a Foo() function.
This is an example of duck typing (if it looks like a duck and quack likes a duck then it's a duck, or in other words, if it has a Foo() function that looks like a Foo() and takes arguments like a Foo() then it has a Foo()).
Still this is all academic, what's the point?
Callbacks! Yes callbacks can be implemented this way and you can pass whatever member function you want by binding it to a static function. The callback can even be a non-template. How do we do this?
Recall that making a static call out of a member call requires that we have a "this" pointer. In the examples so far, we've assumed that "this" has a known type. In a callback system that takes in a static function we won't know specifically what type "this" is, so we'll have to assume that it's void*. This may seem shocking, as generally passing around void* is bad. Bear with me for a moment, I'll convince you that this is that 5% time that it's okay :)
Our callback system is going to be typesafe by construction. That is, all the reinterpret_cast's will be hidden away in the implementation which the caller won't have access to. Lets define a callback struct as so:
Now assuming that we have a valid Callback0 object we would call it like so
Okay so all the pieces are in place and all the remains is how to construct a callback.
The non-template way:
Ahhh! But this is bad, because the programmer has to think about
type safety everytime they have to create a new static function! This can really screw things up. So let the compiler generate this function using templates and maybe we can get typesafety for free!
The template way:
Wow! Look at that! ALL the yucky type-casting is done internally, transparent from the user! We now have a typesafe callback!
So putting this all together it looks like this:
Now for the grand finale, lets declare another class, SomeOtherObject, that also has a function foo, what do you think will happen?
Yes it works! And it will work with any object that declares Foo in the same way!
Practical uses:
1) Callbacks, use this as an alternative to multiple inheritance and virtuals (which REALLY slow down and bloat C++ code, especially in tight loops common in Observer patterns).
2) Allocators which need to know how to construct/destruct the objects they allocate/deallocate.
3) Interfaces, you can guarantee that a class fulfills the interface contract if the interface can bind to all the contracted member functions of a class (duck typing).
~Z~
Remember that a templated function will actually be converted to a real function at compile time. This means that we can treat it just like any other function, pass it to other functions, store the address of it in array etc etc...
You can even do things that you probably didn't think you could do, such as create a static function to a class's constructor and destructor!
How to do this is simple, here's a snippit of a template function that will construct an object using the class's default constructor (note that we assume the memory has already been allocated):
template<typename T>
static void ConstructObject(T* aThisPtr) {
new (aThisPtr)T();
}
template<typename T>
static void DestroyObject(T* aThisPtr) {
aThisPtr->~T();
}
Now we can call this like so:
struct SomeObject {
SomeObject() {}
void Foo() {}
void Foo(int arg1) {}
};
//manually construct the object
SomeObject* so = (SomeObject*)malloc(sizeof(SomeObject));
ConstructObject(so);
DestroyObject(so);
free(so);
A non-contrived example is using constructors and destructors to implement custom memory allocators that support non-trivial data types.
Remember that any functions called by a class has a "this" pointer passed as an implicit argument. So whenever we bind a static template function to a class function we will always need to pass in a "this" pointer.
For example:
SomeObject so;
int arg1 = 0;
so.Foo(arg1);
The call to Foo can really be thought of as this:
SomeObject::Foo(SomeObject* this, int arg1);
So any static template function that binds to a member function is going to need a "this" pointer.
Following our example, lets bind the static function SomeObjectFoo to SomeObject::Foo().
static void SomeObjectFoo(SomeObject* aThisPtr, int arg1) {
aThisPtr->Foo(arg1);
}
//now call the bound foo function
SomeObject so;
SomeObjectFoo(&so, arg1);
Pretty simple huh? Let's generalize this to all Objects that have a Foo() member function.
template<typename T>;
static void CallFoo(T* aThisPtr, int arg1) {
aThisPtr->Foo(arg1);
}
Okay this is getting better, now we can use templates to accept any class that has a Foo() function.
This is an example of duck typing (if it looks like a duck and quack likes a duck then it's a duck, or in other words, if it has a Foo() function that looks like a Foo() and takes arguments like a Foo() then it has a Foo()).
Still this is all academic, what's the point?
Callbacks! Yes callbacks can be implemented this way and you can pass whatever member function you want by binding it to a static function. The callback can even be a non-template. How do we do this?
Recall that making a static call out of a member call requires that we have a "this" pointer. In the examples so far, we've assumed that "this" has a known type. In a callback system that takes in a static function we won't know specifically what type "this" is, so we'll have to assume that it's void*. This may seem shocking, as generally passing around void* is bad. Bear with me for a moment, I'll convince you that this is that 5% time that it's okay :)
Our callback system is going to be typesafe by construction. That is, all the reinterpret_cast's will be hidden away in the implementation which the caller won't have access to. Lets define a callback struct as so:
typedef void (*FunctionCallback0)(void*); //a function call that takes 0 args
struct Callback0 { //takes in 0 args
Callback0(void* aThisPtr, FunctionCallback0 aCallBack) :
thisPtr(aThisPtr), callback(aCallBack) {
}
void Call() {
callback(thisPtr);
}
private:
void* const thisPtr;
const FunctionCallback0 callback;
};
Now assuming that we have a valid Callback0 object we would call it like so
Callback0 *callBack = //...//;
callback->Call();
Okay so all the pieces are in place and all the remains is how to construct a callback.
The non-template way:
static void CallFoo(void* aThisPtr) {
SomeObject *so = reinterpret_cast<SomeObject*>(aThisPtr);
so->Foo();
}
SomeObject so();
FunctionCallback0 funCallfoo = CallFoo;
Callback0 callBackFoo(&so, funCallfoo);
callBackFoo.Call();
Ahhh! But this is bad, because the programmer has to think about
type safety everytime they have to create a new static function! This can really screw things up. So let the compiler generate this function using templates and maybe we can get typesafety for free!
The template way:
//this function creates a local static function which
//acts as the callback to the T's member function Foo()
//all typesafety checks are done via template instantiation
template<typename T>
static Callback0 MakeCallFoo(T* aThisPtr) {
struct CallFooFunctor { //trick to get a local function, see previous post
//this static function is the callback site
static void CallFoo(void* aThisPtr) {
T* t = reinterpret_cast<T*>(aThisPtr);
t->Foo();
}
};
//get the address of the callback defined above
FunctionCallback0 funCallFoo = &CallFooFunctor::CallFoo;
//construct a new callback and return it
return Callback0(aThisPtr, funCallFoo);
}
//main(){...}
SomeObject so();
Callback0 callBackFoo = MakeCallFoo(&so);
//callback now has the static inner function CallFooFunctior::CallFoo
callBackFoo.Call();
Wow! Look at that! ALL the yucky type-casting is done internally, transparent from the user! We now have a typesafe callback!
So putting this all together it looks like this:
static void Dispatch(Callback0& callback) {
callback.Call();
}
SomeObject so();
Callback0 callback = MakeCallFoo(&so);
Dispatch(callback);
Now for the grand finale, lets declare another class, SomeOtherObject, that also has a function foo, what do you think will happen?
struct SomeOtherClass {
SomeOtherObject() {}
void Foo() {}
};
SomeOtherObject soo;
Callback0 callback = MakeCallFoo(&soo);
Dispatch(callback);
Yes it works! And it will work with any object that declares Foo in the same way!
Practical uses:
1) Callbacks, use this as an alternative to multiple inheritance and virtuals (which REALLY slow down and bloat C++ code, especially in tight loops common in Observer patterns).
2) Allocators which need to know how to construct/destruct the objects they allocate/deallocate.
3) Interfaces, you can guarantee that a class fulfills the interface contract if the interface can bind to all the contracted member functions of a class (duck typing).
~Z~
Tricking the C++ compiler to use inner functions
Inner functions are great - they allow you to use organize code and encapsulate it in the outer functions scope. Most languages support inner functions and there aren't any good reasons why C++ wouldn't support this feature.
Well it does actually here's how...
Wrap the function inside a local class (!?). Yes, you can define a local class/struct inside a function, and then use the local class's functions willy-nilly.
It's verbose but it works well, here's a snippit:
Well it does actually here's how...
Wrap the function inside a local class (!?). Yes, you can define a local class/struct inside a function, and then use the local class's functions willy-nilly.
It's verbose but it works well, here's a snippit:
void Foo() {
struct BarFunction {
static void Bar() { /*...*/ }
};
BarFunction::Bar();
}
~Z~
Why I created this blog
This blog constitutes general musings about the C++ language and how to use templates to increase programmer productivity. I will try to stay on the pragmatic although I can't guarantee that some of my entries won't be purely academic.
If you as a reader thinks that I might be interested in some paper involving templates and C++ then don't hesitate to send them in! I love a good read as I take a bus back home and have lots of downtime to delve into such things.
Cheers,
~Z~
If you as a reader thinks that I might be interested in some paper involving templates and C++ then don't hesitate to send them in! I love a good read as I take a bus back home and have lots of downtime to delve into such things.
Cheers,
~Z~
Subscribe to:
Comments (Atom)