Being Novaleaf’s core engine architect, I try to identify problematic workflows and figure out an existing design pattern to apply, or construct a new one.
Since we’ve been parallelizing our engine, one problem I keep seeing pop up is how to manage inter-thread communications: everyone does it differently, and in doing so, has to rewrite the basic data workflow and synchronization (and do so in their own unique way) Due to the subtle nature of race-conditions, this is especially dangerous.
So, I set about designing a solution. My original solution was called “PushProcess” but after doing some searches on wikipedia for naming conventions, I have renamed it to “MapFold” (not to be confused with Google’s MapReduce).
Workflow Diagram
Data Transformation
MapFold is an abstract class, thus derived classes are required to add their own custom Map and Fold computational algorithm, giving clear mechanisms for data transformation.
- Map() allows data being input from the User threads to be transformed immediately (on the same thread).
- Fold() allows enqueued data to be transformed by the Owner thread before or during consumption.
The primary benefit of all of this is encapsulation of all this data transformation logic in a single location (the derived class) and providing an obvious extensibility point for performing these transformations.
Another major benefit of MapFold is the encapsulation and reuse of enqueue/dequeue/synchronization logic.
Source Code (C#)
/// <summary> /// Design Pattern for Multithread data synchronization/communication /// <para>this base class provides the workflow for enqueueing data (<see cref="TInput"/>) from multiple threads, /// and preparing (transforming to <see cref="TIntermediate"/> via the Map method) it for use by this class's owner /// (usually a system on a <see cref="WorkerThread"/> but not required). </para> /// <para>the data can be transformed at 2 positions: /// <para><see cref="TInput"/> --> <see cref="TIntermediate"/>: first by the <see cref="Map"/> method /// (which occurs immediatly upon invocation on the same thread as the caller)</para> /// <para><see cref="TIntermediate"/> --> output (custom): second, /// when the <see cref="Fold"/>() method is invoked (by the owner), /// additional data transformations may occur. /// the output data from this <see cref="Fold"/>() method depends on the descendant /// class overriding this abstract method. </para> /// <para> See the <see cref="FrameState"/> class for an example usage (enqueing framestate changes every frame to worker threads)</para> /// </summary> /// <typeparam name="TInput"></typeparam> /// <typeparam name="TIntermediate">intermediate data type written by <see cref="Map"/>() and processed by <see cref="Fold"/>()</typeparam> /// <remarks></remarks> public abstract class MapFold_Example<TInput, TIntermediate> { /// <summary> /// for internal thread safety use only. /// </summary> private object _lock = new object(); /// <summary> /// calls to the <see cref="Map"/>() method enqueue to this. (locked so threadsafe) /// </summary> private Queue<TIntermediate> mapQueue = new Queue<TIntermediate>(); /// <summary> /// calls to <see cref="Fold"/>() consume this. (we swap-buffer with <see cref="mapQueue"/> every call so this is threadsafe consumption) /// </summary> private Queue<TIntermediate> foldQueue = new Queue<TIntermediate>(); /// <summary> /// thread-safe enqueue <see cref="TInput"/> for consumption by this object owner. /// </summary> /// <param name="input"></param> /// <remarks> /// <para>input will be transformed to <see cref="TIntermediate"/> during this method call.</para> /// </remarks> public void Map(TInput input) { TIntermediate intermediate; Map(input, out intermediate); lock (_lock) { //only the actual enqueue is inside the lock to minimize waits by multiple threads mapQueue.Enqueue(intermediate); } } /// <summary> /// override this method to transform <see cref="input"/> --> <see cref="intermediate"/> /// </summary> /// <param name="input"></param> /// <param name="intermediate"></param> /// <remarks>this work occurs on the user's thread (the "external" execution calling <see cref="Map"/>)</remarks> protected abstract void Map(TInput input, out TIntermediate intermediate); public void Fold() { Fold(default(Action<Queue<TIntermediate>>)); } /// <summary> /// start computations on all currently enqueued <see cref="TIntermediate"/> /// <para>this should be invoked by this object's 'owner', probably once per frame.</para> /// </summary> /// <param name="foldDelegate">if you pass a delegate, this will be executed first, before the internal Fold implementation (if any)</param> public void Fold(Action<Queue<TIntermediate>> foldDelegate) { lock (_lock) { var temp = foldQueue; foldQueue = mapQueue; mapQueue = temp; } if (foldDelegate != null) { foldDelegate(foldQueue); } Fold(foldQueue); foldQueue.Clear(); } /// <summary> /// override this method to specify implementation for the <see cref="Fold"/>() method. /// <para> start computations on all currently enqueued <see cref="TIntermediate"/></para> /// <para>this should be invoked by this object's 'owner', probably once per frame.</para> /// </summary> /// <param name="intermediateQueue">all currently enqueued values sent via the <see cref="Map"/>() method (after being transformed <see cref="TInput"/> --> <see cref="TIntermediate"/> /// <para>usage note: this queue will automatically be cleared after this method completes</para></param> protected abstract void Fold(Queue<TIntermediate> intermediateQueue); } /// <summary> /// an "easy to use" concrete class that allows the min-workflow of MapFold /// without the need to create your own custom class /// </summary> /// <typeparam name="TValue"></typeparam> public class MapFold_Example<TValue> : MapFold_Example<TValue, TValue> { protected override void Fold(Queue<TValue> intermediateQueue) { //no op (owner class can interact with the intermediateQueue through the value returned by the base class's .Fold() method. } protected override void Map(TValue input, out TValue intermediate) { //no work: intermediate is of same type/value as enqueued via the original call to the base class's .Map() method intermediate = input; } } |
An Example
Instead of explaining why this is better than continuously “rolling your own”, I’ll give an example system using this MapFold workflow:
/// <summary> /// This example shows a straight forward and simple way to synchronize /// multithread communication to a render system. /// <para>For the sake of simplicity, some optimizations were omitted /// (such as reduction of value-type copies, etc).</para> /// </summary> public class RenderManager_Example { /// <summary> /// intermediate data type /// </summary> private struct RenderTransaction { public enum TransactionStatus { Alloc, Free, Modify, } /// <summary> /// transaction being done /// </summary> public TransactionStatus transaction; /// <summary> /// object reference for internal render tracking and external coordination. /// </summary> public int objectId; /// <summary> /// world transform /// <para>set when transaction==Alloc|Modify</para> /// </summary> public object xform; /// <summary> /// asset used by this object. /// <para>set when transaction==Alloc</para> /// </summary> public int assetId; } /// <summary> /// an instance of our mapFold for this renderManager /// </summary> private MapFold_Example<RenderTransaction> mapFold; public RenderManager_Example() { mapFold = new MapFold_Example<RenderTransaction>(); } #region public (thread safe) methods /// <summary> /// allocate space in our render system for a new object /// </summary> /// <param name="assetId">asset this object uses</param> /// <param name="objectId">id for our object</param> /// <param name="xform">starting world transform</param> public void Alloc(int assetId, int objectId, object xform) { //invoke our base class's mapFold.Map() which does a thread-safe FIFO enqueue mapFold.Map(new RenderTransaction() { assetId = assetId, objectId = objectId, xform = xform, transaction = RenderTransaction.TransactionStatus.Alloc } ); } /// <summary> /// remove the object from rendering /// </summary> /// <param name="objectId"></param> public void Free(int objectId) { //invoke our base class's mapFold.Map() which does a thread-safe FIFO enqueue mapFold.Map(new RenderTransaction() { objectId = objectId, transaction = RenderTransaction.TransactionStatus.Free } ); } /// <summary> /// change this object's runtime render properties /// </summary> /// <param name="objectId"></param> /// <param name="xform"></param> public void Modify(int objectId, object newXform) { //invoke our base class's mapFold.Map() which does a thread-safe FIFO enqueue mapFold.Map(new RenderTransaction() { objectId = objectId, xform = newXform, transaction = RenderTransaction.TransactionStatus.Modify } ); } #endregion #region private worker methods (execute during the RenderManger's .Update(), which is assumed to execute on it's own thread) private void Owner_ProcessTransactions(Queue<RenderTransaction> toProcess) { //does a FIFO enumeration of enqueued data (from .Map() foreach (var renderTransaction in toProcess) { switch (renderTransaction.transaction) { case RenderTransaction.TransactionStatus.Alloc: Owner_Alloc(renderTransaction.assetId, renderTransaction.objectId, renderTransaction.xform); break; case RenderTransaction.TransactionStatus.Free: Owner_Free(renderTransaction.objectId); break; case RenderTransaction.TransactionStatus.Modify: Owner_Modify(renderTransaction.objectId, renderTransaction.xform); break; default: throw new NotSupportedException(); } } } private void Owner_Alloc(int assetId, int objectId, object xform) { //allocate a slot in our render system } private void Owner_Free(int objectId) { //delete the object from our render system } private void Owner_Modify(int objectId, object xform) { //modify position of existing object in our render system } #endregion /// <summary> /// this .Update() method is meant to be executed in our render thread /// </summary> public void Update() { //FIFO execution of enqueued .Map() data (Alloc,Modify,Free) mapFold.Fold(Owner_ProcessTransactions); //draw goes here } } |
So is this unique?
I am under the impression that while this workflow is certainly not unique, few encapsulate this pattern into a discrete object. What about you? Do you do something similar? Lets discuss in the comments!