openmw.org

I've been brainstorming some small things to do for my first contribution to OpenMW. I noticed that std::map is used frequently in the codebase, so I thought I'd bring this up.

One of the additions in C++11 is the std::unordered_map, which is a hash table, unlike std::map, which is a tree. An unordered map should almost always be faster due to the comparatively fast speed of a hash lookup versus doing multiple comparisons in an ordinary map.

One concern would be with maps that depend on ordered iteration, because unordered maps store their elements in no particular order. There are also a couple other things to consider like explicit std::hash definitions for certain types (std::pair, enum class, etc.), but we could probably leave those more complex ones alone.

So the general idea is that it would make search operations like std::map<std::string, ...>::find() faster. Is this change something that would be desirable, or are std::maps good enough for now? Would the change in performance even be noticeable?

What's the performance difference when initializing an unordered_map, and is that ever done during runtime? I'm not an expert on the standard library, but initializing a hashtable should be farrrr slower than initializing a tree (I guess unless the entire set of data is initialized at the same time? in which case a tree could still be pretty slow? again, not an expert...), and should take up far more memory, if they are implemented normally. You're right that a lookup will be faster, but it could be a tradeoff.

Run a profiler like callgrind and if you see any overhead where maps are used we can think about replacing those in particular... if that's not the case then this is just speculation or in other words a waste of time.

scrawl wrote: ↑07 Nov 2017, 20:10 Run a profiler like callgrind and if you see any overhead where maps are used we can think about replacing those in particular... if that's not the case then this is just speculation or in other words a waste of time.

Right. I was just curious about whether this was something worth investigating in the first place. I haven't made any changes to the codebase yet, and I am aware that some C++11 "upgrades" should be ignored, so I wasn't sure if changing maps to unordered maps fell under that particular umbrella.

I'll look into getting OpenMW built on my machine, although I'm on Windows, so I'd have to find an alternative to Callgrind. Maybe there are a couple other small things I could look into as well, like some typos and simplifying some lerp calculations.

At risk of going against my own advice, I just want to mention that maps are used in ObjectCache/MultiObjectCache which forms the base of the entire resources system, so this one might be worth looking into. I'm just not sure if lookup or insertion is more common here.

I'd definitely be interested in a benchmark for this (especially with 'distant terrain' and 'cell preloading' enabled which adds additional resource usage).

Another option to consider is a flat map (not in C++ standard, but easy to implement). It's basically a sorted vector of objects keyed on some field in the object (which can be a hash value, a hash of a field, or a direct object like a string or int). Implementations I've made have O(log n) lookup complexity like a map, but is far more efficient to iterate over since it's all consecutive (at the cost of insertion and deletion which needs to move objects after the insertion or deletion point). There are other ways to implement hash maps that may be a bit more efficient overall, though: https://www.youtube.com/watch?v=ncHmEUmJZf4

Chris wrote: ↑08 Nov 2017, 04:17 Another option to consider is a flat map (not in C++ standard, but easy to implement).

It was interesting to hear someone in that video say that std::unordered_map has been "known to be slow for many years" (compared to custom hash tables). That says a lot about std::map, too. I do like your suggestion, Chris, but this was kind of my way of getting my feet wet with the OpenMW codebase, so I think I want to stick with trivial replacements for the time being .

I was able to build OpenMW and I can walk around in the world just fine. In terms of profiling, I built it on RelWithDebInfo and ran the VS2015 performance profiler, but I wasn't really seeing any interesting results -- i.e., after searching the call tree, I only found a couple dozen calls to Resource::ObjectCache/std::unordered_map functions, not hundreds like I was expecting, so I haven't been able to make any judgements yet. Maybe someone with more experience with profiling tools on Windows could point me in the right direction?