View Issue Details

IDProjectCategoryView StatusLast Update
0005954The Dark ModCodingpublic03.05.2022 05:54
Reporterstgatilov Assigned Tostgatilov  
PrioritynormalSeverityminorReproducibilityN/A
Status resolvedResolutionfixed 
Product VersionTDM 2.10 
Target VersionTDM 2.11Fixed in VersionTDM 2.11 
Summary0005954: Optimize idClip: broad-phase collision detection
DescriptionOn 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).

TagsNo tags attached.

Activities

stgatilov

stgatilov

03.05.2022 05:37

administrator   ~0014818

Last edited: 03.05.2022 05:54

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

Issue History

Date Modified Username Field Change
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