Use tsl::robin_map and tsl::robin_set

Replace std::unordered_map and std::unordered_set with the above.
Better performance profile.

10 files changed, 68 insertions, 27 deletions

diff --git a/README.md b/README.md
index 23a925b7..d06718a7 100644
--- a/README.md
+++ b/README.md
@@ -274,6 +274,32 @@ AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
 OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 ```
 
+### robin-map
+
+```
+MIT License
+
+Copyright (c) 2017 Thibaut Goetghebuer-Planchon <[email protected]>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+```
+
 ### xbyak
 
 ```
diff --git a/externals/CMakeLists.txt b/externals/CMakeLists.txt
index def524b1..afdf1656 100644
--- a/externals/CMakeLists.txt
+++ b/externals/CMakeLists.txt
@@ -2,11 +2,29 @@
 # simply add the directory to that file as a subdirectory
 # to have CMake automatically recognize them.
 
+# catch
+
+add_library(catch INTERFACE)
+target_include_directories(catch INTERFACE $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/catch>)
+
+# fmt
+
 if (NOT DYNARMIC_NO_BUNDLED_FMT)
     # fmtlib formatting library
     add_subdirectory(fmt)
 endif()
 
+# mp
+
+add_library(mp INTERFACE)
+target_include_directories(mp INTERFACE $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/mp/include>)
+
+# robin-map
+
+add_subdirectory(robin-map)
+
+# xbyak
+
 if (NOT TARGET xbyak)
     if (ARCHITECTURE_x86 OR ARCHITECTURE_x86_64)
         add_library(xbyak INTERFACE)
@@ -14,11 +32,3 @@ if (NOT TARGET xbyak)
         target_compile_definitions(xbyak INTERFACE XBYAK_NO_OP_NAMES)
     endif()
 endif()
-
-add_library(catch INTERFACE)
-target_include_directories(catch INTERFACE
-                           $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/catch>)
-
-add_library(mp INTERFACE)
-target_include_directories(mp INTERFACE
-                           $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/mp/include>)
diff --git a/externals/README.md b/externals/README.md
index 49362f5c..78d9cd57 100644
--- a/externals/README.md
+++ b/externals/README.md
@@ -3,9 +3,10 @@ This repository uses subtrees to manage some of its externals.
 ## Initial setup
 
 ```
-git remote add externals-fmt https://github.com/fmtlib/fmt.git
-git remote add externals-mp https://github.com/MerryMage/mp.git
-git remote add externals-xbyak https://github.com/herumi/xbyak.git
+git remote add externals-fmt https://github.com/fmtlib/fmt.git --no-tags
+git remote add externals-mp https://github.com/MerryMage/mp.git --no-tags
+git remote add externals-robin-map https://github.com/Tessil/robin-map.git --no-tags
+git remote add externals-xbyak https://github.com/herumi/xbyak.git --no-tags
 ```
 
 ## Updating
@@ -15,8 +16,10 @@ Change `<ref>` to refer to the appropriate git reference.
 ```
 git fetch externals-fmt
 git fetch externals-mp
+git fetch externals-robin-map
 git fetch externals-xbyak
 git subtree pull --squash --prefix=externals/fmt externals-fmt <ref>
 git subtree pull --squash --prefix=externals/mp externals-mp <ref>
+git subtree pull --squash --prefix=externals/robin-map externals-robin-map <ref>
 git subtree pull --squash --prefix=externals/xbyak externals-xbyak <ref>
 ```
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index d37aebef..55eb0dfc 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -340,6 +340,7 @@ target_link_libraries(dynarmic
         boost
         fmt::fmt
         mp
+        tsl::robin_map
         xbyak
         $<$<BOOL:DYNARMIC_USE_LLVM>:${llvm_libs}>
 )
diff --git a/src/backend/x64/a32_emit_x64.cpp b/src/backend/x64/a32_emit_x64.cpp
index 6010a798..d90c637d 100644
--- a/src/backend/x64/a32_emit_x64.cpp
+++ b/src/backend/x64/a32_emit_x64.cpp
@@ -5,7 +5,6 @@
 
 #include <algorithm>
 #include <optional>
-#include <unordered_map>
 #include <utility>
 
 #include <fmt/format.h>
diff --git a/src/backend/x64/a32_emit_x64.h b/src/backend/x64/a32_emit_x64.h
index 20bb0780..b5272491 100644
--- a/src/backend/x64/a32_emit_x64.h
+++ b/src/backend/x64/a32_emit_x64.h
@@ -9,7 +9,8 @@
 #include <optional>
 #include <set>
 #include <tuple>
-#include <unordered_map>
+
+#include <tsl/robin_map.h>
 
 #include <dynarmic/A32/a32.h>
 #include <dynarmic/A32/config.h>
@@ -91,7 +92,7 @@ protected:
         u64 callback;
         DoNotFastmemMarker marker;
     };
-    std::unordered_map<u64, FastmemPatchInfo> fastmem_patch_info;
+    tsl::robin_map<u64, FastmemPatchInfo> fastmem_patch_info;
     std::set<DoNotFastmemMarker> do_not_fastmem;
     std::optional<DoNotFastmemMarker> ShouldFastmem(A32EmitContext& ctx, IR::Inst* inst) const;
     FakeCall FastmemCallback(u64 rip);
diff --git a/src/backend/x64/block_range_information.cpp b/src/backend/x64/block_range_information.cpp
index 3633e575..4dab5f05 100644
--- a/src/backend/x64/block_range_information.cpp
+++ b/src/backend/x64/block_range_information.cpp
@@ -3,10 +3,9 @@
  * SPDX-License-Identifier: 0BSD
  */
 
-#include <unordered_set>
-
 #include <boost/icl/interval_map.hpp>
 #include <boost/icl/interval_set.hpp>
+#include <tsl/robin_set.h>
 
 #include "backend/x64/block_range_information.h"
 #include "common/common_types.h"
@@ -24,8 +23,8 @@ void BlockRangeInformation<ProgramCounterType>::ClearCache() {
 }
 
 template <typename ProgramCounterType>
-std::unordered_set<IR::LocationDescriptor> BlockRangeInformation<ProgramCounterType>::InvalidateRanges(const boost::icl::interval_set<ProgramCounterType>& ranges) {
-    std::unordered_set<IR::LocationDescriptor> erase_locations;
+tsl::robin_set<IR::LocationDescriptor> BlockRangeInformation<ProgramCounterType>::InvalidateRanges(const boost::icl::interval_set<ProgramCounterType>& ranges) {
+    tsl::robin_set<IR::LocationDescriptor> erase_locations;
     for (auto invalidate_interval : ranges) {
         auto pair = block_ranges.equal_range(invalidate_interval);
         for (auto it = pair.first; it != pair.second; ++it) {
diff --git a/src/backend/x64/block_range_information.h b/src/backend/x64/block_range_information.h
index 82422f93..7d2d4f28 100644
--- a/src/backend/x64/block_range_information.h
+++ b/src/backend/x64/block_range_information.h
@@ -6,10 +6,10 @@
 #pragma once
 
 #include <set>
-#include <unordered_set>
 
 #include <boost/icl/interval_map.hpp>
 #include <boost/icl/interval_set.hpp>
+#include <tsl/robin_set.h>
 
 #include "frontend/ir/location_descriptor.h"
 
@@ -20,7 +20,7 @@ class BlockRangeInformation {
 public:
     void AddRange(boost::icl::discrete_interval<ProgramCounterType> range, IR::LocationDescriptor location);
     void ClearCache();
-    std::unordered_set<IR::LocationDescriptor> InvalidateRanges(const boost::icl::interval_set<ProgramCounterType>& ranges);
+    tsl::robin_set<IR::LocationDescriptor> InvalidateRanges(const boost::icl::interval_set<ProgramCounterType>& ranges);
 
 private:
     boost::icl::interval_map<ProgramCounterType, std::set<IR::LocationDescriptor>> block_ranges;
diff --git a/src/backend/x64/emit_x64.cpp b/src/backend/x64/emit_x64.cpp
index 8a335a31..4e3f9b48 100644
--- a/src/backend/x64/emit_x64.cpp
+++ b/src/backend/x64/emit_x64.cpp
@@ -4,7 +4,8 @@
  */
 
 #include <iterator>
-#include <unordered_map>
+
+#include <tsl/robin_set.h>
 
 #include "backend/x64/block_of_code.h"
 #include "backend/x64/emit_x64.h"
@@ -305,7 +306,7 @@ void EmitX64::ClearCache() {
     PerfMapClear();
 }
 
-void EmitX64::InvalidateBasicBlocks(const std::unordered_set<IR::LocationDescriptor>& locations) {
+void EmitX64::InvalidateBasicBlocks(const tsl::robin_set<IR::LocationDescriptor>& locations) {
     code.EnableWriting();
     SCOPE_EXIT { code.DisableWriting(); };
 
diff --git a/src/backend/x64/emit_x64.h b/src/backend/x64/emit_x64.h
index 1a50c468..c81899f9 100644
--- a/src/backend/x64/emit_x64.h
+++ b/src/backend/x64/emit_x64.h
@@ -9,10 +9,11 @@
 #include <optional>
 #include <string>
 #include <type_traits>
-#include <unordered_map>
-#include <unordered_set>
 #include <vector>
 
+#include <tsl/robin_map.h>
+#include <tsl/robin_set.h>
+
 #include <xbyak_util.h>
 
 #include "backend/x64/exception_handler.h"
@@ -69,7 +70,7 @@ public:
     virtual void ClearCache();
 
     /// Invalidates a selection of basic blocks.
-    void InvalidateBasicBlocks(const std::unordered_set<IR::LocationDescriptor>& locations);
+    void InvalidateBasicBlocks(const tsl::robin_set<IR::LocationDescriptor>& locations);
 
 protected:
     // Microinstruction emitters
@@ -115,8 +116,8 @@ protected:
     // State
     BlockOfCode& code;
     ExceptionHandler exception_handler;
-    std::unordered_map<IR::LocationDescriptor, BlockDescriptor> block_descriptors;
-    std::unordered_map<IR::LocationDescriptor, PatchInformation> patch_information;
+    tsl::robin_map<IR::LocationDescriptor, BlockDescriptor> block_descriptors;
+    tsl::robin_map<IR::LocationDescriptor, PatchInformation> patch_information;
 };
 
 } // namespace Dynarmic::Backend::X64