Sign in to follow this  
Tangletail

Task Scheduling Question.

Recommended Posts

Tangletail    2915

Alright, sorry about the questions. But I tend to ask for the abstract and concepts more than I ask for direct solutions.

 

First the premises. So after rewriting a good chunk of my engine, and successfully decoupling the rendering system from the main thread -WITH INTERPOLATION! YAAAAY- I now looked into threading my entities.

 

So... after doing the fork join method, I realized two things.

 

A: The entity component system did not suit my needs at all. I quickly swapped to a Component Object design, and am having far better results.

B: Threading Component Objects is more efficient than an ECS system.

 

But I came to a problem. How do you schedule dependencies effectively? I tried planning out two designs on a white board.

 

The first one was by heap sorting the entities by their dependency count. That... came with the problem of update order being from the previous frame.

 

The second came by using Graph Theory, which a lot of schedulers use.  Which means that each task holds an adjacency list. Then figure out an algorithm that will detect branches and push them to separate threads. But... the problem is still... dependencies are known from the last frame.

 

The threading system is being implemented in Lua using LuaLanes and Torch Threads, (yes it's working out well).

 

I understand that a lot of implementations uses a preupdate to determine the scheduling. But the only example I could find was Intel's Nulstein, which had unchanging dependencies. At least as far as I could tell.

 

But how do you go about this preupdate if your game world is mutable? Or is it a matter that every object has three primitive functions to call?

PreUpdate, FixedUpdate, OnFrame

Edited by Tangletail

Share this post


Link to post
Share on other sites
Hiwas    5807

I suggest you look at this differently.  What is it that causes dependencies in the first place?  The code is not dependent on other code and does not require ordering, the problem is all about data access the code performs while running.  It is obvious to state this, but have you ever really thought through the implications?  Entity component systems 'can' be extremely fast and damned near optimal over n-cores in some use cases, so the real question is what is it about a component object model which made things better?  I don't mean to suggest that component object models are better or worse, I find they both have general use cases where they excel and fail, so using one or the other is dependent on your goals.

 

But, specifically, your description of solution points out a common thought process which I, personally, don't agree with.  Attempting to precompute some form of dependency graph is self defeating.  It's like using a qsort on 'mostly' sorted data, a simple bubble sort would have been faster for the use case.  The same thing generally applies to executing game code, normally order doesn't matter all that much and you only have to worry about dependency in a very few cases.  So, instead of sorting objects up front, which have dependencies on other objects, simply allow objects to 'defer' themselves to be executed later.  The idea is that you do one pass on all objects leveraging code/data cache coherency and all the good things of not worrying about dependencies and solve the expensive case of non-linear memory access only after you have reduced the problem to the point of having a hand full of remaining items to compute.

 

I'm not sure the above makes a lot of sense, the point is trying to say that sorting initially in a game is basically a waste of a lot of complicated time.  Let the handful of objects with dependencies identify themselves in the first pass over all objects, wasting a minor bit of performance.  Compared to a big sorting tasked once a frame, taking a small number of cache hits and such in a second (or third/forth) pass over just the remaining items will almost always out perform pre-sorts.

 

Hopefully this suggests other ways to look at the problem..

Share this post


Link to post
Share on other sites
Tangletail    2915


I suggest you look at this differently. What is it that causes dependencies in the first place? The code is not dependent on other code and does not require ordering, the problem is all about data access the code performs while running. It is obvious to state this, but have you ever really thought through the implications?

 

 

I am aware that code is not dependent on code. But code -is- dependent on data. And the accuracy and order of data can be a problem. And I am merely covering loose ends in certain situations, providing a general fix for future problems with a less naïve approach, and reduce problems I have noticed. I've had instances where items that should be updated last, have found their way in the  beginning of the list while the entity it's dependent on is updated last. The item in question actually lags behind.

 

Since I threw out the scene manager, and allowed the actors to handle their transformations if they have the component, the update order does matter a lot now.

 

 

 


Entity component systems 'can' be extremely fast and damned near optimal over n-cores in some use cases, so the real question is what is it about a component object model which made things better? I don't mean to suggest that component object models are better or worse, I find they both have general use cases where they excel and fail, so using one or the other is dependent on your goals

 

 

The engine is being optimized for CRPGs. The problem I ran into for ECS is several reasons.

A. Speed isn't really a problem. But complexity did become a problem. ECS is great if the game is expected to be simple. But it absolutely sucked if you planned on implementing items with different features and functionalities. Especially if a quest was attached to it. Keep in mind I am using  Lua for lua, so things work differently than C++ or big daddy languages.

 

With ECS, I pretty much had to be ridiculously specific. Components are just data. And Systems are what processes them. That's fine and dandy if I have potions with a healing property. You'd just have a component for healing that says +20 hp or something. But, if I planned on having a potion that boosted speed, cursed the player to forever walk upside down, and take damage everytime he swung would make things difficult.

 

With the component system I've got set up in Lua, Components are data. But also mutable systems that can be easily defined with a Lua file.

NewObject { 
    Name = "Fire_Balm",
    Components = {
        {
        Class = "Model",
        Path = ".../Potion",
        },
        {
        Class = "Item",
        Icon = ".../Icon",
        Description = "An alcoholic beverage that will make you spew fire!",
        onPickup = funtion(character){. . .}, -- Function is optional. Argument is the character whom picked it up.
        onDrop = function(character){}, --item is dropped as normal if emtpy. dropping the item is a global function.
        onUse = function(character) { 
                    Hapazardly spew out fire while stumbling over self 
                    },
        Price = 5000 --if -#, can not be sold or bought.
        
        },
        {
        Class = "Clickable",
        onClick = Item.highlight(this),
        Color = {.5,.5,.5}
        }
    }

}

Instances of this item honestly only needs to reference to this data table. ECS forces each entity to copy this data, when the reality is.. if it doesn't change, the only copy of data it needs is transform. So when the item is spawned, it merely grabs a reference of the table.

 

If the item is only instanciated, then it's not assigned an ID. It's just one table that holds a reference to the table, and then an array of transforms for the current level cell.

If the item becomes unique, then it treats the table as a base, generates an ID, and stores it.

 

It might be less efficient in memory access, but constantly allocating in Lua has severe drawbacks. Plus, the entity update is not so slow that it needs a speed boost.

 

Not to mention I found the architecture friendly for modding, and rapidly adding in elements.

 

 

 


But, specifically, your description of solution points out a common thought process which I, personally, don't agree with. Attempting to precompute some form of dependency graph is self defeating. It's like using a qsort on 'mostly' sorted data, a simple bubble sort would have been faster for the use case. The same thing generally applies to executing game code, normally order doesn't matter all that much and you only have to worry about dependency in a very few cases. So, instead of sorting objects up front, which have dependencies on other objects, simply allow objects to 'defer' themselves to be executed later. The idea is that you do one pass on all objects leveraging code/data cache coherency and all the good things of not worrying about dependencies and solve the expensive case of non-linear memory access only after you have reduced the problem to the point of having a hand full of remaining items to compute.

 

I thought about that... and I believe that is a case by case scenario. I see that argument a lot where the chances of dependencies are not that common. But... I'd like to call that out as just bogus. If you have a FPS game where each character is holding onto a gun that can be dropped when they die, and picked up by another player. Each one of those guns are entities.

 

With 60 players on a map at once, you suddenly have 120 entities running around in the map. If 60 of those entities are dependent on the world matricies for their parent's bones for their own position -not to mention the facing of the camera for aim- you suddenly have a strong dependency. If the gun is fired, you have two things that do not care about where the gun is... but for a smoking barrel, the particle system responcible for that must be updated after the gun's position, which must be updated after the player's position.

 

And what of a rocket with a homing missile?

 

And what about a western-esque rpg? Each character is holding a weapon that can be collected after it's dropped. Bows, if in first person, needs to have an arrow that tracks the position of the bow, that tracks the position of the player and his camera.

 

Objects may already be in order when created. That may always be true. But there is no guarantee it will stay in order.

 

Sides... sorting is only... a few microseconds of frame time?

 

 

I'm not sure the above makes a lot of sense, the point is trying to say that sorting initially in a game is basically a waste of a lot of complicated time.  Let the handful of objects with dependencies identify themselves in the first pass over all objects, wasting a minor bit of performance.  Compared to a big sorting tasked once a frame, taking a small number of cache hits and such in a second (or third/forth) pass over just the remaining items will almost always out perform pre-sorts.

 

Hopefully this suggests other ways to look at the problem..

 

Sort of? I'm thinking along the lines of entities that depends on the position of other entities or data, with the ability to change this field. So... not just items being held. But also as a method for AI to target other AI or receive data from other AI. Probably also remove items from the update that do not need to be updated yet. Doors, Items, etc. Though that last part is less of a concern.

Edited by Tangletail

Share this post


Link to post
Share on other sites
phil_t    8084


With ECS, I pretty much had to be ridiculously specific. Components are just data. And Systems are what processes them. That's fine and dandy if I have potions with a healing property. You'd just have a component for healing that says +20 hp or something. But, if I planned on having a potion that boosted speed, cursed the player to forever walk upside down, and take damage everytime he swung would make things difficult.

 

There's nothing stopping you from having a component that has a reference to a function that can do whatever it wants using the game's object model. Like, a component with a script attached to it, which is called when the system processes those components.

 

Yes, that's "breaking out" of the ECS model, but no one ever said you must use an ECS throughout your game.

Share this post


Link to post
Share on other sites
Tangletail    2915

There's nothing stopping you from having a component that has a reference to a function that can do whatever it wants using the game's object model. Like, a component with a script attached to it, which is called when the system processes those components.



Yes, that's "breaking out" of the ECS model, but no one ever said you must use an ECS throughout your game.

 

Yes tongue.png that's why I am using a Component Object model. Uniquely, I hadn't had the need for everything to have an Update component. I allow the physics system to update an object's transforms. As Bullet has it's own scene for handling physics, and call backs.

 

But detracting from the point here... Task Scheduling?

Edited by Tangletail

Share this post


Link to post
Share on other sites
SeanMiddleditch    17565
Components and task scheduling do not and should not interact much if at all.

In more detail, don't shove a ton of live data into your components that live on (or are directly owned by) your game objects. For instance, a naive Transform Component is a broken design. _Everything_ needs object transforms, be it physics, graphics, AI, game logic, etc. That's a pretty serious contention problem.

With a more ECS like model, you have an Entity ID for each game object. There's then no rules that there be exactly one instance of a Transform Component per object inside some singular system. There instead can be a completely separate copy of the Transform Mapper for your physics, for your game logic, and for your graphics. They can all operate independently of each over, intermixing jobs on any number of threads, because there's zero contention for the same data in memory. At some synchronization point, you can move the data from one copy of the Transform Mapper to another. Thus, once all your primary physics jobs are done, you schedule a job to sync physics to graphics+logic.

You don't need an ECS to do that, of course, You don't even need components of any kind. You just have to think about where your data lives and who owns that data. A class hierarchy game can still keep multiple copies of relevant object state separate between physics and graphics, for instance.

You're also probably doing this whether you want to or not anyway, at least in some cases. Odds are, unless you're a crazy person, you're using a third-party physics library like PhysX or Box2D for your game. Those libraries manage their own state internally. They know absolutely nothing about your object system or your component model. They keep their own copies of position, velocity, etc. for each body in their simulation. Even if you have some singular mega Transform Component or Physics Component, those are at best just copies of what your physics library has in it. You have to synchronize the data stored in your components and the physics library at some point.

You can then structure your other systems this way. For instance, _nothing_ in your graphics code should have any idea what a component is, or what a game object is, or so on. All the graphics code needs to deal with is the exact data used to draw on screen. That necessarily implies that it is its own specialized object state for anything on screen, complete with its own copies of transform data.

At that point, you have the Big Three covered. Your physics middleware handles its own data for physics. Your graphics library handles its own data for rendering. And your object/component model handles all the data used for game logic. (Animation systems can add another layer of complexity, especially if animation feeds into physics or game logic and is also driven by physics or game logic. Games with complex AI may have yet another independent module with its own data as path-finding and analysis are typically very asynchronous.)

What you can start seeing then is that many of components don't actually do anything. A Physics Component for instance might have a bunch of initial parameters used to create and prime a corresponding body in the physics library, but that might be it. After game object creation, the Physics Component may even just be a dead lump of unused data! Some game engines even optimize for this case by differentiating between "per-instance" components and "per-archetype" components.

This directly leads into why I dislike the ECS pattern. It's a mistaken design; it's optimizing for a use case you shouldn't ever have if you're doing your job right. Your components and game objects and such shouldn't actually be doing much of anything, because all that code should live off in separate libraries and layers that aren't even able to know what an "entity" is. Largely you'll have some game logic systems operating directly on components, and those aren't going to be your bottleneck (probably).

Share this post


Link to post
Share on other sites
Tangletail    2915

Er... off track once again. And... I'm starting to wonder if I can get a direct answer on this forum without some sort of chiding about my current architecture that is working well, and the need for a refactor would mean to completely rewrite something I am already happy with.

 

My components are not updated one at a time. The entity as a WHOLE is updated. I threw out the ECS because I just couldn't care for it. ECS eventually just got messy to use.

 

I have one GameObject class that acts as a container, and then components that attach to that. Components can be disabled, enabled, and removed at runtime. Components also do not -have- to be updated every frame. But are controlled through basic callbacks and events. GameObject is what has transforms. As GameObject is a class used for specifically Objects that must be placed in the scene. Spector is a class I have for logic that is attached to either the world or the cell.

 

GameObject - The name specifically states for an object that can be seen in the game. Have some form of interaction, or what ever. Basically anything that exists in space and needs to be updated, or has function that is triggered by event. Lights are forced to implement this. Why? Because lights can flicker, may be snuffed out., change color, etc., Can be turned on and off. Concidering the engine is designed for CRPGs where this sort of element is needed. I am not changing it.

 

GameObjects are also clones of templates. Which makes them poor use for regular logic.

 

Spector - Or a ghost object. Something that does not exist in the mortal plane. Soul purpose is for all logical holding that is related to a specific level or the world. Logic for puzzles, logic for checking if a boss is dead, which tells doors to open. Logic that detects if three conduits across the continent have been activated successfully. It may not hold components, but it is allowed to receive and send events to other components.

 

Because all NPCs and the player's controller is just an AI, A global Spector manages callbacks to game overs, character death messages, and user input.

 

Physics is Bullet Physics (for the love of god I am using 3D), and each component is updated one at a time. Some precautions were taken to make interactions are efficient as possible. Certain features for items are automatically turned off until explicitly stated otherwise. If a Collision mesh was detected in the mesh file, then it automatically implements rigid body. But it defaults to dynamics being turned off.

 

The transform (managed by gameobject) is just for logic to have data for, and is pushed off to the graphics. The way bullet physics handles, is that you send data to it's world, and get new transform data. Graphics uses a double proxy, so it has current and old data. I don't see how you'd do otherwise with interpolation -.-;

 

Now can I -please- just get a response to the question that was asked.

Edited by Tangletail

Share this post


Link to post
Share on other sites
phil_t    8084


My components are not updated one at a time. The entity as a WHOLE is updated. I threw out the ECS because I just couldn't care for it. ECS eventually just got messy to use.

 

That might make it hard to manage some dependencies properly (see below...)

 


GameObject - The name specifically states for an object that can be seen in the game. Have some form of interaction, or what ever. Basically anything that exists in space and needs to be updated, or has function that is triggered by event. Lights are forced to implement this. Why? Because lights can flicker, may be snuffed out., change color, etc., Can be turned on and off. Concidering the engine is designed for CRPGs where this sort of element is needed. I am not changing it.

 

One thing you might consider is just letting a light be a light. Flickering, color change, etc... can be implemented by having a script attached to the light object that manipulates properties of the light.

 

 

From your other thread:

 


Because most dependencies are of an acylic nature, we can easily schedule them accordingly. Dependencies are treated like stacks. Last in first out. We want to fire a bullet, which comes from a gun... that comes from a soldier. Well...  bullet is dependent on gun. Gun is dependent on soldier. So the order is Soldier, gun, bullet. Branching dependencies are dispatched to separate threads.

 

I think you're talking about two different kinds of dependencies. One, the gun depending on the solider, is basically a parent-child transformation dependency.

 

The other dependency (the bullet being created at the gun's position, aimed in the right direction) is different, since the bullet is not attached to the gun - it just gets its initial position/orientation based on the gun. After that, there's no reason for it to have any kind of dependency on the gun - it should be its own top-level object controlled by physics.

 

This could be accomplished by having all your parent-child transformation updates processed, and then by running any "post-transformation" scripts. But that's not possible if an entity is completely responsible for updating all aspects of itself.

 

I guess what I'm getting at is: the way you've set things up (an object-to-object dependency tree, and each object responsible for updating everything about itself), you are enforcing "all aspects of entity x" are dependent on "all aspects of entity y". Which may not always be true. For instance: what if an AI attached to an object needs to know the current updated position of another object? And that other object's AI needs to know the current updated position of the first object? That's not possible with your current system, since dependency is at the object level. But it is possible if all objects' transforms are updated first, and then all objects' AI is run subsequently (something that would happen naturally if you were using an ECS, for instance). With your current design, as you progress you might find yourself needing UpdateLate, UpdateEarly, etc... methods on your objects, which can get hard to manage.

 


Now can I -please- just get a response to the question that was asked.

 

It sounds like based on your other thread, you've come up with a solution for managing your dependencies. Care to explain it?

Share this post


Link to post
Share on other sites
frob    44977

I understand that a lot of implementations uses a preupdate to determine the scheduling. But the only example I could find was Intel's Nulstein, which had unchanging dependencies. At least as far as I could tell.
 
But how do you go about this preupdate if your game world is mutable? Or is it a matter that every object has three primitive functions to call? PreUpdate, FixedUpdate, OnFrame

My suggestion would be to not use them.  Only have a regular fixed-time update step.  Having a pre-update and post-update add complexity that can generally be avoided with a bit of design.

 

I don't see what you described as a scheduling problem or dependency problem. 

 

While games often benefit from having multiple cores and parallel processing, generally the core functionality of the game needs to run on minimum spec, which often means you should be able to perform your work on a single core or dual core machine.  You can take advantage of additional processor if they are present, but you generally shouldn't build your game with the assumption that you can always be parallel.

 

I've worked on several games where the engine had a pre and post update step, but we found in practice they were almost never used, and those few times they were used tended to be work that could have been accomplished just fine in the main simulation.  In one particular in-house engine (used for a game and three sequels) we ended up disabling the pre/post update steps to recover the sliver of processing time.

 
 

What specifically are you attempting to do in your preupdate step?  What is it that you cannot do with one round per simulation step?

 

 

 

I've worked on quite a few games that didn't follow that model, and I don't think it caused problems. I don't think the dependencies are are big as you are making them out to be.  They might be for your specific game implementation, but I can't readily imagine them being so as a matter of course.

 

The Sims 3 had a thread model superficially similar to yours.  Instead of threading each component, there were several game tasks that had their own threads (audio, rendering, etc) but critically all of the individual Sim characters lived in their own thread. 

 

We didn't have threads per component, there were lots of components that could be added and removed, just threads per actor in the simulator, and some work threads in the engine. 

 

The simulator behaved as though everything was serial. The simulator used the threads both as an organizational tool and as a safety tool. If something happened to a thread, either it stalled or crashed, the simulator that controlled the thread would reset the Sim associated with the thread and any objects they were using, then start a new thread setting the Sim to a safe idle position.

 

Some actions in the simulator threads were immediately run, but much of it was queued, hidden behind the scenes inside the engine and away from the simulator. Requests to move were exactly that, a request. As a wonderful side effect of the "every sim is a thread" model, when there were requests that required a bit of time, the individual thread could be suspended or otherwise worked around if it made a blocking request, the rest of the game could move on.  

 

With all of that, there was never really a need for pre/post update steps in the simulator for the game. If code needs a delay for time there are many options available, including using clock tools where you can add a timestamp to test against, with both wall-clock times and simulator-clock times available. If you need something to take place in the next update set the alarm for now+1

 

 

 


Basically anything that exists in space and needs to be updated, or has function that is triggered by event. Lights are forced to implement this. Why? Because lights can flicker, may be snuffed out., change color, etc., Can be turned on and off. Concidering the engine is designed for CRPGs where this sort of element is needed. I am not changing it.

I'm not so certain that these need their own threads.  We had similar actions in The Sims. Flickering can be done by an animated texture that is handled by rendering, or by registering a timer with a callback alarm rather than requiring a full thread. Other changes to the light, such as being turned on or off or changing color, are caused be being interacted upon by an actor in the game (using the character's simulation update) or by the player directly (UI thread). 

 

There may be a small number of items that require their own simulator thread, but we found in practice nearly everything can piggyback off callback alarms, character simulator updates, or the UI's direct interactions.

Share this post


Link to post
Share on other sites
Tangletail    2915

Sorry I am a bit loopy on my thoughts with this stupid medication from the doc.

 

The reason for my multi-tasking is that currently Quad Core systems are actually incredibly common. Programming for just a single core isn't quite targeting the common minimum specification. It would be more like targeting walmart computers built in 2005. Plus being mostly a hobby and learning experience, it'd be pretty counter intuitive to dial back a few steps.

 

I am trying to have my game-objects determine their dependencies before the scheduling pass to the task threads. That is to put data dependencies in the correct order, and all strongly dependent items in the same job. Similar to what was done in Shadow Fall. 

 

Or at least figure out how they did it, and make the technique my own. I could just very well be seeing something idealistic or not there, because I can't actually see the video myself, nor afford the costs for GDC. So context to a concept is basically slimmed down to pretty pictures and bullet points.

 

 


The Sims 3 had a thread model superficially similar to yours.  Instead of threading each component, there were several game tasks that had their own threads (audio, rendering, etc) but critically all of the individual Sim characters lived in their own thread. 

 

So... instead of tasking... you had each character existing as an OS thread. That sounds ridiculously expensive. If memory serves correctly... you had approxmiately ninety somethin lots in the sims. And god knows how many characters.

 

Honestly, I'd consider it if my specification were CRPGs. Which basically meant I'm limited to what seems reasonable for that design. And everyone I talk to just basically beats their chests and chants "There are overheads to threads." But if it worked in the Sims... then dear lord.

 


I'm not so certain that these need their own threads.  We had similar actions in The Sims. Flickering can be done by an animated texture that is handled by rendering, or by registering a timer with a callback alarm rather than requiring a full thread. Other changes to the light, such as being turned on or off or changing color, are caused be being interacted upon by an actor in the game (using the character's simulation update) or by the player directly (UI thread). 

Er... why do these need their own threads?

Edited by Tangletail

Share this post


Link to post
Share on other sites
frob    44977

Looks like you are confusing threads with multiprocessing and multitasking.  I suppose that's an easy enough mistake to make since many times they are used for that, but threads have many purposes beyond multiprocessing.

 

 

 


The reason for my multi-tasking is that currently Quad Core systems are actually incredibly common. Programming for just a single core isn't quite targeting the common minimum specification. It would be more like targeting walmart computers built in 2005. Plus being mostly a hobby and learning experience, it'd be pretty counter intuitive to dial back a few steps.

 

Multi-tasking is one use for threads.  There are many parallel algorithms that work extremely well in multiprocessing environments.  They're also fairly advanced and prone to error.  Learning how to write multithreaded code and multiprocessing systems can be useful skills, just be prepared for the complexity it brings. If you thought debugging a single threaded program was hard, it gets roughly exponentially harder for the number of multiprocessing tasks you add.

 

Now in addition to using them for multiprocessing, you can also use them for organizational purposes.  It sounds like your description was to use them for organization, on a per-component basis.  

 

 

 


So... instead of tasking... you had each character existing as an OS thread. That sounds ridiculously expensive. If memory serves correctly... you had approxmiately ninety somethin lots in the sims. And god knows how many characters.

 

Threads are not inherently expensive, although they do have a cost. They are not inherently good or evil.  They are an organizational tool to help organize your processing.

 

Threads can be scheduled, started, stopped, and otherwise manipulated.  That is their power. That is why they work so well for multiprocessing. 

 

In the case of The Sims 3, there were threads for non-simulation tasks; threads for audio, rendering, and so on. These were there to take advantage of multi-processor systems. Those tasks could take place independently of each other, and independently of simulation.  That is one of many great uses of multiprocessing.

 

The simulator had its own thread to control the workload.  The simulator owned a series of other tasks for organizational purposes.  One great use of threads is that since they can be started and stopped independently, if one thread crashes you can continue your program.  The simulator in TS3 had a large number of Sims to simulate, each one had a potential of crashing, stalling, or otherwise causing problems to the entire app.  By organizing them in their own individual threads, each one could be started or stopped individually. In the event of a critical error, the data items associated with the thread could be reset to a sane state and their processing restarted.  A very small number of autonomous objects in the game also needed to have their own simulation running, these were created along with the other states. 

 

Note that like all large games, not all the world is updated all the time.  By using threads to control the workload, and by having the individual objects managed by spatial rules, only a small number of them need to be active at any given time.  While the game world itself may have tens of thousands of game objects, normally TS3 had only a single active lot at a time needing active simulation, plus a small number of neighboring lots that needed occasional simulation. 

 

Just because it used a large number of threads for organizational purposes does not mean they ran through the system like a stampede of raging wild elephants.  Each was tightly controlled and run individually as an organization tool.  More like a set of tightly-reined stallions being shown through dressage. 

 

Controlling your threads is an important part of multithreading and multiprocessing design.  You can let them run wild, like a stampede; this is most likely for someone inexperienced, you are unlikely to get good performance.  You can have them running carefully trained for peak performance, like the Grand National or Kentucky Derby. You can have them tightly controlled and methodical, like the Lipizzaner Stallions. 

 

 

 


Er... why do these need their own threads?

 

One example was a set of gambling objects: an automated poker table, roulette table, and blackjack table. The table had a robotic dealer as part of the game object, shown below:

 

Thumbnail_688x336.jpg

 

When sims sat down at the table, the robotic dealer needed to wake up and have all its simulator steps happen. The robotic dealer needed quite a lot of processing and animation, and was best implemented as its own actor in the sim world. When the poker table cleared out and sims were done using it, the robotic dealer would effectively shut itself off, triggering the end of the thread.

 

These types of objects were the exception rather than the rule. Most of the times the sims themselves went around the world and triggered their own interactions with game objects. The sim's processing thread would call into a game object's interaction and trigger a TV turning on or off, or trigger the lights changing, or trigger whatever else to happen. There was no need for individual components, such as moodlets or traits to have that type of processing.

 

 

 

 


I am trying to have my game-objects determine their dependencies before the scheduling pass to the task threads. That is to put data dependencies in the correct order, and all strongly dependent items in the same job. Similar to what was done in Shadow Fall. 

I understand THEIR dependencies, since they were reviewed at length.  Their dependencies were caused by coupled systems -- object updates were too intimately tied to animation and world manipulation.  These could have been avoided (or significantly reduced) by making them either asynchronous or having the tiny simulation job block for a single task as the external simulator ran the blocking operation and other jobs continued.

 

The question is: what are YOUR dependencies that require it, and can you work around them?  Chances are good the dependencies can be removed with a little thought and cleanup. It is likely less difficult than writing a more complex scheduling and prioritization system for a CRPG simulation.

Share this post


Link to post
Share on other sites
Tangletail    2915

I'll agree that I am basically treating the words Thread, taksing, etc, as synonomous terms. But I do have a number of my systems divided up. Rendering is off on it's own world with a double buffer of the game world to interpolate between. Audio is off on it's own world as well. And three resource loading threads. I am thinking of removing game logic from the main thread. And allow the main thread to only bother with events.

 

I actually have a list! And this isn't from the top of my mind, this is actually something I noticed on my first three tries.

 

A. Items in hand or particle system are treated as entities, and they sometimes lag behind. It's not bad, but it is noticeable. After turning off the interpolation on the renderer, and basically stepping through the frames, the item is actually falling behind.

B. Entities using ray casts for AOE, Cone, and Line based attacks. Sometimes fails to check out. This is probably caused by the two states being drastically different.

C. An entity get's killed and removed from world, and an AI still has it's tag when it's updating suddenly triggers a number of errors on the lua console.

D. Delay when an AI uses doors, though that might be caused by something completely different

 

Those are the only things I have noticed.

 

Though... looking over this list It may not be inherently caused by scheduling.

 

EDIT: I found half of the errors.

 

It seems I was incorrectly updating the physics engine. I think anyways.

But I still have a problem with children lagging behind. I guess, I could go with a quick and dirty fix, and just remove entities the moment they are attached from the update lineup, and hold a reference to them in the parent actor. But... that just seems like an ugly fix.

Edited by Tangletail

Share this post


Link to post
Share on other sites
frob    44977
The items you listed are commonly expensive items.

Manipulating the world in big ways that require hooking up many systems or notifications -- such as adding and removing items from the world -- tend to be expensive operations in all games. You note that items getting removed from the world causes things to fall behind, that may be part of the reason.

Ray casts and area attacks you mention are slow. It may be a side effect of whatever spatial tree systems you are using, or not using. Good spatial trees make spatial queries run nearly instantly. Bad ones or missing spatial trees mean slow operations.

I'd suggest the next thing to be useful is a simple method that times your individual jobs. It doesn't need to be super fancy, just use rdtsc before and after the job and recognize that the instruction has some serious timing concerns if power management happened to kick on or tasks were shuffled between processors. While the number isn't always perfect, a tiny bit of effort and logging can quickly provide a rough profile result for all your tasks and jobs.

That gets back to one of the nicer features of TS3's threading model: When a simulation thread exceeds its scheduled time allowance it could trigger a warning and be suspended until the next round.

Share this post


Link to post
Share on other sites
Tangletail    2915

Mmm... I don't know Bullet's ray cast is pretty quick. Especially if you keep it's distance clipped. But performance is not quite the concern just yet in threading.

 

Also I am terrible with acronyms. But I have probably never heard of these two terms.

 

What is RDST, and what is TS3

Share this post


Link to post
Share on other sites
frob    44977

TS3 = The Sims 3, which had been mentioned several times in the posts. Sorry if you missed that shortening. I probably should have called it out specifically.

rdtsc = A CPU instruction (shortened form of ReaD Time Stamp Counter) that reads the processor's current time stamp. Many compilers provide an intrinsic operation for it, like __rdtsc, that makes it an easy tool for some measurements.  Store the value of __rdtsc before and after the work and you've got a timing value. It suffers from some problems during certain events: power management events can cause it to pause or jump or change frequency, and when a thread moves from one CPU to another CPU it will report whatever value is associated with the other CPU.  The operation is nearly free and often serves for simple performance monitoring.  You can use more complex monitoring methods, but they generally require more work.  The rdtsc method is easy to implement and mostly works okay despite its flaws.

Share this post


Link to post
Share on other sites
Tangletail    2915

Ok I got you now. 

 

EDIT: This post has been drastically changed after a Rubber Duck Debugging.

 

After a quick change to update order. Some other things have been fixed.

 

What I'm gonna try is to see how it works if AI is updated when the state is static. Perfectly safe to grab information directly. 

 

Update Physics. Bullet Physics has callbacks for collisions.Then update entity information on a per actor basis, where only actors can change their own data at this time. All things that changes data would probably need to be passed as messages to be processed when the entity has a chance.

 

Especially when it comes to updating transforms. Where latency will just be a lesser evil. Starting game. Update AI, physics does nothing, Entity sets vector, AI updates again, same message. Physics moves the world, Entities set new course. And so on. And... I guess AI can set state dependencies. A fleeing vagabond must be updated first, before a Gnoll can effectively turn and set it's course.

 

Then floaters, which currently are just items that have little purpose in the update except for fancy stuff and updating their transforms from the physics simulation for the renderer. Meaning they just kinda exist until activated by the AI. The can probably all be jammed into one job. Until an actor shows interest in it. So I suppose doors and chests will only need to be updated if our AI, physics, or player is interested in them.

 

So... order would be.

AI -> Physics -> Entity State Update -> dump to renderer -> repeat.

 

But... I guess with this setup I run into a few problems. Logical updates are now split. This means that the AI should not directly write anything to any actor. Even it's self. I guess this is how Shadow Fall did it's dependency system. The AI is allowed to update, and build it's graphs as well as a queue for each of it's components. After physics are applied, we can update stateful information in the correct order.

 

Huh... I guess it's that simple? If so, thank you. Because it took a bit, but you just made me realize that if logic is split from information, then you can easily determine where things meet.

Edited by Tangletail

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this