Bourbon Fibers: Job Serve Algorithm Comparisons

Preface

When a fiber/thread finishes a job, it has to get another job from the scheduler. I call this process job ‘serving’.

In an environment with priorities attached to jobs (High, Medium, Low, in my case) it’s imperative to avoid inundation of the queues for each priority. For example, if a hundred high priority jobs and one low priority job gets pushed, how long should it be until the low is processed? This is largely subjective, but for game engines it has to be somewhat promptly, yet still remaining less often than the high/medium jobs.

Continue reading “Bourbon Fibers: Job Serve Algorithm Comparisons”

Bourbon Fibers: A Day in the Life of The Scheduler

Here’s a quick diagram I wiped up to get an idea about how the priority of jobs in the naughty-dog-esque fiber scheduler look:

SchedulerFrameCycle

Obviously this is somewhat unrealistic, most systems will not be spawning that many jobs. It demonstrates the point though and also shows the importance of yielding waiting jobs – a part I think was undervalued from the design of this.

We really need a name for this type of engine. I want to stop referencing it as the naughty dog engine, as that just seems inappropriate. This task scheduler is varying enough that I would like a general term. My vote is for DeSync Core.

Anyhow, I’ve settled for a downstream/upstream job queue which I will be detailing soon.

I Gave Systems Programmers the Benefit of the Doubt

To clarify, I define systems programmers in engine development as the developers making the:

  • Graphics Systems
  • Physics Engines
  • Scripting Binds
  • Etc.

Normally, I make my systems interface as rigid as possible. The less flexibility the system programmer has in regards to the core the better. We don’t want them mucking around in there, retrofitting it to their needs. Much the same treatment as a gameplay script, it helps to give them only the minimal subset of data that they need and to enforce that as the only POC (point of contact) between your core and the systems.

Basically, this means they get this:

class ISystem
{
public:
	virtual void Update(std::vector<util::bufferpack*>& packs) = 0;
};

But in my adventures attempting to implement the Naughty Dog De-Sync Core (GDC Vault Talk) I have ended up with this:

class ISystem
{
public:
	virtual void Update(...) {
		// many threads in here at once
	}
};

Let me go ahead and say this is not good. There is one copy of this system and many threads running the same update loop on that copy. Imagine this scenario:

class ISystem
{
	int a;
public:
	virtual void Update(...) {
		// many threads in here at once</code>

		a = 0;
		std::cout << a;
		a = 100;
	}
};

Assuming we run a non-trivial amount of Update’s at the same time, the results from that cout will be mangled and horrific.

Will we have to lock variables everywhere, causing contention issues?

Thankfully, the answer is no. Not because of any greater reason than I am forbidding locks from being used within a system update. Contention immediately ruins the gains that come from the de-sync core, so it is against my coding standard for Bourbon.

In regards to system writing, does this mean that developers cannot use any member variables within the system for fear of threading issues?

Yes and no. Usages like that of a in the previous example are not allowed. You may however, initialize data within the scope of the class. Graphics is a decent example of this, as it is likely the system will share some graphics contexts and other GPU handles. These are less likely to require locks and are therefore permitted.

Side Note: Inquisitive people might stop here and think, “Why have a class at all?”, which is a good point. Unfortunately, each system within the engine must be encapsulated because the entire engine is copy-constructable. This is a design requirement of Bourbon that may or may not apply to other de-sync engines. I’m hoping to run two engines instances within the same process naively. Aside from that, it’s good for sanity ūüôā

So how do we enforce this and/or check for ‘lock correctness’?

Well, that’s where this article comes from. You can’t. I thought long and hard – there’s no mechanism to do so of course – so we’re stuck with the only option left.

Gotta trust system developers for once.

Interface: HTTP Server

Alternative title: “An attempt to decrease interface overhead to nothing”.

I don’t often opt to make bare exposed functions (In this case, merely hiding behind a simple namespace). ¬†Generally this leads to code bloat and is a shy away from singleton hell, minus the singleton itself.

For this project, I needed an http server running on X threads in the background async with the rest of the project. ¬†It’s the most barebones http server. ¬†I’m not going to spin up Apache for this, so I opted to use boost::asio¬†with some simple listener sockets. ¬†On the front end, the usage looks like this:

http::Register(“foo”, [](HttpServer::Response& response, std::shared_ptr<HttpServer::Request> request)
{
auto content = request->content.string();
if (content == “ping”)
response << http::FormatResponse(“pong”);
});

Format response is the saddest part of this system, as some response headers are needed to be written into the response stream.  The alternative that might immediately come to mind is to not expose the stream to the client, handling this part behind scenes.  While this is valid and could be argued for, I opted to do this as it avoids unnecessary string manipulation overhead.  Responses are written directly to stream instead of formatted by the client, then formatted by me, then written to stream.

Register works as a singleton, first call to it boots the server up. Generally registers will happen early in the life cycle of the program, so I don’t see this as a construction overhead. ¬†Register also handles bad request exception without exposing them to the client. ¬†This works well with tiered exception practice as user-code must handled specific exception before hitting the more generic http response exceptions.

[C#] WPF Snafu’s

Is it just me or is some of the API design in WPF very odd?  I can understand MS tailoring to a managed environment but some of this is really nerve-wracking.

Here’s a list of oddities, in no particular order, with their (pseudo) solutions.

  • ObservableCollection implements CollectionChanged and throws¬†NotifyCollectionChangedEventArgs along with it’s changed event but does not reliably set OldItems.
    • Reasoning: A RESET is given along with the event if some drastic change has occurred such that the gathering of OldItems would take more than a trivial amount of time to process. ¬†For the sake of performance, this is understandable.
    • The side effect of this is that your collection changed event should check for a RESET eve- oh wait, it’s not reliable? ¬†RESET can be thrown in a variety of circumstances? Well then.
    • http://stackoverflow.com/questions/224155/when-clearing-an-observablecollection-there-are-no-items-in-e-olditems

 

  • Another one for ObservableCollection: There appears to be no manner in which to suppress collection changed event procs when doing bulk operations on the container.
    • Ex: Adding items one-by-one to the container will refresh data binds and call event callbacks every. single. time. The first look answer is to use an intermediate collection, then AddRange the two together. ¬†This would be great, albeit memory-inefficient, if we actually had an AddRange.
    • Reasoning: I’m not sure. ¬†I’d like this one explained though the sources I’ve found citing the problem are more focused on solving it than figuring out why the API does not come with some manner in which to lock/block collection change notifications for a segment. ¬†Maybe I’m missing something?
    • http://stackoverflow.com/a/670579

 

  • WPF’s TreeViewItem’s Selected event bubbles up. ¬†By selecting a child item, all the parent nodes will also gain Selected event fires. ¬†This is apparently standard behavior which is not that well documented.
    • Quick fix: Set the RoutedEventArgs.Handled of the Selected event to true. ¬†The bubbling will cease.

boost.python and Visual Studio

First off – some helpful links:

 

How to get boost.python running smoothly using only visual studio:

http://stackoverflow.com/questions/10664658/how-to-get-a-python-pyd-for-windows-from-c-c-source-code-update-brisk-now

Using a make file instead of bjam to build python .pyd’s (not useful if you follow the above link for VS):

http://jayrambhia.wordpress.com/2012/06/25/configuring-boostpython-and-hello-boost/

Resolve issues with .dll/.pyd files (missing dependencies and the such):

http://www.dependencywalker.com/

 

Pre-built boost libs and dlls:

http://sourceforge.net/projects/boost/files/boost-binaries/

 

I will do a full write-up on my reflection system coupled with boost.python soon, but for the time being here is a few tips when using boost.python and visual studio:

 

1. *.pyd and *.dll are equivalent. It’s safe for the most part to rename your output .dll into a .pyd. It appears to import fine.

2. If you have problems importing your .pyd from a python script, run dependency walker on it.  The answer for me was a missing .dll

3. You can ignore some of the windows dll’s that dependency walker reports, they are false positives from legacy windows systems.

4. bjam is not required to build the .pyd, regardless of what boost.org says.

Property Table – A simple delegation of list management/passing

Simple Overview
A property table is a simple abstracted data structure that I found to be quite useful in the Mocha Engine. It contains a table which maps generic POD datatypes (‘Properties’) to a list of generic object pointers (‘Elements’) that adhere to the specified property. ¬†The original and primary purpose of this structure is to delegate external-sub-system requests for list of objects to an ordered, managed container.

Pseudo-code for example manual usage:

Foo* a = new Foo();
Foo* b = new Foo();
PropertyTable<string, Foo*> table;
table.InsertManually(“Cat”, a);
table.InsertManually(“Dog”, a);
table.InsertManually(“Dog”, b);
const list<Foo*>* list1 = table.GetListFromProperty(“Dog”); ¬† //list1 contains a,b
const list<Foo*>* list2 = table.GetListFromProperty(“Cat”); ¬† ¬†//list2 contains a

Data structure looks as follows:

| Property | -> [ list of elements]
| Property | -> [ list of elements]
| Property | -> [ list of elements]

Or more pragmatically the underlying structure is simply:

template <typename PropertyType, typename ElementType>
map<PropertyType, list<ElementType>>

As a real world example, the Mocha Engine contains a property table in the game state class that maps component type names to game object lists.  Game objects that are added to the state automatically get added to the property table which enumerates the components that the game object contains and stores the game objects in the appropriate lists.  A client system such as the graphics renderer may then query the state requesting a list of every game object that contains the MeshRenderer component.  The lists are returned near O(1) due to the simplicity of the look-up (property -> hash of property -> list)

Previous solutions to the problem of passing lists to multiple sub systems was solved by allowing the system to directly access the full list of elements/objects, choosing for itself what to retrieve.  Besides violating encapsulation and exposing sensitive data to possibly irresponsible clients, this method is slow and time-consuming for system writers.  The property table allows the owner to manage it fully and set access rights for clients (think const reference to elements for certain sub-systems).   Compared to the naive approach, this container allows for quick-access, improved run-time efficiency, and type-safety at the cost of initialization/destruction time.

Raw properties of a property table:
– No duplicates within a list
– Duplicates allowed between lists
– Near O(1) for list return (hash table efficiency)
– O(nlgn) for insertion and deletion (just O(lgn) for non-safe mode, e.g. allow dupes at client discretion)
– No manual allocated data (transient only)

Possible Expansions:
– Self-regulating property table (verifies list on iteration)
– Return iterator to list instead of list pointer (client usability issue)
– Add solver function which, given an element, determines properties it adheres to (client implementation)

[C++] An Alternative to Generic Function Pointers

Problem:

I often find people asking how to make a generic function pointer, e.g. a pointer to any function regardless of signature and scope.
While something like…

//some generic function foo
void* fncPtr = &foo;
fncPtr();

…would be useful, it is not possible in ANSI C because of the way in which memory addresses are laid out across multiple scopes and schema.
A common use case for a truly generic function pointer would be in a¬†message queue¬†(also called an¬†action list, depending on your application). ¬†This is what I’d like to use as an example use case in this post to address the issue of function pointers.

Take for example the client call:

//push a new message into the message queue
messageQueue.push(Message(&foo));

The output that the client expects would be a message that will call the function¬†foo()¬†whenever it is processed. However, what is¬†foo? Is it¬†void foo(void)? Don’t you need a parameter to pass in so the call can be generic for all clients? So¬†void foo(void*)?
The biggest problem is what happens when the function you wish to call is nested:

struct Bar { void Foo(void*); };

void Bar::Foo(void*)¬†is a completely different signature than previously and will require another completely different function pointer signature to match. Now you’ve limited your callbacks to only one scope – which is no good. What if the client wants to have callbacks bound to their own objects?

Possible Solution:

There’s a number of ways to solve this, but this requires little readjusting to integrate into an existing code base.
Sample:

class Bar : public iMessageListener
{
public:
   virtual void OnReceiveMessage(void*);
}

Using multiple inheritance to your advantage, you can guarantee that all callback methods have the signature:

void iMessageListener::foo(void*);

Then, change your public interface for the message queue to accept a pointer to a iMessageListener along with the message data:

void Push(iMessageListener*, void* param);

This greatly simplifies the client front-end and has the nice side benefit of making processing a callback message as easy as:

msg->messageListener->OnReceiveMessage(msg->param);

Drawbacks: 

There’s a couple caveats with this solution:

  • Only one message callback function per object. Generally, if this is an issue, then you may consider breaking what is likely a god object into multiple sections. Reacting to different message types can become an issue, so you may wish to accompany the sent data param with a message type. See the section on expansions for a workaround for this.
  • All callbacks must be encapsulated. If your architecture features an abundance of singletons or other quasi-global structures you may find using raw function pointers much easier than this.

Expansion:

It is possible in this model to extend new versions of Listener objects that share the same base callback.
Two possible events to be sent to the same destination from different sources could look like this:

class DestinationObject : public iMessageFoo, iMessageBar

Where iMessageFoo and iMessageBar both extend from iMessageListener and implement new callbacks of different names but similiar signatures.