benchmark arrays

src/DotRecast.Core/Buffers/RcRentedArray.cs

@@ -6,7 +6,7 @@ namespace DotRecast.Core.Buffers
 {
     public static class RcRentedArray
     {
-        public static RcRentedArray<T> RentDisposableArray<T>(int minimumLength)
+        public static RcRentedArray<T> Rent<T>(int minimumLength)
         {
             var array = ArrayPool<T>.Shared.Rent(minimumLength);
             return new RcRentedArray<T>(ArrayPool<T>.Shared, array, minimumLength);
@@ -17,44 +17,41 @@ namespace DotRecast.Core.Buffers
     {
         private ArrayPool<T> _owner;
         private T[] _array;
-        private readonly RcAtomicInteger _disposed;
 
         public int Length { get; }
+        public bool IsDisposed => null == _owner || null == _array;
 
         internal RcRentedArray(ArrayPool<T> owner, T[] array, int length)
         {
             _owner = owner;
             _array = array;
             Length = length;
-            _disposed = new RcAtomicInteger(0);
         }
 
-        public T this[int index]
+        public ref T this[int index]
         {
             [MethodImpl(MethodImplOptions.AggressiveInlining)]
             get
             {
                 RcThrowHelper.ThrowExceptionIfIndexOutOfRange(index, Length);
-                return _array[index];
+                return ref _array[index];
+            }
         }
 
-            [MethodImpl(MethodImplOptions.AggressiveInlining)]
-            set
+        public T[] AsArray()
         {
-                RcThrowHelper.ThrowExceptionIfIndexOutOfRange(index, Length);
-                _array[index] = value;
-            }
+            return _array;
         }
 
 
         public void Dispose()
         {
-            if (1 != _disposed.IncrementAndGet())
-                return;
-
-            _owner?.Return(_array, true);
-            _array = null;
+            if (null != _owner && null != _array)
+            {
+                _owner.Return(_array, true);
                 _owner = null;
+                _array = null;
+            }
         }
     }
 }

src/DotRecast.Detour.Crowd/DtPathCorridor.cs

@@ -20,7 +20,6 @@ freely, subject to the following restrictions:
 
 using System;
 using System.Collections.Generic;
-using System.Linq;
 using DotRecast.Core;
 using DotRecast.Core.Numerics;
 
@@ -317,7 +316,7 @@ namespace DotRecast.Detour.Crowd
             var status = navquery.MoveAlongSurface(m_path[0], m_pos, npos, filter, out var result, ref visited);
             if (status.Succeeded())
             {
-                DtPathUtils.MergeCorridorStartMoved(m_path, m_path.Count, m_maxPath, visited);
+                m_path = DtPathUtils.MergeCorridorStartMoved(m_path, m_path.Count, m_maxPath, visited);
 
                 // Adjust the position to stay on top of the navmesh.
                 m_pos = result;

src/DotRecast.Detour/DtPathUtils.cs

@@ -20,7 +20,6 @@ freely, subject to the following restrictions:
 
 using System;
 using System.Collections.Generic;
-using System.Linq;
 using DotRecast.Core.Numerics;
 
 namespace DotRecast.Detour
@@ -142,13 +141,13 @@ namespace DotRecast.Detour
             return path;
         }
 
-        public static int MergeCorridorStartMoved(List<long> path, int npath, int maxPath, List<long> visited)
+        public static List<long> MergeCorridorStartMoved(List<long> path, int npath, int maxPath, List<long> visited)
         {
             int furthestPath = -1;
             int furthestVisited = -1;
 
             // Find furthest common polygon.
-            for (int i = npath - 1; i >= 0; --i)
+            for (int i = path.Count - 1; i >= 0; --i)
             {
                 bool found = false;
                 for (int j = visited.Count - 1; j >= 0; --j)
@@ -170,37 +169,21 @@ namespace DotRecast.Detour
             // If no intersection found just return current path.
             if (furthestPath == -1 || furthestVisited == -1)
             {
-                return npath;
+                return path;
             }
 
             // Concatenate paths.
 
             // Adjust beginning of the buffer to include the visited.
-            int req = visited.Count - furthestVisited;
-            int orig = Math.Min(furthestPath + 1, npath);
-            int size = Math.Max(0, npath - orig);
-            if (req + size > maxPath)
-                size = maxPath - req;
-
-            if (size > 0)
-            {
-                //memmove(path + req, path + orig, size * sizeof(dtPolyRef));
-                for (int i = 0; i < size; ++i)
-                {
-                    if (path.Count <= req + i)
-                        path.Add(0);
-                    
-                    path[req + i] = path[orig + i];
-                }
-            }
-
+            List<long> result = new List<long>();
             // Store visited
-            for (int i = 0, n = Math.Min(req, maxPath); i < n; ++i)
+            for (int i = visited.Count - 1; i > furthestVisited; --i)
             {
-                path[i] = visited[(visited.Count - 1) - i];
+                result.Add(visited[i]);
             }
 
-            return req + size;
+            result.AddRange(path.GetRange(furthestPath, path.Count - furthestPath));
+            return result;
         }
 
         public static List<long> MergeCorridorEndMoved(List<long> path, int npath, int maxPath, List<long> visited)

src/DotRecast.Recast.Toolset/Tools/RcTestNavMeshTool.cs

@@ -1,6 +1,5 @@
 using System;
 using System.Collections.Generic;
-using System.Linq;
 using DotRecast.Core;
 using DotRecast.Core.Numerics;
 using DotRecast.Detour;
@@ -93,7 +92,7 @@ namespace DotRecast.Recast.Toolset.Tools
 
                 iterPos = result;
 
-                DtPathUtils.MergeCorridorStartMoved(pathIterPolys, pathIterPolys.Count, MAX_POLYS, visited);
+                pathIterPolys = DtPathUtils.MergeCorridorStartMoved(pathIterPolys, pathIterPolys.Count, MAX_POLYS, visited);
                 pathIterPolys = DtPathUtils.FixupShortcuts(pathIterPolys, navQuery);
 
                 var status = navQuery.GetPolyHeight(pathIterPolys[0], result, out var h);

test/DotRecast.Core.Test/RcArrayBenchmarkTests.cs

@@ -0,0 +1,101 @@
+using System;
+using System.Buffers;
+using System.Collections.Generic;
+using DotRecast.Core.Buffers;
+using DotRecast.Core.Collections;
+using NUnit.Framework;
+
+namespace DotRecast.Core.Test;
+
+public class RcArrayBenchmarkTests
+{
+    private const int StepLength = 512;
+    private const int RandomLoop = 1000;
+    private readonly RcRand _rand = new RcRand();
+
+    private (string title, long ticks) Bench(string title, Action<int> source)
+    {
+        var begin = RcFrequency.Ticks;
+        for (int step = StepLength; step > 0; --step)
+        {
+            for (int i = 0; i < RandomLoop; ++i)
+            {
+                source.Invoke(step);
+            }
+        }
+
+        var end = RcFrequency.Ticks - begin;
+        return (title, end);
+    }
+
+
+    private void RoundForArray(int len)
+    {
+        var array = new int[len];
+        for (int ii = 0; ii < len; ++ii)
+        {
+            array[ii] = _rand.NextInt32();
+        }
+    }
+
+
+    private void RoundForPureRentArray(int len)
+    {
+        var array = ArrayPool<int>.Shared.Rent(len);
+        for (int ii = 0; ii < array.Length; ++ii)
+        {
+            array[ii] = _rand.NextInt32();
+        }
+
+        ArrayPool<int>.Shared.Return(array);
+    }
+
+
+    private void RoundForRcRentedArray(int len)
+    {
+        using var rentedArray = RcRentedArray.Rent<int>(len);
+        var array = rentedArray.AsArray();
+        for (int i = 0; i < rentedArray.Length; ++i)
+        {
+            array[i] = _rand.NextInt32();
+        }
+    }
+
+
+    private void RoundForRcStackArray(int len)
+    {
+        var array = new RcStackArray512<int>();
+        for (int ii = 0; ii < len; ++ii)
+        {
+            array[ii] = _rand.NextInt32();
+        }
+    }
+
+    private void RoundForStackalloc(int len)
+    {
+        Span<int> array = stackalloc int[len];
+        for (int ii = 0; ii < len; ++ii)
+        {
+            array[ii] = _rand.NextInt32();
+        }
+    }
+
+
+    [Test]
+    public void TestBenchmarkArrays()
+    {
+        var list = new List<(string title, long ticks)>();
+        list.Add(Bench("new int[len]", RoundForArray));
+        list.Add(Bench("ArrayPool<int>.Shared.Rent(len)", RoundForPureRentArray));
+        list.Add(Bench("RcRentedArray.Rent<int>(len)", RoundForRcRentedArray));
+        list.Add(Bench("new RcStackArray512<int>()", RoundForRcStackArray));
+        list.Add(Bench("stackalloc int[len]", RoundForStackalloc));
+
+        list.Sort((x, y) => x.ticks.CompareTo(y.ticks));
+
+        foreach (var t in list)
+        {
+            Console.WriteLine($"{t.title} {t.ticks / (double)TimeSpan.TicksPerMillisecond} ms");
+        }
+    }
+}

test/DotRecast.Core.Test/RcRentedArrayTest.cs

@@ -31,7 +31,7 @@ public class RcRentedArrayTest
             {
                 int length = Math.Max(2, (int)(rand.Next() * 2048));
                 var values = RandomValues(length);
-                using var array = RcRentedArray.RentDisposableArray<int>(length);
+                using var array = RcRentedArray.Rent<int>(length);
 
                 for (int i = 0; i < array.Length; ++i)
                 {

test/DotRecast.Detour.Crowd.Test/DtPathCorridorTest.cs

@@ -1,228 +0,0 @@
-/*
-recast4j copyright (c) 2021 Piotr Piastucki piotr@jtilia.org
-DotRecast Copyright (c) 2023 Choi Ikpil ikpil@naver.com
-
-This software is provided 'as-is', without any express or implied
-warranty.  In no event will the authors be held liable for any damages
-arising from the use of this software.
-Permission is granted to anyone to use this software for any purpose,
-including commercial applications, and to alter it and redistribute it
-freely, subject to the following restrictions:
-1. The origin of this software must not be misrepresented; you must not
- claim that you wrote the original software. If you use this software
- in a product, an acknowledgment in the product documentation would be
- appreciated but is not required.
-2. Altered source versions must be plainly marked as such, and must not be
- misrepresented as being the original software.
-3. This notice may not be removed or altered from any source distribution.
-*/
-
-using System.Collections.Generic;
-using DotRecast.Core.Numerics;
-using Moq;
-using NUnit.Framework;
-
-namespace DotRecast.Detour.Crowd.Test;
-
-public class DtPathCorridorTest
-{
-    private DtPathCorridor corridor;
-    private IDtQueryFilter filter;
-
-    [SetUp]
-    public void SetUp()
-    {
-        corridor = new DtPathCorridor();
-        corridor.Init(DtCrowdConst.MAX_PATH_RESULT);
-        corridor.Reset(0, new RcVec3f(10, 20, 30));
-
-        filter = new DtQueryDefaultFilter();
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldHandleEmptyInput()
-    {
-        var path = new List<long>();
-        const int npath = 0;
-        const int maxPath = 0;
-        var visited = new List<long>();
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(0));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldHandleEmptyVisited()
-    {
-        var path = new List<long> { 1 };
-        const int npath = 1;
-        const int maxPath = 1;
-
-        var visited = new List<long>();
-
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(1));
-
-        var expectedPath = new List<long> { 1 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldHandleEmptyPath()
-    {
-        var path = new List<long>();
-        const int npath = 0;
-        const int maxPath = 0;
-
-        var visited = new List<long> { 1 };
-
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(0));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldStripVisitedPointsFromPathExceptLast()
-    {
-        var path = new List<long> { 1, 2 };
-        const int npath = 2;
-        const int maxPath = 2;
-
-        var visited = new List<long> { 1, 2 };
-
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(1));
-
-        var expectedPath = new List<long> { 2, 2 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldAddVisitedPointsNotPresentInPathInReverseOrder()
-    {
-        var path = new List<long> { 1, 2, 0 };
-        const int npath = 2;
-        const int maxPath = 3;
-        var visited = new List<long> { 1, 2, 3, 4 };
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(3));
-
-        var expectedPath = new List<long> { 4, 3, 2 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldAddVisitedPointsNotPresentInPathUpToThePathCapacity()
-    {
-        var path = new List<long>() { 1, 2, 0 };
-        const int npath = 2;
-        const int maxPath = 3;
-        var visited = new List<long>() { 1, 2, 3, 4, 5 };
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(3));
-
-        var expectedPath = new List<long> { 5, 4, 3 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldNotChangePathIfThereIsNoIntersectionWithVisited()
-    {
-        var path = new List<long>() { 1, 2 };
-        const int npath = 2;
-        const int maxPath = 2;
-        var visited = new List<long>() { 3, 4 };
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(2));
-
-        var expectedPath = new List<long> { 1, 2 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldSaveUnvisitedPathPoints()
-    {
-        var path = new List<long>() { 1, 2, 0 };
-        const int npath = 2;
-        const int maxPath = 3;
-        var visited = new List<long>() { 1, 3 };
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(3));
-
-        var expectedPath = new List<long> { 3, 1, 2 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test(Description = "dtMergeCorridorStartMoved")]
-    public void ShouldSaveUnvisitedPathPointsUpToThePathCapacity()
-    {
-        var path = new List<long>() { 1, 2 };
-        const int npath = 2;
-        const int maxPath = 2;
-        var visited = new List<long>() { 1, 3 };
-        var result = DtPathUtils.MergeCorridorStartMoved(path, npath, maxPath, visited);
-        Assert.That(result, Is.EqualTo(2));
-
-        var expectedPath = new List<long> { 3, 1 };
-        Assert.That(path, Is.EqualTo(expectedPath));
-    }
-
-    [Test]
-    public void ShouldKeepOriginalPathInFindCornersWhenNothingCanBePruned()
-    {
-        List<DtStraightPath> straightPath = new();
-        straightPath.Add(new DtStraightPath(new RcVec3f(11, 20, 30.00001f), 0, 0));
-        straightPath.Add(new DtStraightPath(new RcVec3f(12, 20, 30.00002f), 0, 0));
-        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), 0, 0));
-        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), 0, 0));
-        var mockQuery = new Mock<DtNavMeshQuery>(It.IsAny<DtNavMesh>());
-        mockQuery.Setup(q => q.FindStraightPath(
-                It.IsAny<RcVec3f>(),
-                It.IsAny<RcVec3f>(),
-                It.IsAny<List<long>>(),
-                ref It.Ref<List<DtStraightPath>>.IsAny,
-                It.IsAny<int>(),
-                It.IsAny<int>())
-            )
-            .Callback((RcVec3f startPos, RcVec3f endPos, List<long> path,
-                ref List<DtStraightPath> refStraightPath, int maxStraightPath, int options) =>
-            {
-                refStraightPath = straightPath;
-            })
-            .Returns(() => DtStatus.DT_SUCCESS);
-
-        var path = new List<DtStraightPath>();
-        corridor.FindCorners(ref path, int.MaxValue, mockQuery.Object, filter);
-        Assert.That(path.Count, Is.EqualTo(4));
-        Assert.That(path, Is.EqualTo(straightPath));
-    }
-
-    [Test]
-    public void ShouldPrunePathInFindCorners()
-    {
-        List<DtStraightPath> straightPath = new();
-        straightPath.Add(new DtStraightPath(new RcVec3f(10, 20, 30.00001f), 0, 0)); // too close
-        straightPath.Add(new DtStraightPath(new RcVec3f(10, 20, 30.00002f), 0, 0)); // too close
-        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), 0, 0));
-        straightPath.Add(new DtStraightPath(new RcVec3f(12f, 22, 33f), DtStraightPathFlags.DT_STRAIGHTPATH_OFFMESH_CONNECTION, 0)); // offmesh
-        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), DtStraightPathFlags.DT_STRAIGHTPATH_OFFMESH_CONNECTION, 0)); // offmesh
-
-        var mockQuery = new Mock<DtNavMeshQuery>(It.IsAny<DtNavMesh>());
-        mockQuery.Setup(q => q.FindStraightPath(
-                It.IsAny<RcVec3f>(),
-                It.IsAny<RcVec3f>(),
-                It.IsAny<List<long>>(),
-                ref It.Ref<List<DtStraightPath>>.IsAny,
-                It.IsAny<int>(),
-                It.IsAny<int>())
-            ).Callback((RcVec3f startPos, RcVec3f endPos, List<long> path,
-                ref List<DtStraightPath> refStraightPath, int maxStraightPath, int options) =>
-            {
-                refStraightPath = straightPath;
-            })
-            .Returns(() => DtStatus.DT_SUCCESS);
-
-        var path = new List<DtStraightPath>();
-        corridor.FindCorners(ref path, int.MaxValue, mockQuery.Object, filter);
-        Assert.That(path.Count, Is.EqualTo(2));
-        Assert.That(path, Is.EqualTo(new List<DtStraightPath> { straightPath[2], straightPath[3] }));
-    }
-}

test/DotRecast.Detour.Crowd.Test/PathCorridorTest.cs

@@ -0,0 +1,101 @@
+/*
+recast4j copyright (c) 2021 Piotr Piastucki piotr@jtilia.org
+DotRecast Copyright (c) 2023 Choi Ikpil ikpil@naver.com
+
+This software is provided 'as-is', without any express or implied
+warranty.  In no event will the authors be held liable for any damages
+arising from the use of this software.
+Permission is granted to anyone to use this software for any purpose,
+including commercial applications, and to alter it and redistribute it
+freely, subject to the following restrictions:
+1. The origin of this software must not be misrepresented; you must not
+ claim that you wrote the original software. If you use this software
+ in a product, an acknowledgment in the product documentation would be
+ appreciated but is not required.
+2. Altered source versions must be plainly marked as such, and must not be
+ misrepresented as being the original software.
+3. This notice may not be removed or altered from any source distribution.
+*/
+
+using System.Collections.Generic;
+using DotRecast.Core.Numerics;
+
+using Moq;
+using NUnit.Framework;
+
+namespace DotRecast.Detour.Crowd.Test;
+
+
+public class PathCorridorTest
+{
+    private readonly DtPathCorridor corridor = new DtPathCorridor();
+    private readonly IDtQueryFilter filter = new DtQueryDefaultFilter();
+
+    [SetUp]
+    public void SetUp()
+    {
+        corridor.Init(256);
+        corridor.Reset(0, new RcVec3f(10, 20, 30));
+    }
+
+    [Test]
+    public void ShouldKeepOriginalPathInFindCornersWhenNothingCanBePruned()
+    {
+        List<DtStraightPath> straightPath = new();
+        straightPath.Add(new DtStraightPath(new RcVec3f(11, 20, 30.00001f), 0, 0));
+        straightPath.Add(new DtStraightPath(new RcVec3f(12, 20, 30.00002f), 0, 0));
+        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), 0, 0));
+        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), 0, 0));
+        var mockQuery = new Mock<DtNavMeshQuery>(It.IsAny<DtNavMesh>());
+        mockQuery.Setup(q => q.FindStraightPath(
+                It.IsAny<RcVec3f>(),
+                It.IsAny<RcVec3f>(),
+                It.IsAny<List<long>>(),
+                ref It.Ref<List<DtStraightPath>>.IsAny,
+                It.IsAny<int>(),
+                It.IsAny<int>())
+            )
+            .Callback((RcVec3f startPos, RcVec3f endPos, List<long> path,
+                ref List<DtStraightPath> refStraightPath, int maxStraightPath, int options) =>
+            {
+                refStraightPath = straightPath;
+            })
+            .Returns(() => DtStatus.DT_SUCCESS);
+
+        var path = new List<DtStraightPath>();
+        corridor.FindCorners(ref path, int.MaxValue, mockQuery.Object, filter);
+        Assert.That(path.Count, Is.EqualTo(4));
+        Assert.That(path, Is.EqualTo(straightPath));
+    }
+
+    [Test]
+    public void ShouldPrunePathInFindCorners()
+    {
+        List<DtStraightPath> straightPath = new();
+        straightPath.Add(new DtStraightPath(new RcVec3f(10, 20, 30.00001f), 0, 0)); // too close
+        straightPath.Add(new DtStraightPath(new RcVec3f(10, 20, 30.00002f), 0, 0)); // too close
+        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), 0, 0));
+        straightPath.Add(new DtStraightPath(new RcVec3f(12f, 22, 33f), DtStraightPathFlags.DT_STRAIGHTPATH_OFFMESH_CONNECTION, 0)); // offmesh
+        straightPath.Add(new DtStraightPath(new RcVec3f(11f, 21, 32f), DtStraightPathFlags.DT_STRAIGHTPATH_OFFMESH_CONNECTION, 0)); // offmesh
+
+        var mockQuery = new Mock<DtNavMeshQuery>(It.IsAny<DtNavMesh>());
+        mockQuery.Setup(q => q.FindStraightPath(
+                It.IsAny<RcVec3f>(),
+                It.IsAny<RcVec3f>(),
+                It.IsAny<List<long>>(),
+                ref It.Ref<List<DtStraightPath>>.IsAny,
+                It.IsAny<int>(),
+                It.IsAny<int>())
+            ).Callback((RcVec3f startPos, RcVec3f endPos, List<long> path,
+                ref List<DtStraightPath> refStraightPath, int maxStraightPath, int options) =>
+            {
+                refStraightPath = straightPath;
+            })
+            .Returns(() => DtStatus.DT_SUCCESS);
+
+        var path = new List<DtStraightPath>();
+        corridor.FindCorners(ref path, int.MaxValue, mockQuery.Object, filter);
+        Assert.That(path.Count, Is.EqualTo(2));
+        Assert.That(path, Is.EqualTo(new List<DtStraightPath> { straightPath[2], straightPath[3] }));
+    }
+}