Determinism through serialization cycle

[Uriopass]

I'm trying to make a replay system based on determinism. Actions on the world are saved in a replay and are applied on a hecs::World. Entity objects are stored separately in resources and serialized too.

I have a determinism problem demonstrated via the following code. If a world has gone through a serialization cycle, the entity allocation state is not serialized and therefore entity do not necessarily get the same IDs.

let mut w1 = World::new();
let e = w1.spawn((Comp,));
w1.despawn(e);

let w2 = deserialize(serialize(&w1)); // simplified for example

let e1 = w1.spawn((Comp,));
let e2 = w2.spawn((Comp,));

assert_eq!(e1, e2); // fail! generations don't match. 
// A longer example can also show a set of operations where the id (not the genration) doesn't match either
// since the freelist is not saved.

From what I understand, this is intended. What should I do if I want reproducible worlds that survive through serialization cycles? Is enough of hecs API publicly exposed to be able to do this? That is, doing operations1 -> ser -> deser -> operations2 results in the same World as operations1 -> operations2.

[adamreichold]

What about attaching a persistent ID to each entity which could then be used to match up the new transient entity ID after deserialization? Actions would of course also have to record persistent ID of the entities they were applied to.

[Uriopass]

I would find it disappointing that I must have extra state when the information is already there (entities already have unique ids). But you're right it might be more robust. I'm not sure how much magic would be required to make this work.

[Uriopass]

Iteration order might also change even with the persistent ids, but I don't know enough about hecs internals to check this.

[adamreichold]

One other thing that might help you if it applies to your use case at all: If you basically use the serialization support as a means to copy a world (instead of really persisting and loading it into another process), this could be implemented directly.

For example, in rs-ecs (which is based on hecs albeit simplified) we have World::clone to completely copy a World with all contained entities and components (assuming they can be cloned and the method of doing so has been registered with the given Cloner). This does preserve entity ID and iteration order and could most likely be directly ported to hecs. (In a future with stable specilization the interface would also become much simpler by specializing the internal clone function on the Clone and Copy traits.)

[Uriopass]

I'm using the serialization to do classical save/loading on the filesystem, but with the constraint that I'm building a replay system and I want to ensure determinism, so sadly cloning wouldn't help here.

[Ralith]

I recognize the usefulness of being able to save/restore allocator state for some applications. I don't think it costs us much to expose the freelist for folks to serialize if they really want; even if we have to break it in the future, the cost of doing so is small.

Would you also need generations to be assigned consistently before/after serialization? That might be a good chunk of additional data, and a bit harder to expose ergonomically.

[Uriopass]

How big would it really be? It's all about saving the IDs which aren't that big, no? I'd say generation is not that expensive and ensures 100% state restoration.

[Ralith]

Generations would double the amount of data (which is proportional to the high watermark of the number of entity's you've ever had concurrently live), and aren't conveniently laid out in a dense slice. Not a deal breaker, but would require a bit of thought to expose gracefully.

[ZagButNoZig]

Hey @Ralith I would be interested in this feature too. What additional data would we need to serialize to get deterministic serialization working?

I was looking trough the code and it seems like the "big thing" is to fully serialize the Entities struct inside world, to get consistent ids and generations.

To get a bit by bit identical world we would also in theory need to serialize the id field of the world, do you think that would be relevant?

Would we need to serialize any of the other members of world?

Thanks for the great work btw!

[Ralith]

Two additional pieces of data need to be exposed, both from the entity allocator

• The freelist: required to ensure entities are allocated in consistent order
• The generation counters of non-live entities: required to ensure allocated entities have the same generations

APIs are needed to both expose this information, and to allow it to be provided to a new world.

To get a bit by bit identical world we would also in theory need to serialize the id field of the world, do you think that would be relevant?

No, that ID's purpose is to only distinguish different World objects at runtime. Providing any way to set it would be unsafe.