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

[kring]

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.

[lilleyse]

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 https://github.com/CesiumGS/cesium-native/pull/372#issuecomment-952539065.

[kring]

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]

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.