Quadtree Thread Management

[ada-foss]

Currently, all thread management of the lidarquadtree in the program is regulated by a universal global_pointbucket_mutex object, which is held by any agent performing any operation with any pointbucket. To add clarity to the structure of the program, it would be better to consolidate the responsibility of managing quadtree threading into one place.

[ada-foss]

Make lidarquadtree Threadsafe

One option is to make lidarquadtree threadsafe. The pointbucket's getPoint method is not threadsafe, which is originally the cause for blocking while interacting with the quadtree in the original program. But I suspect there was a hidden bug, where another agent could modify the structure of the quadtree and segfault any agent working with the old structure in the meantime. (In practice, this never turned out to happen.)

The reason for PointBucket::getPoint method being not threadsafe is largely due to the call to PointBucket::cache, which happens when PointBucket doesn't have that point available and needs to fetch it from disk. Although, does that mean cache should lock a mutex, or should the whole pointbucket freeze up until the caller is totally done with it (more like is in practice now)? A rendering thread could potentially go on rendering a pointbucket while another thread modified that pointbucket, and would just display whatever's available whenever it gets around to it.

This seems desirable, but could bugs be introduced later from this approach? At a guess, I would say: if and only if some critical operation, to compute a correct result, depended on some assertion about the relation between some points, and another operation made a change to that relation somehow. Does this happen in LAG ever? Could this ever happen in future?

[ada-foss]

Further to the lidarquadtree thread safety idea: lidarquadtree would then require a mutex in each pointbucket (maybe) and an overall structural mutex (definitely). For serious optimisations, the structural mutex could be divided into sub-structures and such and such, but that's probably way more work than it's worth.

To express this in C++ most elegantly (not necessarily best), I would make a thin wrapper around vector<PointBucket*> if I can, and hide the maintenance from the user of the object. So, this wrapper would inherit from and otherwise behave exactly like a vector, but notify the associated lidarquadtree on creation and deletion, so that the lidarquadtree can track and control how many agents can hold rights to observe its structure, and abstain from changing the structure when doing so would cause problems.

• This also has the advantage of being able to express things about PointBuckets if necessary.

Dilemma: What exactly is the use of this if any agent needs to hold the structural mutex to do anything? This gets back to the global mutex approach, which works and means per-pointbucket mutexes can be done away with, but can hurt performance. Alternatively, the structural mutex could be substituted with a construct which allows concurrent reads but can guarantee exclusiveness for write-operations. However, how do you guarantee that write operations will get a chance to execute if read operations keep coming in constantly? The big example I can think of is the future-case where LAG displays points as and when it's loading: the program wont be able to afford continuous rendering if that blocks the already-slow loading process, especially if it requires hard-disk read operations.

[ada-foss]

The first option I can think of is just to prioritise events to the lidarquadtree in this way:
active read operations > future write operations > future read operations

There is a slight tradeoff here, as future read operations can happen concurrently with active read operations, but it would be complex to implement something which estimated whether a future read operation could end before an active read operation. The simplest policies are just "all one" or "all the other".

AND this still has the problem of stopping the loading process dead in its tracks if something like a frame were rendered.

[mloskot]

If the problem can be described as Associate Mutexes with Data to Prevent Races, it may be worth to take a look at Intel TBB / Microsoft PPL where concurrent_vector class is provided. It serves such purposes much better, than own old-fashion structure+mutex wrappers.

[ada-foss]

This is exactly the sort of thing I want to be doing. Right now, a lot of the code controlling and preventing race conditions just evolved over time as bugs came up and they were fixed, all I did was run through the code and replace sleep operations with propper threading constructs that were less likely to blow up if the operating had some kind of time-sharing hiccup.

At the moment I'm just looking to take all thread-management out of TwoDeeOverview.cpp and Profile.cpp with this approach, in the hope that it will fix issue 22, which I've been puzzling over since before I added it to the issue list over a week ago, and just maybe issue 25 aswell.

I'm going to take a long look at TBB before I do anything else, since I want to make sure I don't tread on my own toes if it turns out I want to change over to that and need to change lots of the old threading stuff (again). Thanks for the tip.

[mikeggrant-pml]

It may be better to try to avoid mutexes everywhere and instead use a reference counting approach. You could then know which buckets are in use and can't be messed with, and which are available for writing/uncaching. In conjunction with something a bit like autoptrs, the reference counting can be somewhat automatic (vs having to take mutexes all over the place).

[ada-foss]

It's hard to avoid mutexes everywhere, as I can't guarantee in modern processors whether even single arithmetic operations are atomic. I removed one from the final design I'll detail below, so the final count for what I'll have to add to each PointBucket to achieve a very concurrency-capable system is something like, per pointbucket: 1 mutex, 1 condition, 1 integer, 2 booleans. It might be possible to save memory with a PointBucketConcurrencyManager class or something, but it would be slower and take longer to implement, so I'll just go with the cost of system memory. If worst comes to worst, I can shuffle some things about when I work on issue #26

Okay, here's the plan I'm putting into action:

• lidarquadtree will have a new class CacheManager (replacing CacheMinder). It will be based off CacheMinder, so this is just a renaming to reflect the new responsibilities it will have.
• CacheManager will spawn an associated thread on creation, dedicated to managing the cache.
• When they need data, PointBuckets will submit requests to CacheManager and block, this will go into a queue which CacheManager receives items from, and will block when it is empty.
• When the CacheManager's caching policy decides to, it will tell a waiting bucket to perform a cache or uncache operation. The current cache and uncache operations will be renamed to perform_cache and perform_uncache, and the cache function will trigger this process, meaning nearly no code at all needs to change there.
• LQTReadVector and LQTWriteVector will be added, which are wraparounds for vector<PointBucket*>, these will manage reference counting in PointBuckets on creation and deletion, and block until the relevant permissions are available.
• PointBuckets will have functions for claiming and relinquishing read and read+write access, for use only by LQTReadVector and LQTWriteVector, and the quadtree itself when inserting points. These can fail, either on cancellation or deletion.
• PointBuckets start with their write access set, so nothing can read them until the quadtree says they're ready.
• PointBuckets that are deleted while a read or write vector is trying to claim permission on them has a boolean flag set to indicate this, the thread calling will then signal all threads waiting and block itself on the same condition is just signalled, the last thread out will then signal the remaining thread on the same signal. THIS SEEMS HACKISH TO ME AND I NEED TO CHECK WHETHER IT WILL WORK
• advsubset will then be overloaded to return either an LQTWriteVector or LQTReadVector (depending on what you're casting it into), so no PointBucket can ever be accessed without going through those types.
• PointBucket will store the number of LQTReadVectors it has, and a writing flag, which is set when LQTWriteVector is claiming access, and blocks any incoming read/read+write permission requests until the write operation is completed.
• The completion of any operation on the quadtree is signalled by the deletion of the respective LQTRead/WriteVector.

[ada-foss]

Change of plans:

• Instead of dealing with the problems that arise when a write thread deletes a PointBucket, priority will be given to read threads. Any write thread wishing to delete a PointBucket must perform the redirection in the QuadTree first (resulting in a floating PointBucket), wait for all operations to finish with the PointBucket, and then do whatever needs to be done. Write threads will passively wait in the background of every PointBucket, and only write when it appears that the coast is clear, but still block any read operation that comes in later.

Two questions..

• Could write threads be made to conditionally take or cede priority?
• Might a thread wishing to delete a PointBucket be able to miss any lingering threads still wishing to operate on it?

[mikeggrant-pml]

If you unhook a PointBucket from the tree, aren't you going to (potentially) end up with inconsistent data for subsequent readers? Or do you mean to keep a "no-reading lock" on all the replacement buckets until the delete is done?

Might it not be simpler to just have the delete and redirect operations wait until the necessary PBs can be secured, then do the operation? This avoids any risk of something accessing the tree while it's in a transistional state and keeps the code simpler.

[ada-foss]

Aha, that's a race condition covered by this point in the post before my last one:

• PointBuckets start with their write access set, so nothing can read them until the quadtree says they're ready.

So the idea is that new requests for that data will automatically find the new PointBuckets, but then block until the appropriate PointBuckets are ready.

For example, the Quadtree can decide that a newly created PointBucket is not ready until it has been populated with it's parents PointBuckets data. This can then happen by aquiring read permission on that pointbucket, which can happen concurrently with any other read operations while new requests go to the new pointbuckets, and only acquire write permissions (while data is now free to access and use the new pointbuckets) when it needs to delete the data at the end.

[mikeggrant-pml]

Good point :) Wouldn't the other way mean that readers could continue to operate while this method blocks further readers? Admittedly the other way means that the writer could be blocked a long time.

I also wonder which way would be simpler code / least surprising.

[ada-foss]

Yes, further readers would be blocked if they arrived, but I would like to be able to assert that they wont. Further readers examine the quadtree and go to the newly created PointBuckets, and block there instead. So we should be able to make the assertion that no new readers can arrive before the writer even thinks about deleting the PointBucket.

Saying that though brings to light yet another race condition: readers that get halfway through a pointbucket lookup, and before they can make themselves known, are unlucky enough to be suspended by the OS to let the writer thread run, which then is unlucky enough to get all of its own work done before it then goes and deletes the PointBucket that the reader thread had already decided it was going to read.

But then, that would require some really extreme thread starvation. I can only imagine it would be likely when the compiler just happens to arrange instructions in memory such that the reader causes the OS to suspend it while it's fetching instructions from RAM. The bug seems like it could be so rare that I wonder whether it's even worth worrying about, especially when the writer thread would be required to perform at least two hard disk write operations before it ever gets around to this. But then, the bug is still there, and may be impossible to figure out when this thread is dead and buried.

[ada-foss]

Final plan (really I mean it)

• Instead of mutexes and conditions, just use pthread's readwrite locks. They implement what's needed.
• Add a structural rwlock to the quadtree
• Threads wishing to acquire a readlock on a pointbucket must first acquire the readlock on the quadtree, and release it once they have the readlock on the pointbucket.
• The insert point procedure has been planned to give precedence to write operations, only because that's what pthread readwrite locks do.
• Write operations which change the structure of the quadtree have a series of hoops they need to jump through to make sure point lookup stays fast and efficient. I will document the design in more detail once it's in-place. By acquiring a write lock on the tree, the assertion can be made that all threads in all buckets have either left or acquired their respective locks.

To-do List

• Make quadtree lookups and insertions threadsafe and parallel
• Implement thread-based caching and uncaching
• Benchmark!