search

gltf-rs / gltf

A crate for loading glTF 2.0
Apache License 2.0
535 stars 124 forks source link

Fix Primitive::attributes serialization determinism issue #337

Closed kirdaybov closed 1 year ago

kirdaybov commented 2 years ago

HashMap uses a hash function that behaves differently based on the moment of the initialization of the program. That leads to the different iteration orders during serialization. Replacing HashMap with BTreeMap fixes the issue

kirdaybov commented 2 years ago

336

alteous commented 1 year ago

Hi, thanks for your PR. I have the exact same problem but I'm concerned replacing HashMap with BTreeMap might affect performance. Perhaps we could implement this as a feature option instead, something along the lines of deterministic_serialization.

kpreid commented 1 year ago

I'm concerned replacing HashMap with BTreeMap might affect performance.

The notable cost of a BTreeMap vs. HashMap is that it requires more pointer indirection to follow the tree nodes. But the value of the “B” constant actually used in Rust's BTreeMap is 6, meaning that the tree contains only one node unless there are more than 2*B - 1 = 11 entries (attributes) stored in it — which is the same amount of indirection a HashMap's storage needs too. So, this is unlikely to be a problem except for (1) very complex attribute sets (2) which are repeatedly accessed directly from the gltf data structure instead of iterated once and copied to the application's own data structure.

alteous commented 1 year ago

@kpreid, thanks for your input, the pointer indirection was indeed my concern. I assumed the B in BTreeMap stood for binary without looking any further into it. I stand corrected. 😄

It's unlikely the number of vertex attributes would exceed 11 so I see no issues merging as-is.

@kirdaybov, I apologise if my misunderstanding caused any frustration.

kirdaybov commented 1 year ago

No hard feelings ;)