The two key benefits that I constantly hear lauded about entity systems are 1) the easy construction of new kinds of entities due to not having to tangle with complex inheritance hierarchies, and 2) cache efficiency.
Note that (1) is a benefit of component-based design, not just ES/ECS. You can use components in many ways that do not have the "systems" part and they work just fine (and plenty of both indie and AAA games use such architectures).
The standard Unity object model (using GameObject and MonoBehaviour objects) is not an ECS, but is component-based design. The newer Unity ECS feature is an actual ECS, of course.
Systems need to be able to work with more than one component, ie both the rendering and physics system need to access the transform component.
Some ECS sort their component containers by Entity ID, meaning that the corresponding components in each group will be in the same order.
This means that if you're linearly iterating over graphics component you're also linearly iterating over the corresponding transform components. You might be skipping some of the transforms (since you may have physics trigger volumes that you don't render or such) but since you're always skipping forward in memory (and by not particularly huge distances, usually) you're still going to have efficiency gains.
This is similar to how you have the Structure Of Arrays (SOA) being the recommended approach for HPC. The CPU and cache can deal with multiple linear arrays almost as well as it can deal with a single linear array, and far better than it can deal with random memory access.
Another strategy used in some ECS implementations - including Unity ECS - is to allocate Components based on the Archetype of their corresponding Entity. That is, all Entities with precisely the set of Components (PhysicsBody, Transform) will be allocated separately from the Entities with different Components (e.g. PhysicsBody, Transform, and Renderable).
Systems in such designs work by first finding all Archetypes that match their requirements (that have the required set of Components), iterating that list of Archetypes, and iterating the Components stored within each matching Archetype. This allows for completely linear and true O(1) component access within an Archetype and allows Systems to find compatible Entities with very low overhead (by searching a small list of Archetypes rather than searching potentially hundreds of thousands of Entities).
You can have components store pointers to other components, or pointers to entities that store pointers to components.
Components referencing other components on the same entity don't need to store anything. To reference components on other entities, just store the entity ID.
If a component is allowed to exist more than once for a single entity and you need to reference a particular instance, store the other entity's ID and a component index for that entity. Many ECS implementations do not allow this case, however, specifically because it makes these operations less efficient.
You can ensure that every component array is 'n' large, where 'n' is the number of entities alive in the system
Use handles (e.g. indices + generation markers) and not pointers and then you can resize the arrays without fear of breaking object references.
You can also use a "chunked array" approach (an array of arrays) similar to many common std::deque implementation (though without the pitifully-small chunk size of said implementations) if you want to allow pointers for some reason or if you have measured problems with array resize performance.
Secondly, this is all assuming that entities are processed linearly in a list every frame/tick, but in reality this is not often the case
It depends on the entity. Yes, for many use cases, it's not true. Indeed, this is why I so strongly stress the difference between component-based design (good) and entity-system (a specific form of CBD).
Some of your components will certainly be easy to process linearly. Even in normally "tree heavy" use cases we have definitely seen performance increases from using tightly packed arrays (mostly in cases involving an N of a few hundred at most, like AI agents in a typical game).
Some developers have also found that the performance advantages of using data-oriented linearly-allocated data structures outweighs the performance advantage of using "smarter" tree-based structures. It all depends on the game and specific use cases, of course.
Say you use a sector/portal renderer or an octree to perform occlusion culling. You might be able to store entities contiguously within a sector/node, but you're going to be jumping around whether you like it or not.
You'd be surprised how much the array still helps. You're jumping around in a much smaller region of memory than "anywhere" and even with all the jumping you're still much more likely to end up in something in cache. With a tree of a certain size or less, you might even be able to prefetch the whole thing into cache and not ever have a cache miss on that tree.
There are also tree structures that are built to live in tightly packed arrays. For instance, with your octree, you can use a heap-like structure (parents before children, siblings next to each other) and ensure that even when you "drill down" the tree you're always iterating forward in the array, which helps the CPU optimize the memory accesses / cache lookups.
Which is an important point to make. An x86 CPU is a complex beast. The CPU is effectively running a microcode optimizer on your machine code, breaking it into smaller microcode and reordering instructions, predicting memory access patterns, etc. Data access patterns matter more than may be readily apparent if all you have is a high-level understanding of how the CPU or cache work.
Then you have other systems, which might prefer entities stored in some other order.
You could store them multiple times. Once you strip down your arrays to the bare minimum details, you might find you actually save memory (since you've removed your 64-bit pointers and can use smaller indices) with this approach.
You could interleave your entity array instead of keeping separate arrays, but you're still wasting memory
This is antithetical to good cache usage. If all you care about are the transforms and graphics data, why make the machine spend time pulling in all that other data for physics and AI and input and debug and so on?
That's the point usually made in favor of ECS vs monolithic game objects (though not really applicable when comparing to other component-based architectures).
For what it's worth, most "production-grade" ECS implementations of which I'm aware use interleaved storage. The popular Archetype approach I mentioned earlier (used in Unity ECS, for example) is very explicitly build to use interleaved storage for Components associated with an Archetype.
AI is pointless if it can't affect the transform or animation state used for an entity's rendering.
Just because AI can't efficiently access transform data linearly doesn't mean that no other system can use that data layout optimization effectively. You can use a packed array for transform data without stopping game logic systems from doing things the ad hoc way game logic systems usually do things.
You're also forgetting code cache. When you use the systems approach of ECS (unlike some more naive component architecture) you're guaranteeing that you're running the same small loop of code and not jumping back and forth through virtual function tables to an assortment of random Update functions strewn all over your binary. So in the AI case, you really want to keep all your different AI components (because certainly you have more than one so that you can compose behaviors!) in separate buckets and process each list separately in order to get the best code cache usage.
With a delayed event queue (where a system generates a list of events but doesn't dispatch them until the system finishes processing all entities) you can ensure that your code cache is used well while keeping events.
Using an approach where each system knows which event queues to read out of for the frame, you can even make reading events fast. Or faster than without, at least.
Remember, performance isn't absolute. You don't need to eliminate every last single cache miss to start seeing the performance benefits of good data-oriented design.
There is still active research into making many game systems work better with ECS architecture and data-oriented design patterns. Similarly to some of the amazing things we've seen done with SIMD in recent years (e.g. JSON parsers), we're seeing more and more things done with ECS architecture that doesn't seem intuitive to classical game architectures but offers a number of benefits (speed, multi-threading, testability, etc.).
Or perhaps there's a hybrid approach that everyone's using but nobody's talking about
This is what I have advocated in the past, especially for folks who are skeptical of ECS architecture: use good data-oriented approaches to components where the performance is critical. Use simpler architecture where simplicity improves development time. Don't shoe-horn every single component into a strict over-definition of componentization like ECS proposes. Develop your component architecture in such a way that you can easily use ECS-like approaches where they make sense and use simpler component structure where ECS-like approach don't make sense (or make less sense than a tree structure, or so on).
I'm personally a relatively recent convert to the true power of ECS myself. Though for me, the deciding factor was something rarely mentioned about ECS: it makes writing tests for game systems and logic almost trivial compared to the tightly-coupled logic-laden component-based designs I've worked with in the past. Since ECS architectures put all logic in Systems, which just consume Components and produce Component updates, building a "mock" set of Components to test System behaviour is quite easy; because most game logic should live solely inside Systems, that effectively means that testing all your Systems will provide fairly high code coverage of your game logic. Systems can use mock dependencies (e.g. GPU interfaces) for tests with far less complexity or performance impact than you'd get if you had to inject those dependencies into thousands of interconnected logic-heavy Components.
As an aside, you might note that a lot of people talk about ECS without really understanding what it even is. I see classic Unity referred to as ECS with depressing frequency, illustrating that too many game developers equate "ECS" with "Components" and pretty much ignore the "Entity System" part entirely. You see a lot of love heaped on ECS on the Internet when a large portion of the people are really just advocating component-based design, not actual ECS. At this point it's almost pointless to argue it; ECS has been corrupted from its original meaning into a generic term and you might as well accept that "ECS" doesn't mean the same thing as "data-oriented ECS". :/
