Sign in to follow this  
Enosch

Templated Message System

Recommended Posts

Hey guys. I've been reading up on messaging systems in the forums because I'm building one into my engine. The biggest problems I can see so far are typecasting (its unsafe), how to make it extensible (so the game that uses your engine can create and use its own messages through your engine's pump), and how to to avoid having to create a bajillion and one message subclasses. I am currently trying to solve these problems by using templated messages and message handlers. The message handler's type is the same as the messages that it will handle. It stores these, of course, in a message queue. My implementation uses a priority queue and prioritizes the messages by timestamp so that the most recently created message is handled first. What are your thoughts on this system? The benefits are really great, as you have typechecking at compile time, any coder can create a new message class and a handler class for that message by simply using the templates, and there is no need for a bajillion message subclasses, since you only create the message classes that you will need you handlers to process. I know I can't be the first person to think of using templates to solve this problem, so does anyone have any experience and/or advice on this? - Enosch

Share this post


Link to post
Share on other sites
Typecasting isn't technically unsafe, at least not anymore than calling a function. If you want to avoid typecasting, use classes and virtual methods for your messages.
You could also use unions to avoid typecasting, but unless you do some tricks (tricks that are much less "safe" than typecasting), you will end up using more memory than you have to.

About your queue, there isn't any reason to prioritize by timestamp. Thats how regular queues work, the first message in is the first message out. You should instead prioritize them by say... priority :) Or not at all if you can't find a reason to have msgs with higher priority.

Hope that helps.

Share this post


Link to post
Share on other sites
Not that I'm terribly experienced with messaging systems, but my first reaction is that a templated system doesn't eliminate casting issues since you'll still need a common base class somewhere or have to do so much template specialization for so many different classes that it will quickly become tedious and/or unmaintainable.

Share this post


Link to post
Share on other sites
blaze02:
For typecasting, I am talking about having messages with a void* and a "type flag" that tells you what type of data the message contains, then casting to a certain type depending on what value the type flag contains. I guess its not "unsafe" if you know what you are doing, but any C programmer knows how many errors have arisen from casting pointers, however easier it makes our lives.

Also, my engine is primarily for MMOs, so I will be having Messages comming in over the network module that may have different timestamps on them (using UDP for incoming protocol). And, I am multithreading parts of my engine, so messages from different threads may have different timestamps. So, by testing priority I make sure that the queue runs as it intuitively should. And like you say, in most cases it will run FIFO, so there won't be much, if any, time spent reorganizing the queue.

Telastyn:
The way I have in mind for this to be used is that any message class that is created will simply inherit from a cMsg template of its choice, depending on what data it wants to have. For instance, you could declare a message class that uses an integer as its data like this:
class cIntMsg : public cMsg<int>
or a vector message class like this:
class cVecMsg : public cMsg<cVector3>.
The code below shows the implementation. Like this, you have handlers and senders automatically defined. To have a class that handles our vector message class above, you would declare:
class cVecMsgHandler : public cMsg<cVector3>::cHandler.
The same is true for sender classes. The handler class will process the messages it receives however it wants, and the sender classes don't have to actually have any knowledge of the handler classes, since it is built in behind what the user sees.

Here is my implementation (not finished yet) of this system so you can see what I mean.



See post below for updated source code.




[Edited by - Enosch on April 21, 2006 11:26:18 PM]

Share this post


Link to post
Share on other sites
Enosch,

I don't understand why typecasting is an issue in your messaging system, could you please give me a synopsis on what you are doing, or point to the main tutorial your learning from?

In all messaging systems I have used in my engines I have a very simple message template->
DWORD TargetSystemId, DWORD MessageId, int *MsgParam1, int *MsgParam2

All official engine messages have ids from 0x00 to 0x0000FFFF. If a user of my engine wants to add some subsystem and their own messages, they can define the messages with ids from 0x00010000 - 0xFFFF0000.

I also don't understand why you would need a timestamp if you have a proper queue setup, since you know the last message in, was the last message sent to your program. If there is a critical message that needs to be dealt with, you can just have a function that forces the engine to process that message right after it's sent instead of it processing the message in its normal traversing of the queue.

Share this post


Link to post
Share on other sites
I see you posted the information I was looking for while I was typing my previous message. I see you are sending your messages with some data value, and not with pointers, and that is the reason you're having typecasting issues.

I think that design is slow and cumbersome, and all the overhead from cMsg is nauseating in my opinion(especially for an MMO!), and I would redesign the system system to pass pointers instead of values.

Share this post


Link to post
Share on other sites
So you just end up with a bunch of parameter specific senders and handlers. I don't see how that really gives you anything more than judicious use of function objects/delegate [to abstract knowledge of the called function from the caller].

This doesn't really provide the two main benefits to a traditional message passing system. It doesn't provide a single ubiquitous interface to arbitrary objects. It doesn't provide a chokepoint to allow for logging, modification or dispatch to differing threads/processes/computers...

It certainly looks like nice reusable code for abstracting calls for easy dispatch to threads... just at first glance though it looks like a proper interpreter would be better for abstracting handling, and common delegates for senders; no need to tie the two together since they're so commonly needed apart.

Share this post


Link to post
Share on other sites
I hate to be the bearer of bad news, but your templated message system isn't going to work, at least without some level of run-time polymorphism. The problem is that there is no uniform type equivalence, since the full type of a templated class includes its template arguments. Thus cMsg<int> and cMsg<float> and cMsg<cVector3> are all different types. This also means that their nested class types are different. You won't be able to store all the handlers in a single list because they're all different types depending on the data they're handling! What's worse is that all the code is generated at compile-time, meaning that not only are there multiple handler lists, but that there's no way to enumerate them all for processing.

Speaking of processing, you'd have to specialize the handler code for each different data type so that each type is handled differently... but at this point you've substituted a run-time polymorphic system where you just virtually overload the handler function in derived classes, to a compile-time "polymorphic" system where you just specialize the handler function for each type, while at the same time losing the benefit of type equivalence through a base class which you would have had with run-time polymorphism.

The bottom line is that templates aren't going to solve your problem the way you're using them, merely morph the problem into something that is more subtle and ultimately impossible to solve without some real unsafe typecasting [smile] It's the type equivalence thing that kills you.

Share this post


Link to post
Share on other sites
Hmmm. Type-casting, as you say, is very unsafe. Especially from void *. Could you possibly use a generic variable container like boost::any for passing values? It's completely type-safe (unless you knowingly abuse it), and your message class architecture still stands. You create a class for each message, then send it to a handler. The type is determined with simple comparisons, something along the lines of if(msg.type() == typeof(MyMessage)) or a switch statement, and you cast safely to the right type with an any_cast statement.

For even faster comparisons that don't rely on the typeid operator, you could have a message ID and a message parameter object (either a class, or a struct, or a basic type). The message parameter object is specific to the message, and is sent to the handler in a boost::any container. Test the message ID, and if it's the one you want, any_cast the message parameter object to the type it should be. The any wrapper serves in this case to remove all doubt from the type-cast.

Disclaimer: The above might be quite bad programming practice. Doesn't seem right for some reason. I just thought it up after seeing your post, as it seemed like a good use of boost::any. However, it might be terrible for real-time purposes, what with the any_casts and the type-checking and all. I'll have a bit of a think about it. I might recant it all [grin]

Share this post


Link to post
Share on other sites
To begin, I know that a lot of the gripe (or advice) so far has been in trying to interpret my incomplete code into the actual usable design I was (poorly) trying to describe above. So, here is the code as it stands now. I have compiled and tested (not extensively) this and know that it at least passes messages. Also, I tried a handler with multiple types and that also works, with the inheriting class only having to implement ProcessMsgs() once for all classes. Also, this new code includes a cMsgGrp class that allows for a group of handlers to receive a single sent message. All of the handlers will have a group name and ID. Another note: please excuse my basic type names. I have included <iTypes.h> which basically contains typedefs to rename basic types. Don't ask, I've been using it too long now to go back anyways. Anyways, here it is:


#ifndef _ENGINE_MSG_H_
#define _ENGINE_MSG_H_
#include <iTypes.h>
#include <queue>
#include <list>
#include <string>

#define INIT_MSG_CLASS(x) std::list< ##x::cHandler* > ##x::cHandler::handlerList;

//=====================================
// Class iMsg,
// Message interface class
//=====================================
class iMsg
{
protected:
iFloat timestamp;
iMsg(iFloat t) : timestamp(t) {}
public:
virtual ~iMsg() {}
inline iFloat GetTimestamp() const { return timestamp; }
inline iBool operator < (const iMsg& m) const { return (timestamp < m.timestamp); }
};

//=====================================
// Class cMsg<>,
// Templated base class for all message types
//=====================================
template <typename DataType>
class cMsg : public iMsg
{
// Protected Members
protected:
DataType data;

// Public Methods
public:
cMsg (DataType d, iFloat t) : data(d), iMsg(t) {}
virtual ~cMsg() {}
inline DataType GetData() { return data; }
inline const DataType GetData() const { return data; }
inline void Send(const std::string& name)
{
for (std::list< cHandler* >::iterator it=cHandler::handlerList.begin(); it!=cHandler::handlerList.end(); ++it)
if ((*it)->name == name)
(*it)->AddMsg(*this);
}
inline void Send(iUInt ID)
{
for (std::list< cHandler* >::iterator it=cHandler::handlerList.begin(); it!=cHandler::handlerList.end(); ++it)
if ((*it)->ID == ID)
(*it)->AddMsg(*this);
}

//=====================================
// Class cHandler<>,
// Templated base class for all message handler types
//=====================================
class cHandler
{
// Friend Class
friend class cMsg;

// Protected Members
protected:
iUInt ID;
std::string name;
std::priority_queue< cMsg > msgQueue;

// Public Methods
public:
cHandler (std::string& n) : name(n), ID(GenNewHandlerID()) { handlerList.push_back(this); }
cHandler (const iString n) : name(n), ID(GenNewHandlerID()) { handlerList.push_back(this); }
virtual ~cHandler()
{
for (std::list<cHandler*>::iterator it=handlerList.begin(); it!=handlerList.end(); ++it)
{
if ((*it)->ID == ID)
{
handlerList.erase(it);
return;
}
}
}
inline std::string& GetHandlerName() { return name; }
inline const std::string& GetHandlerName() const { return name; }
inline void AddMsg (cMsg& msg) { msgQueue.push(msg); }

// Abstract Methods
virtual iBool ProcessMsgs () = 0;

private:
// Inline method to generate a new handler ID
static inline iUInt GenNewHandlerID()
{
if (handlerList.empty())
return 0;
return (*handlerList.end())->ID+1;
}

// Protected static Members
static std::list< cHandler* > handlerList;
};
};

//=====================================
// Class cMsgGroup<>,
// Templated base class for all message types that are sent to groups
//=====================================
template <typename DataType>
class cMsgGrp : public iMsg
{
// Protected Members
protected:
DataType data;

// Public Methods
public:
cMsgGrp (DataType d, iFloat t) : data(d), iMsg(t) {}
cMsgGrp (const cMsgGrp& m) : data(m.data), timestamp(m.timestamp) {}
virtual ~cMsgGrp() {}
inline DataType GetData () { return data; }
inline const DataType GetData () const { return data; }
inline void Send(const std::string& name)
{
for (std::list<sHandlerGrp>::iterator it=cHandler::handlerGrpList.begin(); it!=cHandler::handlerGrpList.end(); ++it)
if (it->name == name)
it->AddMsg(*this);
}
inline void Send(iUInt ID)
{
for (std::list<sHandlerGrp>::iterator it=cHandler::handlerGrpList.begin(); it!=cHandler::handlerGrpList.end(); ++it)
if (it->ID == ID)
it->AddMsg(*this);
}

public:
//=====================================
// Class cHandler<>,
// Templated base class for all message handler types
//=====================================
class cHandler
{
// Handler Group struct
struct sHandlerGrp
{
sHandlerGrp(const iString n) : name(n), ID(GenNewHandlerID()) {}
sHandlerGrp(const std::string& n) : name(n), ID(GenNewHandlerID()) {}
sHandlerGrp(const sHandlerGrp& h) : name(h.name), ID(h.ID) {}

// Methods
inline void AddMsg(cMsgGrp& msg)
{
for (std::list< cHandler* >::iterator it=handlerGrp.begin(); it!=handlerGrp.end(); ++it)
it->AddMsg(msg);
}

// Members
iUInt ID;
std::string name;
std::list< cHandler* > handlerGrp;
};

// Friend class
friend class cMsgGrp;

// Protected Members
protected:
std::priority_queue< cMsgGrp > msgQueue;

// Public Methods
public:
cHandler (std::string& n) { AddHandlerToGrp(this, n.c_str()); }
cHandler (const iString n) { AddHandlerToGrp(this, n); }
cHandler (const cHandler& h)
{
for (std::list<sHandlerGrp>::iterator it=handlerGrpList.begin(); it!=handlerGrpList.end(); ++it)
for (std::list<cHandler*>::iterator it2=it->handlerGrp.begin(); it2!=it->handlerGrp.end(); ++it2)
if (&h == (*it2))
it->handlerGrp.push_back(this);
}
virtual ~cHandler()
{
for (std::list<sHandlerGrp>::iterator it=handlerGrpList.begin(); it!=handlerGrpList.end(); ++it)
for (std::list<cHandler*>::iterator it2=it->handlerGrp.begin(); it2!=it->handlerGrp.end(); ++it2)
if (this == (*it2))
{
it->handlerGrp.erase(it2);
return;
}
}
inline void AddMsg (const cMsgGrp& msg) { msgQueue.push(msg); }

// Abstract Methods
virtual iBool ProcessMsgs () = 0;

private:
// Static list of handlers
static std::list< sHandlerGrp > handlerGrpList;

// Tool Methods
static inline iUInt GenNewHandlerID()
{
if (handlerGrpList.empty())
return 0;
return handlerGrpList.end()->ID+1;
}
static inline void AddHandlerToGrp(cHandler* h, const iString name)
{
for (std::list< sHandlerGrp >::iterator it=handlerGrpList.begin(); it!=handlerGrpList.end(); ++it)
{
if (it->name == name)
{
it->handlerGrp.push_back(h);
return;
}
}
handlerGrpList.push_back(sHandlerGrp(name));
handlerGrpList.end()->handlerGrp.push_back(h);
}
};
};

#endif // #ifndef _ENGINE_MSG_H_




The big differences include: no sender class (messages have a send method to send themselves), I remembered to include my abstract ProcessMsgs() method in the cHandler class this time (lol), there are only two classes (the message and its handler class, no "pump" base class), and the msgQueue holds cMsg objects, not cMsg pointers. This eliminates the need for sending new cMsg objects for every message (which I did initially for typecasting purposes which I don't need now).

As far as typecasting from a void* goes, I just can't agree with it. I know it CAN be implemented safely, but why worry when I can be sure at compile time what the type is. And I know it looks ugly at the base level, but that is all these classes are. You would inherit from these into the message classes and handlers that you want, without ever having to worry about typecasting, since a message can only go into its own type of queue only in a handler that knows already what it is.

For the ease of using pointer messages, I agree. However there are some cases where a pointer would be overkill or not desirable (a message is passed with a boolean as data, or passed using a pointer to a local variable). In these cases, the templated message works.

For the timestamp, I kinda agree that it is most likely a stupid idea and reserve the right to change it at any time, lol.

Anyways, thanks for all the feedback guys. As with any new idea, it needs work (or scrapping, but I'm sure I'll discover which as I go on), but I think that it will be useful.

Zipster: I'm using different queues for different types so that I don't have to typecast at runtime, the same reason I used templates in the first place. Like I said above, I'm still new to this type of programming, but I think that your idea is to let the message operate on a specific type of handler via its overloaded handler function. This obviously works (its popular enough to know that), but its not completely safe. My implementation doesn't necessarily do away with that idea, but it simply moves the handling responsibility to the message handler.

Consider:
I have a cCollider abstract class with a Collide(cCollider* c) method. My cPlayer class inherits from cCollider and cMsg<cCollider*>::cHandler. Now, in the cPlayer::ProcessMsgs() method, it can call Collide(msgQueue.top().GetData()); because it knows that every msg in that queue contains a collider pointer. And it knows this at compile time, so I don't have to spend processor time checking the type. The only thing in that specific msgQueue will be those types of messages.

One oddity that I have with this system (I know you all have problems, but I mean ones that don't involve changing the design) is that the static std::list<cHandler*> handlerList member of cMsg<>::cHandler will need to be instantiated for each new type of cMsg that you template. Hence the nasty macro at the top (again, tested, it works...). I am still trying to find an elegant and safe way to do this, and might update later when I have one, if I haven't scrapped this idea by then.

Wow, that was a longass post. Again, thanks for your feedback, as it keeps me thinking. I still think there is promise in this approach, I just hafta try before I know for sure.

- Enosch

Share this post


Link to post
Share on other sites
Quote:

My cPlayer class inherits from cCollider and cMsg<cCollider*>::cHandler.


And how many other handler classes? It still strikes me as a messy, unwieldy way to call functions. The only thing that seems to be gained is delaying execution until ProcessMsgs is called, and that would be better served with a Queue<boost::function<void()> > and some bind use...

I don't know. These sort of things really show their strengths and weaknesses in use, and I've not used it. I'm sure you have some ideas about where this will fit into your projects. Give it a try and let us know.

Share this post


Link to post
Share on other sites
It's actually not too bad an approach now that I see what you're doing, but what you gain in type-safety you lose elsewhere. For instance, as you mentioned you have to instantiate a handler list for each type of message, which can be a pain for hundreds or thousands of messages. Since your design is multi-list, single-type, as opposed to single-list, multi-type, instead of being able to check a single list and dynamically dispatch based on type, you now have to check multiple lists but statically dispatch based on type. There's also the memory overhead, not only in terms of the handler lists but also on object size, since if you have a class that handles 1000 messages it needs 1000 message queues.

Maybe it's just me, but I don't mind a little casting here and there if I know it's safe (like through type ids or other metadata). It's no different from reading data from a file or across a network, you're essentially "casting" raw data into typed objects, but no one ever complains that serialization or data marshaling are unsafe because there's a structured system in place. In the end, the compiler can only assure you of type-safety within your own program, but there's no way you can write anything useful without being able to communicate outside the boundaries of your application. The strict typing is there to protect you, but for data marshaling purposes it can get in the way.

Share this post


Link to post
Share on other sites
Telastyn:
The big difference is that you won't need to know what object is registerer as the handler, only the string name of it, from the sender. From what I can tell, the main bonus of using a message system at all instead of simply calling methods to change state is (1) that all the state changes happen (or don't happen) at once in a specific method, and (2) that it eases object-object collaboration, since an object only needs to know that there is a handler for that type of object with this name or ID, just like in a normal message system (as far as I can tell). If the sender knew the object (had a pointer to it, for instance) then it would be redundant, except for issue 1, to send it a message instead of simply calling the appropriate method. Also, the sender would not need to know the method to call, only that the handler WOULD do something with the message (however, this isn't necessarily a FEATURE, just a side effect that might be useful in rare circumstances).

Another cool thing about this system is that it can nest messages (the traditional system could as well, in the same way) to emulate the traditional typecasting method where appropriate, while still maintaining its primary type-safety functionality elsewhere.

Zipster:
The handler list instantiation would basically just take the place of having to write the bajillion message classes used otherwise. You would still have a common header containing that message, but the time spent writing new message type and handler code would be reduced (from what I see so far). And yes, the number of queues is a BIG issue. Not sure if that could be remedied in this way (I don't see it happening unless I use a base handler class which stores base class messages, which defeats the whole purpose). However, the main memory overhead gathered from multiple queues is really just them unsigned int size variable (I think). My implementation uses std::vector to store messages, and that only has the one size variable and (I think) a max size variable. Using linked lists would cost 1 or 2 pointers (4 bytes, I think) each message in the queue. So memory cost isn't too bad, unless, like you said, you have 1000 types of messages to handle. I've never done a whole game, and, of course, have never used a message system at all. But I don't think any classes will have that many types to handle. And remember, it doesn't have a seperate queue for each message class, just the underlying type of data in the message.

EDIT: Also, you would have a seperate ID and name for each inherited handler type. I forgot about those, Grrr... I see how the traditional message system is useful (good point about files/networking) since you can get any type of message, but only handle the ones you want. I still think this system can be useful in some way, but maybe messaging is the wrong task. I dunno.

Again, thanks for your ideas guys.
- Enosch

[Edited by - Enosch on April 22, 2006 8:15:21 AM]

Share this post


Link to post
Share on other sites
Don't get me wrong, I think your system is a very good first attempt, and it's assuring to know that you put typesafety on such a high pedestal. But at the same time I feel you're restricting yourself to a weird design because you want to be platonically "typesafe," when you can have all the safety you'll need just by having a waterproof design. Let objects handle their own serialization, encode safeguards into the data such as type metadata or parity and other forms of error-detection/correction.

This is where I think your messaging system is trying to do too much. It worrying about preserving the type of the data while at the same time facilitating the communication of that data. What I would do is create a separate serialization system, which controls how typed objects and data are turned into streams of bytes and then converted back. The messaging system would just be responsible for transferring streams of bytes, without regard for what they were. The benefit of this setup is that serialization system could also be used in any situation where you work with untyped streams of bytes - network transfer, disk storage, inter-process communication, etc., and could be enhanced to handle things such as encryption (for secure data) and compression (for large objects). And now the messaging system is free to worry about other things, i.e. such as how the data buffers for communication are handled, how persistent they are, etc.

Serialization is cool anyway, so if you have both a messaging system and a general-purpose serialization system you're ahead of the game [smile]

Share this post


Link to post
Share on other sites
I described a typesafe template message system a few years back.

What I did was create a "message post" per type, where you would register to receive messages, and post messages. The actual delivery could be per message type, or could be serialized across all messages using a global message manager that the message posts use.

Something like this:


class MessagePostBase {
public:
virtual void deliver() = 0;
};

class MessageManager {
public:
static void deliverAll() {
std::for_each(posts_.begin(), posts_.end(), DeliverToPost());
}
template<class M>
static MessagePost & post() {
static MessagePost<M> instance;
return instance;
}
private:
static std::list<MessagePostBase *> posts_;
};

template< class M > class MessagePost : public MessagePostBase {
public:
void addListener(Function1Arg<M const &> const & l) {
listeners_.push_back(l);
}
void removeListener(Function1Arg<M const &> const & l) {
listeners_.erase(std::find(listeners_.begin(), listeners_.end(), l));
}
void deliver() {
while (messages_.size()) {
std::for_each(listeners_.begin(), listeners_.end(), DeliverMessage<M>(messages_.front()));
messages_.pop_front();
}
}
M & postMessage() {
messages_.push_back(M());
return messages_.back();
}
MessagePost() {
MessageManager::addInstance(this);
}
private:
std::list<Function1Arg<M const &> > listeners_;
std::list<M> messages_;
};


I'm assuming you know how to write classes DeliverToPost() and Function1Arg<>().

Usage is something like:


// How to declare a message -- just a struct.
struct MyMessage {
int arg;
};

// How to post a message.
MyMessage & msg = MessageManager::post<MyMessage>().postMessage();
msg.arg = value;

// How to start listening for a specific kind of message.
// In this case, a message delivery will go to a member function.
MessageManager::post<MyMessage>().addListener(Function1Arg<MyMessage>(this,&MyClass:memberFunc));

// Deliver all previously posted messages to all listeners.
MessageManager::deliverAll();


If you want to deliver messages in time order, the system can easily be modified to schedule all messages through keeping a pair of message and time and some smarts in deliverAll().

The biggest risk in this set-up is that you have to remember to remove yourself as a message listener in your destructor, plus the code for adding/removing listeners and messages really should be slightly smarter to allow for re-entrancy and removing while in a delivery.

The memory overhead is really minimal. Theres a MessagePost (which is basically a std::list) per message type. There's a Function1Arg<M> per listener, which likely is no worse than you'd have with a non-type-safe message system.

Best of all: Because the message queues are created implicitly when you post or listen for messages, absolutely zero initialization is needed! (For you C++ nuts: If you want to register for messages during static init, then the list in MessageManager needs to be constructed through a static getter, rather than as static data, to guarantee ordering).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this