Threading question

With that type of design, you could use a semaphore for condition. When you add something to resource_queue you would increment the semaphore (usually called post or release, depending on the semaphore implementation) once for each item added, the loading thread would then block until at least one resource was waiting, and process one at a time.



The loading thread is processing resources serially, so you only pop one at a time and don't need a temp_queue. This also makes counting on the semaphore simpler and could let you have multiple loading threads processing the queue simultaneously.

Ah, that makes sense, I'll give it a shot. Thanks!

One more thing... I'm using boost for threading, and all I can find is boost::mutex. What is the name of boost's semaphore and critical section objects?

Boost's mutex is the equivalent of a Win32 "critical section". Unfortunately, Win32 chose to use the name 'mutex' for something else.

Boost threading doesn't have semaphores for some reason :(


Your original design should work with a bit of modification. condition.wait should actually be passed the lock - while it's waiting the lock is released (so the main thread can grab it, and update the condition variable), then once the worker-thread is resumed/notified, the lock is aquired again. Also, instead of just waiting on this condition, you can make a boolean variable that works alongside it.

[Edited by - Hodgman on July 29, 2010 7:03:04 PM]

I'd just like to call attention to the fact that Hodgman tests the requireLoading flag in a loop around the wait on the condition variable.

You need to do this rather than using a simple if-test because while waiting on a condition variable, it may wake spuriously.

Thanks for the responses... one more question.

If getData() is called before the data is loaded, I want the main thread to block until it is. Currently what I have is:

// while the data has not been loaded/generated...while (!generated) {	// if it is due to a loading error, return NULL	if (fail)		return NULL;	// process the generate queue, which must be called on the main thread	// this function is thread safe, so once data	// has been added to the queue, processGenUngenQueue()	// will generate the data and set generated to true (or failed)	resourceLoaderManager.processGenUngenQueue();}return fail ? NULL : &resData

Of course, the problem with this is that the main thread constantly checks, rather than waiting until some notification.

Is there some way to pause and automatically resume once resourceCondition starts waiting? So what would happen is that while the loading thread did its thing, the main thread would wait until the loading thread hit resourceCondition.wait(), and it would call the generate function then. Like if there was some form of join() which blocked until a condition was hit, rather than until the thread ended.

If you're dealing with low level primitives, the way to wait for something is almost always to use a condition variable (or a semaphore, but you can transform code using semaphores to code using condition variables and vice versa, personally I find condition variables much easier to reason about).

But if you're planning to use threads a lot, it's worth moving a step higher up the abstraction ladder so you don't necessarily have to worry about locks, flags, condition variables and so on. If you can restructure things in terms of tasks rather than threads, it will make life much easier (anecdotally speaking). A concept that might be useful for you in this situation is that of a future -- an object that represents a value that may not yet have materialized.

If this was me, I wouldn't have any given thread dedicated to a particular kind of job (unless it was needed because a particular API demanded it). So, rather than having a "loading thread", I'd have a system where I could submit "loading tasks" to a thread pool, processing queue, or whatever:

// pseudocodetask_pool tasks;for (f in files_to_load)    tasks.add(bind(load_resource, f))// submit the tasks for processingfuture<void> done = tasks.flush(thread_pool);// perhaps do some other stuff in the mean time// ...done.wait(); // wait for resources to load.

I'd like to give a more targeted response, but I'm not sure what this getData() function you speak of is supposed to do or how it fits in with the rest of the system, as this is the first time you've mentioned it.

I have read about thread pools, and they do seem like a good scalable approach, but since I'm just using multithreading for this one thing (loading resources... this is just a hobbyist project and I'm already pretty far in, next time I'll start with a multithreaded design), I'd rather just stick with this.

Basically, once resources are loaded, the resource's data can be accessed using the getData() method. There is also an isReady() method. What I'd like to happen is if the user wants to allow the data to load in the background while the game is running, they should check first using the isReady() method. However, in situations where the player has moved, say, to quickly and all the data has not yet loaded, getData() should block until the resource either loaded, or failed to load (again, there are probably better designs, but this is fine for me).

Quote:

Original post by Gumgo Basically, once resources are loaded, the resource's data can be accessed using the getData() method. There is also an isReady() method. What I'd like to happen is if the user wants to allow the data to load in the background while the game is running, they should check first using the isReady() method. However, in situations where the player has moved, say, to quickly and all the data has not yet loaded, getData() should block until the resource either loaded, or failed to load (again, there are probably better designs, but this is fine for me).

The easiest thing would probably be to use the future/promise stuff in boost.

EDIT: I should probably add a little more meat to this response.

I think the easiest thing to do would be to have an object that maintains your resource loading thread. It might look something like this:

class ResourceLoader : noncopyable{    public:        ResourceLoader(); // starts loading_thread        ~ResourceLoader(); // stops the thread        shared_future<Resource> load(const std::string &resourceIdentity);        // ...    private:        void thread_body();        Resource load_synchronously(const std::string &resourceIdentity);    private:        thread loading_thread;        mutex mtx;        condition cond;        ResourceQueue resource_queue;        bool destructor_wants_to_stop;};

Here, ResourceQueue is actually a queue of boost::packaged_tasks. The functor associated with each packaged task is created by something like boost::bind(&ResourceLoader::load_synchronously, this, resourceIdentity). The load() method would add such a packaged tasks to the queue and return a corresponding future.

The thread_body() method would be what the thread runs. It simply pulls packaged_tasks out of the queue and executes them.

You'll use the existing technique based on a condition variable to handle the queue synchronisation.

[Edited by - the_edd on July 31, 2010 6:51:53 PM]

Quote:

Original post by Gumgo getData() should block until the resource either loaded, or failed to load (again, there are probably better designs, but this is fine for me).

Blocking is crappy. Human brain can quickly accustom to any amount of latency (removing the latency results in simulator sindrome), but it gets hammered by jitter.

For smooth transitions, use proxy objects. Have a set of permanent proxies (texture, one bind-pose mesh for each distinct model). When starting to load a resource, start displaying it immediately using proxy resource. When it's loaded, blend, or even pop the real one.

Optionally, for meshes and such, displaying nothing is a better option than blocking, as long as invisible objects are loaded sufficiently in advance.

This approach also simplifies many things, since it avoids not_loaded special case. Consider dependencies - loading a model requires animation, mesh, textures, and perhaps even more. With above, you could get into staggered blocking. With proxies, each of those is rendered instantly, and then progressively refined. Model will be first in bind pose, then textures will be filled in, finally all the bumps, specular and other details.

It seems to be also the defacto technique for a very long time now.

Antheus: I guess that is a good point. If I let getData() return NULL if it is not loaded yet (there is a failed() function to explicitly check for that case too), I can manage each case correctly - if a texture hasn't loaded for example, no big deal, but if critical game data hasn't loaded, I can have a short "loading" pause until it does (because there isn't much alternative).

EDIT: Well, I've been working on this for hours, and it's not working.

void workerThreadMain() {	while (!done) {		std::queue <Request> tempQueue;		{			boost::unique_lock <boost::mutex> lock( workerMutex );			while (!requireLoading)				workerCondition.wait( lock );			requireLoading = false;			while (!workerQueue.empty()) {				tempQueue.push( workerQueue.back() );				workerQueue.pop();			}		}		while (!tempQueue.empty()) {			Request req = tempQueue.back();			tempQueue.pop();			// load request		}	}}void pushRequest( const Request & req ) {	{		boost::unique_lock <boost::mutex> lock( workerMutex );		workerQueue.push( req );		_WriteBarrier();		requireLoading = true;	}	workerCondition.notify_one();}

Sometimes it works, sometimes it doesn't. The same object seems to be pushed onto the queue when calling pushRequest multiple times for some reason! For example, if I call pushRequest twice in a row with two different objects (object1 and object2), tempQueue.push( workerQueue.back() ) reads object2 twice and does not read object1! My mutexes seem all correct... are there any obvious problems?

One thing (which I don't think is the problem, because if it's possible it seems like it would be very rare, but I'll mention it anyway)... Could this ever occur: workerCondition is waiting, and pushRequest is called from the main thread. BEFORE requireLoading is set to true, workerCondition spuriously wakes up and tests requireLoading. Finding it still false, it proceeds to call workerCondition.wait() again, but before it can, workerCondition.notify_one() is called from the main thread, and THEN workerCondition.wait() is called from the loading thread. In this case, workerCondition would not detect the notification, but there would be a resource on the queue, and the only way for it to be loaded would be either for another spurious wakeup or for another pushRequest call.

EDIT2: Nevermind about the first part... due to sheer stupidity, I managed to get queue.front() and queue.back() confused. It works fine now. However, I'm getting an error when join() is called (when I stop the thread, I first make sure everything in the queue is done, so I join the thread until it terminates). The error: R6010 - abort() has been called. I believe this is because I'm sending a message to the thread to terminate, then calling join(), but it seems that the resource loading thread is able to terminate before join() is called, and I guess calling join() on a thread that isn't executing causes a crash. What I need is a join_if_running() method.

[Edited by - Gumgo on August 1, 2010 6:32:14 AM]

First of all, waiting for something is almost always a very bad idea. So all these condition variables shouldn't be used in a realtime application. I know many people do it that way, and that's exactly why so many games with resource streaming out there have such a jerky behavior and occasionally long pauses. This is because the OS puts the thread asleep whenever there're no work for the thread to do. This can eat up millions of CPU cycles. And when a request arrives the OS needs to wake up the thread again which also takes millions of CPU cycles. You are wasting a lot of CPU power that way. In other words, using synchronization primitives provided by the OS is not advisable.

A better solution is to use a lock-free queue and to spin around until a resource is about to be loaded. This way the thread is always *hot* and never put asleep by the OS. Some code:


As a rule of thumb, never wait for anything. So it's also a bad idea to wait for a resource to be loaded. Instead just poll whether the resource is available. If so, then use that resource, otherwise use a fallback-path. For instance, the loading of textures could be done like this:


All default textures are loaded and cached at startup. The Unreal Engine 3 does it this way, for instance.

Quote:

Original post by Christian Weis A better solution is to use a lock-free queue and to spin around until a resource is about to be loaded. This way the thread is always *hot* and never put asleep by the OS.

Lock-free has the practical problem of not being readily available from some standard library.

The multi-buffered queue where buffers are flipped inside a regular mutex or critical section are somewhat cruder, but considering the flip occurs once per frame, it's not all that bad since contention is only possible around a pointer swap. Multi-buffered or even regular synchronized queue/vector isn't problematic either, since contention can occur only once per frame as well.

For large number of items non-threaded batch processing + synchronized swap likely outweighs the per-item poll which incurs the extra cost of volatile code and related memory impact.

Either way, the number of items for resource loader will be relatively small (one cannot realistically have millions of textures loaded during handful of frames, or at all), so either approach works. I just prefer to lean on readily available, preferably standard library functionality.

The high-level approach remains the same so implementations are interchangable and can be profiled at a later point.

Quote:

Original post by Antheus Lock-free has the practical problem of not being readily available from some standard library.

That's right. It's about time to add lock-free data structures to boost.

Quote:

Original post by Antheus Either way, the number of items for resource loader will be relatively small (one cannot realistically have millions of textures loaded during handful of frames, or at all), so either approach works.

It does matter when each mipmap is loaded individually rathen than the texture as a whole. And having some thousands of mipmaps per second loaded in a background-thread is common. It also depends on how fast the player can move and whether he can teleport himself around.

Quote:

Original post by Christian Weis It does matter when each mipmap is loaded individually rathen than the texture as a whole. And having some thousands of mipmaps per second loaded in a background-thread is common. It also depends on how fast the player can move and whether he can teleport himself around.

For large number of items batching is likely to be a better choice. The cost of critical section acquisition is comparable to interlocked operations, but in case of batching resource loader needs to do one acquire per item, the main thread however will only do one per frame to acquire entire batch. The probability of congestion is low, and operations within critical section are fast.

Added benefit of batching (in case of vector or similar) is that consumer can process results as a stream if needed.

Depending on implementation, lock-free operations also require spinning which may put pressure on CPU cache synchronization, especially if larger number of items is being constantly produced and consumed.

There is the other side, pushing requests. With batching, main thread can push all resources to be loaded in a single lock (swap of vectors), and resource thread consumes all in a single request. So the cost of requests is O(1) on both sides, the rest of the operations are completely thread-local.


There is also another higher level aspect. Multi-buffered data transfer can be combined with other systems, not just resource loading. It can include everything from input to event/command processing to inter-system messaging. In those cases being able to have threads work on completely thread local data set that is flipped once per frame/per tick simplifies passing large number of diverse messages between many threads.

Batched/multi-buffer updates do have potentially lower granularity, but this doesn't matter for anything that is tied to tick or rendering rate.

Quote:

Original post by Antheus For large number of items batching is likely to be a better choice. The cost of critical section acquisition is comparable to interlocked operations, but in case of batching resource loader needs to do one acquire per item, the main thread however will only do one per frame to acquire entire batch. The probability of congestion is low, and operations within critical section are fast.

Agreed! However, batching/multi-buffering does only work well in a 1-1 relationship, that is, single producer, single consumer. So the producer fills the first buffer with requests while the consumer processes the second buffer. They can act 100% simultaneous without any contention. And at the end of each frame you simply swap the buffers with a cheap InterlockExchange. In fact it's one of the most efficient approaches. I also use this whenever possible. Yet it assumes a 1-1 relationship.

What about n/m relations (multiple producer, multiple consumer)! Of course, with today quad-cores you can design the engine in such a way, so that you have 1-1 relations exclusively. You can work around it. Or you can simply fall back to critical sections. And yes, they're fast, especially on Windows where they are simple spin-locks basically. And spin-locks spin around in a loop as well, and you have exactly the same issues with cache coherence, cache line fighting as with lock-free structures. No win here.

I'm currently asking myself how processors might look like in the near future. And my personal guess is, that we'll have processors with dozens of cores able to run dozens of hardware threads. On such platforms it's very hard to avoid n/m relations between threads. And I think that in such a massive multithreaded world lock-free structures may supersede locks/multi-buffering.

By the way, you also missed one thing. Lock-free programming is hard and error-prone. Batching with multi-buffering is very simple and straightforward to implement and maintain. One more point for you ;)

However, I like lock-freedom for some reason, and it's an interesting alternative.

Quote:

Original post by Christian Weis What about n/m relations (multiple producer, multiple consumer)!

Scatter/gather or map/reduce. Each system has at least two buffers, one shared read-only, and one into which only a single thread writes at any given time. Topologically sort the systems, then only synchronization needed is when selecting a specific node from the graph - system updates and the bulk of computation occurs in isolation. This allows fine-grained scheduling across fixed number of workers.

The gotcha here is potential aliasing issues if one individual work unit is disproportionally large compared to others and blocks graph transition between levels. Intra-node update can be partitioned as well using parallel_for.

Second issue that can suffer from latency or aliasing issue is the render thread which needs to be scheduled on a specific/main thread. This may require main thread to be idle while waiting for full graph update.

If individual work units are guaranteed to be small compared to single frame rendering time, then main thread can act as worker as well, at the expense of potential added latency when rendering.

GPUs are asynchronous, data parallel and multi-buffered anyway, so why not just organize the rest of logic in same way.