-
Notifications
You must be signed in to change notification settings - Fork 2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
The data structure problem with active objects #14613
Comments
I am currently working on a solution to this. The data structure I'm implementing is a dynamization of k-d-trees, meaning it would store O(log n) many k-d-trees with sizes of powers of two. This means:
Josiah and I tried optimizing this by using an off-the-shelf R-tree library a while ago. This failed due to bad constant factors for our medium-size workloads. It's also a bit overkill: It is centered around boxes. It would have made supporting higher variance in box dimensions easier. But currently we don't need that; we can just approximate the relatively small objects as points for now. I'm optimistic that with this new approach, I have a good chance of getting the constant factors low enough since there are plenty of knobs to tweak:
|
I've had an idea tossing around for a while now on the subject, it would need optimized but generally:Object ID vector of pointers (std vector) Std Vector of unused entries Std unordered map with three levels: Each level represents an Octree subdivision, With the bottom layer corresponding with the 16,16,16 mapblock boundary (to align with when entities need to be put to sleep or awoken). This bottom layer is two std::vector()s to hold unlimited entities, same on-erase mechanics as the main std vector list of objects. So, you have two lookup methods: by Octree bin (basically x,y,z) and by id in a vector. When insertions occur in the vector, they are mirrored in the unordered maps. When positions updates occur, just need to verify we haven't changed mapblock, if we have, erase our entry in that mapblock vector and insert into the new mapblock vector. So the tradeoff is position updates are more expensive. Finally, the main unordered map stores pointers, at least at the highest level, so as to keep RAM usage down. When I last looked at it, I think it was about 15 MB for the whole optimization stack at startup, with a couple kilobyte allocations when the first entities are inserted to mapblocks. Note: will be updating this comment as I do an actual design on the task - might be able to actually do this one. Update 1: Nice we already have an object manager class using a std::map structure with garbage collecting, so that takes care of my first vector manager. Wonder why we need to use maps? Like, couldn't the vector index be the object id? Update 2: The locations that for loop over all objects at ton during runtime are: In activeObejctManager.cpp
// Get vector sorted by distance around origin point within max distance
ActiveObjectMgr::getActiveObjects(const v3f &origin, f32 max_d, std::vector<DistanceSortedActiveObject> &dest)
// Raycasts
ActiveObjectMgr::getActiveSelectableObjects(const core::line3d<f32> &shootline)
// objects inside radius
ActiveObjectMgr::getObjectsInsideRadius(const v3f &pos, float radius, std::vector<ServerActiveObject *> &result, std::function<bool(ServerActiveObject *obj)> include_obj_cb)
// objects inside area
ActiveObjectMgr::getObjectsInArea(const aabb3f &box, std::vector<ServerActiveObject *> &result, std::function<bool(ServerActiveObject *obj)> include_obj_cb)
// Maintain Inactive/Active Objects
ActiveObjectMgr::getAddedActiveObjectsAroundPos(v3f player_pos, f32 radius, f32 player_radius, const std::set<u16> current_objects, std::vector<u16> &added_objects)
|
So I took a walk and here's my idea: It bases around the "one-off cache" approach I said wouldn't work but uses some tricks to make it workable. Keep the The gist of it is that objects exist in either When an object is inserted it is put into the The cache has to be (re-)created at some point. This should happen when the When an AABB query happens the spatial lookup performance: let's go through the checklist:
bonus:
caveats:
If you read closely you will notice that the requirements for the
It can be transparently replaced with any other — better — data structure. |
Thanks for addressing this problem. If we can help any further, please let me know - whatever readouts, logs, temporary code compiled into the engine ... For reference YL bugtracker 3723, 6325, 6326, 5289, administration 188 |
Sfan: Why is just Z-position enough to cache? Does that speed up any of our lookups by position by enough to matter? Also, why are position updates no cost? |
I think the most likely next step when someone has working code is for you to test the performance in a real situation.
It may not be, but see the last section.
After updating an object the cost is paid during every following spatial query, that's the |
Oh, that makes perfect sense. Okay yeah I can see a way to get my idea to fit in your world relatively painlessly. Just take the int16(x) >> 4 | int16(y) >> 4 | int16(z) >> 4. That will put all entities into mapblock sized bins and easily fit in 64 bits. Should still yield nice speedups for objects in radius, raycast, and whatnot, just gotta make the algorithms for those lookups. Could be as simple as running the same algorithms at 16x16x16 size first and iterate over those relevant bins instead of the whole active object list like we currently do. Bin size should be played with, obviously. Because 1x1x1 bins wouldn't yield much value I suspect. |
i tried to take a stab at a better data structure for this. the result, in lua, is here https://github.com/fluxionary/minetest-futil/blob/main/data_structures/point_search_tree.lua. the biggest issue with it is that it can't be re-balanced when new points are added or removed. i found a paper about that but never got around to implementing it https://arxiv.org/abs/1410.5420 |
I also have a Lua implementation of k-d-trees. I think trying to rebalance k-d-trees is a dead end. I tried for a while, it doesn't seem to really be feasible to me. But it is possible to build an efficient dynamic data structure out of a forest of static k-d-trees (see "transforming static data structures to dynamic structures"), which is what I'm suggesting here and currently implementing. I can't tell whether this will hold up in real world usage, but implementing and testing it is the only way to find out. I'm optimistic that we can get decent constant factors because there are plenty of knobs to tweak. |
Thought through sfan's idea more (worked on it). There's also a remove (when object is no longer active) that is also |
Alright, I've got a seemingly working (according to a quick randomized test against a naive implementation) dynamic forest of k-d-trees data structure whipped up, feel free to take a peek at my branch. The big O for this should be good (though not quite as good as what I advertised initially; for example deletion is amortized O(log(n)²) rather than O(log n) with this implementation), what remains to be seen is how it holds up in practice (potentially after some optimization), and integration into the active object manager, which I may get to on the weekend. |
Will take a look, sfans idea was short enough that I just jumped right into server::active object mgr integration, the only not straight forward thing is how to signal object position updates. In mine I just check if last position is different from the new position after step(). I will probably not write tests for your structure directly, as MT is a much better stress test of complexity than I can imagine haha, but I can at least look for obvious things. Not quite done with my version, but perhaps ready for integration tests against servers/mods by end of week. |
Some feedback / thoughts:
|
DS:
You can't see here, but I've made a lot of progress on the hash map
solution for us. I'm only focusing on server side right now, so selection
boxes aren't a consideration. That said, everything in Minetest must have a
position within 2^16 of 0,0,0 which helps tremendously, allowing me to pack
everything into buckets of size 16x16x16 nodes. We can revisit later if we
want to make this changeable as a setting.
As for big objects, they just have a plain old single origin position,
that's all that's needed right now.
My single unordered multi map, is a single layer Octree, and with 10,000
mostly evenly spaced out entities (current benchmark), it's quite
performant, haha.
I agree this is a super dead simple solution and gets us good performance
compared to what we have (by far). Will post a PR hopefully by end of day.
Performance of the map can absolutely be optimized later, it's just very
flexible of a solution.
|
Alrighty, there's my current merge^^^ Here's the performance results: Summary for the lazy:
|
There's a closely related older issue (#6453) but I felt like a fresh start here was better.
Problem
tl;dr: optimizing anything else server-side is basically a waste until this is solved, skip to the next section.
The nice people from the Your Land server sent me several profiling traces of their production server and a common theme is that about 40% of time (on the server thread) is spent just iterating the entity list (average, not peak!).
Now their mods use
get_objects_inside_radius
a bunch, but this is not a sole cause and I expect any sizeable server will be plagued with this exact issue.The issue are spatial queries on the entity list, which happen more often than one might think:
get_objects_inside_radius
,get_objects_in_area
ServerEnvironment::getAddedActiveObjects
All of these are
O(n)
with n being the number of entities. When you consider that every entity does collision detection this becomesO(n²)
right in the main thread.Solution requirements
What we need is a new data structure.
It must:
getObjectsInArea
) on the entity positionexternal circumstances:
getObjectsInsideRadius
) can be emulated on top of AABB queries and are not an important pointFinally we will also need to figure out how to reliably propagate position updates up to the container.
There are many ideas in the form of "just add a cache to <thing>" that come to mind, but keeping it in sync is generally the trickier part than designing the structure.
Real-world example data
(thanks to @Bastrabun)
There are 4500 entities. About 1400 move often, 3100 are static.
The text was updated successfully, but these errors were encountered: