9
\$\begingroup\$

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.)

\$\endgroup\$
10
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Sep 27, 2011 at 4:43
  • \$\begingroup\$ A good question is: is this really a performance bottleneck, or are you just worrying prematurely? \$\endgroup\$ Sep 27, 2011 at 5:17
  • \$\begingroup\$ 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) \$\endgroup\$ Sep 27, 2011 at 5:36
  • \$\begingroup\$ 100K objects sounds awful high for just a game. Is this a server or an end user client application? \$\endgroup\$ Sep 27, 2011 at 7:54
  • \$\begingroup\$ 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) \$\endgroup\$ Sep 27, 2011 at 14:48

3 Answers 3

5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 27, 2011 at 4:19
  • 1
    \$\begingroup\$ +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. \$\endgroup\$ Sep 27, 2011 at 5:03
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ Sep 27, 2011 at 20:16
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ So you should use a 32-byte fixed-length string instead of std::string. Fantastic! I hadn't thought to change the string type. \$\endgroup\$ Sep 27, 2011 at 20:38
0
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .