Before moving on, I decided to add one more concurrent container to the library I mentioned in my last post. Stack and queue are relatively primitive in that they are a singly linked list of data with either one or two pointers held by the class. Operations such as push and pop can be simplified to just changing the head or tail of the data structure. I really wanted to do one more that is an especially useful data structure so I wrote a pretty basic implementation of std::map but concurrent.
The concurrent map was implemented using a combination of buckets for a very small and basic hash, and then for any collisions in these buckets were stored in a balanced binary tree (AVL, which is contrary to the STL's red-black tree implementation). A simple hash was used because it allowed me to partition the values into "thread-safe zones" that I could wrap a mutex around. It's a pretty naive/basic way of adding concurrency to a map compared to more advanced lock and wait-free methods but it does work.
At this point I'm very anxious to get back to programming for my game and have already started reading a new book on ZeroMQ, which is a very robust library for handling many network connections in a simplified manner. I'm not sure if this is the library I will end up using for networking in the game, but it's extremely interesting none-the-less and I look forward to learning more about it.
Anyways, for those interested in checking out the source for the new concurrent map, check it out at: https://github.com/Salgat/Concurrent-Containers-Library/blob/master/containers/map.hpp
No comments:
Post a Comment