Support for Unique hash map?

[GilesBathgate]

As discussed on https://github.com/CGAL/cgal/issues/4049 I am investigating using robin_hood::unordered_map for a unique hash map. A Unique hash map is a specialization on insertion only and unique hash values allow for a more time and space-efficient implementation. In the case of the implementation in CGAL the memory addresses of Handle objects are used for key-hashes and therefore by their very nature there cannot be duplicates/collisions.

The CGAL implementation suffers from poor construction speed due to the default hardcoded table size of 512, and this is what I hope to improve by using robin_hood::unordered_map. However the insert speed of the CGAL::Unique_hash_map does seem to outperform by a factor of 0.2, as can be seen in my benchmark project https://github.com/GilesBathgate/hashmap-benchmarks

What I'd like to establish is whether improvements can be made to either CGAL::Unique_hash_map that would facilitate faster construction, or whether robin_hood::* can be improved with the techniques used in the CGAL implementation.

I realise that the main purpose of robin hood hashing is to handle the case when there are duplicate keys, so perhaps its not the best candidate. Are there any other faster hash map implementations that can be used for a unique hash map that would be more suitable?

[martinus]

Had a quick look at your benchmark, and I do not think this is a realistic benchmark.

You are sequentially inserting consecutive numbers. Is that really what's happening in CGAL? robin_hood map is optimized for random insertion.

[GilesBathgate]

@martinus I've updated the benchmark to use handles, the performance gain is much smaller now.

[martinus]

insert benchmark should probably also clear the map, or you are constantly reinserting elements that are already there.

reserve could use a map.reserve(handles.size()) to initially already get to the correct size.

Map specialization might work with

using Map = robin_hood::unordered_node_map<Handle, int>; using Map = robin_hood::unordered_flat_map<Handle, int>;

So not using CGAL::Handle_hash_function, but robin_hood's hash. If that's not working you might need to do

using Map = robin_hood::unordered_node_map<Data, int>; using Map = robin_hood::unordered_flat_map<Data, int>;

Other than that, not much you can do in the benchmark. I would though test with real data if possible

[GilesBathgate]

insert benchmark should probably also clear the map, or you are constantly reinserting elements that are already there. reserve could use a map.reserve(handles.size()) to initially already get to the correct size.

@martinus Yeah this was the problem with the benchmark. insert is now faster using robin_hood. However, I've added an update benchmark and this is still slower than the Unique_hash_map. (probably I did something else wrong :joy:)

[GilesBathgate]

@martinus Using -O2 pushes everything in favour of robin_hood

[martinus]

:man_facepalming: :smile:

[GilesBathgate]

@martinus Sorry to bother you again. I did a comparison between std::unordered_map's try_emplace vs the robin_hood::unordered_node_map version and I am seeing slower performance for robin hood. Probably I did something else wrong but I am not sure what.

https://github.com/GilesBathgate/hashmap-benchmarks/tree/robin-hood-vs-unordered-map

[martinus]

Please try to do some real world benchmarks. If these still show that std::unordered_map is better, then there is no reason to use robin_hood map.

[GilesBathgate]

@martinus Well this is "real world" in the sense that CGAL is creating a map between a memory address and some integer. But I will try to create a better benchmark. Thanks.

[martinus]

I mean a benchmark often only makes sense when it operates on real data, and in real "environment". The surrounding code is important too. Compilers are sneaky and can do strange tricks, especially in microbenchmarks.

[GilesBathgate]

@martinus Thanks again. These benchmarks are showing a slight improvement in favour of robin_hood https://github.com/CGAL/cgal/pull/5484#issuecomment-782870345 . But as I said, there are probably other areas of the CGAL codebase to investigate performance gains.

[martinus]

I can highly recommend Hotspot to find performance issues: https://github.com/KDAB/hotspot