Building a fast ECS on top of a slow ECS
Вставка
- Опубліковано 27 вер 2022
- This is a quick introduction to Entity Component System Framework design. Specifically focused on how I built and implemented mine. There's a few interesting challenges with cache coherency, entity management, and entity filtering to tackle; so let's take a look!
Articles about building ECS frameworks
⁍ / building-an-ecs-1-wher...
⁍ skypjack.github.io/2019-02-14...
Other links
⁍ Twitter: bit.ly/UnitOfTimeOnTwitter
⁍ Discord: / discord
⁍ Code: github.com/unitoftime/ecs - Наука та технологія
I'd been saying for years that Go wouldn't be viable for a working ECS until it had generics. And here we are.
Yeah I originally tried to build one by generating code but it was incredibly painful to work with. Glad to have generics around now.
Great video, I was reading several articles and could NOT wrap my head around what the archetype is supposed to be. Your video was very easy to understand and much appreciated!
Glad it was helpful!
Great video as always. Curious to see the next video. My current ECS imlementation uses a similar approach.
:) Yeah benchmarks are always fun to see!
honestly that chart at 1:15 instantly made it make sense to me holy crap
nice. I tried writing an ecs in typescript a year ago but gave up after being stuck in the weeds debugging type issues. Now I'm redoing the project in python and this video has been very helpful as you're extremely concise compared to other resources
Thanks! Glad that you found it helpful!
Great content! Thank you for your time assembling such a great summary in such a consumable way! :D
Thanks! Glad you enjoyed it! :)
This is really cool, I don't know anything about Go, but the background knowledge of ECSs is really nice!
Thanks glad you liked it!
Very nice explanation of what goes into an ECS. Thanks for the Flecs shoutout!
Thanks! Your medium articles are incredibly good and gave me a lot of solutions to many of my ECS problems. Glad to have had you watch and like my video!
great video and explanation Unit! 🙂
Thank you!
Underrated channel; also a nice listen. thank you
Thanks! Appreciate it!
Great lecture, thank you.
Very cool! The Archetype pattern loosely reminds me of how the v8 Javascript engine stores Prototypes, the internal object schema for all objects in a Javascript runtime.
Oh cool. I had no idea! Thanks for sharing!
the old name for archetypes was prototype!
I tried a lot of different ecs systems. What worked for me and is good enough for
Yeah. That's definitely a viable approach. The only downside (besides cache coherency) I would see is that if you need to filter your 20k entities for the 5 that contain a certain set of components, you would still have to loop over all 20k entities to see what components they have. But that might not be a huge issue or it might be mitigatable depending on the app. Thanks for watching!
@@UnitOfTimeYT It indeed really depends on the application.
Instead of searching for entities in an archetype, I just constantly update each archetype's list of entities each time a change in components happen on an event model, which is much faster.
So each archetype knows about all the eligible entities at any given moment.
Yeah sounds smart. I do the same thing for individual entity lookups. I have one table for id -> archetype. then inside of an archetype I have another to look up the index
Very cool system
I was playing with it as I have recently just started using Go.
However, I have a question... If you were to create a system that says relies on more than 2 components, would you have to write a new Implementation of query2 for each query you would need? Or would code generation come in handy here? Sorry if this is a dumb question, not really an expert Go developer.
Thanks for the video by the way. So cool to watch.
Hey thanks. Yeah unfortunately Go doesn't support variadic generic arguments, Go also doesn't support overloading function names. So If I want to iterate over 9 different components in my ECS, I have to write a query9 function (for example). This seems to be how the Go authors do it, when I've seen them write functions that do Map2() Map3(), etc. type functions. Luckily, I haven't had to iterate over more than 3 so far. I also think that if your components are so sparse to where you have to iterate over a lot of different arrays at the same time, then you might need to reorganize. But what you pointed out is definitely a very important callout and limitation of my ECS. Thanks for pointing that out!
Great!
Hi, great video! What do you use to create those illustrations ?
Hey thanks! For some of them (specifically the bubbles floating around) I pointed my opengl framebuffer to ffmpeg and encoded it to a video. For the graphs, I used the very popular and featured library, manim. And for block diagrams I usually use draw.io. Then I render codeblocks to images using this tool called marp. Now that I think of it I'm using a lot of different things lol
Sorry I thought this comment was on my Rust vs Go video. For this one it's mostly draw.io for diagrams and then marp for generating slides! Got the idea from the NoBoilerplate who does slide-based video presentations.
Since you are working on Golang, I wonder if channels help in this case for concurrency/parallelism?
Yeah. I think Go has great concurrency. Because the data is laid out really nicely. All I have to do is section of blocks of data to be processed concurrently. ie [0, 1023], [1024, 2047] ... etc. I probably wouldn't pass underlying data around via channels. but I might pass things like slice headers that tell worker threads which section they are responsible for processing.
Interesting idea. But man that's a lot of overhead just for a few doubles and so many iterations to get to the actual data.
I'd just make an array of doubles, keep track of each entity/component start index and length in the array and then for integration send that entire array to the integrator (s += dt*ds). And if there are colliding objects I'd not give each object access to each other object in the world, I'd pre-cluster them so that each one checks a handful but not millions of entities.
Appreciate the comment. I think it feels like a lot of overhead when laid out in the video, but the core of the loop is still what you described (ie pass an array to an integrator or system function). The overhead is only needed when fetching that array (which would be once per tick). Incidentally, some of that overhead is still present when looking up one individual entity, but I'm looking into ways to reduce that if I can. For my cases, looking up individual entities is somewhat uncommon, but still - always a way to improve!
The challenge with just making a single array of doubles and tracking a section of that for each entity is that it doesn't scale well (cache-wise and memory-wise) when the entity has a lot of components. It also causes a decoding problem of "How do I decode this chunk of floats/bytes into my entity struct" - or if you pack a bunch of structs in a big array you'll just waste space when entities have blank data. Obviously, these could both be reasonable approaches depending on your game/data layout.
I don't think I had collision code in this particular video, but yeah, It's more optimal to pre-cluster your colliders either via spatial hash or KD trees. Hoping to look into that for the future!
Thanks for watching!
@@UnitOfTimeYT Thanks for the reply. Well I guess it depends on how much data you actually have and what kind of different entities are needed, as you said.
Hey, I'm currently working on implementing an ECS in rust. I decided to use a sparse-set based system instead of archetypes, but my question is around how you managed to multithread your ECS? Are there any resources you can point me towards, as hours of googling have given me really unspecific results that haven't been any help.
Thanks.
Hey, Yeah I think there's two main ways you might multithread:
1. You could multithread different systems. You can think of your set of systems as a Directed Acyclic Graph (DAG), and then figure out the dependencies between each system. Then you can run two systems at the same time if they don't depend on eachother, and if they don't use the same underlying storage.
2. Inside of each system, if you have a large enough dataset, you can parallelize the execution of your function on the underlying dataset. I'd guess that this is much easier for archetype based ECS's. Mostly because in archetype ECS's you can just divide up indexes because each component array has the same order (with respect to entity). My understanding is that for sparse sets, different arrays can have different entity orders which makes it hard to divide up what work needs to be accomplished.
I think if you check the description of this video there's two links for two famous ECS authors, you might check out their articles. They probably have more information about this ( I don't have specific references tho, sorry)
@@UnitOfTimeYT Hey, thanks for the reply.
I did some research on implementing this in rust; it would certainly be difficult and would be macro heavy or have clunky syntax, beyond actually developing a concrete multi-threading implementation.
It leads me to think; is multithreading actually an upside? For reference, the game I developed this ECS for is a Rogue-lite. Adopting a multithreaded system will mean that very few things can be truly parallel, as there must be a sequential order of events in terms of systems (physics comes before rendering), and because of the nature of a rogue-like bullet hell, many systems can affect other parts of systems. This makes the overhead of having a multithreaded system questionable, since spawning threads is not cheap and figuring out the dependencies of systems isn't either.
In addition, for things that affect the world, you'd need to delay them to some sort of sync point. You can't have two systems concurrently spawn an entity with the position component unless everything is behind RW (Read-Write) Locks, which also makes the performance of such a system questionable.
What have you found in your game? With this, I developed an ECS for developer ergonomics with performance as a convenient upside. I'm not sure multithreading would be good for either.
Yeah I think you're rightfully calling out a lot of the difficult challenges with multithreading. You might take a look at how bevy does it as well. I believe they use both of the approaches I mention in my previous comment. For approach 1, you'll really only get gains if your game is such that you have separate systems that don't really interact, then for approach 2 I think you're more likely to get gains if you have large sets of data that don't interact.
In my own ECS library, I currently don't have much in the way of multithreading. Though I've intentionally left room for myself mostly in approach 2. Just from my game systems, I've observed that (other than the main draw calls, which aren't really multithreadable) there are a few systems that the majority of every frame time: collision detection and batching dynamic geometry. I think optimizing the systems which take the most time is probably your best bet for making your game run faster.
Yeah, you'll definitely need sync points to add new entities back to your underlying storage. Bevy has "Commands" that they buffer inside a system and then execute at the conclusion of the system. I'm planning to eventually do something like that, but haven't really finalized it much past a basic prototype. I don't think the overhead of locking here will cause too much trouble, but I don't really have any data to confirm that, so I guess I'll find out as I do more profiling.
Right now my game isn't really big enough to warrant much multithreading and I get most of my optimizations by just improving the rendering code. Most of my concurrency surrounds the IO part of my game: ie pulling in packets and decoding them is done concurrently. And then, most of my scalability problems (with things like rendering and physics) I've been able to solve by just using better algorithms.
Hope it helps!
@@UnitOfTimeYT Yes, this has been really productive.
I think the correct approach for me is to develop some sort of task/job system multi-threading model and have systems run sequentially with access to some sort of job resource which enables me to multithread on a case by case basis. For example, if I implement a procedural generation algorithm which has potential for multtihreading, I could do it specifically in that system without an overarching approach, and everything else would run sequentially.
I also agree with you in the sentiment that my game is not big enough to warrant multithreading; the game I'm setting out to create will be 2.5d and performance will almost certainly not be an issue.
I have also gandered at bevy's, specs, and legions source codes to varying degrees and have read about their multithreading implementations. The conclusion I've come to is that it is way too complicated for just me to tackle.
Overall, after doing so much research, I'm just overall not sure multithreading for this specific project is a net gain. The benefits will be limited, and if needed, I could multithread on a case by case basis. Much of my development decisions have been driven by EnTT and the article you linked by its creator, and after looking at EnTT, it seems they adopt this sort of approach as well.
what does the := operator in 1:40 mean ?
The := operator in Go is just used to create a variable and assign the values to it. In this case I'm just creating a pos and vel variable in a kind of "for each position and velocity in the world" sort of way
Noot Noot
Just wondering, why can't you just put all like components in their own arrays? Each component would just need a reference to affect its entity, and this would work fine right? This sounds simpler than making archetypes, but I'm curious why I'm probably wrong.
I might not understand your exact question, so let me know if my response doesn't answer it.
You can think of one Entity as being a column created by pulling a component out of every array at the same index. So if we pull index 5 out of every component array, that gives us the full entity at index 5.
The main problem that led me to archetypes is "What do you do when you have entities who don't have a specific component?". If I have one big array for all the health components, and but then index 5 is a rock with no health, I still have to put something in the index 5 health box. There's a couple ideas:
1. Make it a health pointer, then just null when its not there: This means all healths need to be pointers which means a lot of extra dereferencing which could make us slower
2. Add a bool to indicate that the entity doesn't have health: This is similar to health pointer, but wastes some space every time an entity doesn't have a health component.
The biggest problem with the ideas 1 and 2 is that: If we have a system that draws healthbars. Let's say that we have 1M entities and 1k of them actually have the health component. If we have one big array, we have to loop over all 1M entities; first checking if they have the health component, and second drawing the heathbar.
There's two solutions I know of to the "one big array" problem:
3. Archetypes like I discussed
4. Sparse sets - Which is where you still have one big array for all components, but you do some mapping magic to compress a sparse array to a dense array. This lets you just delete all of the holes
Both archetypes and sparse sets come with their own tradeoffs. I personally preferred archetypes because it made more sense to me.
Just as a little side-note, there's two reasons you might structure your game this way:
1. Organizationally, a gamedev it's nice to dynamically add and remove components from your entities, and then based on those components run different systems on them.
2. You have so many entities that organizing the memory becomes important
Performance may not matter to you, and in that case you can definitely implement some more simpler ECS patterns if you want. Also organizationally, you might not need that much configurability (in fact, you may not even want it). So there's definitely reasons for and against using an ECS in general.
Hope that helps!
@@UnitOfTimeYT Thanks for taking the time to explain, I appreciate it. I just realised that I was asking why we don't use the slow ECS, which you answered in the video already 0_0. I guess what didn't click at first is why the 'slow ECS' is slow, and I kinda understand now.
@@Shack263 All good! Happy to answer :) Yeah IMO at this level of performance optimization it becomes really situational on which memory organization will become faster, and it's not super obvious why until you really dig into it.
Archetypes should not be intersecting sets. The set "position, velocity, sprite" already contains the set "position, velocity". You can read the former without accessing the sprite as if it was the latter set. This prevents you from keeping track of and updating more sets than you actually need. The sets "position, velocity" and "position, sprite" are not intersecting and would be the kinds of sets you actually want to keep track of in this way. Other than that, I really liked the video.
Yeah that could certainly be a way to reduce the number of archetypes you have. Practically, I'm not sure how you'd heuristically decide in a simple way which archetypes fall into others without ending up with one mega archetype that contains every possible component. In practice though, I do typically have very similar archetypes that are like "all of these components, but also this one" so there is maybe some potential for optimization there.
Like reinventing the wheel?
careful with the "add" and "remove".
in game dev, there should be no adds or removes, if by that you imply memory reallocation.
have fixed size arrays, do not reallocate. ever.
predetermine how big the arrays must be, limit object instantiations, keep track of the arrays actual size (index pointing to the "end" within the big array).
and simply juggle around data within it.
Yeah I'd generally agree that it's good to reduce and remove memory allocations. In my ECS there's an initial growth period as arrays get sized up to hold more entities, but at some point the array gets large enough for the application and entities are essentially "pooled" in terms of their memory.
I am not sure I get the point. It sounds like this is just trying to fix problems that are otherwise fixed by just writing code properly.
Can you outline exactly why you would want to structure your code like this please?
Sure, this sort of technique is mostly used in game development, where you have relatively tight performance requirements and also often times need very flexible object creation (where you can dynamically add and remove components at will). This way of organizing your data, as a struct of arrays of components, will get you better cache performance than if you organized your data in the opposite direction (ie as an array of a struct of your components). Definitely not a fit for every software project. Hope that helps.
@@UnitOfTimeYT It does thanks but aside from the performance benefits which I think you could mostly get by not mangling your domain objects with a ton of needless inheritance and then using the appropriate data structures ... why is it worth essentially denaturing your codebase.
It feels like a really horrible way to organise your code from a DX point of view.
Whats it like to work with?
just use c++.
Hi, just a hint by some none native english speaker: you speak way too fast and you seem to have removed the pauses between sentences. It's therefore hard to follow your explanations. I need to rewind every now and then which doesnt always leads to better understanding. Which is a pity since you seem to know what you're talking about.
Thanks for the feedback! Yeah I agree, especially in my earlier videos I talk way too fast. Will try to continue to improve this for future videos!