Java Custom Annotations - Intuitive view

Java Custom Annotations - Intuitive understanding

Annotation, in simple terms, is a description of something, but not all descriptions could be considered as valid annotations in programming world. Simple Java comments couldn't be considered as an annotation, but a Javadoc could be. Formally, annotation is meta-data of some data. Meta-data is a type of data which could be understood by compiler or run-time like JVM, but shall be treated differently than normal data.

For instance, Annotations in a java class is a means to provide some extra information about that class. But, why is it useful? You could have used some of the compile-time annotations in your code, which provide some hints to the compiler like @ SuppressWarnings, @Deprecated, etc. Annotations are much more powerful which could make certain great stuff possible. Let us start with an example and understand the power of Annotations intuitively.


Let us think of a simple client-server protocol which exchanges messages through TCP Layer. And we define Messaging protocol as follows:

command + "END" + data

command -> defines the action to be performed
"END" -> delimiter for command message
data -> data on which action shall be performed

For example,
"echoENDHello World" shall be handled by the Server to return the data "Hello World" as echo is the command which is not supposed to do any operation on the data.

Now let us think of the server's implementation for this. All messages shall be received by a socket and sent to a message processor object for processing. In the processor, parsing may happen and according to the command, a right handler could be selected to process further.


The complete example is uploaded in the GIT. https://github.com/karthikmit/AnnotationsDemo

And this is for demo purpose and expect some TODOs here and there :)


For the Echo command, we may define a EchoHandler class which extends Handler interface. We may define a handler factory which returns the EchoHandler object, given the command parameter, echo. This design is almost loosely coupled as adding a new command, needs a new handler class to be implemented and some changes in Handler Factory and no changes needed in other components. Wait, what is the information being held by this Handler factory? Is that dependency really needed? Yes, because a class derived from Handler interface isn't capable of informing its own purpose to other components. There are several ways by which this information could be injected into the class, think of a final string which says which command it is capable of handling.

Annotations is a non-intrusive and programmatic way by which this sort of extra information about the class can be clearly expressed. Non-intrusive means the annotations don't do any harm on its own to the host class. If we could annotate the new controller with the new command, message processor could utilize this annotation during its handler discovery phase. A perfect de-coupling is possible with annotations. Let us get into some details of annotations.

Annotation is actually an interface and Handler annotation could be defined as follows.



@ in front of interface keyword, can be understood as AT, Annotation Type. Apart from this, there is no distinction between normal interface and Annotation definition.
Target and Retention are the meta annotations which "describe" annotations. To make this example complete, Target says this annotation should be applied at Class level;  BTW, Method and Field level annotations are also possible. Retention says annotation should be available at RunTime. We need this annotation at run-time for message processor object to discover the command handlers.

Given annotation is an interface, we need to instantiate somewhere, right. Let us check the Echo handler code to understand this.



Like a Java modifier, annotation precedes the definition. In the above snippet, we annotate the EchoMessageHandler with Handler and makes its value to return "echo". This could be thought of as instantiation of Handler annotation interface.

I need to digress a bit; Check the Override annotation in the above snippet, which is actually annotating "handle" method. This annotation says that this method should be the parent interface method and is getting overridden. If that is not so, compiler would throw an error. Since Override annotation is Compile-time stuff, Run-time doesn't have any idea about this annotation.

Handler discovery of MessageProcessor class can be defined as follows:



Every Class object of type and Method object of class methods has a method getAnnotations which gives an array of annotations. This could be utilized for Handler discovery in this example.

Thread Pooling in Java - Part 2 - Internals.

For the basics of Java threads, please check this post, http://karthikpresumes.blogspot.in/2013/02/java-multi-threading-basics.html

In the first part, we had analyzed the needs for Fixed and cached Thread Pools.

http://karthikpresumes.blogspot.in/2012/03/thread-pooling-in-java-intuitive.html

Fixed thread pools have fixed number of running threads operating on a finite unbounded tasks queue.
Cached thread pools spawn as many number of threads as the task count at any time and have a Synchronized Queue.

And we had seen use cases for each of the thread pools in the previous part. Now, what if an use case needs the mixed behaviors of the above. For instance, behave like a CachedThreadPool until a fixed number of tasks.

Analysis of the implementations of the above thread pools would open new doors for solving interesting variants of thread-pool based problems.

Actually, both Fixed and Cached thread pools creation, internally would create instance of ThreadPoolExecutor with different parameters.
For instance, let us analyze the FixedThreadPool call,

public static ExecutorService newFixedThreadPool(int nThreads) {
return new ThreadPoolExecutor(nThreads, nThreads,
0L, TimeUnit.MILLISECONDS,
new LinkedBlockingQueue());
}

The declaration of ThreadPoolExecutor is,

public ThreadPoolExecutor(int corePoolSize,
int maximumPoolSize,
long keepAliveTime,
TimeUnit unit,
BlockingQueue workQueue) { ...

Let us try to understand each and every parameter.

CorePoolSize: This represents the number of threads to be alive even in the absence of any task. In Fixed Thread Pool, it should be equal to the total or Max thread count as we know the optimal number of threads and destroying/ recreating the threads incur performance hurt.

Maximum Pool Size: This represents the maximum number of threads that could be created in the thread pool. If the count of running threads exceeds "corePoolSize" and queue of waiting tasks are filled completely, then a new thread could be created if Maximum Pool Size > Core Pool Size.

Keep Alive Time: In case threads created exceeds the corePoolSize and some of the threads are idle for "keepAliveTime" then those would be killed to save the resources in the System. And the next parameter is the unit for KeepAliveTime.

BlockingQueue: It describes the queue to be used for Waiting tasks. For Fixed Thread Pool, it is unbounded. And for CachedThreadPool, it is SynchronizedQueue, means at any time, queued task must be immediately served; means no task could be queued for processing later.

So, if we could statistically analyze the peak and average traffic of incoming tasks, we could come up with optimal values for Core, Max pool size and KeepAliveTime; which could make our thread-pool efficient and resources conservative. :)

To make the discussion complete, we will try to understand the implementation of ThreadPoolExecutor.

Well, we need to discuss what happens when Execute of ThreadPoolExecutor called.

Algorithm which backs Execute is simple. If number of threads is less than the core pool size, a new thread will be spawned to handle this new task. If the number of active threads exceeds the core pool size and queue is filled up fully, algorithm would check for the spawning of additional threads, constrained by the max pool size count, is possible; If not, rejection handler would be called.

ThreadPoolExecutor holds a control state variable ctl, which is an AtomicInteger, provides some useful information like effective worker threads and state of ThreadPool(Running, Shutting down, etc). And there are several utility functions around this variable.

Apart from this, there are several other functionalities which assist the main functionalities like termination of Thread Pool and thread factory, etc. People interested in that, could dive into the source code for complete understanding. I hope I tried my best to keep the information concise.

Thanks for Reading.

Thread Pooling in Java - Intuitive overview. Part 1

You may want to check my post on basics of Java threads, http://karthikpresumes.blogspot.in/2013/02/java-multi-threading-basics.html

Today Let us talk about Thread Pooling. Before that, let me give you an intuitive idea of why pooling of threads needed.

Let us start with a trivial web server implementation. In this, main thread would keep on listening to incoming requests and process those messages according to their arrival. This is easy to implement; Good for single processor web-server, given tasks are CPU bound or intensive. Normally, servers would have multiple processors. So, in Quad-core machine, even CPU intensive tasks would be utilizing about 25% of entire system's capability, if service is single-threaded.

Simultaneously, N number of requests could be easily served in N-processor based web server. Now, let us make our trivial web server to run N threads simultaneously to improve the performance by N fold. Cool. This way of scaling(generally, it means increasing number of requests served, per unit time) of a service is known as Vertical Scaling.

Let us discuss, how this system shall be designed. Since the requests served are of CPU intensive, we know the optimal number of concurrent threads., a priori. So, the system shall be designed as given below.

1. At most, only the given number of threads be running and not more than that.
2. It should be having finite unbounded queue of pending tasks; This is a moot point, by the way. But we will believe eventual completion of a task is better than rejecting that.
3. Already created threads shouldn't be killed or shouldn't die on its own after the completion of a task. Since creating threads are generally known to be costly.
4. During task execution, if a thread happens to crash itself, thread pool must be intelligent enough to create one.

The above design is so generic and could be abstracted easily. Java's FixedThreadPool does exactly the same job. It has to be defined with number of threads; It has finitely unbounded queue(roughly, 4 gig entries could be waiting in this queue, in a 32 bit machine) for waiting tasks.

It could be created using below line of code.

ExecutorService threadExec = Executors.newFixedThreadPool(numThreads);
ExecutorService is an interface which has APIs for submitting a task to the pool and Shutting down, etc. We will discuss this and "Future" in the next part of this blog as it would be digressing if we start discussing that right now.

A complete test code could be found here. You can test with several parameters and see the power of thread pooling.

http://code.google.com/p/threadpool-tests-java/source/browse/FixedThreadPoolTest.java

Let us assume, our web server has to handle very simple requests which doesn't take much time to complete and involves huge of I/O activities - Files I/O, network activity like another web service to process. In this scenario, it is not good to limit the number of threads as most of the time would be spent on I/O and not on computing.

Main problem with this case is, determining the number of threads at most could run on a system. Even if we could get that parameter statistically, it is not good to hold those many threads running always. For instance, after some analysis, we come to know that there may be around 1000 threads needed, at most. If we go for FixedThreadPool, it is a waste of resources as we wouldn't get the peak traffic always. Since these tasks are asynchronous and probably short lived, getting a proper max bound on number of optimal threads wouldn't be always possible.

The system that could handle this scenario, shall be designed as follows.

1. The system should create threads as and when needed.
2. After a thread's task completion, it could wait for certain time and die if no other task is available.
3. It shouldn't have any waiting tasks, rejection shall be preferred instead. Think about a SynchronousQueue in Java.

Java's CachedThreadPool is designed with the above-said design goals. It is perfectly great for short-lived, asynchronous tasks. Creating a CachedThreadPool and working with that is essentially tantamount to FixedThreadPool. So, the line below, doesn't need any further explanations.

ExecutorService threadExec = Executors.newCachedThreadPool();

And a test program to analyze this is,
http://code.google.com/p/threadpool-tests-java/source/browse/CachedThreadPoolTest.java
We will discuss the implementation details of Fixed and Cached Thread Pool in the next part.

Thanks for Reading.

Visitor Pattern in C++ - Intuitive understanding.

Today we will discuss Visitor pattern in an intuitive way as on the face of it, it would seem pretty intricate. First off, we need to understand the scenarios, in which Visitor would be of great helpful. Let me start with basic examples and move on to complex details of Visitor pattern.

When we design any container, our focus should be on data-structure which holds the data but not on algorithms which work on contained data. For instance, STL containers had been designed in such a way that algorithms can be developed independent of data containers. STL achieves this by the concept of iterators and by the uniformity of type of contained elements. Every container that supports iterators, can be used seamlessly in algorithms.

What if the contained elements are of disparate types? Now iterators wouldn't help this situation as types are varying. More importantly, if the contained elements need to be treated differently for different types, even deriving from a same base class wouldn't be much helpful. Consider an example of Shape objects like rectangle and Ellipse. Even though both can be described by Bounding rectangles, calculation of area would differ. So, a common algorithm for area is not possible, even though both are Shape objects. This is one of the scenarios in which Visitor can help.

In a nutshell, Visitor pattern can be used to add a new algorithm to work on a container without modifying the container itself. Now, let us translate the above line in OOP way.

Visitor is a way to add a new behavior to the existing class without modifying the class itself.

Perhaps, this is one more to way to achieve Open-Closed principle of OOP, Let us explore.

Let us implement some trivial examples to proceed further. Implementations are not of production quality; proper memory management is not there. This is just to explain the concepts.

Let us define an interface, IShape from which Rectangle and Ellipse are derived as given below.

struct Bounds

{

Bounds() : left(0), right(0), top(0), bottom(0)

{

}

Bounds(int ileft, int itop, int iright, int ibottom) : left(ileft), top(itop), right(iright), bottom(ibottom) { }

int left;

int right;

int top;

int bottom;

};

class IShape

{

public:

virtual Bounds GetBounds() = 0;

virtual void Draw() = 0;

};

class Rectangle : public IShape

{

public:

Rectangle(Bounds bounds) : currentBounds(bounds)

{

}

Bounds GetBounds()

{

return currentBounds;

}

void Draw()

{

// Draw Rectangle here.

}

private:

Bounds currentBounds;

};

class Ellipse : public IShape

{

public:

Ellipse(Bounds bounds) : currentBounds(bounds)

{

}

Bounds GetBounds()

{

return currentBounds;

}

void Draw()

{

// Draw Ellipse here.

}

private:

Bounds currentBounds;

};

Let us define a Graphics Designer, a composite class for Shapes. At Run-time several shape objects could be added to this toy Graphics Designer and Draw can be invoked to draw all the elements.

class GraphicsDesigner : IShape

{

public:

void AddRectangle(Bounds inBounds)

{

currentElements.push_back(new Rectangle(inBounds));

}

void AddEllipse(Bounds inBounds)

{

currentElements.push_back(new Ellipse(inBounds));

}

void Draw()

{

// Enumerate through the currentElements and Draw each.

}

private:

vector<IShape*> currentElements;

};

Given a class like GraphicsDesigner, How to add a new algorithm to work on contained elements! For instance, we need to find the Minimal rectangle which covers all the elements. In order to achieve this, we would need to add a method in container which enumerates through the elements and execute the algorithm. This violates OOP. And every time, we need to implement a new algorithm, we would end up adding new methods into the container class.

Algorithms are getting bound to the data container.

We will analyse further to understand the problem well.

Adding methods to the container is not a good idea as algorithms just depend upon the contained elements and not on the state of the container.

Needed algorithms can't be defined before hand, just think of possible algorithms on Integers containers, finitely huge, right.

Given that, we need to find out a way to dynamically add the behaviors on to the containers. Without further ado, we will define Visitor pattern and see how it resolves this.

For every algorithm, we should derive a class from Visitor interface; Visitor interface should contain a collection of overloaded Visit methods one for each different types of Visit-able classes. Visit-able classes as per our example, are Rectangle and Ellipse(and general Shape also). Every visit-able class should define a method "Accept".

Let me define a simple PrintVisitor to clarify the needs of all these interfaces.

Before that, given below are the example classes after the changes, made with Visit and Accept interfaces.

class Rectangle;

class Ellipse;

class IShapesVisitor

{

public:

virtual void Visit(Rectangle*) = 0;

virtual void Visit(Ellipse*) = 0;

};

class IShape

{

public:

virtual Bounds GetBounds() = 0;

virtual void Draw() = 0;

virtual void Accept(IShapesVisitor* visitor) = 0;

};

class Rectangle : public IShape

{

public:

Rectangle(Bounds bounds) : currentBounds(bounds)

{

}

Bounds GetBounds()

{

return currentBounds;

}

void Draw()

{

// Draw Rectangle here.

}

void Accept(IShapesVisitor* visitor)

{

visitor->Visit(this);

}

private:

Bounds currentBounds;

};

class Ellipse : public IShape

{

public:

Ellipse(Bounds bounds) : currentBounds(bounds)

{

}

Bounds GetBounds()

{

return currentBounds;

}

void Draw()

{

// Draw Ellipse here.

}

void Accept(IShapesVisitor* visitor)

{

visitor->Visit(this);

}

private:

Bounds currentBounds;

};

class GraphicsDesigner : IShape

{

public:

void AddRectangle(Bounds inBounds)

{

currentElements.push_back(new Rectangle(inBounds));

}

void AddEllipse(Bounds inBounds)

{

currentElements.push_back(new Ellipse(inBounds));

}

void Draw()

{

// Enumerate through the currentElements and Draw each.

}

Bounds GetBounds() { return Bounds(); }

void Accept(IShapesVisitor* visitor)

{

vector::iterator shapeItr = currentElements.begin();

for(; shapeItr != currentElements.end(); shapeItr++)

{

IShape *val = (*shapeItr);

val->Accept(visitor);

}

}

private:

vector<IShape*> currentElements;

};

Now, we will define a simple PrintVisitor to show the power of Visitor pattern.

class PrintVisitor : public IShapesVisitor

{

public:

void Visit(Rectangle* inShape)

{

cout << "This is a Rectangle" << endl;

}

void Visit(Ellipse* inShape)

{

cout << "This is an Ellipse" << endl;

}

};

Of course, "Print" is so trivial to be considered as an algorithm which works on the data. But it clearly avoided the need for having "Print" virtual function in Shape derived classes. Now let us think of a decent algorithm which could work on the data. Let us assume, we need to find the total area occupied by all shapes in GraphicsDesigner. Without Visitor pattern, we would have to add up a new member function in GraphicsDesigner class. But with Visitor pattern, things become very easy that we need to add a new class in Visitor hierarchy as given below.

class TotalAreaVisitor : public IShapesVisitor

{

public:

TotalAreaVisitor() : TotalArea(0.0)

{

}

void Visit(Rectangle* inShape)

{

Bounds bounds = inShape->GetBounds();

int width = bounds.right - bounds.left;

int height = bounds.bottom - bounds.top;

int currentArea = width * height;

TotalArea += currentArea;

}

void Visit(Ellipse* inShape)

{

Bounds bounds = inShape->GetBounds();

int width = bounds.right - bounds.left;

int height = bounds.bottom - bounds.top;

double currentArea = width * height * 3.14 / 4;

TotalArea += currentArea;

}

double GetTotalArea()

{

return TotalArea;

}

private:

double TotalArea;

};

I hope now the need for Visitor pattern is very clear. For every new algorithm, instead of adding a new method in container class, we can add a new visitor. This helps us to achieve one of the SOLID principles, Open-Closed principle. There are disadvantages also like a new Shape derived can't be easily added as it needs modification of all possible Visitors.

So, Visitor pattern trades off the ease of adding new behaviours into Visit-able hierarchy with not easily allowing to create a new derived class in Visit-able hierarchy.

Thanks for Reading.

Bloom filter implementation in C++ - NikBloomFilter

Bloom filter can be considered as a succinct representation of a set of elements. Set of elements might be stored in files or in Database tables, etc. And a set may support operations like insertion, deletion and retrieving elements.

For this discussion, Let us assume a dictionary of passwords which is a set of huge number of strings which is stored in several files according to their starting character like A-List, B-List,etc. We assume that we don't keep all this information in Main memory. So, in order to find a string's presence in the dictionary, Program has to fetch the right file according to the starting character and keep it in main memory for a Binary search. Generally, we don't require frequent insertions and deletions from this set, but queries for the presence of an element. Only way to make the queries fast is to cache complete set of elements in Main memory. But there are some scenarios in which caching is unaffordable.

Bloom filter, as I said early, is a succinct data-structure which registers the presence of elements in a set. While we insert an element in a set, Bloom filter must be updated. Bloom filter is basically a bit array. A small subset of bits in that array would correspond to an element in the set. So, when an element is inserted, corresponding bits should be set. Now query is simply a check for the corresponding bits state; if all the bits corresponding to that element are set, then query would return true. But this true may not be a real true. Since every element maps to a subset of bits in the bit array, overlapping may occur and which could cause a false positive. Before going further, we will analyse this structure mathematically.

Bloom filter is a probabilistic data structure. When an element is inserted, it has to set certain bits in the bits array. In order to find out what are all the bits to be set, we need to hash the content of an element. Now, hashed elements could be used to construct the indices of bits to be set. For instance, MD5 of a byte array would result in 16 bytes which could be used to construct 4 indices. We will get into implementation details later in this discussion. As we discussed early, this data structure may give false positive. Luckily, we could be able to control this by trading off space.

Let us get into the analysis. Let us assume the size of the bloom filter, "M" bits and "N" elements had been inserted into the set, hence in Bloom filter also.

Now, probability of a bit B[i] to be unset or zero is (1 - 1/M) ** kN. Here ** represents "power of" operator. k is the number of bits to be set for an element in a set. The above formula could be easily derived as follows: Since N elements are inserted, setting some bit in the bloom filter would have happened for kN times. One particular bit not set in the first time is M-1 / M, for two consecutive times, is (M-1 / M) * (M-1 / M) and so on. Underlying assumption in this, is setting bits are statistically independent. Asymptotically, this is true. So, we will assume so in this discussion.

P{ B[i] == 0] } is (1 - 1/M) ** kN, approximately e ** (-kN/M).

False positive is a condition in which bloom filter tells a string present in the set which is not actually present. Cause of this condition is the bits corresponding to the string set by other independent strings and due to cumulative effect of that, as described earlier in this discussion. Probability of false positive is all the bits corresponding to the string are set which is,

(1 - e ** (-kN / M) ) ** k => P{ False Positive }

Since the false positive probability depends on the factors k, N, M, we need to minimize the function ( taking derivative and equating to zero) with respect to 'k'. Analysis shows this function becomes minimum if 'k' becomes (M / N) * ln 2. ln 2 is natural logarithm of 2.

If we assign 'k', the value (M/N) * ln2 in the False positive probability function, we will get,

P{ False Probability } = (1 - e ** -(ln 2) ) ** k = (1/2) ** k or (0.6185) ** (M/N).

The above result is the lynch-pin of the Bloom filter implementation, as it gives the way to control False positives. For instance, if we wish to have F.P of 0.2 then M/N must be around 8. "N" is the number of elements in the set. Given that, "N", bit-set size of the Bloom filter, could be easily calculated.

An implementation of Bloom filter in C++ has been done and checked in to the Git-hub.

https://github.com/karthikmit/NikBloomFilter

This implementation doesn't have support for Deletion and merging with some other Bloom filter as it is the initial release. Any comments on this is welcome.

Thanks for Reading.

Prototype Pattern in C++, Dynamic instantiation.

Before starting the discussion of Prototype pattern, We will understand the problem of Dynamic instantiation.

Given a typename ( a class name ) in C++ as a string, how an object can be created of that type?

First off, there is no language level support for dynamic instantiation in C++ unlike Java and C#. Since in C++, there is no common base class for all classes, dynamic instantiation support is generally not possible. MFC, a C++ framework provides support for Dynamic instantiation as all classed are derived from CObject. Let us try in the same line, making use of common base and Prototype pattern to achieve Dynamic instantiation.

Prototype pattern imposes a class to have a method, Clone, whose sole purpose is to generate a new object of same type. With a clone-able object, we could be able to generate a new object of same type. In order to achieve this, all classes must be derived from a common base class. And in that common base class, we can have a pure virtual member function(interface), Clone. So, all classes derived from that, would be clone-able.

Let us call that common base class "Object" as in Java. My minimalistic implementation of the Object is as given here,

class Object

{

public:

virtual ~Object() {}

virtual Object* Clone() const = 0;

static Object *MakeObject(std::string type);

static void AddNewClassInfo(std::string type, Object* in);

static std::map objectsTable;

};

Clone is the key method of this abstract class. Implementation of the same could be like the one given below.

class Derived : public Object

{

Object *Clone() { new Derived(); }

};

So, all the classes derived from Object can be cloned using this method call. In order to "Clone" an object, we should have one initial object, prototypical instance. And we should be able to get that base prototypical instance from the type name. If we could be able to do this, then Making an object using type-name alone is a cake-walk. "objectsTable" map in Object class holds the aforesaid mapping; a map of type-name and a prototypical instance.

Adding a prototypical instance can be done through the method, "AddNewClassInfo", whose implementation can be like this.

// Populate map with type-name and its corresponding prototype.

void Object::AddNewClassInfo(std::string type, Object *in)

{

objectsTable[type] = in;

}

Now the implementation of "MakeObject" must be easily understandable.

Object* Object::MakeObject(std::string type)

{

std::map::iterator itr;

itr = objectsTable.find(type);

if( itr != objectsTable.end())

{

return itr->second->Clone(); // Clone the prototypical instance.

}

else

return NULL;

}

All the essential implementations of "Object" is done. Since it has a static member, it should be defined in CPP file as given here,

std::map Object::objectsTable;

OK. Now let us create a derived class from Object and test this implementation.

#include "Object.h"

class DynamicInstantiable : public Object

{

public:

DynamicInstantiable() {}

void SayHello()

{

std::cout << "Hello! " << std::endl;

}

Object* Clone() const

{

return new DynamicInstantiable();

}

};

The above class has the implementation for Clone method and is derived from Object. Now, this type must be added in Static Map in "Object" class using Object::AddNewClassInfo. We have several options here. But I would like to keep things simple. So, I have added a new header file which has a global function "InitializeDynamicObjects". And this method must be called in "main()" function in the very first line itself.

A sample implementation is given below.

void InitializeDynamicObjects()

{

Object::AddNewClassInfo("DynamicInstantiable", new DynamicInstantiable());

}

Here is the sample Main function, I have written to test the code.

#include "DynamicInstantiable.h"

#include "ObjectInitializer.h"

using namespace std;

int main()

{

InitializeDynamicObjects();

DynamicInstantiable* newInst = dynamic_cast(Object::MakeObject("DynamicInstantiable"));

if( newInst != NULL)

{

newInst->SayHello();

}

cout << "Hello World" << endl;

}

I hope this post explains Prototype clearly. Comments and Queries are welcome.

Thanks for Reading.

References:

http://www.cs.sjsu.edu/~pearce/modules/lectures/oop/types/reflection/prototype.htm

Curiously recurring template Pattern, CRTP - Static Polymorphism in C++

Let us start this discussion with some minimalistic C++ classes, which doesn't convey any meaning but serves the purpose of discussion.

class Base

{

public:

void PrintMe()

{

std::cout << "Print: Base" << std::endl;

}

};

class Derived : public Base

{

public:

void PrintMe()

{

std::cout << "Print: Derived" << std::endl;

}

};

void TestPolymorphism()

{

Base *ptrBase = new Derived();

ptrBase->PrintMe(); // This would print "Print: Base"

}

In the above code, ptrBase is initialized with an object of Derived. Ideally, PrintMe should have printed "Print: Derived". But it would print "Print: Base". Any C++ programmer could identify the issue; early binding according to the type. It means when we say, ptrBase->PrintMe(), compiler would check whether the function called is virtual or not. If it is not virtual, it would bound this call to the address of function defined in the calling type; In this case calling type is Base.

Dynamic binding can be achieved using "Virtual" specifier, in method declaration. When we mark a function with Virtual, compiler wouldn't make early binding; it would resolve the same using V-Table. Every class which has a virtual method, would have a table of function pointers. And a hidden pointer for the table, will be inserted into the class and will be initialized during construction of objects of the class. So, during a real method invocation on objects, two things would happen. Getting the right function address from V-Table and calling the function pointed by the same. Even though this extra indirection doesn't cause much performance degradation, in several scenarios this could be easily avoided. Please find the snippet below, after adding virtual specifiers.

class Base

{

public:

virtual void PrintMe()

{

std::cout << "Print: Base" << std::endl;

}

};

class Derived : public Base

{

public:

virtual void PrintMe()

{

std::cout << "Print: Derived" << std::endl;

}

};

void TestPolymorphism()

{

Base *ptrBase = new Derived();

ptrBase->PrintMe(); // This would print "Print: Base"

}

As we discussed early, even though dynamic polymorphism doesn't cause much performance overhead, it would make a function not "in-line"able. Sometimes, in-lining a simple function would improve performance especially if it is being called several times in code. Since normal function call breaks code execution flow, CPU level, caching like optimizations, are not possible. With static polymorphism, we could achieve the in-lining capability. Now let us get into the topic of Static polymorphism.

Let us try to make Base class function a bit intelligent.

In Base class, if we could cast the "this" pointer's type to the right Derived class, we could be able to solve the issue of Dynamic binding; Means avoiding Virtual specifier.

The below code snippet won't compile, but it gives the idea of what to do.

class Base

{

public:

void PrintMe()

{

static_cast<Derived*>(this)->PrintMe(); // This would call "Print: Derived"

}

};

We had successfully removed Virtual Keyword; So, V-Table wouldn't be created and function can be in-lined. There are some problems; First off, it wouldn't compile, as compiler doesn't know the Derived class yet. Secondly, this is specialized for only one derived class. This specialization can be removed with templates. Yes. that is the whole idea.

template<Derived>

class Base

{

public:

void PrintMe()

{

static_cast<Derived*>(this)->PrintMe(); // This would call "Print: Derived"

}

};

Now, you could derive classes from the above class like this,

class Derived : public Base<Derived>{ };

Deriving from template classes, specialized with the same Derived class type, is called as CRTP, curiously recurring template pattern. Even though the above example is very minimalistic, there are several uses for this pattern. One of the great examples, as given by Wikipedia is Counter base class. In order to get the statistics of objects of a particular type, we can implement a Counter class as below.

template<T>

class Counter

{

public:

static int GetTotalObjectsCreated()

{

return nObjectsCreated;

}

protected:

Counter() { nObjectsCreated++;}

~Counter() { nObjectsCreated--; }

private:

static int nObjectsCreated;

};

template<T>

int Counter<T>::nObjectsCreated = 0;

Let us assume we need to get the number of objects created for a particular type, Test. Derive Test from Counter, specialized with Test itself.

Class Test : private Counter<Test>{ };

// Private derivation is to show that it is not 'is a' relationship.

Now at any point of time, in program execution, we could get the number of objects alive using the call like this.

int nObjects = Counter<Test>::GetTotalObjectsCreated();

CRTP is cool and positive side effect of Code replication based generics mechanism, unlike Java and .NET.