Optimize RangeList by not doing an allocation on every call to the Find methods

3 files changed, 92 insertions, 28 deletions

diff --git a/Ryujinx.Graphics.Gpu/Image/TextureManager.cs b/Ryujinx.Graphics.Gpu/Image/TextureManager.cs
index 413ba327..5e5b1c97 100644
--- a/Ryujinx.Graphics.Gpu/Image/TextureManager.cs
+++ b/Ryujinx.Graphics.Gpu/Image/TextureManager.cs
@@ -11,6 +11,9 @@ namespace Ryujinx.Graphics.Gpu.Image
 {
     class TextureManager
     {
+        private const int OverlapsBufferInitialCapacity = 10;
+        private const int OverlapsBufferMaxCapacity     = 10000;
+
         private GpuContext _context;
 
         private TextureBindingsManager _cpBindingsManager;
@@ -24,6 +27,8 @@ namespace Ryujinx.Graphics.Gpu.Image
 
         private RangeList<Texture> _textures;
 
+        private Texture[] _textureOverlaps;
+
         private AutoDeleteCache _cache;
 
         public TextureManager(GpuContext context)
@@ -41,6 +46,8 @@ namespace Ryujinx.Graphics.Gpu.Image
 
             _textures = new RangeList<Texture>();
 
+            _textureOverlaps = new Texture[OverlapsBufferInitialCapacity];
+
             _cache = new AutoDeleteCache();
         }
 
@@ -321,10 +328,12 @@ namespace Ryujinx.Graphics.Gpu.Image
             bool isSamplerTexture = (flags & TextureSearchFlags.Sampler) != 0;
 
             // Try to find a perfect texture match, with the same address and parameters.
-            Texture[] sameAddressOverlaps = _textures.FindOverlaps(info.Address);
+            int sameAddressOverlapsCount = _textures.FindOverlaps(info.Address, ref _textureOverlaps);
 
-            foreach (Texture overlap in sameAddressOverlaps)
+            for (int index = 0; index < sameAddressOverlapsCount; index++)
             {
+                Texture overlap = _textureOverlaps[index];
+
                 if (overlap.IsPerfectMatch(info, flags))
                 {
                     if (!isSamplerTexture)
@@ -376,12 +385,14 @@ namespace Ryujinx.Graphics.Gpu.Image
             // Find view compatible matches.
             ulong size = (ulong)sizeInfo.TotalSize;
 
-            Texture[] overlaps = _textures.FindOverlaps(info.Address, size);
+            int overlapsCount = _textures.FindOverlaps(info.Address, size, ref _textureOverlaps);
 
             Texture texture = null;
 
-            foreach (Texture overlap in overlaps)
+            for (int index = 0; index < overlapsCount; index++)
             {
+                Texture overlap = _textureOverlaps[index];
+
                 if (overlap.IsViewCompatible(info, size, out int firstLayer, out int firstLevel))
                 {
                     if (!isSamplerTexture)
@@ -412,8 +423,10 @@ namespace Ryujinx.Graphics.Gpu.Image
                 // otherwise the copied data would be overwritten by a future synchronization.
                 texture.SynchronizeMemory();
 
-                foreach (Texture overlap in overlaps)
+                for (int index = 0; index < overlapsCount; index++)
                 {
+                    Texture overlap = _textureOverlaps[index];
+
                     if (texture.IsViewCompatible(overlap.Info, overlap.Size, out int firstLayer, out int firstLevel))
                     {
                         TextureInfo overlapInfo = AdjustSizes(texture, overlap.Info, firstLevel);
@@ -432,8 +445,10 @@ namespace Ryujinx.Graphics.Gpu.Image
                 // of the 3D texture to the newly created 3D texture.
                 if (info.Target == Target.Texture3D)
                 {
-                    foreach (Texture overlap in overlaps)
+                    for (int index = 0; index < overlapsCount; index++)
                     {
+                        Texture overlap = _textureOverlaps[index];
+
                         if (texture.IsViewCompatible(
                             overlap.Info,
                             overlap.Size,
@@ -456,9 +471,19 @@ namespace Ryujinx.Graphics.Gpu.Image
 
             _textures.Add(texture);
 
+            ShrinkOverlapsBufferIfNeeded();
+
             return texture;
         }
 
+        private void ShrinkOverlapsBufferIfNeeded()
+        {
+            if (_textureOverlaps.Length > OverlapsBufferMaxCapacity)
+            {
+                Array.Resize(ref _textureOverlaps, OverlapsBufferMaxCapacity);
+            }
+        }
+
         private static TextureInfo AdjustSizes(Texture parent, TextureInfo info, int firstLevel)
         {
             // When the texture is used as view of another texture, we must
diff --git a/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs b/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs
index 30bd1302..a066585c 100644
--- a/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs
+++ b/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs
@@ -8,6 +8,9 @@ namespace Ryujinx.Graphics.Gpu.Memory
 {
     class BufferManager
     {
+        private const int OverlapsBufferInitialCapacity = 10;
+        private const int OverlapsBufferMaxCapacity     = 10000;
+
         private const ulong BufferAlignmentSize = 0x1000;
         private const ulong BufferAlignmentMask = BufferAlignmentSize - 1;
 
@@ -15,6 +18,8 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
         private RangeList<Buffer> _buffers;
 
+        private Buffer[] _bufferOverlaps;
+
         private IndexBuffer _indexBuffer;
 
         private VertexBuffer[] _vertexBuffers;
@@ -57,6 +62,8 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
             _buffers = new RangeList<Buffer>();
 
+            _bufferOverlaps = new Buffer[OverlapsBufferInitialCapacity];
+
             _vertexBuffers = new VertexBuffer[Constants.TotalVertexBuffers];
 
             _cpStorageBuffers = new BuffersPerStage(Constants.TotalCpStorageBuffers);
@@ -207,9 +214,9 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
         private void CreateBuffer(ulong address, ulong size)
         {
-            Buffer[] overlaps = _buffers.FindOverlapsNonOverlapping(address, size);
+            int overlapsCount = _buffers.FindOverlapsNonOverlapping(address, size, ref _bufferOverlaps);
 
-            if (overlaps.Length != 0)
+            if (overlapsCount != 0)
             {
                 // The buffer already exists. We can just return the existing buffer
                 // if the buffer we need is fully contained inside the overlapping buffer.
@@ -218,10 +225,12 @@ namespace Ryujinx.Graphics.Gpu.Memory
                 // old buffer(s) to the new buffer.
                 ulong endAddress = address + size;
 
-                if (overlaps[0].Address > address || overlaps[0].EndAddress < endAddress)
+                if (_bufferOverlaps[0].Address > address || _bufferOverlaps[0].EndAddress < endAddress)
                 {
-                    foreach (Buffer buffer in overlaps)
+                    for (int index = 0; index < overlapsCount; index++)
                     {
+                        Buffer buffer = _bufferOverlaps[index];
+
                         address    = Math.Min(address,    buffer.Address);
                         endAddress = Math.Max(endAddress, buffer.EndAddress);
 
@@ -234,8 +243,10 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
                     _buffers.Add(newBuffer);
 
-                    foreach (Buffer buffer in overlaps)
+                    for (int index = 0; index < overlapsCount; index++)
                     {
+                        Buffer buffer = _bufferOverlaps[index];
+
                         int dstOffset = (int)(buffer.Address - newBuffer.Address);
 
                         buffer.CopyTo(newBuffer, dstOffset);
@@ -253,6 +264,16 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
                 _buffers.Add(buffer);
             }
+
+            ShrinkOverlapsBufferIfNeeded();
+        }
+
+        private void ShrinkOverlapsBufferIfNeeded()
+        {
+            if (_bufferOverlaps.Length > OverlapsBufferMaxCapacity)
+            {
+                Array.Resize(ref _bufferOverlaps, OverlapsBufferMaxCapacity);
+            }
         }
 
         public ulong GetComputeUniformBufferAddress(int index)
diff --git a/Ryujinx.Graphics.Gpu/Memory/RangeList.cs b/Ryujinx.Graphics.Gpu/Memory/RangeList.cs
index e3435292..45f23cf3 100644
--- a/Ryujinx.Graphics.Gpu/Memory/RangeList.cs
+++ b/Ryujinx.Graphics.Gpu/Memory/RangeList.cs
@@ -1,9 +1,12 @@
+using System;
 using System.Collections.Generic;
 
 namespace Ryujinx.Graphics.Gpu.Memory
 {
     class RangeList<T> where T : IRange<T>
     {
+        private const int ArrayGrowthSize = 32;
+
         private List<T> _items;
 
         public RangeList()
@@ -72,14 +75,14 @@ namespace Ryujinx.Graphics.Gpu.Memory
             return _items[index];
         }
 
-        public T[] FindOverlaps(T item)
+        public int FindOverlaps(T item, ref T[] output)
         {
-            return FindOverlaps(item.Address, item.Size);
+            return FindOverlaps(item.Address, item.Size, ref output);
         }
 
-        public T[] FindOverlaps(ulong address, ulong size)
+        public int FindOverlaps(ulong address, ulong size, ref T[] output)
         {
-            List<T> overlapsList = new List<T>();
+            int outputIndex = 0;
 
             ulong endAddress = address + size;
 
@@ -94,24 +97,29 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
                     if (item.OverlapsWith(address, size))
                     {
-                        overlapsList.Add(item);
+                        if (outputIndex == output.Length)
+                        {
+                            Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+                        }
+
+                        output[outputIndex++] = item;
                     }
                 }
             }
 
-            return overlapsList.ToArray();
+            return outputIndex;
         }
 
-        public T[] FindOverlapsNonOverlapping(T item)
+        public int FindOverlapsNonOverlapping(T item, ref T[] output)
         {
-            return FindOverlapsNonOverlapping(item.Address, item.Size);
+            return FindOverlapsNonOverlapping(item.Address, item.Size, ref output);
         }
 
-        public T[] FindOverlapsNonOverlapping(ulong address, ulong size)
+        public int FindOverlapsNonOverlapping(ulong address, ulong size, ref T[] output)
         {
             // This is a bit faster than FindOverlaps, but only works
             // when none of the items on the list overlaps with each other.
-            List<T> overlapsList = new List<T>();
+            int outputIndex = 0;
 
             ulong endAddress = address + size;
 
@@ -126,20 +134,25 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
                 do
                 {
-                    overlapsList.Add(_items[index++]);
+                    if (outputIndex == output.Length)
+                    {
+                        Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+                    }
+
+                    output[outputIndex++] = _items[index++];
                 }
                 while (index < _items.Count && _items[index].OverlapsWith(address, size));
             }
 
-            return overlapsList.ToArray();
+            return outputIndex;
         }
 
-        public T[] FindOverlaps(ulong address)
+        public int FindOverlaps(ulong address, ref T[] output)
         {
-            List<T> overlapsList = new List<T>();
-
             int index = BinarySearch(address);
 
+            int outputIndex = 0;
+
             if (index >= 0)
             {
                 while (index > 0 && _items[index - 1].Address == address)
@@ -156,11 +169,16 @@ namespace Ryujinx.Graphics.Gpu.Memory
                         break;
                     }
 
-                    overlapsList.Add(overlap);
+                    if (outputIndex == output.Length)
+                    {
+                        Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+                    }
+
+                    output[outputIndex++] = overlap;
                 }
             }
 
-            return overlapsList.ToArray();
+            return outputIndex;
         }
 
         private int BinarySearch(ulong address)