Paths

Table of Contentst

Use std::unordered_map, std::unordered_set for boost::unordered_map, boost::unordered_set, drop std::unary_function
ClosedPublic
Actions

Authored by elexis on Nov 24 2019, 11:35 PM.

Details

Reviewers: None
Commits: rP23191: Replace boost::unordered_map, boost::unordered_set with std::unordered_map, std…

Summary

When I Wanted to add an std::unordered_set to CGUI, I noticed it currently uses boost::unordered_set.
Wondering why it uses that and not std::unordered_set, I saw that the boost one was the predecessor and that it later (C++11) got added to std.
So it's basically historical ballast (it has negative weight since it requires another library dependency and mixing boost and std variants is confusing).

boost::unordered_set uses hash_value function, std::unordered_set uses a std::hash<T> class with an operator() function, otherwise the syntax and semantics are the same.

The replacement also drops std::unary_function which is marked as deprecated in C++11 and dropped in C++17.
https://en.cppreference.com/w/cpp/utility/functional/unary_function

This diff also drops the boost hash_combine function to avoid the lib dependency only for this function, to increase cohesiveness of the affected codebase,
and since the function is only seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);.
https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine

While at it, alphabetically sort the includes of the affected files and replace most typedef with using.

Test Plan

Notice that the code should have the same functionality, that it uses the same hashing functions and thus should not have an algorithmic complexity change.
The hash_value function to std::hash class change means that there is more instantiation going on, which is hopefully mitigated by storing helper std::hash class instances as private members of the std::hash instances used here. Otherwise blame the standard.

Diff Detail

Repository

rP 0 A.D. Public Repository

Lint

Automatic diff as part of commit; lint not applicable.

Unit

Automatic diff as part of commit; unit tests not applicable.

Event Timeline

elexis created this revision.Nov 24 2019, 11:35 PM

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/1158/display/redirect

Harbormaster failed remote builds in B10124: Diff 10414!Nov 24 2019, 11:36 PM

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/vs2015-differential/642/display/redirect

namespace for path.h

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/1159/display/redirect

Harbormaster failed remote builds in B10125: Diff 10415!Nov 25 2019, 12:14 AM

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/vs2015-differential/643/display/redirect

ugly namespace for all std::hash.

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/vs2015-differential/644/display/redirect

Successful build - Chance fights ever on the side of the prudent.

Linter detected issues:
Executing section Source...

source/tools/atlas/GameInterface/DeltaArray.h
|  21| template<typename·T>·class·DeltaArray2D
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.

source/graphics/FontManager.h
|  30| class·CFontManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCFontManager{' is invalid C code. Use --std or --language to configure the language.

source/graphics/MeshManager.h
|  31| class·CMeshManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCMeshManager{' is invalid C code. Use --std or --language to configure the language.

source/simulation2/Simulation2.h
|  45| class·CSimulation2
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCSimulation2{' is invalid C code. Use --std or --language to configure the language.

source/graphics/ShaderManager.h
|  41| class·CShaderManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCShaderManager{' is invalid C code. Use --std or --language to configure the language.

source/lib/adts/cache_adt.h
| 114| template<class·Entries>·float·ll_calc_min_credit_density(const·Entries&·entries)
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.

source/gui/CGUI.h
|  51| class·CGUI
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCGUI{' is invalid C code. Use --std or --language to configure the language.

source/lib/allocators/allocator_adapters.h
|  77| »   »   vm::Free(p,·size);
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'vm::Free' is invalid C code. Use --std or --language to configure the language.

source/ps/CStrIntern.h
|  37| class·CStrIntern
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCStrIntern{' is invalid C code. Use --std or --language to configure the language.

source/gui/GUIManager.h
|  42| class·CGUIManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCGUIManager{' is invalid C code. Use --std or --language to configure the language.

source/graphics/TextureManager.h
|  70| class·CTextureManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCTextureManager{' is invalid C code. Use --std or --language to configure the language.

source/lib/hash.h
|  29| template·<typename·T>
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.

source/lib/path.h
|  45| namespace·ERR
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'namespaceERR{' is invalid C code. Use --std or --language to configure the language.

source/simulation2/serialization/SerializeTemplates.h
|  33| template<typename·ELEM>
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.

source/graphics/ObjectBase.h
|  37| class·CObjectBase
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCObjectBase{' is invalid C code. Use --std or --language to configure the language.

source/ps/CStr.h
|  62| class·CStr:·public·std::tstring
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCStrW:' is invalid C code. Use --std or --language to configure the language.

source/ps/CStr.h
|  62| class·CStr:·public·std::tstring
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCStr:' is invalid C code. Use --std or --language to configure the language.

source/graphics/ShaderDefines.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/graphics/ShaderDefines.h
|  39| template<typename·value_t>
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.

source/graphics/ParticleManager.h
|  29| class·CParticleManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCParticleManager{' is invalid C code. Use --std or --language to configure the language.

source/simulation2/system/ComponentManager.h
|  39| class·CComponentManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCComponentManager{' is invalid C code. Use --std or --language to configure the language.

source/graphics/SkeletonAnimManager.h
|  38| class·CSkeletonAnimManager
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classCSkeletonAnimManager{' is invalid C code. Use --std or --language to configure the language.
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/1160/display/redirect

Harbormaster completed remote builds in B10126: Diff 10416.Nov 25 2019, 12:55 AM

Existing preference of std over boost:
rP18423 for Profiler2
rP19235 for ComponentManager
rP21867 for JSInterface_ConfigDB http://irclogs.wildfiregames.com/2018-08/2018-08-13-QuakeNet-%230ad-dev.log

Following clang warnings not pointed out by gcc:

In this patch (fixing by keeping use of struct):

../../../source/graphics/TextureManager.cpp:39:1: warning: 'TPhash' defined as a class here but previously declared as a struct; this is valid, but may result in linker errors under the Microsoft C++ ABI [-Wmismatched-tags]
class TPhash
^
../../../source/graphics/TextureManager.h:137:9: note: did you mean class here?
        friend struct TPhash;
               ^~~~~~
               class

Following rP9961:

../../../source/lib/res/h_mgr.cpp:99:18: warning: unused variable 'TAG_MASK' [-Wunused-const-variable]
static const u64 TAG_MASK = 0xFFFFFFFF; // safer than (1 << 32) - 1
                 ^
../../../source/lib/res/h_mgr.cpp:114:19: warning: unused function 'h_tag' [-Wunused-function]
static inline Tag h_tag(Handle h)
                  ^

In the existing code, not going to touch that now:

../../../source/lib/allocators/headerless.cpp:760:43: warning: 'Allocate' is missing exception specification '__attribute__((nothrow))' [-Wmissing-exception-spec]
NOTHROW_DEFINE void* HeaderlessAllocator::Allocate(size_t size)
                                          ^
                                                                __attribute__((nothrow))
../../../source/lib/allocators/headerless.h:79:24: note: previous declaration is here
        NOTHROW_DECLARE void* Allocate(size_t size);
                              ^
shared_ptr.cpp
1 warning generated.
unique_range.cpp
../../../source/lib/allocators/unique_range.cpp:70:21: warning: 'CallUniqueRangeDeleter' is missing exception specification '__attribute__((nothrow))' [-Wmissing-exception-spec]
NOTHROW_DEFINE void CallUniqueRangeDeleter(void* pointer, size_t size, IdxDeleter idxDeleter)
                    ^
                                                                                              __attribute__((nothrow))
../../../source/lib/allocators/unique_range.h:68:30: note: previous declaration is here
LIB_API NOTHROW_DECLARE void CallUniqueRangeDeleter(void* pointer, size_t size, IdxDeleter idxDeleter);

There was no introduction of a boost unordered container after the introduction of C++11 code in 0ad (rP23044 only added a missing include)

Any performance difference in using one of the other? I'm all for removing dependencies though.

In D2441#101896, @Stan wrote:

Any performance difference in using one of the other? I'm all for removing dependencies though.

(Just for the record I had written first half of the post already, I don't forget such a thing.)

For performance:

When I search for "boost::unordered_map vs std::unordered_map performance" I get "C++Now 2018: You Can Do Better than std::unordered_map ...". But that seems to be for containers with 32million elements, but there should be thousands or less here (entities, actors, files, components)
In D2258 std::map performed faster than std::unordered_map. The specs speak of logarithmic complexity for std::map and worst-case linear complexity (i.e. worse) for std::unordered_map (but average constant complexity, which would be faster).
In rP19235 / D82, std::map performed worse than std::unordered_map and was changed accordingly.
boost::flatmap may be an alternative over unordered_map, see https://www.boost.org/doc/libs/1_65_1/doc/html/boost/container/flat_map.html
This guy comparing boost against std implementation reported a 10x improvement by using boost::unordered_map, but it was because of the hashing algorithm, not because of the std/boost difference https://comp.lang.cpp.moderated.narkive.com/VPUab6if/performance-difference-between-std-unordered-map-and
D1739 proposes a custom SparseFlatMap container.

So we take away from that that it's not obvious which container is the best for performance.

Hence looking at all the code changed to identify the most performance crucial parts of the code.

Most places use the unordered container to keep track of which files had been loaded already. Those should not be so relevant, since files are not loaded that often, nor considered to be loaded often.
ConstructComponent happens mostly when loading a map, but also when creating new entities during the game, so that's not irrelevant for performance.
The MeshManager m_MeshMap is accessed only by CMeshManager::GetMesh, which is only called from CObjectEntry::BuildVariation, if Im not mistaken only called when setting the visualactor.

So I did an exemplary measurement with the MeshManager. PROFILER3 didn't show anything in the profiler.txt and the Profiler2 WebUI is not feasible for comparison of many data points.

I measured the nanoseconds per find call using std::chrono, debug_printf, started a skirmish map, wrote out the performacne results, repeated thrice.
Then I reverted MeshManager.h change (using this diff:

Index: source/graphics/MeshManager.cpp
===================================================================
--- source/graphics/MeshManager.cpp	(revision 23188)
+++ source/graphics/MeshManager.cpp	(working copy)
@@ -40,12 +40,21 @@ CMeshManager::~CMeshManager()
 
 CModelDefPtr CMeshManager::GetMesh(const VfsPath& pathname)
 {
 	const VfsPath name = pathname.ChangeExtension(L"");
 
+	mesh_map::iterator iter;
 	// Find the mesh if it's already been loaded and cached
-	mesh_map::iterator iter = m_MeshMap.find(name);
+	{
+		auto start = std::chrono::system_clock::now();
+		iter = m_MeshMap.find(name);
+        auto end = std::chrono::system_clock::now();
+
+        std::chrono::nanoseconds ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
+        debug_printf("m_MeshMap.find %s %lu\n", pathname.string8().c_str(), ms.count());
+	}
+
 	if (iter != m_MeshMap.end() && !iter->second.expired())
 		return CModelDefPtr(iter->second);
 
 	PROFILE("load mesh");
 
Index: source/graphics/MeshManager.h
===================================================================
--- source/graphics/MeshManager.h	(revision 23188)
+++ source/graphics/MeshManager.h	(working copy)
@@ -26,10 +26,22 @@
 class CModelDef;
 typedef std::shared_ptr<CModelDef> CModelDefPtr;
 
 class CColladaManager;
 
+namespace boost {
+
+template<>
+struct hash<Path> : std::unary_function<Path, std::size_t>
+{
+	std::size_t operator()(const Path& path) const
+	{
+		return hash_value(path.string());
+ 	}
+};
+}
+
 class CMeshManager
 {
 	NONCOPYABLE(CMeshManager);
 public:
 	CMeshManager(CColladaManager& colladaManager);

wrote out the results, repeated thrice, then plotted the results for comparison.

I made the mistake to not replay the match, there were different civs and thus different models, however for the first and third replay the civs match.

Libreoffice excelthing file:

perf.ods134 KBDownload

The results are indistinguishable performance, thanks for nothing at the cost of wasted hours.
Someone who wants to optimize performance can do so, this is not the objective of this diff (but rather to make it possible to add an unordered map to source/gui/ without having both boost and std variant in the same file and without using the boost variant needlessly).

For replay 1 and 3 where civs seem to be correlating the graphs are literally identical.
For replay 2, there is exactl 1 lagspike in both of them.

Also I didn't ensure that the cache was prebuilt in both cases, however I won't invest more time for this now.

This revision was not accepted when it landed; it landed in state Needs Review.Nov 25 2019, 3:30 PM

Closed by commit rP23191: Replace boost::unordered_map, boost::unordered_set with std::unordered_map, std… (authored by elexis). · Explain Why

This revision was automatically updated to reflect the committed changes.

elexis added a commit: rP23191: Replace boost::unordered_map, boost::unordered_set with std::unordered_map, std….

Owners added subscribers: Restricted Owners Package, Restricted Owners Package, Restricted Owners Package.Nov 25 2019, 3:30 PM

Thanks for the patch and the detailed answer. I just wanted to make sure we were not doing something wrong by replacing those.