[quote name='Hodgman' timestamp='1328684518' post='4910803']
It doesn't matter how you transition a thread into a sleep state - once in that state, the kernel's scheduler won't come around and poke it back into a ready state until the next scheduling cycle, which defaultsto15ms on windows IIRC.

Hmmm.. I use Sleep(1) in my multicore support code, after reading more about this topic it seems, that you can utilize the timeBeginnPeriod/timeEndPeriod to increase the timer resolution. As far as I understand, this will affect the whole OS (OS will take the highest resolution). Therefore I would try to encapsulate the sleep like this:

timeBeginPeriod(1);
Sleep(1);
timeEndPeriod(1);

Is this a bad idea (too much overhead, slowing down the OS) ?
[/quote]

Even if you change the timer resolution you still won't have any guarantees that a thread will wake up on time, (If you also boost the thread priority so it is higher priority than everything else on the system then it most likely will wake up on time though), only call timeBeginPeriod once early in the application:

(from msdn.microsoft.com)
Use caution when calling timeBeginPeriod, as frequent calls can significantly affect the system clock, system power usage, and the scheduler. If you call timeBeginPeriod, call it one time early in the application and be sure to call the timeEndPeriod function at the very end of the application.[/quote]

timeBeginPeriod(1);
Sleep(1);
timeEndPeriod(1);
Is this a bad idea (too much overhead, slowing down the OS) ?

In my experience, it seems to be fairly common practice to call [font=courier new,courier,monospace]timeBeginPeriod[/font]/[font=courier new,courier,monospace]timeEndPeriod[/font] in your main function (i.e. applying the increased scheduling precision for the entire life of your program). N.B. you're also supposed to use [font=courier new,courier,monospace]timeGetDevCaps[/font] to find the system's minimum value, instead of using a hard-coded [font=courier new,courier,monospace]1[/font].
Also, despite the bad guarantees for how long a [font=courier new,courier,monospace]Sleep(1)[/font] will last on Windows, there aren't many other good options if you have to put a thread to sleep -- e.g. if you've got two threads sharing one core, you'll have to sleep them at some point (especially if their priorities are different - in which case one could be starved until it get's it's priority boost after 3-5 seconds of starvation).

But when it comes to processing more complex structures, like the entities in an Octree, I keep finding blocks where the code will end up becoming serialised regardless of threading

You're Doing It Wrong™

Instead of shoehorning parallelism into an already explicitly serial design (trees and linked lists in general are inherently serial data structures; there's no effective way to traverse them in parallel without the threads stepping on each other's toes. Before you ask, skip lists are cheating/hacky) ask yourself if there are any alternative approaches that would instead scale well in a more threaded environment. As DICE found out when building their visibility system for Battlefield 3, the 'dumb' approach can certainly end up a lot faster than clinging to a conventional 'smart' solution simply because that's the way it's been done previously. Data is, ultimately, king

I don't see a problem with traversing a tree in parallel. Updating it with new state is the issue of course. With "lock step" threading I can see how it would work. Jobs run, store their results, all results are applied to the tree at the end. I'd be sceptical about the resulting performance improvements of course. Anyway will check out the BF presentation later.

On the surface, yes, you're bang on the money. You can certainly have multiple threads be traversing the 'physical' tree in memory without incident. Actually doing work on it, however, is a bit murky. Consider the case of arrays for a moment. You can do a blanket segregation at the beginning, maybe partitioning the whole thing out into n chunks (where n is defined as being at or around the number of physical processor cores on the target machine for simplicity's sake) and then have all your threads go in guns blazing. If your computations are otherwise embarrassingly parallel or you're doing some super scheduling cleverness, you can actually get away with no additional synchronization; threads can just do computation without ever needing to interact with one another. You can actually handle array modifications in a similar way by trying to provide some upper bound on work that each thread would do, segregating output slots ahead of time, then having all threads write their (potentially variable-width) output within that set of bounds. You can then coalesce everything in later (possibly also parallel) passes over that data-- this is actually a fairly common approach (though not often directly seen) used in graphics and it actually has a name: stream compaction. There's quite a bit of research dedicated to doing this effectively and I'd suggest some Google-fu if it sounds interesting, as it's a very broad topic mostly outside the scope of discussion.

So, bringing that massive (bi)tangent back to heel, we're back with the idea of work distribution for arrays vs. trees. This is actually somewhat more subtle, but the speed advantage of trees for searching comes directly from their hierarchical skipping of regions based on previous sorting. Since we're in a hierarchy, we don't actually know what region(s) we need to search next until we run the current set of computations; this really, really kills the parallelism factor since it introduces hard synchronization points, and frequently. You can task multiple queries through the structure and see some speedup there, but it's still the same sort of 'bolted-on' concurrency dead end as things like a 'physics/render thread.' It helps in edge cases, but it's very likely those edge cases won't be a limiting factor or even present at all for most of your processing time. As an example, parallel view queries won't help you if you only have one camera, but parallel queries in of themselves will benefit one camera or 10,000 equally.