• Advertisement
Sign in to follow this  

Task Scheduling Question.

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

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
Advertisement

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


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


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

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

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


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

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

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
Sign in to follow this  

  • Advertisement