Re: [Algorithms] General purpose task parallel threading approach

[Jon W. <jw...@gm...>]

Sebastian Sylvan wrote:
> Again, this goes back to the halting problem. It is mathematically 
> impossible to know the flow of a general function ahead of time - you 
> have to execute it to find out. If you think your system can do this 
> then you've either broken the universe, or you're wrong :-)

Luckily, I don't ship general functions; I ship specific functions.

>  
>
>     If you have wildly different dependencies based on a switch(),
>     then that
>     is better expressed as a behavior component (that you can swap out)
>     rather than a code switch(). (The "pure OO" movement claims that every
>     switch can be turned into a virtual dispatch, but I wouldn't go
>     that far)
>
>
> But it's still impossible to know which behaviour to swap in until 
> you've started executing the tasks!

If you swap in a new behavior, that will take effect the next frame.

> Look, all I'm saying is that your system isn't general - it only works 
> for a restricted form of computation where all dependencies can be 
> known before starting to execute the tasks. Is this incorrect?
>

Luckily, all games, as well as all business software, fall into that 
"restricted" form.

> I'm sure you understand that code in general doesn't work like that, 
> even this wouldn't be possible:
>
> x = spawn(foo);
> y = spawn(bar);
> sync;
> if ( x && y )
> {
>    z = spawn(baz);
> }
>

So I'm saying you, as the component writer, don't need to worry about 
spawning at all. Tasks are created by the system, to resolve the 
semantics as described by the system. Having the programmer create 
deadlocks and races and global dependencies willy-nilly sounds to me a 
lot like writing your code in assembly. Very last-century, and not where 
the industry is going. I believe the computer can actually make more 
sense, and schedule your dependencies better, than you can.


>     > You specify dependencies, yes, but they may be dynamic
>
>     Which is why the scheduler must be dynamic!
>
>
> Precisely!
>

At least we agree on something :-)

>     Subsystems can have dependencies, too. It's perfectly fine to specify
>     that AI reasoning depends on collision detection, and collision
>     detection depends on integration output (position) from the last
>     frame.
>     That way, you can re-use the collision output data for AI, rather than
>     to have to re-run queries, too.
>
>
> Precisely. As you say the AI reasoning must depend on collision 
> detection, even though it doesn't *actually* depend on it for most 
> frames (and you can't know in advance if it will). Meaning that it 
> can't run even though it's ready, it must wait for the worst-case set 
> of dependencies to finish first.

If you're not doing at least some AI reasoning each frame, then you're 
not using your cores right :-)
Seriously, though, I'm OK with saying that a task that depends on the 
output of collision testing is actually forced to run after collision 
testing. Tasks that depend only on, say, the game being in "paused" 
mode, or depend on the player input controller being pushed forward, or 
whatever, can run independent of that.

I think the discussion has come to an end, though. You want to enable 
old-school low-level code to run as well as it can under the explicit 
control of the programmer, and you're willing to pay the cost of 
allocating and switching stacks at runtime to do it. I want to move 
threading decisions away from the programmer, and let the software do 
that, based on intentions and dependencies expressed by the programmer. 
Two different problems lead to two different solutions. I don't think 
I'll convince you that your problem is "too old-school to solve," and I 
don't think you'll convince me that my problem is "too high-level to be 
useful."

Sincerely,

jw