Sfml: Performance: Replace std::map with std::unordered_map

[dbechrd]

SFML is using trees instead of hash tables in many places

I was profiling my SFML app and noticed this:

https://github.com/SFML/SFML/blob/b762276a27efac365968c8330bdb0b5cca44bf52/include/SFML/Graphics/Font.hpp#L332 https://github.com/SFML/SFML/blob/b762276a27efac365968c8330bdb0b5cca44bf52/include/SFML/Graphics/Font.hpp#L392

Both GlyphTable and PageTable should be unordered_map. Ordered iteration is not required by the Font class, and this causes sf::Font::GetGlyph to be much slower than is necessary.

There are numerous other instances of std::map in the SFML codebase at a quick glance. Most or all of them could likely be replaced with std::unordered_map for noticeable performance gains.

[LaurentGomila]

Can you do the modification, and show us the results using your profiler?

[Bromeon]

Probably needless to say, but make sure you profile in Release mode and without Debugger running (these are two independent settings in MSVC).

Also, this should probably become part of the C++17 solution design. I would even go as far as saying that after C++11, std::unordered_map should be the default choice for key-value stores, not std::map. That's also what virtually every other programming language on this planet does.

[dbechrd]

I spent a few minutes trying to get SFML build, but was getting a bunch of errors. I don't entirely know how to configure it correctly. I generally just use the pre-built binaries for VS 2019 from the "Releases" section on Github so that I don't have to fiddle around with CMake.

You can set up a simple test case yourself by just rendering an sf::Text string to the window with a large enough number of characters for GetGlyph to show up in your profiler (100-200 should be plenty, more if you want to stress test it). The profiler in the screenshot above is Intel VTune, which is freely available here (https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/vtune-profiler.html).

The exact performance numbers are obviously going to depend on the code and hardware, but you don't need to profile to know that std::unordered_map is O(1) amortized and std::map is O(log N). It would be more valuable for the SFML team to use their own code and hardware, rather than depend on my results, so that you can perform consistent benchmarks across future versions and changes.

[Bromeon]

The exact performance numbers are obviously going to depend on the code and hardware, but you don't need to profile to know that std::unordered_map is O(1) amortized and std::map is O(log N).

Of course, although scale matters. For a few dozen objects, the difference between hash maps and tree maps may not be visible. There's also other factors, like quality of the hash/compare function, insertion/deletion/read patterns, etc. But I agree that unordered_map is a reasonable default choice. With std::vector it's similar: it's almost always the right choice. Its cache friendlyness and fast random access are so significant that it often outperforms alternatives, even if the O-numbers speak against it.

The Rust developers realized this and advertise it in the documentation:

To get this out of the way: you should probably just use Vec or HashMap. These two collections cover most use cases for generic data storage and processing. They are exceptionally good at doing what they do. All the other collections in the standard library have specific use cases where they are the optimal choice, but these cases are borderline niche in comparison. Even when Vec and HashMap are technically suboptimal, they're probably a good enough choice to get started.

Use a LinkedList when:

• ...
• You are absolutely certain you _really, truly_, want a doubly linked list.

NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.

[dbechrd]

Of course, although scale matters. For a few dozen objects, the difference between hash maps and tree maps may not be visible.

Sure. Consider an sf::Text object with 100 characters. That's 200 map lookups. If we assume the user is only using one characterSize and ignore the m_pages lookups, then it's only 100 map lookups. If outlineThickness, bold and character index are all consistent, there likely won't be many more than ~60 glyphs in the GlyphTable (English, lower/upper/symbols). Log2(60) is still ~6 accesses (and potential cache misses) per getGlyph call vs. one access for an unordered_map. Probably not the slowest thing in your app (especially if you're drawing sf::Sprites and not batching them, which was the first major bottleneck in my code), but it's free gains.

[ayaankhan98]

Of course, although scale matters. For a few dozen objects, the difference between hash maps and tree maps may not be visible. There's also other factors, like quality of the hash/compare function, insertion/deletion/read patterns, etc. But I agree that unordered_map is a reasonable default choice.

Yes, you are right there are other factors which becomes important in performance comparision of std::map and std::unordered_map. The problem is we cannot test the performance over all possible cases. I mean the performance depeneds on the data fed to the data structure. In most of the cases it turns out unordered_map are fast and offers O(1) access. Whereas in some other cases the performance of unordered_map may be equal to map or even wort than map (if large number of collisons occurs). Replacing map with unordered_map is worth improvement in performance for almost all cases.

[eliasdaler]

I'd say if C++11 was used when SFML was originally written, you'd need to prove that you really need std::map over std::unordered_map. So ideally I'd like to see all instances of std::map replaced to std::unoredered_map unless the order of elements really matters and we gain something by having elements be sorted.

[Bromeon]

I think we all agree here 🙂

As I wrote, TLDR:

But I agree that unordered_map is a reasonable default choice.

[ayaankhan98]

I think we all agree here 🙂

As I wrote, TLDR:

But I agree that unordered_map is a reasonable default choice.

Yes, should i make a PR, updating all the instances of std::map with std::unorderd_map?

[Bromeon]

Before you jump right into this, we would like to iron out the C++17 solution design a bit, so it becomes clear in what direction SFML should go, and which guidelines to use for migrations. This aims to communicate clearly what is in scope and what not, and would avoid lengthy discussions in each C++17 related issue.

I'll try to take care of that within the next days.