Legion ECS Discussion

(Théo Degioanni) #21

Excellent idea!

Scripting would work in specs without too much work. What Frizi is describing is how once your components are statically declared in specs, you cannot access them as flexibly as you could in their development-time form. This is not an issue for scripting itself as dynamic dispatcher rebuild and conditional dependencies are a development-time thing. I would need to know more about Frizi’s engine use case to give an opinion on how feasible specs is for their specific use case, but it is not related to scripting.

However I do agree that legion would give more advantages on those aspects, especially on that first point which to me is extremely important and extremely difficult to achieve without locking all the time in specs. But this is outside the scope of scripting.

TL; DR: scripting can work in specs if we want it to.

2 Likes
(OvermindDL1) #22

I just took a look at legion and I have a question:

This sounds exceptionally bad for an ECS library. I add and remove components very rapidly, all the time, all over the place, and this seems backwards from how it is traditionally done… Just how much ‘significantly slower’ is it and why? If it is baking component ‘sets’ into arrays then that sounds more like a dataflow system than ECS, which is fine, but it’s not ECS.

1 Like
(Zicklag) #23

From the Discord conversation:

Ayfid

It is optimised for entity creation, deletion and iteration speed. Dynamically adding and removing components from existing entities is supported but slow. You can generally design game code around avoiding the need to do component addition/removal outside of entity creation, but you cannot avoid creating, deleting or iterating through entities; those are the core functions of an ECS.

I do not think adding/removing components to existing entities is nearly as high a priority as creation and iteration speed

As far as I understand it, it is slower because of the chunked design of the entity storage, which is part of where it gets its speed everywhere else.

If you needed to add and remove components on an entity I would imagine you could add a boolean enabled field to the component and ignore any non-enabled components in the systems that use it.

(OvermindDL1) #24

That wouldn’t really work. In my old engine I add/remove components rapidly for determining things such as status effects, query information, etc… etc… and tend to number in the hundreds of components. Having all of those enabled on every possible entity that might have them, which tend to be in the hundreds of thousands of entities or far more), sounds like an exceptionally large waste of memory and processing.

(OvermindDL1) #25

The ‘chunked’ design that keeps being referenced looks like a classic dataflow pattern rather than ECS, and dataflow is exceptionally useful and fast, but it is not ‘dynamic’ in the realm that ECS is (ECS is quite literally a rapidly dynamic dataflow pattern).

Perhaps there should be two types of components, those that get chunked, ala the current dataflow design, and the other types that are stored out-of-band, ala normal ECS style (specs style for example). Generally the components that are rapidly added and removed tend to be fairly few in number (though not always). The few cases that tend to be large in number tend to change less often as well in the ‘bulk’ cases with a few (few hundred that is) entities changing fairly rapidly (boundary components are common here). This seems like it would satisfy both worlds, and it is possible they could work via the same interface as well, or at the very least the same query interface.

(Kae) #26

That comment about changing entity structure being significantly slower is misleading IMO. The existing legion implementation may be because it does heap allocations for a number of things, but all that is required is to swap remove the components from its current chunk and add it to a new chunk.

I don’t know what you mean with chunked component storage being somehow “not ECS” or “not dynamic”. Is there a true Scotsman argument being made?

2 Likes
(Kel) #27

All an ECS is, is a way to relate an index of items to the data for those items, while decoupling procedures operating on that data. Legion satisfies these properties, and is an ECS.

1 Like
(OvermindDL1) #28

Not at all, I think this is just a lack of definitions of terms, I use definitions that I’ve learned ~30 years ago with ECS having come out ~20-25 years ago, so essentially the definitions I’ve been taught (just to make things unambiguous):

  • Dataflow is a set of structs in one or more arrays where an array holds a single ‘type’ of struct. It is easy to add and remove entities to the system, but changing the data they hold involves removing them from one array and putting them onto another, if made well (POD in other words) that’s as simple as a memcpy of the different struct elements from one layout to another.
  • ECS Is Dataflow except instead of the components of an entity being held in the same allocation, instead each component is held in its own array with the same index across them being the same entity.

Most games tend to use dataflow in a large variety of areas, particle systems are the most common, many games actually use dataflow for their game entities in full, take Factorio as an example, where each ‘type’ of entity is a different dataflow array, to change components involves destroying the old and recreating it in another with a different set (how legion works it seems).

They are both accessed via indices, what differs is the memory layout and access patterns. The Dataflow pattern existed before the ECS pattern by a good couple of decades and ECS is considered a subpattern of Dataflow. In other words, all ECS’s are Dataflow, but not all Dataflow’s are ECS.

This is not at all saying that Dataflow is bad, it is absolutely more common than ECS (quite literally near every engine has parts that are dataflow, especially particle systems), just that the access patterns are different since Dataflow focuses more on static speed of small collections by combining the components into singular arrayed structs and ECS focuses more on rapid adding and removal of components.

Non-ECS Dataflow isn’t always faster than ECS either, when there are many components and the sizes become too large than it causes too large of jumps between objects when you are trying to access only small amounts of data.

This is also why some ECS engines combine both patterns into one engine, where certain components are marked as batched and get combined based on their batching tag, for example:

  • Component Transformation has batch tag 0
  • Etc PhysicsLink has batch tag 0
  • Renderable has batch tag 0
  • Inventory has batch tag 1
  • A has batch tag 1 (I’m running out of ideas for names, I just woke up…)
  • B has batch tag 1
  • C has batch tag 1
  • D has no batch tag
  • E has no batch tag
  • Jump has no batch tag
  • etc…

So component Transformation, if it exists for a given entity, will be combined into dataflow batches with others also tagged 0 (PhysicsLink and Renderable in this example). Inventory will be combined with A, B, and C anytime any of them exist. D and E and Jump are untagged and will never be batched with other components whatsoever, this is similar to how specs works now, these are optimal for components that are added and removed rapidly, where batching is most optimal for when they are less often used or only often used together.

This is generally considered the most optimal ECS pattern where it appears dynamic via the API but there are optimized paths using non-ecs style dataflow, though I never got around to adding batching in my old engine (other than manually in a few cases), it is what I’ve always wanted to experiment with.

I’ve not actually heard ECS being defined with such a definition in over 20 years that I’ve been using it?
That style could describe even the old Unity system, which is exceedingly and extremely inefficient and is not dataflow in any way whatsoever (with significant performance detriments because of it), and it is not generally considered an ECS even though it has entities, components, and calls to operate over that data. It’s always best to define things very precisely.

2 Likes
(Kae) #29

Thanks for the clarification! Then in these terms I think legion's storage design is a sort of combination?

  • Component data is partitioned into fixed size (16kB) allocations called “chunks” based on each entity’s set of component types. Each partition is called an Archetype.
  • Components within a chunk are stored in separate arrays for each component type.
  • An array of entity IDs is stored within a chunk. An index across component and entity ID arrays refer to data belonging to the same entity.
  • A hashmap is maintained in the World with the location of each entity for point lookups.

So adding/removing components from an entity would require the following steps,

  • Find/allocate a new chunk for the entity’s new Archetype
  • Copy component data and entity ID into the new chunk
  • Remove components and entity ID from current chunk, probably by replacing it with the last entity in the chunk
  • Update entity location entries

The runtime of this will increase relative to the total size of the entity’s component data, and does include 1-2 hashmap lookups, but there’s nothing inherently slow about it, at least by my definition. It’s all O(1) relative to the number of entities in the World.

3 Likes
(OvermindDL1) #30

That’s how it was seeming to me, I’d only seen that in a closed source library in the past, not an open source, so it was a nice surprise. ^.^

It might be fine as it is, benchmarks will tell for sure! :slight_smile:

2 Likes
#31

@kabergstrom - curious, if I’m building a scene graph renderer thing for wasm (single-threaded), should I use your fork or the official repo?

Or generally, just kinda wondering what the roadmap is - I see your repo is 16 commits ahead… are you planning to diverge completely or just working towards a milestone before making a PR?

(Kae) #32

IMO you should use my fork, as I believe future work will be based off it. I should probably make a PR or discuss the maintainer situation with @Ayfid

3 Likes
#34

Another ECS to consider: shipyard

FYI @kabergstrom - I made a tiny PR on the original repo to allow passing a name in. It’s actually required for using legion in wasm environments since the randomized name thing breaks there. It hasn’t been merged yet, so not sure what the right approach here is… maybe I should revoke the PR and make it against your fork instead?

(Joël Lupien) #35

It seems like legion didn’t have any updates in the past 5 months :confused:

(Kel) #36

This one has had updates in the past 10 days : D https://github.com/kabergstrom/legion/commits/master

(Joël Lupien) #37

Yeah, Frizi updated me on that but then I forgot to update my forum comment here. Thanks :wink:

1 Like
(Zicklag) #38

Just a heads up, a scheduling discussion was started in the Legion repository:

I’m not sure how it compares with the scheduling that was started in @kabergstrom’s fork, but it would probably be good to look at.

3 Likes
(Jaynus) #39

I’ve started implementation of that scheduler design, building off of @kabergstrom’s design and incorporating his job management into it.

I’m working with the author of Legion to help get things up to speed and usability for amethyst and hopefully integrating some of our needs (like schedulers and resources) directly into it. You can see progress in his experimental-soa branch and my ‘scheduler’ branch in my fork.

6 Likes
(OvermindDL1) #40

So I tried writing an experiment between specs and legion, a simple in-memory game of the style I usually do (specifically porting one of my tests from old C++ engine), I’m having some issues writing it in legion.

First thing, couldn’t find entity_data anywhere, the readme states to use it to test query things like .filter(!entity_data::<Velocity>()) yet I can’t find entity_data anywhere in the code?

So simplifying the test to not rely on that feature, first test is toggling a components existence on or off depending on the state of another component (this is a super common ECS pattern, a toggling system to mark whether it is needing to process energy or not based on work performed in the ‘game’, the component(s) holds the current ‘state’ of the operations), first thing to note is that world is not accessible while iterating the data, so instead I’m pushing the ones that need to have their component toggled to a Vec to process after the loop (technically I’m filter_mapping the entities and collecting them into a Vec to then for_each on after). So the second issue was, testing this with only 100k entities wanted critereon to take 362529 s to run, even with 10k entities would have taken a few dozen minutes, had to simplify the test much further than the mini-game and reduce the entity count to 1000 to get it to complete in 6 seconds, the results of just altering 1000 entities components via mutate_entity (the only way I saw to add/remove components to an entity that didn’t change the entity ID) twice (once to perform the action, the other to reverse it to restore the test on each iteration), the result being:

iter-swap-components    time:   [836.79 us 842.53 us 848.30 us]

And this is with no other entities around on my very old (but not at all bad) CPU (Phenom ][). So reducing the code to something not really representative of the game at all gets it to being able to mutate 2000 entities (1000 changed twice) in a very serialized way (not at all how the game actually runs) in a single ‘frame’ costs about 842 microseconds. My old C++ engine handled this with a million entities changing about 10k entities per frame on average in much less time.

Hmm, let me clone legion and add it as a benchmark, this is what I have now, please advise if this is the worst way to do this or so:

fn bench_iter_swap_components(c: &mut Criterion) {
    c.bench_function("iter-swap-components", |b| {
        let mut world = setup(0);
        add_background_entities(&mut world, 10000);

        world.insert_from(
            (),
            (0..1000).map(|_| (Position(0.),)),
        );

        let mut query_pos = <(Read<Position>)>::query();
        let mut query_rot = <(Read<Rotation>)>::query();

        b.iter(|| {
            {
                let es: Vec<_> = query_pos.iter_entities(&world).map(|(e, _pos)| e).collect();
                es.into_iter().for_each(|entity| {
                    world.mutate_entity(entity, |e| {
                        e.remove_component::<Position>();
                        e.add_component(Rotation(1.0));
                    });
                });
            }
            {
                let es: Vec<_> = query_rot.iter_entities(&world).map(|(e, _pos)| e).collect();
                es.into_iter().for_each(|entity| {
                    world.mutate_entity(entity, |e| {
                        e.remove_component::<Rotation>();
                        e.add_component(Position(2.0));
                    });
                });
            }
        });
    });
}

And this one runs in this time here:

iter-swap-components    time:   [1.0058 ms 1.0128 ms 1.0197 ms]

So the extra entities added by the test scaffolding of add_background_entities slowed it down by almost 200 microseconds to bring it up to over a millisecond for just 1k entity mutations (which is absolutely nothing compared to how many mutations actually happen in a frame in this, especially considering how many entities will not have identical component sets as another).

And the same benchmark in specs, same count of entities (1000 each time, no background entities), same process, same adding, same removing, same pattern of code (collecting the entities via a join into a Vec and then for_each’ing over those, etc…, but in System), etc., gives this result:

Add Then Remove         time:   [139.02 us 142.88 us 146.79 us]

This is a significant difference. And there aren’t even any other components. As the entities end up having more components (in my engine an entity averages anywhere from 5 to 100 components on it depending on what it does) I’d imagine legion would get even slower where specs would stay the same speed.

This is why grouping is so important. Whether allocated groups in Specs or allocated groups in legion need to be added, but there needs to be a way to define that A, B, and C components should be allocated together (as they are often accessed together), same with D, E, F, and G, and H should always allocate by itself (rapidly changing component for example).

As it stands I don’t think I could use legion with how it is currently designed, though it doesn’t seem like it would take much work on it to fix it, by adding explicit grouping. Either specs needs to get the allocated-together help of similarily accessed components (which I could easily see being something like changing a component derive from something like #[storage(VecStorage)] to being something like #[storage(ChunkStorage, Physics)]) or legion needs to get the ability to not have components grouped together, or with their own groups (even if only a group of 1).

Hmm, it really might just be as simple as that, make a new storage type in specs, called something like ChunkStorage. Specify some method of tagging (the Physics in the above example), and any component of that same tag gets chunked with other components of that same tag when they exist. That would gain specs the chunk iterable style speed of legion while being able to control how the grouping appears (and why you don’t want grouping to exist for certain components at all due to them rapidly changing or so)… I wonder how much of a change in specs itself it would need to be able to access multiple components from a single storage container…

EDIT: Just an interesting note, my old C++ engine didn’t do grouping like this, but rather it could force only a set of components to be on, so if A was on then B was not allowed (removed) and vice-versa, so I kind of did a manual chunking system using that, automating it would be very nice though.

4 Likes
(Kel) #41

I’ll defer to Frizi’s words earlier in the thread on the other aspects of the API besides perf.

However, the point on grouping is especially pertinent I think. Aaand I see you just read Flecs author Sander’s comment on Discord about EnTT groups! Heh, I was just about to mention it here.

1 Like