3/06/2012

03-06-12 - Oodle Handle Table - WFMO

The other big advantage of a unified handle system is that you can do things like a true WFMO (wait for multiple objects).

Often you have the case that you have launched several asynchronous operations (let's call them A,B, and C), and you wish to do something more, but only after all three are done.

You can always do this manually by just waiting on all three :


Wait(A);
Wait(B);
Wait(C);
*- now all three are done

(note : the invariant at * is only true if the state transition from "not done" to "done" is one way; this is an example of what I mentioned last time that reasoning and coding about these state transitions is much easier if it's one way; if it was not then you would have absolutely no idea what the state of the objects was at *).

Obviously the disadvantage of this is that your thread may have to wake up and go to sleep several times before it reaches *. You can minimize this by waiting first on the item you expect to finish last, but that only works in some cases.

The overhead of these extra thread sleeps/wakes is enormous; the cost of a thread transition is on the order of 5000-50,000 clocks, whereas the cost of an OS threading call like signalling an event or locking a mutex is on the order of 50-500 clocks. So it's worth really working on these.

So to fix it we use a true WFMO call like WFMO(A,B,C).

What WFMO does is esentially just use the forward permits system that the unified handle table uses for all dependencies. It creates a pseudo-handle H which does nothing and has no data :


WFMO(A,B,C) :

create handle H
set H depends on {A,B,C}
  sets A to permit H , etc.
  sets H needs 3 permits to run
Wait(H);
free handle H

The result is just a single thread sleep, and then when your thread wakes you know all ABC are done and there is no need to poll their status and possibly sleep again.

3 comments:

Tom Johnstone said...

Can you poll a handle? eg. IsDone(A)

In our job system we have a WFMO(ArrayOfHandles, NumHandles, bWaitForAll)

I know I'm just kicking semantics around here!

cbloom said...

Sure, of course. In fact "IsDone" requires only one "load acquire" - on x86 it's not even an atomic op. (*)

(* = actually there's a subtle case that requires a #StoreLoad just for IsDone status checking; you don't need to be concerned about that internally, but I use internally for WFMO checks :

http://cbloomrants.blogspot.com/2011/11/11-28-11-some-lock-free-rambling.html
)

Oddly I haven't actually implemented the "wait for any" type of WFMO yet because I haven't found any case where I want it.

Tom Johnstone said...

Well in our case, we have a fixed pool of job handles and no mechanism which automatically recycles those handles without calling 'wait', so "wait for any" is a nice way of recycling handles. Obviously you try and keep your array of handles in order of likely to finish soonest to latest.

old rants