Horde3D

I've done some hacks to use my dual core inside of Horde3D.
Profiling revealed that SceneManager::updateNodes and SceneManager::updateQueuesRec are quite expensive and might benefit from parallelization.

Assumptions: Any node in the scene graph depends only on its parent and their parents etc. That means we can process the nodes in any order as long as parents are processed before their children.

Idea: Use a pool of worker threads to do updateQueuesRec / SceneNode::update in parallel.
I started with updateQueuesRec and tried to transform the scene graph into a linear structure - split according to depth level of the nodes. Generating this data every frame proved to be too expensive and data locality wast lost, so I used a simpler approach:
Processing only the children of the root node in parallel instead of a parallelism on every recursion level. Additional cost is scattering (very cheap) / gathering the data.

Goal: Speedup factor of at least 1.5 which would result in an overall benefit for Chicago of around 8% and should increase with larger scene graphs.

Results:

Chicago:
100 instances of man: -6% / -3FPS
500 instances of man: +10% / +1FPS
1000 instances of man: no measureable change
500 instances of sphere and no animation: no measureable change
2000 instances of sphere and no animation: +15% / +1FPS

Terrain:
no reproducible change

Knight:
nothing really reproducible, but it showed a tendency to be slower with threads.





- for small scene graphs there's a tendency to be slower
- huge dependency: boost::thread
- added complexity
- benefits for large scene graphs as long as "enough" nodes are direct children of the root node to allow equal load distribution. Otherwise fallback to old behavior
- better testcase is needed


If anyone is interested in the code I can cleanup it up and post a patch against community svn trunk.

I would be interested to see the code, if you don't mind - I might be able to offer suggestions to speed it up.

_________________
Tristam MacDonald - [swiftcoding]

Good job ! I can't wait no longer to see the source code. Perhaps we can gain better performance boosts on Quad cores and higher. It's great to have a benchmark on Quad core and old HTT enabled cpus too

So here's the code. Still a bit of a mess with local functions

In egScene.h is a new define which enables / disables threads. In egScene.cpp are two locations where a variable NUM_PARTS is defined. These must be tuned more carefully to get the best results. Too few and the last thread takes too long while the main thread waits, too many and the overhead gets to large.

You need boost 1.34 / 1.34.1

Just read through the code, looks like you did a very nice job. I don't think that scenes as small as the ones in the samples will benefit any from multi-threading though. If you build a scene with several hundred nodes, we might see an increase in performance.

_________________
Tristam MacDonald - [swiftcoding]

Nice work

I think this is important though:On a quad-core CPU with my engine, I use one thread to call Horde functions, and at the same time 3 other threads start updating all the game entities for the next frame - so I would actually prefer Horde to be single-threaded

If we choose to integrate this into the core I'd like to make this runtime configureable with an engine option which sets the number of worker threads. If you choose 0, you get the old behavior. If we additionally integrate some kind of profiler we could let the engine choose what's best depending on runtime statistics.

I had another think about it, and if threading is a long-term goal of Horde3D then it might fit with horde's philosophy to allow the user to create threads for it.
For example, we could allow the user to specify a call-back function that Horde can use internally when scheduling "threaded work"/"tasks". Then we can leave it up to the call-back function to take responsibility for creating threads and dividing "tasks" between them.



Then internally, when we have a "task" to do, we call the user's call-back function, or if they haven't set a call-back then fall back to a default.


Then we could write something like the following in the utility layer to provide a default multi-threaded implementation:

If there is a lot of work with multithreading, I'll be glad to help you Optimizing the utmath is near to end and some little bugs must be fixed [I think this takes ~1-3 weeks], after that I'm going to be a bit friendly with boost lib and learning their usage from their online manual [anybody knows any offline resources?].

tip : I think it's better to place the patched files too and this makes the integrating process a bit faster

BTW, it's better to share the work between community members and don't leave the optimizers alone

DarkAngel:
The idea to allow the user to create the threads is really good. That would avoid any unwanted dependencies like boost.
But I see a few problems:
We can implement a threadsafe queue with atomic operations but the pop operation would have to block if there is nothing to do. Implementing that blocking efficiently needs some OS support. The same is true for a waitUntilEmpy function - but here we could at least help processing the work.
Another tricky issue is signaling shutdown / g_Abort: the while(!g_Abort) could be optimized away. But some kind of memory barrier should help here, at least gcc provides primitives for that. No volatile tricks, please.

A way around this would be if the user not only creates the threads for us, but also a queue implementation with efficient waiting. But this again can be more complicated than it sounds: My current implementation supports having independent thread pools, so that fire and forget tasks don't interfere with other sections of the engine were we have to wait for the results.
I don't use this feature at the moment, but it could be useful later. I'll think about more about this.

Siavash:
Posting the real files instead of patches is suboptimal - what if someone changes the same files in svn? Just happened with the "no using in headers" patch. Maybe it's just to easy to generate these patches with git and keep them up to date...
Anyone can help. My proof of concept implementation needs some more testing, especially with large scenes to show if it's really useful. Before integrating it into the engine we should discuss some more possible designs and their respective dis-/advantages.

Thanks
A memory barrier isn't needed as the CPU's ordering of reads/writes from/to the abort flag are unimportant - we just need to stop the compiler from re-ordering or optimising away the flag.
Making that variable volatile should ensure that the compiler actually reads the value of the flag each iteration.
Unfortunately, newer versions of MSVC actually do insert memory barriers automatically when using volatile variables - as this isn't required in our case it's overkill, but hopefully not a performance-killer.
I don't like the idea of pop blocking - IMO it should just return false if there is nothing for it to pop. In my example, this would result in a tight loop, so you could write something like this to cause it to block:

In my engine, I wouldn't want it to ever block - if the queue becomes empty then I will immediately re-use the thread to perform other tasks.

As for the efficient pausing/signalling/blocking - we can probably 'borrow' some code from GLFW, which implements cross-platform pause/resume.
In the example that I gave, the queue is implemented in the utility library, which means the user doesn't have to use it if they don't want to - they're free to use their own implementation.
If the user has their own work-queuing system, they should be able to correctly schedule horde tasks by passing their own function to Horde3D::SetNewTaskCallback. For example, within your callback you could put the tasks into a high-priority queue so they don't end up waiting for F&F tasks.

The memory barrier is detected by the compiler and will restrict optimizations of the flag accordingly


Search for "volatile considered harmful" or something like that. It's explained fairly good in the Linux kernel docs what volatile is and what it's not. It's not intended do be used for thread synchronization / event signaling.


And I have looked for a small library with portable threads to use instead of boost...

Actually, is the util library already dependant on GLFW?
If so, I think it has threads too

[edit]


I found that linux document - it just seems to say that you should use their pre-written synchronisation primitives instead of trying to do it yourself with volatile.
There's still nothing wrong with using volatile, it's just linux has higher-level alternatives. Internally, these alternatives make use of volatile themselves.

In the case of a simple abort flag, we have simple requirements:
- the flag starts as false. It will be set to true once. It will not be set to false.
- many threads read the flag many times - these reads must not be optimised away.
- one thread will set the flag to true, one time.

In this case, race conditions are not a concern as they can't occur (only one writer) and even if they did (if there were two writers), the written value would be the same anyway.
So given the simple requirements we can get away with avoiding any kind of synchronisation primitive (barriers, spin locks, etc...) just as long as we ensure the compiler doesn't optimise the multiple reads (which is what volatile does).

Ok, then we'll use volatile.

The utils library does not depend on glfw, only the samples. Probably not ideal to change that, so lets default to disabled for the thread support for now.

probably a good idea to put a comment in there with my justification of why it's ok, otherwise other people might not trust it either

If we can't put thread-creation in the util library, then I'd be up for writing some a sample program for GLFW and one for Boost that show how to create the threads (perhaps license the sample code as BSD so people can use it directly with their own code?).