Multi-threading issues (it seems)
Closed this issue · 7 comments
Thanks for writing the library; the first results on Google definitely don't stand up to this lib. However I'll be using the QTree for fairly performance intensive, multi threaded stuff (why else would you use one?), and the stress testing I'm doing seems to be causing the code some trouble.
I'm using the integer rectangle quad tree, just in a test app for now. The issue would happen when moving or removing/inserting a set of data while also drawing the outputs on a timer.
I would sometimes get "We are not the root, and this object doesn't fit here. How did we get here?" , and also often got issues while in CleanThis(), where line 416 of QuadTreeNodeCommon.cs , where this assert would fail:
//Debug.Assert(beforeCount + child._objectCount == Count);
This seems to happen especially regularly when I have code which is moving many rectangles around within the tree, and then I delete one of the rectangles. This would cause a repeatable failure. (Code attached)
Now if I go into the code and ensure all the parallel algorithms and tasks are run synchronously (as the CPU usage is negligable, and the data-structure will pay for itself in quick lookups), things do seem to run more stably.
On an unrelated note it would be nice if the API exposed enough info to be able to render the quad tree for debugging; otherwise you really just have to hope that the tree balancing and distribution is working well.
Thanks again,
Kestas
QuadTreeTester.zip
Hi,
Your QuadTree has been corrupted. There is minimal checking in the interest in speed for this library. Assertions do most of the heavy lifting (although a few are commented out due to edge cases etc).
You must have an exclusive lock before any additions, updates or moves etc. A reader writer lock will suffice as read operations are safe.
Hmm. I did put a lock() around all my mutating operations I think, I think the problem was that the async tasks were delaying things until after the lock() expired, then things happened all at once and starts getting corrupted. For what I'm doing speed is definitely second to accuracy, and I'd rather know calls to the tree are blocking and handle threading elsewhere.
I think I'll make some tweaks to make it more suited to my needs in this regard (a multi-threaded test app, an always-block flag, some extra hooks to get more info); would you prefer a pull request with a multi-threaded test app and extra or a fork?
If you mean unit tests then yes feel free to pull request additional tests. An app utilising the library is probably better in a separate repository.
Okay I've put together a stress test app. It's not a unit test sort of thing since it's more about evaluating the library overall against different use cases, rather than testing individual paths.
I've noticed the following: (Note I'm testing against a synchronous version currently)
-
If nothing moves the query results are always accurate. However if I change a rectangle and then call Move() on it it seems to move it without affecting the query results. Before I take a look at the code any thoughts? (I wasn't 100% sure I was using Move() right, maybe I'm not..) What's especially odd is that sometimes it does seem to work fine.
-
The root quad is massive; if I have a dataset from x/y 0 to 1000 the root quad is -118xxxxxxx to 966xxxxxx. It doesn't seem to be having a performance impact. Is there any way to explicitly trigger the tree to grow/shrink to fit its dataset?
-
On a related note: If the tree grows out of its original size it doesn't seem to expand. Once enough items are cleared something happens and it suddenly seems to "get it" and capture everything. Any thoughts what this might be before I go digging?
-
(Again maybe related) The balancing functionality, where quad sizes can change to fit the data, is quite nice and I can see how it would improve performance, but if you have a long living tree that is quite dynamic I can see this causing issues with unbalancing where an initially optimal split becomes inoptimal. Was the intention to make this a tuneable functionality or do you think it'll be good for all use cases?
Otherwise the library seems very robust and performing great. Thanks for any help.
The root quad is nothing more than a bounds check optimization.
When we used this we did alot of inserts and removals. We did a full rebuild every X cycles. I did not find a faster way to optimise an unbalanced tree. The costs of detecting balance were high.
Okay thanks. A rebuild every so often wouldn't do for our use since if queries come back wrong it may mean missed interactions between objects.
If I do a Remove and Insert instead of Move it always gets it (or so it seems), so I'll just use that. There may be a delay before I come back to this and I think you've answered my issue so feel free to close.
closing