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()

[ikpil]

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

cc @wrenge @Danil0v3s

[Sarofc]

Test with ba68157

It is better to keep the GC pause time within 0.5ms.

[ikpil]

It is better to keep the GC pause time within 0.5ms.

Thank you for the insight, I'll check it out!

[wrenge]

Hello! I'm back with some news.
Things has changed since last time I've updated. There's some progress.
Top allocations before:

RcVec3f[]
RcRentedArray<Single>
DtNode[]
List<DtNode>
List<DtMeshTile>
DtMeshTile[]
DtCrowdAgent[]

Top allocations after after:

DtPoly[]
DtMeshTile[]
DtNode[]
List<DtNode[]

However there are some methods I would like to be more optimized than it is now. Specifically DtNavMeshQuery class. I will try to fix some issues. The ultimate goal is to make it zero alloc.

[ikpil]

@wrenge What do you think about actually using RcRentedArray.Rent? When I tested it, I was able to reduce the creation of new memory, but I didn’t see any significant speed improvement, so I haven’t applied it.

[wrenge]

@wrenge What do you think about actually using RcRentedArray.Rent? When I tested it, I was able to reduce the creation of new memory, but I didn’t see any significant speed improvement, so I haven’t applied it.

Depends on runtime. In CoreClr gc moves objects in memory and defragments it. So allocation itself is pretty fast since its always on top of the heap. However when it comes to garbage collection itself, the performance hit can be significant. It also depends on gc implementation. Server one collects garbage rarely. But it does a lot. The memory consumption is higher. Client one collects much more often, but memory consumption is lower.
Whatever the implementation is, it will always block all the execution.

In unity and mono (correct if I'm wrong) gc doesn't move objects. So allocation is slower.

The reason why I started to care about memory consumption is because my dedicated server was generating so much garbage, the runtime runs out of memory and forces gc.

[wrenge]

In #85 I tried to fix most of concering places.

[ikpil]

@wrenge Thank you. I will review the code you contributed whenever I have time and apply it to DotRecast while mentioning you. I apologize for the delayed responses as I am not a full-time open-source developer.

[ikpil]

@wrenge

Hello,

We are currently analyzing the contributions you made and applying them to the project.

While working on the implementation, there are some parts we do not fully understand, so I would like to ask a question.
Could you please explain why "RentIdGen" and "RentIdPool" are necessary?

[wrenge]

@wrenge

Hello,

We are currently analyzing the contributions you made and applying them to the project.

While working on the implementation, there are some parts we do not fully understand, so I would like to ask a question. Could you please explain why "RentIdGen" and "RentIdPool" are necessary?

Hello!

Since RcRentedArray is a struct now, that means passing it into a function or field means making a copy. If you dispose it the old way, the other copies of struct won't be able to know the array is returned and not valid.
To deal with that each copy now has a RentId - identifier of rent and RentIdGen - the generation of specific rent. When struct is disposed and array is returned to the pool, RentIdGen of this specific RentId will be incremented. That means the combination of that RentId and RentGen is no longed valid. All of the instances of RcRentedArray will be able to know that.

All of this is not neccessary if you rent and return array in the same place. Like using using var semantic. There was a test checking for this behaviour so I wrote this implementation.

[wrenge]

It is a similiar principle used in many ECS frameworks to determine if entity is alive or not.

[ikpil]

Thank you for letting me know that I designed it incorrectly.
My original intention was for RcRentedArray to exist only on the stack.

Therefore, I will check if it can be changed to "readonly ref struct RcRentedArray"!

[ikpil]

commit: 156e0f4

BenchmarkDotNet v0.14.0, Windows 11 (10.0.26100.2605)
AMD Ryzen 5 3600, 1 CPU, 12 logical and 6 physical cores
.NET SDK 9.0.100
[Host] : .NET 9.0.0 (9.0.24.52809), X64 RyuJIT AVX2
DefaultJob : .NET 9.0.0 (9.0.24.52809), X64 RyuJIT AVX2

Method	HashTableSize	Mean	Error	StdDev	Median	Gen0	Allocated
New	16	5.842 ns	0.0500 ns	0.0443 ns	5.849 ns	0.0182	152 B
Stackalloc	16	4.142 ns	0.0831 ns	0.0777 ns	4.112 ns	-	-
Rent	16	16.409 ns	0.0244 ns	0.0204 ns	16.399 ns	-	-
New	256	50.550 ns	1.0255 ns	2.8245 ns	49.036 ns	0.2477	2072 B
Stackalloc	256	65.315 ns	0.2746 ns	0.2293 ns	65.259 ns	-	-
Rent	256	39.722 ns	0.0638 ns	0.0597 ns	39.734 ns	-	-
New	1024	285.897 ns	22.9065 ns	67.5402 ns	303.147 ns	0.9813	8216 B
Stackalloc	1024	261.509 ns	0.3847 ns	0.3410 ns	261.528 ns	-	-
Rent	1024	87.780 ns	0.1627 ns	0.1359 ns	87.752 ns	-	-
New	8192	1,156.367 ns	9.6633 ns	9.0390 ns	1,156.284 ns	7.8125	65560 B
Stackalloc	8192	2,134.754 ns	5.4929 ns	4.8693 ns	2,134.541 ns	-	-
Rent	8192	582.443 ns	1.0532 ns	0.9336 ns	582.631 ns	-	-