Entity ID assignment

[someguynamedjosh]

I noticed that entity IDs are assigned randomly:

impl Entity {
    #[allow(missing_docs)]
    pub fn new() -> Self {
        Self(rand::random::<u32>())
    }

I'm concerned about this. I implemented the equations from the birthday paradox using this Python script:

import decimal

Dec = decimal.Decimal
decimal.getcontext().prec = 100

total_num_ids = Dec(2 ** 32)
num_spawned_entities = 1000

all_unique_ids_probability = Dec(1.0)
for item_index in range(0, num_spawned_entities):
    all_unique_ids_probability *= (total_num_ids - Dec(item_index)) / total_num_ids
duplicate_id_probability = Dec(1.0) - all_unique_ids_probability

print("{:.2f}".format(Dec(1.0) / duplicate_id_probability))

According to the results, a program that spawns 1000 entities will contain at least 1 duplicate ID every 8599.03 times it is run, on average. A more impractical application that spawns 10,000 entities will contain at least 1 duplicate ID every 86.41 times it is run. I'm currently experimenting with the Bevy engine and would be interested in creating a pull request to fix the problem. I am making this issue to collect any input from current project maintainers for things I should keep in mind or look out for as I am not particularly familiar with the codebase.

[someguynamedjosh]

I don't know if I'm missing anything, because in the documentation it says that entities that are living are guaranteed not to share an ID, but it doesn't seem like anything is done to guarantee this.

If the code does need to be changed, my main hangup is how to do it efficiently. The simple thing would be to have an Arc<Mutex<u32>> that is just incremented for each new entity. It would take 2^32 entity spawns to result in a duplicate ID (alternatively, spawning and then deleting 100 entities a second for 12,000 hours). However, I worry that it might be slow because of having to constantly lock and unlock the mutex.

[someguynamedjosh]

Nevermind, I just noticed this is included as part of #71.

[Ralith]

Just in case it wasn't clear, the code you're citing is from Bevy's fork; hecs assigns guaranteed-unique IDs, mediated via the internal Entities data structure. I don't intend to change that, in part for the reasons you describe. Thanks for the issue, though!

[Ratysz]

It bears mentioning that a recent development moved Bevy back to generational IDs.