Entity/component model in prototypes

Things that we aren't going to implement
Post Reply
mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Entity/component model in prototypes

Post by mknejp »

Hi,

I am currently in the process of writing my first mod for Factorio and there are quite some aspects of the API that I find cumbersome. First a bit of background about me: I have been programming since I can remember (mostly C++) and my professional work is centered around 3D/game engines, so I do know how these things work (I also speak Czech :D). This is partly the reason why the mod API surprised my a bit, since I assume it reflects how the game works internally.

To my understanding from reading the forum a "type" in Lua corresponds to a class in C++ where entities are probably stored in big arrays, one for each entity type and processed every tick (hopefully without abstract base classes, virtual functions, and the whole inheritence forest problem). So this basically makes it impossible to change an entity's behavior without having to touch C++ code. It also means that if I want to have an electric boiler I also have to touch C++ code and either hardcode a new entity class or give the existing entity some new operation mode (I think electric boiler mods currently actually use a "pump" type to circumvent this, with lots of Lua hacks in on_tick). To me this indicates a quite inflexible system, both for mod devs *and* for the game devs.

I have also looked at other mods to get some insights and see whether I'm doing something wrong. One particular pattern showed up repeatedly, especially when they try to model an entity that is more complex. They listen to the on_built_entity event, then create some new internal invisible entities, use the on_tick event to modify those internal entities, and when the "primary" entity is removed they also remove the secondary entities. For example, I wanted to have a simple entity that consumes electricity and does something with it, but there are only a handful entities that are capable of consuming electricity. So what I'm doing is creating an internal pump and every tick remove "energy" from the pump to simulate consumption. And it seems others are doing similar things.

This "entity amalgamation" is so ubiquitous that I think it deserves attention.

There is an easy solution called the entity/component system (KSP calls it part/modules but it's the same thing). Are the devs familiar with that concept?

In this pattern an entity is actually nothing else but a container for components (in some engines it is literally a container of pointers to components, in others it's just an ID). An entity doesn't do anything on its own, it is just an abstraction used to associate components to the same entity. It's the components which are responsible for behavior. Actually, even the components are just "plain old data" objects. Every component type has an associated system which does the real work. Every tick the system for component type A processes all components of type A, where all components of type A are stored in one big array containing *all* components of type A active in the game. Then system B processes all components of type B, and so on. This arrangement has very good data and instruction cache efficiency. In such a design components are the smallest granularity of "behavior" in the game. Let me show this on the example of a boiler. Currently a boiler is a hardcoded entity that does one specific thing. But it can actually be disassembled into multiple components/behaviors:

1. Inventory
2. Fluid box
3. Fluid connector(s)
4. Fuel burner
5. Energy buffer
6. Fluid heater

Now there is no longer a "boiler" per-se. The fact it is a boiler is the result of how its components interact. The update every tick goes through each system and manipulates all components of that type:

1. Fluid heater increases temperature of fluid box taking energy from buffer
2. Burner takes item from inventory and stores the contained energy in buffer if it has available capacity
3. Fluid system moves fluid

Now imagine you want an electric boiler. All you have to change are the components of the entity:

1. Power grid coverage
2. Fluid box
3. Fluid connector(s)
4. Power grid consumer
5. Energy buffer
6. Fluid heater

1. Fluid heater increases temperature of fluid box taking energy from buffer
2. Consumer takes energy from power grid and stores it in energy buffer if it has available capacity
3. Fluid system moves fluid

This approach gives you a lot more re-usability of components. As each component/system is plug-and-play. Some might now look at this and think "this is adding more things, therefore overhead, therefore must be slow", but actually the opposite is the case. Because the "fluid heater" system can process *all* fluid heater components in one batch, data and instruction cache utilization is much better (if arranged in arrays). So doing job 1 for all fluid heaters, then job 2 for all energy converters, then job 3 for all fluid boxes is CPU cache friendlier than doing jobs 1, 2, 3 for boiler 1, then jobs 1, 2, 3 for boiler 2, etc. This means that if, for example, you have both boilers and electric boilers in the game the "fluid heater" system runs for both boiler types because they have "fluid heater" components. (It actually doesn't iterate entities searching for ones with associated fluid heaters but instead the one big "fluid heater" array.) This is a really important aspect of this design.

The better cache utilization comes from the fact that the same operation (usually short, fitting well into icache) is executed for every array element, and once done with the component type it is never touched again and the cache progresses to the next array. The prefetcher plays a big role in this. Even if a system needs to process an array multiple times doing different things the data is "hot" and likely still in L1/L2 cache (how important cache locality is can be seen in experiments where bubble sort beats any other sorting algorithm for small data sets and even linear searches in arrays can be faster than binary search).

Under this system an entity is defined by the components associated with it. From the game engine's perspective there is no difference between a coal fueled car and an electric car (that can only move in range of power poles, wouldn't that be funny). There are no dedicated "fuel car" and "electric car" entities, because entities are just IDs. It's how you wire up the components that determines the behavior of an entity. What we know as "prototype" would no longer reflect an actual C++ class but a blueprint to the game engine on what components to instantiate and how to connect them together (often called an "archetype" in other engines).

So how would this affect mods? Let's assume I want to make a wind turbine. Currently I'd have to make an entity representing the actual turbine and the object the player places on the ground. I need to create an internal-only steam engine and fill it with a hot liquid based on wind speed. This means hooking into on_built_entity, on_entity_died, on_preplayer_mined_item and on_robot_pre_mined, creating the second entity, ensuring the second entity is invisible, invincible and cannot be marked for deconstruction (otherwise the whole thing falls apart) and remove it when the turbine dies or is mined. But I won't get around the issue of the mouse-over info for my entity to either show nothing or a magic liquid in its fluidbox that doesn't really make any sense. Instead what I want is

1. Power grid coverage
2. Energy buffer
3. Power grid supplier

Then all I have to do in my on_tick is add energy to the buffer based on wind speed, since that is the "special" behavior the C++ code doesn't model. This is how it might look:

Code: Select all

data:extend({
  {
    -- note there is no "type" here
    name = "wind-turbine",
    ..., -- graphics, animations, stuff
    components = {
      grid = {
        type = "power-grid-coverage",
      },
      buffer = {
        type = "energy-buffer",
        capacity = "100kJ",
      },
      generator = {
        type = "power-grid-supplier",
        source = "buffer",
      },
    },
  },
})
The names of components are identifiers used by the game engine to connect components so the C++ high-performance code knows where to take stuff and where to put stuff. With this more fine-grained control over the behavior of entities it becomes easier to build more complex entities without having to run huge amounts of Lua code slowing the game down (and we all know modders like doing that), or having to special-case every combination of components as a dedicated C++ class. Components become the basic building blocks. Many folks in the industry attest to how simple it is to extend a game with such a system (both internally and by modders) because a lot of functionality is already there and can be easily re-used in other entities. I remember the KSP devs giving a talk about this at GDC on how it boosted their productivity once they transitioned to this system.

Now, for all I know the game might already work this way and just not expose it in the mod API making all this talk moot :). Otherwise this might be some food for thought to the devs in case they aren't familiar with the entity/component design. It may or may not be a significant endeavor that may or may not be worth it (certainly not if only for the benefit of modders).

Thanks for reading. Now if you excuse me, I have a mod to make.

User avatar
Adil
Filter Inserter
Filter Inserter
Posts: 945
Joined: Fri Aug 15, 2014 8:36 pm
Contact:

Re: Entity/component model in prototypes

Post by Adil »

It's been suggested to death actually. (There's even one right few threads in the list below yours) Devs keep saying it's not gonna happen. I believe at this point we should start asking for the base components being added as independent types, so that we could glue those with lua instead of hidden entities with superfluous features. :mrgreen:
I do mods. Modding wiki is friend, it teaches how to mod. Api docs is friend too...
I also update mods, some of them even work.
Recently I did a mod tutorial.

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

Adil wrote:It's been suggested to death actually. (There's even one right few threads in the list below yours) Devs keep saying it's not gonna happen. I believe at this point we should start asking for the base components being added as independent types, so that we could glue those with lua instead of hidden entities with superfluous features. :mrgreen:
Indeed, I did look through the forum to see if this was suggested before but somehow the mentioned thread slipped by. I do not buy the performance argument since the technical and productive benefits of a entity/component model have been demonstrated in games and simulations repeatedly since Dungeon Siege brought the industry's attention to it, but I certainly accept the point that it is too late for such a change.

Rseding91
Factorio Staff
Factorio Staff
Posts: 13209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Entity/component model in prototypes

Post by Rseding91 »

mknejp wrote:
Adil wrote:It's been suggested to death actually. (There's even one right few threads in the list below yours) Devs keep saying it's not gonna happen. I believe at this point we should start asking for the base components being added as independent types, so that we could glue those with lua instead of hidden entities with superfluous features. :mrgreen:
Indeed, I did look through the forum to see if this was suggested before but somehow the mentioned thread slipped by. I do not buy the performance argument since the technical and productive benefits of a entity/component model have been demonstrated in games and simulations repeatedly since Dungeon Siege brought the industry's attention to it, but I certainly accept the point that it is too late for such a change.
When I see a game implement it at a scale that Factorio runs at then I'll take back my argument about performance.

http://i.imgur.com/sdX9Zcq.jpg
  • 5,455,472 total entities
  • 234,049 active entities (entities updating each tick)
  • 60 ticks per second so that means all 234,049 entities have < 16.6~ MS per tick to run all of the logic they implement
  • 4.2 GB of RAM used
If you want to get ahold of me I'm almost always on Discord.

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

Rseding91 wrote:When I see a game implement it at a scale that Factorio runs at then I'll take back my argument about performance.

http://i.imgur.com/sdX9Zcq.jpg
  • 5,455,472 total entities
  • 234,049 active entities (entities updating each tick)
  • 60 ticks per second so that means all 234,049 entities have < 16.6~ MS per tick to run all of the logic they implement
  • 4.2 GB of RAM used
"240,000" entities each tick doesn't really say much without knowing what these entities are and what they do. You can have a million entities that are just adding numbers together or a million entities that are part of a protein folding simulation.

But there seems to be a misunderstanding here. Let me try to elaborate on an example that I understand how it works (I think), namely the transport belts. Looking at the mod API it seems that a belt has "transport lines" which are the things that are actually simulated by the game and I assume those are accumulated into some bigger system. So in fact there is already an entity/component separation here: the "transport belt" entity containing "transport line" components. In an ECS you just go one step further and ditch the "transport belt" entity class because it actually doesn't matter to the game logic and serves no purpose. It's just a container of transport lines. So whatever computations the game is running doesn't change because the transport lines are still there and it's the transport lines that do the actual work. The entity/component system separates objects from behaviors. What really matters to the game logic is the *behavior*: the transport line, which even in an ECS is part of a dedicated specialized system doing one thing and one thing only. The entity is just a logical grouping of components presented to the player as one "thing". In such a system there is no (technical) reason why a power pole couldn't also have a transport line, because the game doesn't simulate a "power pole with transport line". It simulates a "transport line". Creating a new "power pole with transport line" adds a transport line to the transport line system, a power grid box to the power grid system, and sprites to the graphics system. The fact these three components are somehow related only becomes relevant when the entity is created or destroyed.

Liquids are another aspect of the game where I assume exists some bigger system that moves contents between connected "fluidbox" components instead of between "pipe", "storage-tank" or "pump" entities. So there seem to be glimpses of an entity/component system in the game, it's just that it doesn't seem to be applied consistently, or not exposed as such at the API level.

When it comes to numbers then, yes, a component/entity system has overall higher object count, but they each are smaller in size and simpler in execution, so the overall memory consumption is the same (or even less due to removed padding needed for alignment in larger classes). Updating a component that only has a few integers with a function that's only a few simple operations is orders of magnitudes faster than updating bigger entities with longer update methods. Cache utilization is significantly better (if only arrays are used and no pointer chasing takes place) due to tighter data packing and prefetching dominates due to predictable memory access patterns, which these days is the most critical performance impact next to threading. It's basically why "structure of arrays" always outperforms "array of structures", on CPUs and GPUs, and also lends itself better to vectorization and parallelization. Systems also make it much easier to spread work over multiple frames for aspects of the game that don't need to be udpated at 60 Hz.

See concepts like "entities are IDs", "all data in components", "code only in systems" for much more in-depth explanations and real-world examples.

This is obviously just speculation since we have no idea how the game architecture actually looks like and maybe the differences aren't as big as it seems or totally incompatible. And if only hard numbers can convince anyone then that's pretty much impossible without forking the game because definitive statements about performance can only be made after measuring and comparing results, but the principal difference between SoA and AoS is very easy to demonstrate.

But as I said before: there is no point in doing any of this solely for the benefit of modders, that would be insane. And the game may be at a stage of its development where it's too late for such a change even if it were beneficial. But if not it is a point of research I wouldn't dismiss just because no other game has done it at Factorio's scale. Factorio is doing many things at a scale no other game has done before, so why stop there.

Rseding91
Factorio Staff
Factorio Staff
Posts: 13209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Entity/component model in prototypes

Post by Rseding91 »

Everything I look at online is always a concept - some person or group talking about the idea of a component based system. I've never actually seen anyone implement it. I've heard KSP uses some such system but KSP is a prime example of poor performance with no scalability. Don't take that wrong - it's an amazing game and I enjoy playing it - but it's just not something I'd point at and say "Make a game that does it like that game does".

Also do remember that we're making a *game*. We're not making a game engine designed to make other games.
If you want to get ahold of me I'm almost always on Discord.

seronis
Fast Inserter
Fast Inserter
Posts: 225
Joined: Fri Mar 04, 2016 8:04 pm
Contact:

Re: Entity/component model in prototypes

Post by seronis »

Rseding91 wrote:Everything I look at online is always a concept - some person or group talking about the idea of a component based system. I've never actually seen anyone implement it. I've heard KSP uses some such system but KSP is a prime example of poor performance with no scalability. Don't take that wrong - it's an amazing game and I enjoy playing it - but it's just not something I'd point at and say "Make a game that does it like that game does".

Also do remember that we're making a *game*. We're not making a game engine designed to make other games.
Dont Starve uses lua for game logic and scripting and uses a component system to control entity behavior. Factorio can support 1000 times more entities than Dont Starve. I dont know if DSs backend is really that much less efficient than yours but you're doing something right with this game =-)

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

seronis wrote:
Rseding91 wrote:Everything I look at online is always a concept - some person or group talking about the idea of a component based system. I've never actually seen anyone implement it. I've heard KSP uses some such system but KSP is a prime example of poor performance with no scalability. Don't take that wrong - it's an amazing game and I enjoy playing it - but it's just not something I'd point at and say "Make a game that does it like that game does".

Also do remember that we're making a *game*. We're not making a game engine designed to make other games.
Dont Starve uses lua for game logic and scripting and uses a component system to control entity behavior. Factorio can support 1000 times more entities than Dont Starve. I dont know if DSs backend is really that much less efficient than yours but you're doing something right with this game =-)
There isn't much point in comparing games of such a different nature and then conclude that one performs better than the other because one has 100 entities and the other has 100k. It very much depends on the complexity of their behavior. The AI of an RTS controlling 100 units can be as computationally intensive as a game moving around a million inanimate rocks. The number of entities is an irrelevant metric.

KSP's bad performance isn't caused by the part/module system but primarily by the single threaded physics simulation of Unity 4. The 1.1 update will be using Unity 5 and beta testers are reporting significantly better framerates and part counts. It may also simply be a case of using C# for something it maybe wasn't designed for (there's a reason why IL2CPP exists).

Anyway, this is about Factorio. I'd like to inquire about the nature of the game entities in order better my understanding of the game itself and to avoid basing any further discussion on wild speculation. From what I gathered on the forum so far my impression is the entities look something like this

Code: Select all

class boiler : entity
{
  fuel_slot fuel;
  energy_buffer buffer;
  fluidbox fluid;
  ...
  virtual void update(...);
};
With an active list of entities being updated every frame by calling the virtual update() method. Does this come anywhere close?

P.S.: I hope you understand I'm doing this because I like the game and I want to see it succeed and improve, even if there was no mod API. The bigger the bases the game supports at smooth framerates the more enjoyable and impressive it becomes for everyone,

Rseding91
Factorio Staff
Factorio Staff
Posts: 13209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Entity/component model in prototypes

Post by Rseding91 »

mknejp wrote:... KSP's bad performance isn't caused by the part/module system but primarily by the single threaded physics simulation of Unity 4. The 1.1 update will be using Unity 5 and beta testers are reporting significantly better framerates and part counts. It may also simply be a case of using C# for something it maybe wasn't designed for (there's a reason why IL2CPP exists).
Factorio's core logic is all single threaded as well :)
mknejp wrote:Anyway, this is about Factorio. I'd like to inquire about the nature of the game entities in order better my understanding of the game itself and to avoid basing any further discussion on wild speculation. From what I gathered on the forum so far my impression is the entities look something like this

Code: Select all

class boiler : entity
{
  fuel_slot fuel;
  energy_buffer buffer;
  fluidbox fluid;
  ...
  virtual void update(...);
};
With an active list of entities being updated every frame by calling the virtual update() method. Does this come anywhere close?
Close, the base entity type isn't updatable but a side type of UpdatableEntity { virtual void update() = 0; Entity* getEntity() = 0; } which updatable types inherit from along side of the base entity type. There is also different boost intrusive lists of active vs. inactive entities that handle the updating of entities that need to be active.
mknejp wrote:P.S.: I hope you understand I'm doing this because I like the game and I want to see it succeed and improve, even if there was no mod API. The bigger the bases the game supports at smooth framerates the more enjoyable and impressive it becomes for everyone,
It's fine, I've got nothing against the concept in general I just don't believe it actually works when applied to something that runs at the scale that Factorio does as I've never seen anyone do it (probably for good reason).
If you want to get ahold of me I'm almost always on Discord.

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

Rseding91 wrote:Factorio's core logic is all single threaded as well :)
A component system can help with this, significantly. It is better suited to allow parallel component/entity updates without data conflicts.
Rseding91 wrote:Close, the base entity type isn't updatable but a side type of UpdatableEntity { virtual void update() = 0; Entity* getEntity() = 0; } which updatable types inherit from along side of the base entity type. There is also different boost intrusive lists of active vs. inactive entities that handle the updating of entities that need to be active.
Then I am afraid you are leaving tons of performance lying on the floor unless the active entities are densely packed in memory and sorted by type before updating. Otherwise I suspect an update cycle is dominated by L2 cache misses if you're chasing intrusive list pointers all around memory. This isn't even related to entity/component stuff, it's the very foundation behind data oriented design.

People are always taught in school that linked lists are better suited for insert/remove because they're O(1) instead of O(n) but they always forget the constant factor, which in the case of a CPU with cache hierarchies is significant if you're not hitting data in cache, and chasing random pointers through memory is the best way to waste CPU cycles. It can be faster to scatter/gather into/from temporary arrays and process those in bulk than chasing linked list pointers. People are also taught that OOP is the be-all and end-all, the pinnacle of software engineering. But it is just a tool. And like every other tool, it has its uses and abuses. Data oriented design also requires some effort from the programmer to stop thinking in single objects but rather in data and the transformations on it ("behavior" in a game) and embrace the fact that it's the data that matters the most.

Try imagining the difference from the CPU's point of view between running around random memory locations and calling arbitrary virtual functions versus having an array of boilers, an array of assembly machines, etc. Then add branch misprediction into the mix and you're basically forcing the CPU to spend most of its time waiting. To the CPU the intrusive list approach looks like

Code: Select all

while(p = p->next) // The next object is likely not in dcache, prefetcher useless because unpredictable memory location
  p->update(); // The code to run in the virtual function is unpredictable and likely not in icache
Compare this to

Code: Select all

for(auto& boiler : boilers) // All data is contiguous, dcache is hot, prefetcher does its job
  update(boiler); // No virtual call, icache is hot
As mentioned this is unrelated to entity/component systems. I would consider it a primary issue when designing a game to go down a data oriented design instead of "pure OOP" because it better reflects the reality of the machine. It's a big change but it can be worth it. The speedup can be up to 50x to 100x depending on what the update function does and whether it needs to hit cold data (which in an entity/component system it does not, touching only data in cache) and that is all coming from minimizing L2 cache misses. Loading data from L1 cache takes about 3 cycles, loading it from main memory about 200 cycles. You can maybe update some 10 components in the time it takes to load one from a random cold memory location.

And finally this is where an ECS really shines. It's unfeasible to have such coarse grained entities like "boiler" or "car" hardcoded because most of them share some behaviors. Instead they are broken down into atomic reusable parts that are composed together to make the actual behavior of an object. This design allows you to organize your data into small enough chunks and update routines that many of them fit in dcache at once. Thus your signal/noise ratio of memory bandwidth utilization is as high as possible. This breakup of entities allows for update cycles to only load the data they need.

Let's take the boiler again as example: every boiler entity has a fuel slot with additional stuff in it. The fuel slot is only important to the boiler when the energy buffer reaches 0, which for the most part of a boiler's lifetime doesn't happen. It takes hundreds of update cycles on average until the buffer is empty. And yet all the data is loaded into cache for every single boiler, regardless if its used or not. That is a very poor utilization of memory bandwidth. If instead the boiler actually consisted of a fuel slot component, a buffer component and a fluidbox component, each stored in separate arrays, then a "fluid heating" system only has to iterate over the buffer and fluidbox arrays, never touching any fuel slots, and thus not wasting memory bandwidth on them. While updating it stores all the empty buffers in another "refueling needed" list. On the next frame the "refueling system" runs through the "refueling needed" list, loading the fuel slot and buffer arrays, followed by the "fluid heating" system. Does that mean some components are loaded more than once? Yes, but the reality of how the cache and prefetcher work makes it clear that this is still faster than loading data that is not needed due to the higher information density. It's basically again why SoA dominates AoS for large data applications and simulations (which is a category Factorio certainly fits into).

This may sound complicated (and I may not be very good at explaining stuff) and it sure is more work than a simple linked list of polymorphic objects. The gains, however, can be significant. Furthermore, if you have n components and m CPU cores you can split up the work on all cores by partitioning the arrays in n/m chunks and handing them to each core in a fork-join pattern: instant profit! Next you can schedule components onto different cores that don't have any dependencies between them: more instant profit!
Rseding91 wrote:It's fine, I've got nothing against the concept in general I just don't believe it actually works when applied to something that runs at the scale that Factorio does as I've never seen anyone do it (probably for good reason).
As already mentioned the "scale" is difficult to compare without measuring how much "work" each entity does in one game compared to the other game. Consider all the physics/transform/visibility/etc computations a typical 3D game has to do that have absolutely nothing to do with actual game logic, so you end up with less entities, but each requires more work per frame. Only looking at the number of "objects" on the map is a very misguided metric. Unfortunately most games don't make their source code available, but we actually know data oriented design, and the entity/component system naturally stemming from it, is found everywhere. It does regularly surface in blogs and GDC talks. So stating no game has done it is incorrect. Here is a CppCon 2014 talk by Mike Action, Insomniac Games Engine Director that I consider highly informational and a must-see (even though I disagree with the C++ bashing). UE4, CryEngine and Unity all use them to a certain degree ("hybrids" because they are general-purpose engines so they have to make some compromises, but you don't have to). Look for data oriented design in games. That's why it surprises me so much (considering the "scale" of Factorio as you call it) that you aren't already using a data oriented design, because the very existential purpose for data oriented designs is to get the maximum performance out of the machine :)

Rseding91
Factorio Staff
Factorio Staff
Posts: 13209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Entity/component model in prototypes

Post by Rseding91 »

I already tested storing the entities by type and running updates in series on all entities of a type - it had zero difference in performance. There's so much data and so many entities that any cache improvements mean nothing when it comes to entity updates.

By-type updates aside - they use intrusive lists because entities move between active and not active so frequently that putting them in a container like a vector DESTROYS performance with the amount of memory moving that has to be done to remove items from the container.
If you want to get ahold of me I'm almost always on Discord.

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

Hm. Interesting.

Well, I certainly could keep on going with more data points, more advise, more questions, and so on. And the points you raise do sound to me like the very symptoms of a typical classic "game object"-centered design where data layout doesn't align with data access. Funnily enough "too much data" is exactly the problem data oriented design is aiming to solve :) (and moving lots of data around can be OK if it all happens in cache). But in the end without knowing the code it's impossible to judge whether there is room for improvement or not. And whether it's worth the change is an entirely different story. I know that it can be very challenging to change an existing object oriented design into a data oriented one.

I hope I'm not coming across as implying you're incompetent or something. The fact the game works the way it does is a testimony to your skills. I'm just wondering if things can be improved. I'm kind of a performance/optimization nerd and that's sort of the primary thing I do for a living as a programmer. So I always like talking about these things and analyze them to death, which I admit can be annoying sometimes :).

Sean Mirrsen
Long Handed Inserter
Long Handed Inserter
Posts: 86
Joined: Wed Apr 27, 2016 6:30 pm
Contact:

Re: Entity/component model in prototypes

Post by Sean Mirrsen »

Sorry for butting into such a high-level discussion, I am in no way competent enough in programming to comment on how to optimize the game (aside from commenting on how it manages to juggle tens of thousands of objects with no slowdown on my potato of a tablet PC, which is really impressive! :D).

But I'd like to make an observation.

Assuming the "modules" in question are nothing but the already-existing prototypes, using some form of code bridge to mash their identical-ish parameters together (i.e. burner converts fuel into energy, generator suddenly sees it has energy, converts it into electricity). Would there not be a net performance increase if the existing vanilla entities stayed the same (single prototype each), but mods could define multiple prototypes instead of doing the hu-lua-hoop dance with event checking, in a "massive factory in a game modded to all heck" situation?

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

So I have to say this discussion has kept me thinking a lot over the past few weeks. Factorio is certainly an intriguing use case to analyse. Judging from all the information gathered from the forum alone and even though I don't know the code I am convinced there is room for improvement. There always is in typical "OO" architectures that try dealing with big data, I have yet to see the opposite. I have so many questions now. I wish I could somehow test my hypotheses. It's driving me crazy.

silverkitty23
Fast Inserter
Fast Inserter
Posts: 117
Joined: Wed May 11, 2016 6:52 am
Contact:

Re: Entity/component model in prototypes

Post by silverkitty23 »

mknejp wrote:People are always taught in school that linked lists are better suited for insert/remove because they're O(1) instead of O(n)
off topic: eehhhhhh... it's O(1) to insert, sure, but finding/deleting is O(n) (because to delete a particular item you have to find it). but this does nothing to change your point or your post, which is why I marked this as "off topic". Just a little side pedantry. Sorry.

mknejp
Fast Inserter
Fast Inserter
Posts: 154
Joined: Wed Apr 27, 2016 8:29 pm
Contact:

Re: Entity/component model in prototypes

Post by mknejp »

silverkitty23 wrote:
mknejp wrote:People are always taught in school that linked lists are better suited for insert/remove because they're O(1) instead of O(n)
off topic: eehhhhhh... it's O(1) to insert, sure, but finding/deleting is O(n) (because to delete a particular item you have to find it). but this does nothing to change your point or your post, which is why I marked this as "off topic". Just a little side pedantry. Sorry.
More off-topic pedantry: Removing and searching are two distinct operations. If you know what to remove (via existing pointer/iterator to the element) the remove operation itself is O(1) for a doubly linked list, but still O(n) for a vector where n elements have to be shifted to fill the empty space. What people usually skim over is that, up to a certain point, moving n contiguous elements in memory can be orders of magnitude faster than accessing the prev/next list nodes in random memory locations to reassign their pointers, especially if you have to do it multiple times in a hot path.

Post Reply

Return to “Won't implement”