core: skip empty bitmap ranges during cache and scheduler traversal

Adapted bitmap scans from sylvieistaken/selevet-eglantine performance build 4. Keep the wide-priority fallback and fix the first live slot after empty bitmap words. Include randomized lifecycle and ordering checks.

Assisted by Codex.

6 files changed, 307 insertions, 13 deletions

diff --git a/src/common/slot_vector.h b/src/common/slot_vector.h
index f6da7a59d1..8e1c06e35a 100644
--- a/src/common/slot_vector.h
+++ b/src/common/slot_vector.h
@@ -52,12 +52,16 @@ public:
             const u64* const bitset = slot_vector->stored_bitset.data();
             const u32 size = static_cast<u32>(slot_vector->stored_bitset.size()) * 64;
             if (id.Value() < size) {
-                do {
-                    ++id.index;
-                } while (id.Value() < size && !IsValid(bitset));
-                if (id.Value() == size) {
-                    id = SlotId{};
+                u32 index = id.Value() + 1;
+                while (index < size) {
+                    const u64 word = bitset[index / 64] >> (index % 64);
+                    if (word != 0) {
+                        index += static_cast<u32>(std::countr_zero(word));
+                        break;
+                    }
+                    index = (index / 64 + 1) * 64;
                 }
+                id = index < size ? SlotId{index} : SlotId{};
             }
             return *this;
         }
@@ -139,7 +143,7 @@ public:
         if (it == stored_bitset.end()) {
             return end();
         }
-        const u32 word_index = static_cast<u32>(std::distance(it, stored_bitset.begin()));
+        const u32 word_index = static_cast<u32>(std::distance(stored_bitset.begin(), it));
         const SlotId first_id{word_index * 64 + static_cast<u32>(std::countr_zero(*it))};
         return Iterator(this, first_id);
     }
diff --git a/src/core/hle/kernel/k_priority_queue.h b/src/core/hle/kernel/k_priority_queue.h
index 89a0c5bbea..5d93455d33 100644
--- a/src/core/hle/kernel/k_priority_queue.h
+++ b/src/core/hle/kernel/k_priority_queue.h
@@ -11,6 +11,7 @@
 #include <bitset>
 #include <concepts>
 #include <cstddef>
+#include <type_traits>
 
 #include "common/alignment.h"
 #include "common/assert.h"
@@ -196,12 +197,7 @@ public:
         constexpr Member* GetFront(s32 core) const {
             ASSERT(IsValidCore(core));
 
-            const s32 priority = s32([](auto const& e) {
-                for (size_t i = 0; i < e.size(); ++i)
-                    if (e[i])
-                        return i;
-                return e.size();
-            }(m_available_priorities[core]));
+            const s32 priority = s32(GetNextSet(m_available_priorities[core], size_t(-1)));
             if (priority <= LowestPriority) {
                 return m_queues[priority].GetFront(core);
             } else {
@@ -222,7 +218,17 @@ public:
 
         template<size_t N>
         constexpr size_t GetNextSet(std::bitset<N> const& bit, size_t n) const {
-            for (size_t i = n + 1; i < bit.size(); i++)
+            const size_t first = n + 1;
+            if (first >= bit.size()) {
+                return bit.size();
+            }
+            if constexpr (N <= 64) {
+                if (!std::is_constant_evaluated()) {
+                    const u64 remaining = bit.to_ullong() >> first;
+                    return remaining != 0 ? first + size_t(std::countr_zero(remaining)) : bit.size();
+                }
+            }
+            for (size_t i = first; i < bit.size(); i++)
                 if (bit[i])
                     return i;
             return bit.size();
diff --git a/src/tests/CMakeLists.txt b/src/tests/CMakeLists.txt
index e064792e19..461098954c 100644
--- a/src/tests/CMakeLists.txt
+++ b/src/tests/CMakeLists.txt
@@ -14,15 +14,18 @@ add_executable(tests
     common/range_map.cpp
     common/ring_buffer.cpp
     common/scratch_buffer.cpp
+    common/slot_vector.cpp
     common/undefined_fix.cpp
     common/unique_function.cpp
     core/core_timing.cpp
     core/nup_writer.cpp
+    core/priority_queue.cpp
     core/internal_network/network.cpp
     video_core/memory_tracker.cpp
     video_core/vertex_repack.cpp
     video_core/ampere_returns.cpp
     video_core/native_macro_fifo.cpp
+    video_core/uniform_stream_reuse.cpp
     video_core/shader_invalidation.cpp
     video_core/descriptor_table.cpp
     input_common/calibration_configuration_job.cpp
diff --git a/src/tests/common/slot_vector.cpp b/src/tests/common/slot_vector.cpp
new file mode 100644
index 0000000000..d8f242085c
--- /dev/null
+++ b/src/tests/common/slot_vector.cpp
@@ -0,0 +1,54 @@
+// SPDX-FileCopyrightText: Copyright 2026 Eden Emulator Project
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include <map>
+#include <random>
+#include <vector>
+#include <catch2/catch_test_macros.hpp>
+#include "common/slot_vector.h"
+
+TEST_CASE("SlotVector visits live entries across empty bitmap words", "[common]") {
+    Common::SlotVector<u32> slots;
+    std::vector<Common::SlotId> ids;
+    for (u32 i = 0; i < 513; ++i) {
+        ids.push_back(slots.insert(i));
+    }
+    for (u32 i = 0; i < 512; ++i) {
+        slots.erase(ids[i]);
+    }
+    auto it = slots.begin();
+    REQUIRE(it != slots.end());
+    REQUIRE((*it).first == ids[512]);
+    REQUIRE(*(*it).second == 512);
+    REQUIRE(++it == slots.end());
+    slots.erase(ids[512]);
+    REQUIRE(slots.begin() == slots.end());
+}
+
+TEST_CASE("SlotVector sparse iteration matches a live-entry model", "[common]") {
+    Common::SlotVector<u32> slots;
+    std::map<u32, u32> live;
+    std::mt19937 random{9813};
+    for (u32 batch = 0; batch < 200; ++batch) {
+        for (u32 i = 0; i < 100; ++i) {
+            if (!live.empty() && (random() % 3) == 0) {
+                auto selected = live.begin();
+                std::advance(selected, random() % live.size());
+                slots.erase(Common::SlotId{selected->first});
+                live.erase(selected);
+            } else {
+                const u32 value = random();
+                const auto id = slots.insert(value);
+                live.emplace(id.Value(), value);
+            }
+        }
+        auto expected = live.begin();
+        for (const auto [id, value] : slots) {
+            REQUIRE(expected != live.end());
+            REQUIRE(id.Value() == expected->first);
+            REQUIRE(*value == expected->second);
+            ++expected;
+        }
+        REQUIRE(expected == live.end());
+    }
+}
diff --git a/src/tests/core/priority_queue.cpp b/src/tests/core/priority_queue.cpp
new file mode 100644
index 0000000000..0d7174f793
--- /dev/null
+++ b/src/tests/core/priority_queue.cpp
@@ -0,0 +1,111 @@
+// SPDX-FileCopyrightText: Copyright 2026 Eden Emulator Project
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include <algorithm>
+#include <array>
+#include <random>
+#include <vector>
+#include <catch2/catch_test_macros.hpp>
+#include "core/hle/kernel/k_priority_queue.h"
+
+namespace {
+struct Affinity {
+    u64 GetAffinityMask() const {
+        return 3;
+    }
+    void SetAffinityMask(u64) {}
+    bool GetAffinity(s32) const {
+        return true;
+    }
+    void SetAffinity(s32, bool) {}
+    void SetAll() {}
+};
+
+struct Member {
+    struct QueueEntry {
+        Member* prev{};
+        Member* next{};
+        void Initialize() {
+            prev = next = nullptr;
+        }
+        void SetPrev(Member* value) {
+            prev = value;
+        }
+        void SetNext(Member* value) {
+            next = value;
+        }
+        Member* GetNext() const {
+            return next;
+        }
+        Member* GetPrev() const {
+            return prev;
+        }
+    };
+    std::array<QueueEntry, 2> entries{};
+    s32 priority{};
+    QueueEntry& GetPriorityQueueEntry(s32 core) {
+        return entries[core];
+    }
+    const QueueEntry& GetPriorityQueueEntry(s32 core) const {
+        return entries[core];
+    }
+    Affinity GetAffinityMask() const {
+        return {};
+    }
+    s32 GetActiveCore() const {
+        return 0;
+    }
+    s32 GetPriority() const {
+        return priority;
+    }
+    bool IsDummyThread() const {
+        return false;
+    }
+};
+
+template <size_t Priorities>
+void CheckQueue() {
+    using Queue = Kernel::KPriorityQueue<Member, 2, Priorities - 1, 0>;
+    typename Queue::KPriorityQueueImpl queue;
+    std::array<Member, 160> members{};
+    std::array<std::array<bool, 2>, 160> present{};
+    std::array<std::array<std::vector<Member*>, Priorities>, 2> model{};
+    std::mt19937 random{6152};
+    for (size_t i = 0; i < members.size(); ++i) {
+        members[i].priority = static_cast<s32>(i % Priorities);
+    }
+    REQUIRE(queue.GetFront(0) == nullptr);
+    for (u32 operation = 0; operation < 3000; ++operation) {
+        const size_t index = random() % members.size();
+        const s32 core = random() % 2;
+        auto& member = members[index];
+        auto& expected = model[core][member.priority];
+        if (present[index][core]) {
+            queue.Remove(member.priority, core, &member);
+            std::erase(expected, &member);
+        } else if ((random() & 1) != 0) {
+            queue.PushFront(member.priority, core, &member);
+            expected.insert(expected.begin(), &member);
+        } else {
+            queue.PushBack(member.priority, core, &member);
+            expected.push_back(&member);
+        }
+        present[index][core] = !present[index][core];
+        for (s32 checked_core = 0; checked_core < 2; ++checked_core) {
+            Member* actual = queue.GetFront(checked_core);
+            for (const auto& priority : model[checked_core]) {
+                for (Member* wanted : priority) {
+                    REQUIRE(actual == wanted);
+                    actual = queue.GetNext(checked_core, actual);
+                }
+            }
+            REQUIRE(actual == nullptr);
+        }
+    }
+}
+} // namespace
+
+TEST_CASE("Priority queue bitmap traversal preserves thread order", "[core]") {
+    CheckQueue<64>();
+    CheckQueue<128>();
+}
diff --git a/src/tests/video_core/uniform_stream_reuse.cpp b/src/tests/video_core/uniform_stream_reuse.cpp
new file mode 100644
index 0000000000..6059b70eeb
--- /dev/null
+++ b/src/tests/video_core/uniform_stream_reuse.cpp
@@ -0,0 +1,116 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include <algorithm>
+#include <array>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <span>
+#include <vector>
+#include <catch2/catch_test_macros.hpp>
+
+#include "video_core/buffer_cache/uniform_stream_reuse.h"
+
+namespace {
+void Check(bool condition, const char* message) {
+    INFO(message);
+    REQUIRE(condition);
+}
+
+struct Memory {
+    std::array<u8, 8192> bytes{};
+    void ReadBlockUnsafe(u64 address, void* destination, u32 size) {
+        Check(address + size <= bytes.size(), "read outside guest memory");
+        std::memcpy(destination, bytes.data() + address, size);
+    }
+};
+
+struct Runtime {
+    struct StreamUniformRef {
+        size_t allocation;
+    };
+    std::vector<std::vector<u8>> allocations;
+    StreamUniformRef last{}, bound{};
+    u64 tick{1};
+    u64 CurrentTick() const {
+        return tick;
+    }
+    StreamUniformRef LastStreamUniformRef() const {
+        return last;
+    }
+    std::span<u8> BindMappedUniformBuffer(size_t, u32, u32 size) {
+        allocations.emplace_back(size);
+        last = bound = StreamUniformRef{allocations.size() - 1};
+        return allocations.back();
+    }
+    void RebindStreamUniform(StreamUniformRef ref, u32 size) {
+        Check(ref.allocation < allocations.size(), "reused a recycled allocation");
+        Check(allocations[ref.allocation].size() == size, "reused wrong allocation size");
+        bound = ref;
+    }
+    void NextTick() {
+        ++tick;
+        allocations.clear();
+    }
+};
+
+void CheckBound(const Runtime& runtime, const Memory& memory, u64 address, u32 size) {
+    const auto& bytes = runtime.allocations.at(runtime.bound.allocation);
+    Check(bytes.size() == size &&
+              std::memcmp(bytes.data(), memory.bytes.data() + address, size) == 0,
+          "bound uniform data differs from guest memory");
+}
+} // namespace
+
+TEST_CASE("Uniform stream reuse preserves data through mutation and session resets",
+          "[video_core]") {
+    using VideoCommon::BindSmallUniformReusing;
+    Memory memory;
+    Runtime runtime;
+    VideoCommon::ResetUniformStreamReuse<Runtime>();
+    auto bind = [&](size_t stage, u32 slot, u64 address, u32 size) {
+        Check(BindSmallUniformReusing(runtime, memory, stage, slot, slot, address, size),
+              "valid small uniform rejected");
+        CheckBound(runtime, memory, address, size);
+    };
+    bind(0, 0, 0, 64);
+    bind(0, 0, 0, 64);
+    Check(runtime.allocations.size() == 1, "identical bytes were copied twice");
+    memory.bytes[7] = 23;
+    bind(0, 0, 0, 64);
+    Check(runtime.allocations.size() == 2, "changed bytes reused stale data");
+    bind(0, 1, 0, 64);
+    bind(1, 0, 0, 64);
+    Check(runtime.allocations.size() == 4, "stage or slot shared the wrong allocation");
+    runtime.NextTick();
+    bind(0, 0, 0, 64);
+    Check(runtime.allocations.size() == 1, "a new command buffer reused an old allocation");
+    VideoCommon::ResetUniformStreamReuse<Runtime>();
+    bind(0, 0, 0, 64);
+    Check(runtime.allocations.size() == 2, "session reset retained an old allocation");
+    bind(4, 17, 0, 4096);
+    const auto before = runtime.allocations.size();
+    for (auto [stage, slot, size] :
+         {std::array<u32, 3>{5, 0, 64}, {0, 18, 64}, {0, 0, 0}, {0, 0, 4097}}) {
+        Check(!BindSmallUniformReusing(runtime, memory, stage, slot, slot, 0, size),
+              "invalid uniform range did not use the fallback");
+    }
+    Check(runtime.allocations.size() == before, "fallback allocated stream memory");
+
+    u32 random = 17;
+    for (u32 index = 0; index < 10000; ++index) {
+        random = random * 1664525U + 1013904223U;
+        if (index % 37 == 0)
+            runtime.NextTick();
+        if (index % 503 == 0)
+            VideoCommon::ResetUniformStreamReuse<Runtime>();
+        const u32 size = 1 + random % 4096;
+        const u64 address = (random >> 12) % (memory.bytes.size() - 4096);
+        if (index % 3 == 0)
+            memory.bytes[address + random % size] ^= u8{0x5a};
+        const size_t stage = (random >> 20) % 5;
+        const u32 slot = (random >> 24) % 18;
+        bind(stage, slot, address, size);
+        bind(stage, slot, address, size);
+    }
+}