View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0005954||The Dark Mod||Coding||public||03.05.2022 05:34||03.05.2022 05:54|
|Product Version||TDM 2.10|
|Target Version||TDM 2.11||Fixed in Version||TDM 2.11|
|Summary||0005954: Optimize idClip: broad-phase collision detection|
|Description||On the first beta of Lucy's Quest, idClip::ClipModelsTouchingBounds takes about 5.8% time according to MSVC profiler (7.5% with all related methods).|
The main problems seems to be:
1) Fixed structure of spatial data structure (16 x 16 x 16) is obsolete for large maps like this.
2) List of clipmodels for a grid cell is stored in linked list, and traversing them is very slow (cache/TLB misses).
|Tags||No tags attached.|
Reimplemented spatial data structure in svn rev 9918.
Copying commit message below.
The old data structure was fixed BSP tree, which splits the world bounds into 16 x 16 x 16 cells,
with linked list of clipmodels attached to every cell (BSP leaf).
Non-adaptive space subdivision and linked lists caused ClipModelsTouching(Moving)Bounds run slow due to cache/TLB misses.
This new data structure idBoxOctree stores dynamic object/boxes of varying sizes.
It is an octree, with every node (not only leaves) containing a list of objects in it.
The tree is grown on demand: when a node gets more than 90 objects which are smaller than 25% of node box size, 8 sons are generated and small objects are pushed down to them.
This allows the structure to naturally adapt to the shape and density of the particular map.
The attached list of objects is stored as a linked list of 127-object chunks, which combines fast traversal of arrays and simple custom memory allocation.
On Lucy's Quest first beta, I see the following improvement in timings:
Fresh start (1 min):
9.62 -> 9.14 RunGameTic
1.16 -> 1.04 ProcessStimResponse
0.66 -> 0.63 ServiceEvents
Savegame load (5 min):
7.82 -> 7.52 RunGameTic
1.09 -> 0.96 ProcessStimResponse
0.64 -> 0.62 ServiceEvents
This map has a lot of AIs, each of them regularly sends visualStim to the others.
In order to send visualStim, idClip query is done on a pretty large box.
This stresses ClipModelsTouchingBounds function inside ProcessStimResponse.
Forum post: https://forums.thedarkmod.com/index.php?/topic/21389-growing-arrays-and-memory-allocation/&do=findComment&comment=473374
|03.05.2022 05:34||stgatilov||New Issue|
|03.05.2022 05:34||stgatilov||Status||new => assigned|
|03.05.2022 05:34||stgatilov||Assigned To||=> stgatilov|
|03.05.2022 05:37||stgatilov||Note Added: 0014818|
|03.05.2022 05:38||stgatilov||Status||assigned => resolved|
|03.05.2022 05:38||stgatilov||Resolution||open => fixed|
|03.05.2022 05:38||stgatilov||Fixed in Version||=> TDM 2.11|
|03.05.2022 05:54||stgatilov||Note Edited: 0014818|