-
Notifications
You must be signed in to change notification settings - Fork 1.4k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Use Abseil hash maps instead of std unordered containers for a huge speedup #4049
Comments
https://github.com/abseil/abseil-cpp license is Apache License 2.0. It is very permissive. |
https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ had some rather detailed comparisons recently, which seem to yield similar observations. |
Shall @maxGimeno propose a global plan with the introduction of |
abseil is rather inconvenient to use (without bazel or cmake): you need to link about 30 libraries to get a trivial example working 😞 |
@mglisse commented on Jul 4, 2019, 9:14 AM GMT+2:
Hopefully CGAL uses CMake. add_subdirectory(googletest)
add_subdirectory(abseil-cpp)
target_link_libraries(copy_polyhedron PRIVATE absl::flat_hash_map)
Our opting for Abseil will be conditional to a macro. With it we will easily be able to build benchmarks. Even users should be made aware of that, so that they can tune. |
As a header-only library, it doesn't matter what CGAL uses (if it uses anything at all). Providing CGALConfig.cmake does help. But users of CGAL don't all use cmake. |
@mglisse commented on Jul 4, 2019, 9:38 AM GMT+2:
We do not care. Abseil will be an optional dependency of CGAL, and our CMake users will get it almost for free. As for the others... they can do experiments and benchmarks using CMake, and them make the effort in their build system if the speedup is compelling. Actually, I do not get your point. Do you have a suggestion about an alternative? |
Just my two cents, it would be good to see a higher level CGAL algorithm than |
@mglisse commented on Jul 4, 2019, 9:14 AM GMT+2:
Actually, can you elaborate? Because on my machine abseil seems to require only the pthread support, and no other dependency. |
@afabri it concerns everything related to unordered maps, not only copy_face_graph(). |
The questions is if it has measurable impact on Mesh_3, Constrained_triangulation_2, Arrangement_2...... |
We will probably have to bench to be sure. But I have seen traces of unordered maps at least in Mesh_3 and Arrangements_on_surface_2, so there will probbaly be an impact. |
For at least one user of us, |
I didn't mean external dependencies. Using a trivial program:
Complete the command line with a minimal number of |
Just that abseil is a bit inconvenient to use, not as easy as using more Boost stuff for instance (even the parts that require linking with a library). I don't know yet if you plan to test for the presence of abseil or to include a copy of it.
Not particularly. Mael posted a link to a comparison between many implementations, some of which are header-only. They don't all have Google maintaining them though, and you may wish to use more stuff from abseil later. |
I would love to use the single-header implementation
|
@lrineau commented on Jul 4, 2019, 3:05 PM GMT+2:
I have artificially removed |
I don't remember if you tried recently to remove it, to see what breaks. But that's not the right place to discuss it. I guess constexpr is a context where gcc should ignore rounding modes...
The list also includes phmap, which is described as essentially a headerified version of abseil. |
Hi @lrineau, I've been experimenting with replacing the map in https://gist.github.com/GilesBathgate/3fb78d3949ca52f4d1a0d14dcc66ae23 Would this benefit from the |
The whole point of this issue is that std::unordered_map is slow, what did you expect? |
@mglisse 😂 Yes, But my reason for investigating it (prior to coming across this PR) was that in some cases, I've found anything other than For example here:
where visited only contains approximately 6 to 10 elements. The chained_map construction dominates the CPU usage, making O(1) lookup irrelevant probably a |
Hi Giles, I do not have the time to investigate on your issue. I hope others will, though. The best way to know if the Abseil hash maps can benefit your code is to try, anyway. |
@lrineau Thanks I've given it a try https://gist.github.com/GilesBathgate/3fb78d3949ca52f4d1a0d14dcc66ae23 @mglisse Abseil was 20% slower than |
@lrineau @mglisse I am getting good results with Updated gist: |
Did you try a flat_map for this one? (I know nothing about that code, and in particular not if the size of this container can ever be large) Such small maps are not a typical use case for hash maps, so many are probably not optimized for that case. The code you point to seems suboptimal, it calls Nice if robin hood works well, although if you want to change Unique_hash_map, which is used a lot in CGAL, and not just use a different map in one specific place, reviewers are likely to ask for various benchmarks, to make sure it doesn't regress some other use cases (bigger table, more expensive key, etc). But it seems quite possible that it is indeed faster all around. |
@mglisse Yes, I tried a Regarding |
If you know the maximum size of the hashmap, it is beneficial to call Also, as @mglisse said, the linked code looks suboptimal. E.g. |
... be wrapped in a std::queue, which could then use its default backend deque 😉 |
So this could be done: - CGAL::Unique_hash_map<SVertex_const_iterator,bool> visited(false);
+ robin_hood::unordered_flat_set<SVertex_const_iterator,Handle_hash_function> visited;
+ visited.reserve(number_of_svertices()); but unfortunately: cgal/Nef_3/include/CGAL/Nef_3/Vertex.h Lines 214 to 219 in 74af3e7
😞 |
@mglisse Presumably one can use |
Probably, but why? It would perform exactly the same iteration. |
Because I thought it was a random access iterator, so |
@mglisse Yes it can be large if you have a cone with 10,000 sides, the sphere_map of the apex will have 10,000 svertices. so visited would need that many elements. |
Issue Details
Inspired by one of the cppcon talks I listen to during my free time, I have quickly tried the hash maps from Abseil instead of
std::unordered_map
.My try was a modification of
copy_face_graph
:The results are stuning: now 3.2 seconds instead of 7.1 seconds
Source Code
The .cpp code: https://gist.github.com/2e9ea602a7b1e46cd34773611acac3c6
Here is the local patch to
CMakeLists.txt
(a non-clean hack):I had to checkout abseil and gtest:
I ran that modified
copy_polyhedron.cpp
ondemo/Polyhedron/data/man.off
, and as I said the speedup is huge: 3.2s after the patch to<CGAL/boost/graph/copy_face_graph.h>
, instead of 7.1s.Environment
-O3
The text was updated successfully, but these errors were encountered: