So I recently figured out how to elegantly use partial orderings to order asynchronous tasks. Basic partial orderings are binary relationships in the set
Unordered, Before, After and with this you can do a fair bit, but it doesn't really let you specify any asynchronous relationships. Basically I want to be able to specify things like "A runs while B runs", and to this end I added relationships
Within, Without.
Within specifies that one task runs while another runs, in the sense that the the first starts after the second starts, and ends before the the second ends, and
Without specifies the opposite.
You can kind of imagine this model like stacking blocks, some blocks must come before or after others, and some must come atop or below others. The ones on top of others have to be either smaller or just the same size than the ones below, and can't overhang.
Now, it's important to be able to check that your ordering doesn't have any loops as that could cause the program to hang, and for the simple model with just the three relationships this is easy, you just build a graph and follow edges of one of the relationships through the graph, looking for loops. What are the implications of "A is within B" however? Well, it's solvable, but the solution is kind of absurd and inelegant. Furthermore, it'd be nice to be able to specify more specific things like "A starts after B starts" —half of the
Within relationship, or "A ends after B ends" —better thought of as specifying that B must finish first.
A week ago I had an epiphany and realized that if I redefine the problem I can write a better, faster, and more flexible algorithm! What you need to do is separate the blocks into their ends, recognizing that the beginning of a block is implicitly before it's end, and vice versa.
At this point you can just remove the
Within/
Without relationships as they are redundant, and then you can use the naive loop detection algorithm without having to worry about them, so long as you account for the implicit relationship between a block's start and it's end. This also enables more interesting relationships like "A starts before B ends", the only unfortunate side effect of which is that you now have to specify which ends of the block you are referring to as well as before/after.
It's also pretty easy to actually iterate through the tree in partial order, all you have to do is loop through all the blocks and count the relationships; first count how many things must happen before this block starts, then how many things may start after this block starts, how many things must happen before this block ends, and how many things may start after this block ends. Keep a queue of things that may currently execute, and initialize it with the things that have zero things before them. Every time you take something out of the queue you notify everything that is waiting for it to start, and then after you're done with the item and everything that must happen before it's end, you notify everything that comes after it. Once a block has nothing that must happen before it, you put it in the queue. It's all a matter of incrementing and decrementing a couple integers if you do it right.
I'm doing this all in service of creating a game engine whose main loop is entirely asynchronous, and to that end you could just have numbered steps in the loops like "Physics Prepare", "Render Scene Synch", "Early logic", "Late Logic", etc. But in truth this is a cumbersome and inaccurate way of doing things —what if something is in early logic, but you need to execute something else first?— so it makes much more sense to me to instead order things relatively; "A starts after Logic starts, A ends before Logic ends" "B starts after Logic starts, B ends before A starts".
