SOH allocation issues

[Danil0v3s]

Rider keeps telling me that Small Object Heap allocation is high for the DtCrowd.Update method.

This is my usage

Where the Update method is called every 0.3...

On the pictures above the compiler is complaining about 200mb-ish, but I've seen it complaining about almost 800mb. Do you have any idea of what could it be?

[Danil0v3s]

[ikpil]

I'll check and mention you!!

[ikpil]

@Danil0v3s

Using stack memory introduces some potential risks that need careful consideration.
Could you please review the following changes and confirm their appropriateness?

before

            // Build sampling pattern aligned to desired velocity.
            float[] pat = new float[(DT_MAX_PATTERN_DIVS * DT_MAX_PATTERN_RINGS + 1) * 2];

after

            // Build sampling pattern aligned to desired velocity.
            int patSize = (DT_MAX_PATTERN_DIVS * DT_MAX_PATTERN_RINGS + 1) * 2;
            RcStackArray512<float> pat = RcStackArray512<float>.Empty;
            ThrowHelper.ThrowExceptionIfIndexOutOfRange(patSize - 1, pat.Length);

[Danil0v3s]

@Danil0v3s

Using stack memory introduces some potential risks that need careful consideration.

Could you please review the following changes and confirm their appropriateness?

before

            // Build sampling pattern aligned to desired velocity.

            float[] pat = new float[(DT_MAX_PATTERN_DIVS * DT_MAX_PATTERN_RINGS + 1) * 2];

after

            // Build sampling pattern aligned to desired velocity.

            int patSize = (DT_MAX_PATTERN_DIVS * DT_MAX_PATTERN_RINGS + 1) * 2;

            RcStackArray512<float> pat = RcStackArray512<float>.Empty;

            ThrowHelper.ThrowExceptionIfIndexOutOfRange(patSize - 1, pat.Length);

Hey, thanks for taking the time to look at the issue. The solution is a bit above my league so I can't really say anything. But if you wish to release a preview version I can see if the SOH warnings are gone

[ikpil]

I added RcRentedArray, which internally utilizes the functionality of ArrayPool. If everything seems fine with its features and usage, I will release it and mention you.

Thank you for reporting the issue.

    [Test]
    public void Test()
    {
        var rand = new RcRand();
        for (int loop = 0; loop < 1024; ++loop)
        {
            int length = (int)(rand.Next() * 2048);
            var values = RandomValues(length);
            using var array = RcRentedArray.RentDisposableArray<float>(length);

            for (int i = 0; i < array.Length; ++i)
            {
                array[i] = values[i];
            }

            for (int i = 0; i < array.Length; ++i)
            {
                Assert.That(array[i], Is.EqualTo(values[i]));
            }
            
            Assert.That(array[^1], Is.EqualTo(values[^1]));
            
            Assert.Throws<IndexOutOfRangeException>(() => array[-1] = 0);
            Assert.Throws<IndexOutOfRangeException>(() => array[array.Length + 1] = 0);
            Assert.Throws<IndexOutOfRangeException>(() => _ = array[-1]);
            Assert.Throws<IndexOutOfRangeException>(() => _ = array[array.Length + 1]);
        }
    }

[ikpil]

[ikpil]

next !!

[ikpil]

in DtNodePool.GetNode()

[ikpil]

in DtNavMesh.GetPolyHeight()

[ikpil]

in DtPathUtils.MergeCorridorStartMoved()

[ikpil]

in RcRentedArray()

[ikpil]

in DtNavMeshQuery.Raycast()

[ikpil]

new Vector3f[3] in DtNavMesh.GetPolyHeight()

[ikpil]

DtNodePool.GetNode()

[wrenge]

There are some caveats to consider for allocating on stack. The stack is limited and size may vary on different platforms. The best case is to use it when you know size beforehand and can use constant.
Second thing is you can only allocate unmanaged structures.
Last thing is if you want to allocate more than 1 kilobyte you'd probably want to use heap. Stack limit is 1mb but it may vary.

[wrenge]

Here's benchmarking result for .NET 8.0 Native AOT

ArrayPool<int>.Shared.Rent(len) 13,9643 ms
stackalloc int[len] 16,2544 ms         
RcRentedArray.Rent<int>(len) 26,9255 ms
new RcStackArray512<int>() 29,8794 ms  
new int[len] 36,882 ms

For some reason results on IL2CPP for stackalloc are significantly better than native AOT on desktop processor. I wonder why.

[wrenge]

Here's all allocations I've detected on each frame:

DotRecast.Detour.Crowd/DtCrowd.cs:553 (120B):
  :557 `new RcSortedQueue<DtCrowdAgent>((a1, a2) => a2.targetReplanTime.CompareTo(a1.targetReplanTime));`
  :560 `new List<long>();`

DotRecast.Detour.Crowd/DtCrowd.cs:849 (3.5KB):
  :853 `new DtProximityGrid(_config.maxAgentRadius * 3);`
  :860 `_grid.AddItem(ag, p.X - r, p.Z - r, p.X + r, p.Z + r);` (3.2KB):
    DtProximityGrid.cs:
    :77 `ids = new List<DtCrowdAgent>();`
    :68 `_items.Add(key, ids);` // Dictionary resize
    :81 `ids.Add(agent);` // List resize

DotRecast.Detour.Crowd/DtCrowd.cs:928 (3.6KB):
  :948 `ag.corridor.FindCorners(ref ag.corners, DtCrowdConst.DT_CROWDAGENT_MAX_CORNERS, _navQuery, _filters[ag.option.queryFilterType]);` (3.6KB)
    DtPathCorridor.cs:
    :165 `corners = corners.GetRange(start, end - start);`
    :137 `navquery.FindStraightPath(m_pos, m_target, m_path, ref corners, maxCorners, 0);` (3.0KB)
      DotRecast.Detour/DtNavMeshQuery.cs
      :1439 `straightPath.Add(new DtStraightPath(pos, flags, refs));` // List Resize

DotRecast.Detour.Crowd/DtCrowd.cs:892 (???KB):
  :897 `new DtCrowdAgent[MAX_NEIS];`
  :924 `(o1, o2) => o1.dist.CompareTo(o2.dist)` // Lambda allocation

DotRecast.Detour.Crowd/DtCrowd.cs:882 (4.9KB):
  DtLocalBoundary.cs
  :108 `new List<RcSegmentVert>();`
  :109 `new List<long>();`
  :113 `navquery.GetPolyWallSegments(m_polys[j], false, filter, ref segmentVerts, ref segmentRefs);` (1.0KB)
    DotRecast.Detour/DtNavMeshQuery.cs
    :3062 `new List<DtSegInterval>(16);`
    :3113 `segmentVerts.Add(seg);` // Possible list resize
    :3114 `segmentRefs.Add(neiRef);` // Possible list resize
    :3135 `segmentVerts.Add(seg);` // Possible list resize
    :3136 `segmentRefs.Add(ints[k].refs);` // Possible list resize
    :3149 `segmentVerts.Add(seg);` // Possible list resize
    :3150 `segmentRefs.Add(0L);` // Possible list resize
  :102 `navquery.FindLocalNeighbourhood(startRef, pos, collisionQueryRange, filter, ref m_polys, ref m_parents);`(3.8KB)
    DotRecast.Detour/DtNavMeshQuery.cs
    :2871 `new LinkedList<DtNode>();` // Better use Queue<T> or cyclic pool to avoid allocations and copy
    :2903 `m_tinyNodePool.GetNode(neighbourRef);` (2.9KB)
      DtNodePool.cs
      :87 `new List<DtNode>();`
      :88 `m_map.Add(id, nodes);` // Dictionary resize
      :98 `new DtNode(m_nodeCount);`
      :113 `nodes.Add(node);` // List resize
      
DotRecast.Detour.Crowd/DtPathCorridor.cs:312 (9.0KB)
  :315 `new List<long>();`
  :319 `DtPathUtils.MergeCorridorStartMoved(m_path, m_path.Count, m_maxPath, visited);` (1.6KB)
    :178 `new List<long>();`
    :185 `result.AddRange(path.GetRange(furthestPath, path.Count - furthestPath));` // GetRange and list resize
  :316 `navquery.MoveAlongSurface(m_path[0], m_pos, npos, filter, out var result, ref visited)` (7.1KB)
    DotRecast.Detour/DtNavMeshQuery.cs
    :1817 `stack.AddLast(startNode);`
    :1935 `stack.AddLast(neighbourNode);`
    :1862 `RcRentedArray.Rent<long>(MAX_NEIS);` // not an allocation but better use outside loop. stackalloc would be even better.
    :1958 `visited.Add(node.id);` // list resize
    :1816 `new LinkedList<DtNode>();` // better use Queue
    :1810 `m_tinyNodePool.GetNode(startRef);` // pool needs optimizing
    :1915 `m_tinyNodePool.GetNode(neis[k]);` // same

[ikpil]

wow! thank you!

[wrenge]

Tried to merge pr/fix-small-object-heap-issue into master in my fork. Here are results. Before and after:


I know the work is not done yet. Just wanted to check some progress.

[ikpil]

@wrenge
Thank you for letting me know. With the RcSpan issue resolved, I'm ready to proceed again

[ikpil]

It was released on 2024.2.1.
Will you check it out?

cc @wrenge @Danil0v3s