Linear Search in TypeExpression.Matches(IEnumerable) impacts performance for (extremely) wide Archetype Signatures

[thygrrr]

What:

Optimization potential. In very complex N:N or 1:N / O(N²) cases, type expression searches have a massive impact on runtime. While the shown unit test is a THEORETICAL situation, the same might also apply in normal use.

For example it could also be a case for very complex Worlds (i.e. many, many Archetypes) where new Queries would need to search and match many Archetypes, and Archetypes would need to go and update Queries many times (each time a new Archetype is created or disposed).

Filter Expressions would also drastically benefit from this in complex or degenerate Worlds, not just Query Expressions / Match Expressions.

Repro:

e.g. this code is very slow for 500+ relations (that's a LOT of relations on just one Entity, clearly a degenerate case); and it is slow mostly because of the foreach loop in the while loop, which causes to the order of 500² linear set searches of O(~500) elements each, but the cost is also significant (but in the low milliseconds) without this extra loop.

    [Theory]
    [InlineData(1)]
    [InlineData(2)]
    [InlineData(3)]
    [InlineData(10)]
    [InlineData(100)]
    [InlineData(500)] // takes a long time
    public void DespawnRelationTargetRemovesComponent(int relations)
    {
        using var world = new World();
        
        var subject = world.Spawn();
        
        world.Entity()
            .Add<int>(default, subject)
            .Add(Link.With("relation target"))
            .Spawn(relations)
            .Dispose();
        
        var targets = new List<Entity>(world.Query<int>(subject).Compile());

        var rnd = new Random(1234 + relations);
        foreach (var target in targets)
        {
            subject.Add<int>(Relate.To(target));
        }

        while (targets.Count > 0)
        {
            var target = targets[rnd.Next(targets.Count)];

            Assert.True(subject.Has<int>(target)); // o(n)*o(n)
            
            target.Despawn();
            targets.Remove(target);

            foreach (var remaining in targets)
            {
                Assert.True(subject.Has<int>(remaining)); // o(n)*o(n)*o(n)
            }
            
            Assert.False(subject.Has<int>(target));
        }
    }

Potential Fix

It would be possible to considerably speed this up by providing a MatchSignature property (this is cheap to make) which is the same as the Signature, but also includes the relevant wildcards. e.g. an Archetype with Entity-Entity Relation components will also contain the Match<T>.Entity wildcard for those relations in its MatchSignature even though no such Storage<T> exists; simply as to match queries with Match<T>.Entity in them.

In fact, this may be a simple enhancement with profound impact on scalability for (admittedly degenerate!) relationship scenarios.

Caution

If this is implemented, reverse lookups, such as DespawnDependencies, must have access to a non-commutative means of matching; because commutative matching will not work with these wildcards added to the Signatures.

Possibly a storage list / storage signature / pure signature is easier to build.

This could also speed up matching in general for a infinitesimal, one-time cost during Archetype creation.

[thygrrr]

Improved in #16

[thygrrr]

No, I was mistaken. This is still alive and kicking, because of how Signature.Contains works (it's not the set contain - it's actually the Linq IEnumerable Contains!)

Only cut it down by ~50%, but that doesn't help with polynomial degree > 2 runtime.

[thygrrr]

Nah, it was actually resolved, but now the linear o(n) runtime is in Signature.Expand() which takes up half of the cost of creating new archetypes (for CRAZY LARGE signatures, averaging lengths of ~500 Match Expressions ... and only when doing this in a CRAZY complex N:M relation web)

Might need to turn the matching logic around somehow. This is tricky, I'll keep you all posted.