   Private Thread Heaps for thread-safe programming
  This really is only Theory (not private-thread-heaps, but the implementation im using), as i havnt tried to implement it yet, but have had it floating in my mind for a while, as im on the quest to find a way to make code thread-safe with minimal lock usage.Basically, the idea is to make a heap-per-thread, in which i would hold things allocated by that thread, and that thread only. Using an example, lets say im building a multi-threaded game server, that will be on a constant heavy load of players, NPCs, ect... Certainly, this cant all be handled by one thread, so a solution would be to multi-thread to distribute the processing load.The problem that arises, is its going to need alot of locks... A lock per-object. This creates a large amount of risk for deadlock (especially if you are working with several developers that dont have much knowledge about threading or locks)So, what if we make a heap-per-thread that only that thread can access (by using its thread id). These private heaps will hold all memory allocated by that thread, in which, if we allocate a player there, he HAS to be processed there, in that thread.Another problem arises. What if the server is in an un-active state (with alot of allocated players), and all of a sudden, those players become very active in the world. We have no way to expand, such as creating another thread, and copying half the heap (or so) to the new thread. But, we do have a way to contract, in which if a thread becomes very unpopulated with objects, it will copy its heap to another thread, and then destroy itself.Yet another problem arises. What about cross-thread access? What if i need to access my fellow player in thread A when im in thread C? What if i need to access my fellow NPC in thread B when im in thread F? Delegates? I dont know, i havnt figured this one out yet.Please go easy on me, as this is just a theory, and ive tried to google and find  some examples of private-heaps-per-thread, but have come up short with full examples. But, please tell me where i have something wrong, or if my theory might not work at all (and why).Thanks,GanonPhantom   
  You're basically talking about a kind of thread local storage, and you're not necessarily applying it in an appropriate situation.Quote:Using an example, lets say im building a multi-threaded game server, that will be on a constant heavy load of players, NPCs, ect... Certainly, this cant all be handled by one thread, so a solution would be to multi-thread to distribute the processing load.The problem that arises, is its going to need alot of locks... A lock per-object. This creates a large amount of risk for deadlock (especially if you are working with several developers that dont have much knowledge about threading or locks)You don't need a lock around any regular memory that is consumed by a given thread -- provided that only one thread touches it. This is something you can generally quite easily guarantee in your code itself, and you don't need to build a complex 'private heap' implementation around it. Generally, either being careful or using existing thread-local-storage mechanisms are sufficient (these are generally OS-level services).Furthermore, you seem to be making the assumption that the processing load is distributable, which may not be true. Any data with interdependence isn't as easy, or possible, to simply "multi thread to distribute processing load." It might just slow you down.Quote:Yet another problem arises. What about cross-thread access? What if i need to access my fellow player in thread A when im in thread C? What if i need to access my fellow NPC in thread B when im in thread F? Delegates? I dont know, i havnt figured this one out yet.Then you need to lock. Or better, you need to figure out why you need the cross thread access and eliminate it. This is the fundamental issue: the biggest, most useful gains are had from threading where you never need to talk across threads during the actual work of the thread (only when the thread is spun up and down). What you're trying to solve here is just going to be putting a band-aid on a giant, gaping wound.   ;Quote:Original post by jpetrieYou don't need a lock around any regular memory that is consumed by a given thread -- provided that only one thread touches it. This is something you can generally quite easily guarantee in your code itself, and you don't need to build a complex 'private heap' implementation around it.Well, wait. You don't need a lock to access the memory -- but you do need a lock to access the heap itself. If you share a heap across all your threads and are seeing a lot of allocator traffic, you're going to get lock contention there. In that type of situation, per thread heaps would be useful.Now, whether you should be getting a lot of allocator traffic in a game server is a different matter entirely, and it's probably not unreasonable to argue that the solution is to reduce allocator load, not add heaps to reduce lock contention.   ;  First off i would like to say, thanks for the help so far guys :).Quote:Furthermore, you seem to be making the assumption that the processing load is distributable, which may not be true. Any data with interdependence isn't as easy, or possible, to simply "multi thread to distribute processing load." It might just slow you down.Well, currently im working on a server emulator, for a game that no longer exists (in the current state it used to be), and there are several server communites that have quite a large amount of players "ready" to play when it is finished. So the server needs to be able to handle quite an amount of load, while still being able to handle AI, PVP, ect... Which i do understand that threading isnt the issue to this problem completely, as an addition im using clustering to allow load to be distributed between computers.But that said, processing packets in a synchronous way will make it "seem" faster, because you dont have to wait for other players packets to be processed before yours, and will hopefully make the game seem a bit more in-sync (especially under large amounts of stress)Quote:Original post by jpetrieYou're basically talking about a kind of thread local storage, and you're not necessarily applying it in an appropriate situation.Thanks, i will look into that :), didnt know that it was an OS-level thing.Quote:Well, wait. You don't need a lock to access the memory -- but you do need a lock to access the heap itself. If you share a heap across all your threads and are seeing a lot of allocator traffic, you're going to get lock contention there. In that type of situation, per thread heaps would be useful.Now, whether you should be getting a lot of allocator traffic in a game server is a different matter entirely, and it's probably not unreasonable to argue that the solution is to reduce allocator load, not add heaps to reduce lock contention.Yes, i read about that somewhere, about the exclusive access to the global heap, and you are right about arguing the amount of allocations that should be in the game server.Currently, the plan is to have almost everything prealloced (NPCs, Resources, Buildings, ect..) and only allocate minimal things like Players, Loot, ect... at runtime, and even then, use memory pools.;Quote:Original post by GanonPhantomBut that said, processing packets in a synchronous way will make it "seem" faster, because you dont have to wait for other players packets to be processed before yours, and will hopefully make the game seem a bit more in-sync (especially under large amounts of stress)In other words, players with lower latency will have a competitive edge over those with higher.Sync still needs to be considered regardless of how and when packets are received (up to certain limits). For accurate simulation of certain combat events you may even need to roll back entire state to compensate for a laggy client.Or you may choose to ignore the issue, but then problems occur with exploits. These can be trivial (shooting more often) or dangerous (spamming start/cancel trade on multiple clients, cable disconnect to cause several seconds of latency and similar).Quote:So the server needs to be able to handle quite an amount of load, while still being able to handle AI, PVP, ect...You'll be hard pressed to get those guesstimates right from the start. AI for typical MMORPG is somewhat trivial. Scripting via Lua or equivalent isn't a problem either. Bottlenecks tend to become spatial relations (collision detection if it needs to be accurate, database access, even cache coherency when dealing with large state, causing poor utilization of L1/L2 cache).But the above may be completely incorrect - it really is hard to predict where things will break once you scale. For example, I've had considerable problems with network drivers. Portable library, when used under windows pegged kernel CPU load the moment packets were being fragmented - under Linux, on considerably poorer CPU, load scaled linearly. Another issue I encountered were routers. The broadband ones tend to be really poor as load increases, so all stress testing needs to be done over "real" hardware to get accurate estimates.As for local heaps - they seem appealing at first, but eventually end up mostly useful for sharing globals (especially via TLS). Typically, one wants to either share no state (everything is local, some is stack allocated), or everything is read-only global.Once you start distributing, another bottle-neck becomes information passing (messages, RPC, ...), where data needs to be copied.Long story short - unless you set aside some hard numbers and aim for those planning for scalability is hard.   ;  Thanks for the reply Antheus.Quote:Original post by AntheusQuote:Original post by GanonPhantomBut that said, processing packets in a synchronous way will make it "seem" faster, because you dont have to wait for other players packets to be processed before yours, and will hopefully make the game seem a bit more in-sync (especially under large amounts of stress)In other words, players with lower latency will have a competitive edge over those with higher.This is an MMORPG Emulator, so thats not to much of a problem (because everything is turn based for the most part), but i see where you are coming from, and that could be a problem with several other systems in the game im emulating.Quote:Once you start distributing, another bottle-neck becomes information passing (messages, RPC, ...), where data needs to be copied.I actually worked on another team that is making an emulator for the same game I am, and that was a huge bottle neck (it toke atleast 2x as long for a packet to be processed, because it had to be passed from the connection server to the zone server, then back again.)As far as the thread local storage goes. I would like everything to be local only, but allow for global access of some singletons (kinda like you said above), but read-access only on those singletons.But the problem i guess is that players need to access each other to be able to read/write things, and they will be distributed across many different threads, and im not sure how im supposed to do that without a global heap, and do it without locks. (Delegates?)Anyway, thanks for the replies guys, your really helping, alot.GanonPhantom;Original post by GanonPhantomThis is an MMORPG Emulator, so thats not to much of a problem (because everything is turn based for the most part), but i see where you are coming from, and that could be a problem with several other systems in the game im emulating.It's still a problem if game is running prediction on client, and makes assumptions you're not emulating.Quote:I am, and that was a huge bottle neck (it toke atleast 2x as long for a packet to be processed, because it had to be passed from the connection server to the zone server, then back again.)That is the same problem as above - you're not compensating for latency correctly.