Add index key for entities to improve use case performance

[damody]

Description

Add API can set key for entities, and use the key fast find entities
"specs::prelude::WorldExt" add function
fn find_entities(&self, key: T) -> Read
and add
fn create_entity_by_key(&mut self, key: T) -> EntityBuilder

Motivation

In open source game "veloren"
I usually see the code.

let entity_opt = (&ecs.entities(), &ecs.read_storage::<comp::Player>())
                .join()
                .find(|(_, player)| player.alias == player_alias)
                .map(|(entity, _)| entity);

Basically, any query from player will loop all entities to find alias equal query name.
If ecs has 10000 players. the design include performance bottleneck.

Drawbacks

• Is it a breaking change?
  no.
• Can it impact performance, learnability, etc?
  to improve performance for search specific entitie

Unresolved questions

I just learn this project. I think author group will give me a best solution.

---

Please indicate here if you'd like to work on this ticket once it's been approved. Feel free to delete this section if not.

[WaDelma]

You could always cache the results of that query (as in the entity), but yeah adding some kind of index could be beneficial. Easiest way to implement one would probably be a wrapper storage that handles updating the index data structure and provides index based lookup method.

[WaDelma]

Well actually you cannot: get_mut ruins it as it can update the value which the index is based on and one cannot get the final value.

[damody]

thanks your response.

[WaDelma]

I would still keep this open: I have an idea that might just work, but I have to experiment more. And there could be some other approaches too.

Edit: Apparently I don't have power to open issues :D

[WaDelma]

The approach would be to modify the trait so that you can return a wrapper type Wrapper<T> instead of &mut T. This maybe requires HKT which I think can be emulated in some form already without GAT. The wrapper type would then update the index data structure upon drop to reflect any changes.

My first idea was to have some global data structure and the wrapper type would contain index to it, but after thinking a while I think the wrapper type can just contain reference to the index data structure.

I am still not sure how this idea will work with rest of specs.