Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Event Systems are amazing, they make extremely unwieldy code tame and really allow for dynamic creation of games through easy communication of objects and the game loop. I am having a hard time with the efficiency of my current implementation. Currently my slight optimization of separating the lists of objects into the events they respond to has done wonders, but there should be more I can do.

Currently I have two methods:

  1. Simplest : all objects are added to a vector when an event is sent all objects are sent the event through it's handle_event() method

  2. More complex : I have a map with string as it's key and int as it's value. When an event type is added, it's added to this map, with the int simply being incremented (there must be a better way)
    the vector of vectors of objects then pushes back a new vector to handle that type of event.
    When an event is called it simply calls the corresponding int in the eventTypes map to the type inside the vector of vectors of objects and sends that event to each object handling that event type.

These first method is quite slow (obviously) for lots of objects, but quite quick for very few of objects. Whereas the second method is quite quick with large objects that would like to handle different types of events, but slower than the first method per object with objects handling the same type of event.

Is there a faster (run time wise) way? Is there a faster way to look up an int from the string type? (initially I had an enum, but it didn't allow custom types, which are necessary because of the desired level of dynamism)

share|improve this question
1  
This is kind of what Hash Maps (or Hash Table) are for, the string gets computed down to a hash number which then is used to look up directly in an array. en.wikipedia.org/wiki/Hash_table –  Patrick Hughes Sep 27 '11 at 4:43
    
A good question is: is this really a performance bottleneck, or are you just worrying prematurely? –  Jari Komppa Sep 27 '11 at 5:17
    
It's already implemented, and there is a bottleneck, when many objects are used. My previous comment about the lack of bottleneck was not in the application itself but actually the speed difference between the two implementations above where the same number of objects was actually handled. I was hoping for other methods of creating event systems... However some of the ideas in this thread will increase speed quite a bit, especially in the loading of the event system (11-25 full seconds load time with 100000 objects) –  ultifinitus Sep 27 '11 at 5:36
    
100K objects sounds awful high for just a game. Is this a server or an end user client application? –  Patrick Hughes Sep 27 '11 at 7:54
    
This is my engine, so I am really going for flexibility. It will be used in server applications and end user applications (less often the first, optimization) –  ultifinitus Sep 27 '11 at 14:48
show 5 more comments

3 Answers

up vote 4 down vote accepted

It sounds like you're saying the big performance bottleneck is looking up event IDs (integers) from their string names. You could preprocess your game data to convert all event names into integers before running the game, or possibly while loading the level; then you wouldn't have to do any conversions during gameplay.

If objects are frequently being created and destroyed, there may be a lot of churn in the vectors of objects. In this case you could benefit by using linked lists instead of vectors; they're faster for insertion and deletion.

share|improve this answer
    
The bottleneck isn't large (for 100,000 objects it loses .0000076 ms/object) but I think your idea is a great idea! I think I'll actually do a one time lookup of the id, and have the eventID stored as an int rather than the original string data. And I actually hadn't thought of linked lists, good idea. –  ultifinitus Sep 27 '11 at 4:19
1  
+1 For preprocessing the IDs. You could also do it lazily by having an EventType type that each module could obtain via something like EventType takeDamageEvent = EventSystem::CacheEventType("takeDamageEvent");. Make it a static member of classes and you'll only have one copy floating around in each class that needs it. –  michael.bartnett Sep 27 '11 at 5:03
2  
Note that storing ids instead of strings will make debugging somewhat difficult. It's always useful to be able to see some text specifying where an object came from. You can go half-way by storing both the id and the string, which you keep around for debugging purposes (perhaps is even removed in release builds). –  Nicol Bolas Sep 27 '11 at 20:16
add comment

Well, let's get the simple stuff out of the way first. You have this map between strings (the name of the event, presumably) and integers (the index of the registered event listeners).

Lookup time in a map is based on two things: the number of items in the map, and the time it takes to do the comparison between two keys (ignoring cache issues). If the lookup time is a problem, one way to handle it is to change the comparison function by changing the string type.

Let's assume you're using std::string and operator< for comparison. This is highly inefficient; it does a byte-wise comparison. You don't care about the real string less-than comparison; you just need some kind of comparison that gives a strict-weak ordering (because map doesn't work otherwise).

So you should use a 32-byte fixed-length string instead of std::string. I use these for identifiers. Comparison tests for these fixed strings don't do byte-wise comparisons; they do 32-bit (or 64-bit) comparisons instead. It takes every 4 bytes as an unsigned integer and compares it with the corresponding 4 bytes of the other string. That way, the comparison only takes at most 8 compares. It ensures a strict-weak ordering, though the ordering has nothing to do with the data as characters.

Storing strings longer than 31 bytes (need the NULL character) truncates the string (but from the middle, rather than the ends. I find that entropy tends to be greatest at the beginning and the end). And strings shorter than that pad out the remaining characters with \0.

Now, you could ditch the map entirely and use a hash table. If you really have over 100,000 different kinds of event types, this could be a good idea. But I don't know of a game where that would be a remotely reasonable thing.

share|improve this answer
    
So you should use a 32-byte fixed-length string instead of std::string. Fantastic! I hadn't thought to change the string type. –  ultifinitus Sep 27 '11 at 20:38
add comment

To answer the general question:

Better Way To Set Up an Event System

There is none. All you can do is identify the specific needs you'll have for your event systems (there can be several different) and then use the right tool for the right job.

I've implemented and tried to generalize tons of event systems and I have come to this conclusion. Because tradoffs are really differents if you make it compile-time or run-time, if you use object hierarchies or blackboards etc.

The best way is to study the different kinds of event systems and then you'll have clues about which one to use in which case.

Now, if you want the really most flexible system, implement a black-board system (runtime) with dynamic properties of events and you'll have something very flexible but maybe very slow.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.