Sign in to follow this  

O(1) packet dispatcher

This topic is 3197 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'd like to represent the small template class using for dispatch packets with O(1) efficiency. Rationale. The chain of packet handling is quite similar from game to game. It contain the steps: (1) get the packet header (2) from the packet header get payload length and code defined packet handler (I don't describe here or additional work like check integrity, encryption, rtt handling and so on which usually handled on underlayer) (3) using code, found corresponding handler, (4) demarshalling packet inside this handler (5) do some work. So shortly speaking it looks like
GamePacket* message;
swicth(codeFunc) {
    case PlayrMove:
    {
        struct PlayerMoveStruct pms(message);
        movePlayer(pms);  //call corresponding player 
                          //usually member function of Player object
    }     
    break;
};
Or demarshaling provided inside the function handler in this case it looks like
class Player 
{
   void movePlayer(const GamePacket* message)
   {
       struct PlayerMoveStruct pms(message);
       //doSomething
   }
}
packets code are usually enums:
enum PlayerCode { PlayrMove, PlayerShoot, ...}
The drawbacks of this approach is obvious, (1) the central point of handler is very huge switch block (remember we need to handle usually hundreds of messages). (On compilation stage this block will be convert to if{}else if{} set of instruction) which very difficult to mountain (Imagine you forget add break somewhere...) (2) You need to repeat and repeat demarshaling code for each type of structure in every "case" block. Traditional approach to avoid those drawbacks is using some sort of container containing handler function pointers. Usually it is a map (or hash map). Hence, when we talk about mmo game practice we can note that enumerator types defining types of game packet represented without holes, or with the few holes:
enum packeType
{
firstType  = 0,
PlayerMove = 1,
PlayerShoot = 2, 
PlayerEat   = 5,
TheEndType = 256,
EnumSizeDefinition = 0xFFFF
}
So, we can use vector instead a map to increase performance a bit. Well, outline of this approach represented below:
#include <vector>

template <class TMessage, class T>
class Dispatcher
{
public:
	typedef void (Dispatcher<TMessage, T>::*func)(const TMessage*); 
	Dispatcher() {};
	template <typename P, void(T::*FuncType)(P)>
	void regFunc_t(int idx)
	{
		dispatch_table_[idx] = &Dispatcher<TMessage, T>::tFunc<P, FuncType>;
	};

	template <typename P, void(T::*FuncType)(void)>
	void regFunc_v(int idx)
	{
		dispatch_table_[idx] = &Dispatcher<TMessage, T>::vFunc<void, FuncType>;
	};

	template <typename P, void(T::*FuncType)(void)>
	void init(size_t size, T* owner)
	{
		owner_			= owner;
		dispatch_table_ = std::vector<func>(size, &Dispatcher<TMessage, T>::vFunc<P, FuncType>);
		def_func_		= &Dispatcher<TMessage, T>::vFunc<P, FuncType>;
	};
	void callFunc(size_t idx, const TMessage* buff)
	{
		if(idx < dispatch_table_.size())
			(this->*dispatch_table_[idx])(buff);
		else
			(this->*def_func_)(buff);
	};

private:
	template <typename P, void(T::*FuncType)(P)> 
	void vFunc(const TMessage* message)
	{
		(owner_->*FuncType)();
	};
	template <typename P, void(T::*FuncType)(P)> 
	void tFunc(const TMessage* message)
	{
		P p; //add marshalling here from buff to structure T something like P p(message)
		(owner_->*FuncType)(p);
	};
	T*					owner_;
	func				def_func_;
	std::vector<func>	dispatch_table_;
};

class Test  {
public: 
	Test()  { };
public:
	void init_disp(void) {
		disp_.init<void, &Test::def_handler>(10, this); //def_handler will be invoked when we out of vector range or point to the 
                                          //"hole" in our set of types
                                          //the first parameter here defined the size of the vector and usually equals TheEndType  
		disp_.regFunc_v<void, (&Test::addDir)>(0);
		disp_.regFunc_t<int, (&Test::qqDir)>(1);
		disp_.regFunc_t<Test, (&Test::ppDir)>(2);
	};
	void addDir(void) 
	{
		printf("from adddir\n");
		return;
	};
	void qqDir(int) 
	{
		printf("from qqDir\n");
		return;
	};
	void ppDir(Test) 
	{
		printf("from ppDir\n");
		return;
	};
	void def_handler(void) 
	{
		printf("from def_handler\n");
		return;
	}
	void dispatch(int idx, void* buff)
	{
		disp_.callFunc(idx, buff);
	};
private:
	Dispatcher<void, Test> disp_;
};

int main(int argc, char** argv)
{
	Test t;
	t.init_disp();
	void* qq = 0;
	t.dispatch(0, qq);
	t.dispatch(1, qq);
	t.dispatch(2, qq);
	t.dispatch(3, qq);
	return 0;
}
I don't have any desire to convert this code to library (to cover all possible use case) so, i just change it if i need something more special. Two types of function are allowed here void VoidHandler(void), void TypeHandler(AType T); I'll be glad if it will be helpful.

Share this post


Link to post
Share on other sites
So, if I send a message with a command code that's not registered, and there's a vector of dispatchers, exactly what gets called?

Generally, dispatching is done with a hash table, which is O(1) too, but doesn't use as much memory for sparse arrays. However, dispatching really isn't the big problem -- naming and resolving the appropriate message target objects is much harder, and more interesting, IMO. Especially when you support a composed object model.

Share this post


Link to post
Share on other sites
(this->*def_func_)(buff); will be called for holes and when you send "to big" command code.

Yes you are pretty right here (when we talk about hash map) but i guess that *(ptr + i) is the fastest from all hash functions which can be imagined:) Few words about using hash map:) it is not o(1) structure as far as i know it is o(1) in average, in the worst scenario it is o(n) effective structure. second, it is the same sparse array inside (with collision list as in one of stl realization) with default load factor 75% we've still got 25% of holes inside hash map.

Much memory? I talked about sparse array before, from my experience it is not a problem at all we can control each hole in array of message types. What is the reason to do a hole in enums? I think the reason is to fill it in the future without touching protocol. So, each hole is controlled by programmer.

Yep I agree again that there are more interesting tasks, the reason of publishing this small template is very simple. IMHO it's easy to use, it is more effective than switch or hash table from tr1 lib (actually it as effective as computed goto i mean http://gcc.gnu.org/onlinedocs/gcc-3.1.1/gcc/Labels-as-Values.html), it works with object function, and i guess it is really easy to understand. isn't it? I know that i don't invent America here but i cannot found via google any similar:) So, i just publish a piece of my work code:) Nothing else:)

[Edited by - aissp on March 13, 2009 1:33:39 AM]

Share this post


Link to post
Share on other sites
Ah, I thought the table grew automatically when adding message codes from different subsystems. Now that I read the code more closely I see I have to initialize it with a specific size, so it pre-fills the slots with the default function. You might want to assert the index on registration is less than the size, though -- not all STL implementations have that assertion built-in.

Anyway, is there any particular reason you didn't use either a generic functor class (STL or boost), or just an interface for "you got this packet, now you deserialize the rest and deal with it" ?
The template stuff looks more complex than I think it has to be.

If you want to pass a demarshalled struct to the handler in question, you might do something like:

[code]class Dispatcher {
public:
virtual void Dispatch(GamePacket *p) = 0;
};

// you could use whatever functor wrapper you feel like and
// typedef Handler<T> to that instead.
template<typename T> class Handler {
public:
virtual void operator()(T &t) = 0;
};

class PacketCodeDispatcher
{
public:

template<typename T> void Register(size_t code, Handler<T> *h) {
if (map_.find(code) != map_.end())
throw logic_error("The code is already registered.");
map_
 = MakeDispatcher(h);
}

void Dispatch(GamePacket *p) {
size_t code = p->readCode();
hash_table::iterator ptr = map_.find(code);
if (ptr == map_.end())
throw protocol_error("Received an unknown code.");
(*ptr)(p);
}

protected:

// use whatever table or map you want
hash_table<size_t, Dispatcher *> map_;
template<T> class ImplDispatcher : public Dispatcher {
public:
ImplDispatcher(Handler<T> *h) : h_(h) {}
void Dispatch(GamePacket *p) {
T t(p); // assume each struct can demarshal from GamePacket
h_->Handle(t);
}
Handler<T> *h_;
};

template<typename T> Dispatcher *MakeDispatcher(Handler<T> *h) {
return new ImplDispatcher<T>(h);
};
};



Now, if you're really into templates, you can omit the "code" bit entirely, by legislating that the code is an know enum member of the struct instead, but maybe you want the same struct for two different codes or something :-)

Share this post


Link to post
Share on other sites
well point by point (imho for sure :))

(1) boost using: there are two library which can using here: function and bind

function: quite "heavy" object, and you will still need send *this to invoke it (if i remember, for sure)

bind (or functor object:)): bind doesn't have a type, i mean i don't know how do keep different bind objects inside the container. What does it mean? It means that we need to write almost all code in templates. It is fine for programmers who created libraries (like boost guys, moreover if you can create library and in the same time change c++ standard to simplify your life it is double gain :)) but actually, you know, it is nightmare to mountain application level project which use template everywhere, for ex try to add functionality to boost::asio to support named pipes for windows in the same way as domain unix socket... So, my point here, do not be passionate with template using. Oh, for example of template using from real practice it like:

if(PlayerTakeARest<messageType> pl = PlayerTakeARest<messageType>())
pl.doSomething();
else if(PlayerGetContract pl = PlayerGetContract<messgeType> ())
...;

Refactoring of this code takes a quite time... I guess.

(2) Virtual function, and interface inheritance: we need to know bout price of this approach:

(2-1) from programmer practice relationship between interface and derived class is very close, this mean when somebody changing something in interface you need to make appropriate changing in all hierarchy of derived classes, if you derive more than one interface you can get interference problem


class Base1 { doSomething() = 0 ;} class Base2 { doSomething() = 0;} class Derived : public Base1, public Base2 {} //oops


It's one problem - very solid binding between base derived, the second sort of problem here - realization inheritance which looks nice but cause problem when you need refactoring code to cover changing in requirements.
I mean something like

Derived::doSomething()
{
Base::doSomething();
}


where we need to write derived code before after? what's happened if we need to do something before and after of this calling? What's happened with whole class hierarchy if i will need to change Base::doSomething? Will I bitten by another team member? I guess yes :)

(2-2) Performance degradation - two dereference happened here twice, the first one when we lookup a handler in container, the second one when we lookup handler in vtable. Moreover, I think you loose the processor cache-line with 100% probability:)

Uh, it looks like more philosophical essay than message to conference:)

Just for summary: (1) we know the function which will be handled the message in compilation time, when we create object we know the pointer to this object, as far as we know who and how will handle message we don't need to add any additional levels of indirection, i think; (2) the project will be maintained by the whole team, so code should be clear and isolated as much as possible and not affected other:) Template? ok but not more than 25 string length:)

It's just where i try to stand:)

And again, I strongly agree with you when different type of messages should handled by different type of objects (belonging the same ClientSocket class):

class Client {
private:
ClientShopping shp;
ClientChating chp;
ClientFighting fgt;
};
}

the task is going to be more complicate, and (first impression) required another level of indirection (virtual function or dynamical changing pointer to handlers table or something else).

and thanks :)

I guess i was clear :)

Share this post


Link to post
Share on other sites

This topic is 3197 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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