From 43ebd7a9bbba0c1290a9e98b9224f0752627c400 Mon Sep 17 00:00:00 2001 From: gdkchan Date: Sun, 10 Apr 2022 10:49:44 -0300 Subject: New shader cache implementation (#3194) * New shader cache implementation * Remove some debug code * Take transform feedback varying count into account * Create shader cache directory if it does not exist + fragment output map related fixes * Remove debug code * Only check texture descriptors if the constant buffer is bound * Also check CPU VA on GetSpanMapped * Remove more unused code and move cache related code * XML docs + remove more unused methods * Better codegen for TransformFeedbackDescriptor.AsSpan * Support migration from old cache format, remove more unused code Shader cache rebuild now also rewrites the shared toc and data files * Fix migration error with BRX shaders * Add a limit to the async translation queue Avoid async translation threads not being able to keep up and the queue growing very large * Re-create specialization state on recompile This might be required if a new version of the shader translator requires more or less state, or if there is a bug related to the GPU state access * Make shader cache more error resilient * Add some missing XML docs and move GpuAccessor docs to the interface/use inheritdoc * Address early PR feedback * Fix rebase * Remove IRenderer.CompileShader and IShader interface, replace with new ShaderSource struct passed to CreateProgram directly * Handle some missing exceptions * Make shader cache purge delete both old and new shader caches * Register textures on new specialization state * Translate and compile shaders in forward order (eliminates diffs due to different binding numbers) * Limit in-flight shader compilation to the maximum number of compilation threads * Replace ParallelDiskCacheLoader state changed event with a callback function * Better handling for invalid constant buffer 1 data length * Do not create the old cache directory structure if the old cache does not exist * Constant buffer use should be per-stage. This change will invalidate existing new caches (file format version was incremented) * Replace rectangle texture with just coordinate normalization * Skip incompatible shaders that are missing texture information, instead of crashing This is required if we, for example, support new texture instruction to the shader translator, and then they allow access to textures that were not accessed before. In this scenario, the old cache entry is no longer usable * Fix coordinates normalization on cubemap textures * Check if title ID is null before combining shader cache path * More robust constant buffer address validation on spec state * More robust constant buffer address validation on spec state (2) * Regenerate shader cache with one stream, rather than one per shader. * Only create shader cache directory during initialization * Logging improvements * Proper shader program disposal * PR feedback, and add a comment on serialized structs * XML docs for RegisterTexture Co-authored-by: riperiperi --- .../Shader/HashTable/PartitionHashTable.cs | 452 +++++++++++++++++++++ 1 file changed, 452 insertions(+) create mode 100644 Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs (limited to 'Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs') diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs new file mode 100644 index 00000000..6a563c16 --- /dev/null +++ b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs @@ -0,0 +1,452 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Numerics; + +namespace Ryujinx.Graphics.Gpu.Shader.HashTable +{ + /// + /// Partitioned hash table. + /// + /// Hash table entry type + class PartitionHashTable + { + /// + /// Hash table entry. + /// + private struct Entry + { + /// + /// Hash bytes of . + /// + public readonly uint Hash; + + /// + /// If this entry is only a sub-region of , this indicates the size in bytes + /// of that region. Otherwise, it should be zero. + /// + public readonly int OwnSize; + + /// + /// Data used to compute the hash for this entry. + /// + /// + /// To avoid additional allocations, this might be a instance of the full entry data, + /// and only a sub-region of it might be actually used by this entry. Such sub-region + /// has its size indicated by in this case. + /// + public readonly byte[] Data; + + /// + /// Item associated with this entry. + /// + public T Item; + + /// + /// Indicates if the entry is partial, which means that this entry is only for a sub-region of the data. + /// + /// + /// Partial entries have no items associated with them. They just indicates that the data might be present on + /// the table, and one must keep looking for the full entry on other tables of larger data size. + /// + public bool IsPartial => OwnSize != 0; + + /// + /// Creates a new partial hash table entry. + /// + /// Hash of the data + /// Full data + /// Size of the sub-region of data that belongs to this entry + public Entry(uint hash, byte[] ownerData, int ownSize) + { + Hash = hash; + OwnSize = ownSize; + Data = ownerData; + Item = default; + } + + /// + /// Creates a new full hash table entry. + /// + /// Hash of the data + /// Data + /// Item associated with this entry + public Entry(uint hash, byte[] data, T item) + { + Hash = hash; + OwnSize = 0; + Data = data; + Item = item; + } + + /// + /// Gets the data for this entry, either full or partial. + /// + /// Data sub-region + public ReadOnlySpan GetData() + { + if (OwnSize != 0) + { + return new ReadOnlySpan(Data).Slice(0, OwnSize); + } + + return Data; + } + } + + /// + /// Hash table bucket. + /// + private struct Bucket + { + /// + /// Inline entry, to avoid allocations for the common single entry case. + /// + public Entry InlineEntry; + + /// + /// List of additional entries for the not-so-common multiple entries case. + /// + public List MoreEntries; + } + + private Bucket[] _buckets; + private int _count; + + /// + /// Total amount of entries on the hash table. + /// + public int Count => _count; + + /// + /// Creates a new instance of the partitioned hash table. + /// + public PartitionHashTable() + { + _buckets = Array.Empty(); + } + + /// + /// Gets an item on the table, or adds a new one if not present. + /// + /// Data + /// Hash of the data + /// Item to be added if not found + /// Existing item if found, or if not found + public T GetOrAdd(byte[] data, uint dataHash, T item) + { + if (TryFindItem(dataHash, data, out T existingItem)) + { + return existingItem; + } + + Entry entry = new Entry(dataHash, data, item); + + AddToBucket(dataHash, ref entry); + + return item; + } + + /// + /// Adds an item to the hash table. + /// + /// Data + /// Hash of the data + /// Item to be added + /// True if the item was added, false due to an item associated with the data already being on the table + public bool Add(byte[] data, uint dataHash, T item) + { + if (TryFindItem(dataHash, data, out _)) + { + return false; + } + + Entry entry = new Entry(dataHash, data, item); + + AddToBucket(dataHash, ref entry); + + return true; + } + + /// + /// Adds a partial entry to the hash table. + /// + /// Full data + /// Size of the sub-region of used by the partial entry + /// True if added, false otherwise + public bool AddPartial(byte[] ownerData, int ownSize) + { + ReadOnlySpan data = new ReadOnlySpan(ownerData).Slice(0, ownSize); + + return AddPartial(ownerData, HashState.CalcHash(data), ownSize); + } + + /// + /// Adds a partial entry to the hash table. + /// + /// Full data + /// Hash of the data sub-region + /// Size of the sub-region of used by the partial entry + /// True if added, false otherwise + public bool AddPartial(byte[] ownerData, uint dataHash, int ownSize) + { + ReadOnlySpan data = new ReadOnlySpan(ownerData).Slice(0, ownSize); + + if (TryFindItem(dataHash, data, out _)) + { + return false; + } + + Entry entry = new Entry(dataHash, ownerData, ownSize); + + AddToBucket(dataHash, ref entry); + + return true; + } + + /// + /// Adds entry with a given hash to the table. + /// + /// Hash of the entry + /// Entry + private void AddToBucket(uint dataHash, ref Entry entry) + { + int pow2Count = GetPow2Count(++_count); + if (pow2Count != _buckets.Length) + { + Rebuild(pow2Count); + } + + ref Bucket bucket = ref GetBucketForHash(dataHash); + + AddToBucket(ref bucket, ref entry); + } + + /// + /// Adds an entry to a bucket. + /// + /// Bucket to add the entry into + /// Entry to be added + private void AddToBucket(ref Bucket bucket, ref Entry entry) + { + if (bucket.InlineEntry.Data == null) + { + bucket.InlineEntry = entry; + } + else + { + (bucket.MoreEntries ??= new List()).Add(entry); + } + } + + /// + /// Creates partial entries on a new hash table for all existing full entries. + /// + /// + /// This should be called every time a new hash table is created, and there are hash + /// tables with data sizes that are higher than that of the new table. + /// This will then fill the new hash table with "partial" entries of full entries + /// on the hash tables with higher size. + /// + /// New hash table + /// Size of the data on the new hash table + public void FillPartials(PartitionHashTable newTable, int newEntrySize) + { + for (int i = 0; i < _buckets.Length; i++) + { + ref Bucket bucket = ref _buckets[i]; + ref Entry inlineEntry = ref bucket.InlineEntry; + + if (inlineEntry.Data != null) + { + if (!inlineEntry.IsPartial) + { + newTable.AddPartial(inlineEntry.Data, newEntrySize); + } + + if (bucket.MoreEntries != null) + { + foreach (Entry entry in bucket.MoreEntries) + { + if (entry.IsPartial) + { + continue; + } + + newTable.AddPartial(entry.Data, newEntrySize); + } + } + } + } + } + + /// + /// Tries to find an item on the table. + /// + /// Hash of + /// Data to find + /// Item associated with the data + /// True if an item was found, false otherwise + private bool TryFindItem(uint dataHash, ReadOnlySpan data, out T item) + { + if (_count == 0) + { + item = default; + return false; + } + + ref Bucket bucket = ref GetBucketForHash(dataHash); + + if (bucket.InlineEntry.Data != null) + { + if (bucket.InlineEntry.Hash == dataHash && bucket.InlineEntry.GetData().SequenceEqual(data)) + { + item = bucket.InlineEntry.Item; + return true; + } + + if (bucket.MoreEntries != null) + { + foreach (Entry entry in bucket.MoreEntries) + { + if (entry.Hash == dataHash && entry.GetData().SequenceEqual(data)) + { + item = entry.Item; + return true; + } + } + } + } + + item = default; + return false; + } + + /// + /// Indicates the result of a hash table lookup. + /// + public enum SearchResult + { + /// + /// No entry was found, the search must continue on hash tables of lower size. + /// + NotFound, + + /// + /// A partial entry was found, the search must continue on hash tables of higher size. + /// + FoundPartial, + + /// + /// A full entry was found, the search was concluded and the item can be retrieved. + /// + FoundFull + } + + /// + /// Tries to find an item on the table. + /// + /// Data accessor + /// Size of the hash table data + /// The item on the table, if found, otherwise unmodified + /// The data on the table, if found, otherwise unmodified + /// Table lookup result + public SearchResult TryFindItem(ref SmartDataAccessor dataAccessor, int size, ref T item, ref byte[] data) + { + if (_count == 0) + { + return SearchResult.NotFound; + } + + ReadOnlySpan dataSpan = dataAccessor.GetSpanAndHash(size, out uint dataHash); + + if (dataSpan.Length != size) + { + return SearchResult.NotFound; + } + + ref Bucket bucket = ref GetBucketForHash(dataHash); + + if (bucket.InlineEntry.Data != null) + { + if (bucket.InlineEntry.Hash == dataHash && bucket.InlineEntry.GetData().SequenceEqual(dataSpan)) + { + item = bucket.InlineEntry.Item; + data = bucket.InlineEntry.Data; + return bucket.InlineEntry.IsPartial ? SearchResult.FoundPartial : SearchResult.FoundFull; + } + + if (bucket.MoreEntries != null) + { + foreach (Entry entry in bucket.MoreEntries) + { + if (entry.Hash == dataHash && entry.GetData().SequenceEqual(dataSpan)) + { + item = entry.Item; + data = entry.Data; + return entry.IsPartial ? SearchResult.FoundPartial : SearchResult.FoundFull; + } + } + } + } + + return SearchResult.NotFound; + } + + /// + /// Rebuilds the table for a new count. + /// + /// New power of two count of the table + private void Rebuild(int newPow2Count) + { + Bucket[] newBuckets = new Bucket[newPow2Count]; + + uint mask = (uint)newPow2Count - 1; + + for (int i = 0; i < _buckets.Length; i++) + { + ref Bucket bucket = ref _buckets[i]; + + if (bucket.InlineEntry.Data != null) + { + AddToBucket(ref newBuckets[(int)(bucket.InlineEntry.Hash & mask)], ref bucket.InlineEntry); + + if (bucket.MoreEntries != null) + { + foreach (Entry entry in bucket.MoreEntries) + { + Entry entryCopy = entry; + AddToBucket(ref newBuckets[(int)(entry.Hash & mask)], ref entryCopy); + } + } + } + } + + _buckets = newBuckets; + } + + /// + /// Gets the bucket for a given hash. + /// + /// Data hash + /// Bucket for the hash + private ref Bucket GetBucketForHash(uint hash) + { + int index = (int)(hash & (_buckets.Length - 1)); + + return ref _buckets[index]; + } + + /// + /// Gets a power of two count from a regular count. + /// + /// Count + /// Power of two count + private static int GetPow2Count(int count) + { + // This returns the nearest power of two that is lower than count. + // This was done to optimize memory usage rather than performance. + return 1 << BitOperations.Log2((uint)count); + } + } +} -- cgit v1.2.3