Skip to content
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.

Sign up for GitHub

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

Jump to bottom

CesiumGltf objects stored in a vector get copied rather than moved on resize #375

Open
kring opened this issue Oct 29, 2021 · 3 comments · May be fixed by #537
Open

CesiumGltf objects stored in a vector get copied rather than moved on resize #375

kring opened this issue Oct 29, 2021 · 3 comments · May be fixed by #537
Labels
performance Improvements to performance, including reductions in memory usage

Comments

@kring
Copy link
Member

kring commented Oct 29, 2021

Most CesiumGltf objects inherit from ExtensibleObject, and that class has two fields, one a JsonValue::Object (AKA a std::map) and the other a std::unordered_map. Neither of these types has a move constructor that is declared noexcept. At least in Visual Studio 2017. Why? Because the standard doesn't require it. For reasons, apparently: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

That's really painful when these objects are stored in a std::vector. When we add a new item to a vector and it doesn't have the capacity, it allocates a new array and moves all the existing items into the new array. Except that's not quite true. It only moves the items into the new array if the item type has a noexcept move constructor. Otherwise, it copies them. And our CesiumGltf types don't have a noexcept move constructor. So our objects get copied instead.

That's super painful for CesiumGltf, because it uses vectors a lot and it has big chunks of data that are expensive to copy. If we add a new Buffer to model.buffers and it triggers a vector realloc, that will cause every byte of data in every existing buffer to be copied! 😱

Again, this is in Visual Studio 2017. I'm not sure about 2019. Based on a table linked from the StackOverflow question above, neither libc++ nor libstdc++ have this problem.

I'm not entirely sure what to do about this, but a couple of options off the top of my head:

  • Ignore it and hope it goes away (maybe it already has in VS 2019, but we're stuck with 2017 a little longer for Unreal)
  • Use other containers that don't have this problem to replace Microsoft's std::map and std::unordered_map.
  • I think potentially we could hackily declare things noexcept that aren't and let our program die if an allocation fails, which is probably what it's going to do pretty soon anyway in this situation if we're honest with ourselves.

I happened to notice this because I was doing dodgy things that would have worked if the move was happening, but instead I got a copy and that caused a crash. Took me awhile to figure out why.
@kring kring added the performance Improvements to performance, including reductions in memory usage label Oct 29, 2021
@lilleyse
Copy link
Contributor

Use other containers that don't have this problem to replace Microsoft's std::map and std::unordered_map.

This could be another reason to write our own vector-backed map class, CC #372 (comment).

@kring kring mentioned this issue May 31, 2022
Open
30 tasks
@kring
Copy link
Member Author

kring commented Aug 2, 2022

As mentioned in the issue Sean linked above, take a look at Tessil's ordered_map:
https://github.com/Tessil/ordered-map

The order preservation is a nice feature, and the improved insertion performance reduced memory usage compared to std::unordered_map is nice as well. I'm not certain if it has a noexcept move constructor... hopefully!

@joseph-kaile
Copy link
Collaborator

Using the code in the stack overflow link, is_nothrow_move_constructible<C>::value, the Tessil ordered map is not nothrow move constructible. However, the hash map (https://github.com/greg7mdp/parallel-hashmap) is no throw move constructible.

In the branch https://github.com/CesiumGS/cesium-native/tree/phmap-replacement, I replaced all std::unordered_map and std::map with phmap::flat_hash_map. The map is also replaced with a hash map because replacing with phmap::btree_map runs into difficult compile errors.

Next, to test the performance of the two, I loaded all the models in GLTF-Samples (https://github.com/KhronosGroup/glTF-Sample-Models). The time for std::unordered_map was around 4.2 seconds. The time for phmap was 3.8 milliseconds. My conclusion is that the phmap is only slightly faster than unordered map in most cases.

Only in one case the difference was dramatic. I loaded one GLTF model, and then made 50,000 copies, pushing each one to a vector. phmap took around 30 seconds, std::unordered_map took 6 minutes.

Cesium-unreal also works and didn't need to be modified.

@joseph-kaile joseph-kaile linked a pull request Aug 4, 2022 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
performance Improvements to performance, including reductions in memory usage
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Replace std::unordered_map and std::map with Parallel Hashmap CesiumGS/cesium-native
3 participants
@lilleyse @kring @joseph-kaile