Jump to content
  • Advertisement
Sign in to follow this  
Khao

Server Optimization : Find user

This topic is 3792 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

Hey guys, I'm working on programming a server for an online game using C++, the development is going really smooth, but there's one thing bothering my mind. Since it's for an online game, performance optimization is, of course, one of my main priority. I'm looking for an algorithm to find a user by it's user ID in a userlist. For example, if a user does a whisper command to the user 'bobby' I would prefer an algorithm that doesn't loop through the complete userlist to find that user bobby, especially if that user isn't logged on, the loop won't stop till it reaches the end. Right now my userlist is a vector, each index of the vector represents the socket number of that user (I'm programming on unix so socket definitions are integers) I'm really not sure about what I could use as a way of finding users quickly with only their user ID or they username, since my list is organized by socket number. Any help will be greatly appreciated :) Thanks!

Share this post


Link to post
Share on other sites
Advertisement
Use an associative container (a hash table or a map) to associate the name with the user identifier. Of course, you have to ask yourself whether this is really important, or if your precious time would not be better spent somewhere else (such as compressing position-change packets).

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Use an associative container (a hash table or a map) to associate the name with the user identifier. Of course, you have to ask yourself whether this is really important, or if your precious time would not be better spent somewhere else (such as compressing position-change packets).
I'd say learning about basic datastructures and algorithms like these is an excellent use of his time.
Whether this particular optimization has any real impact on the game's performance is an entirely different matter..

Share this post


Link to post
Share on other sites
At some point it may become convenient to de-couple the relation between objects being sockets.

What if I want to send in-game mail to someone that's not online? Since friends list is stored on server, how will I retrieve the names of those that aren't online? Let's say that a crafted item has creator's name - how will I look it up? What happens if creator no longer exists?


While you will indeed need a fast look up structure, the question remains how to populate it.

One way is for your lookup table to act as cache. If a look up fails, database is queried, and result stored. Result of query is integer ID representing the player. This ID may then be mapped onto socket, but only if that player is currently connected. Bonus points for storing failed queries in a way DNS client does, to prevent database DOS via invalid queries.

Another reason for mapping straight to sockets is inconvenient - what happens if player loses connection. While their connection is timing out, they are already connecting. At some point, they will be logged in twice, and your query will contain either socket id.

If you map to some player object, or only their UID, this type of problems disappears.

Sockets are just a transient resource, it comes down to the persistent items you want to map onto.

Share this post


Link to post
Share on other sites
Thanks for all the replies so far :)

For the idea of using a map, it seems like a good idea, I will look into this possibility!

Of course I also take time to optimize packages being sent to be as compressed as I can, since it is a crucial point in a server.

To reply to Antheus' post,
I think for me it is a very effective way to use sockets representing users, since when I see that the socket x has data to read from, userList[x] gives me the corresponding user. It seems to me that this also makes it a lot faster to find socket descriptors to write to, when I store a list of socket IDs in a game and I need to propagate a chat command for example. I only write to each ID in the list.

Of course, I'm not completely against restructuring my server, but I think it would create too many lists and maps. Socket -> User, UID -> User. For example if I need to send a chat command to all users logged into a lobby it would look like Lobby -> UIDs -> User -> Socket.

For what you said about users being logged on twice. I thought that when a connection error occurs, the server will know as soon as it crashes that the socket is no longer valid. If not, I will need to make sure that when you try to log in, your account isn't already logged in and if so, test the corresponding socket. Doesn't it throws an error when you try to write to a socket that closed unexpectedly?

I still need time to think about what kind of mapping will be the most effective for the server but all your ideas are welcome! :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Khao
Doesn't it throws an error when you try to write to a socket that closed unexpectedly?


To the server, there is no difference between a dead connection (the computer on the other side is permanently unavailable) and a slow connection (the computer on the other side has not received the data yet). Servers usually implement a timeout system: before a certain duration, connections are considered slow, and beyond that duration they are considered dead. That duration, however, means that a player can attempt to reconnect even though his previous socket is not dead yet.

Quote:
Of course, I'm not completely against restructuring my server, but I think it would create too many lists and maps. Socket -> User, UID -> User. For example if I need to send a chat command to all users logged into a lobby it would look like Lobby -> UIDs -> User -> Socket.


Where is the problem in that? You greatly overestimate the performance hit of following a few references (especially since the bottleneck will be the actual sending of the data, and not the reference following).

Quote:
I think for me it is a very effective way to use sockets representing users, since when I see that the socket x has data to read from, userList[x] gives me the corresponding user. It seems to me that this also makes it a lot faster to find socket descriptors to write to, when I store a list of socket IDs in a game and I need to propagate a chat command for example. I only write to each ID in the list.


Effective in what sense? As far as elementary computer performace goes, there is no serious advantage to doing userList[x] instead of userList[playerid[x]], because the memory access time is so slow that it's dwarfed by all the other processing you do. In fact, making the cache locality better on the userList (by clustering identifiers close together instead of spreading them along socket numbers) you might actually get a performance gain by adding that level of indirection.

As far as object manipulation goes, you're violating the single responsibility principle: for instance, as outlined before, this completely prevents manipulation of offline players.

Quote:
Of course I also take time to optimize packages being sent to be as compressed as I can, since it is a crucial point in a server.


My question wan't related to the 'of course I also' answer. I know you will do anything you can to optimize your game. What I was questioning is whether you actually enjoy spending a few days writing an optimization that result in no measurable performance gain. Beyond that, how you schedule your development time between things that matter and things that don't is your own personal choice.

Share this post


Link to post
Share on other sites
I'm convinced. :P

Quick resume :
My user object needs to store its socket number, I need to map UIDs to user objects, Usernames to UIDs, and use those maps as cache for logged-off clients also.

Thanks for the help guys, I see that I had a huge mistake in my code there :P

Share this post


Link to post
Share on other sites
You want a hash table. When you need to map ID -> object, without there being an obvious benefit in having an ordered collection, you always want a hash table. Unless you can use the ID as a direct index into a table, but that's often troublesome when objects go away.

Regarding delivering whispers (or whatnot), typically the ID table will map from ID to user object, and the user object will have an interface for "receive chat message" -- what that does, is up to the interface implementation, and may vary. For example, some users may have "ignore" or "filter" turned on, which means that the message will not be immediately sent on a socket (and may even be dropped on the floor, metaphorically speaking).

Share this post


Link to post
Share on other sites
Ok I've done some research about Hash Tables and it looks like the best way I could do it with the best performance vs. using a map. It says that to find an index with a map it takes O(log n) and with a hash table it's constant time but the memory usage it greater. Is the difference in memory that big or I should not bother with this?

Also I'm not sure where to look to find a good hash table library for C++, anyone can help me?

Share this post


Link to post
Share on other sites
There is no important difference in memory usage between a map and a hash table in general. A map requires child pointers for nodes and storing the R/B state; a hash table requires the top-level pointers, list pointers and the hash code. They typically balance out. The only difference you should worry about is the trade-off of O(lg n) vs O(1) and sorted vs not.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!