Entt: Loop a view while looping a view (!)

[gale93]

Hi, I am trying to iterate the same view more times because I need to do cross checks somewhat like this:

auto view = registry->view<C1, C2>();
for (auto entity : view)
{
    auto &c1 = view.get<C1>(entity);
    auto &c2 = view.get<C2>(entity);
    for (auto entity2 : view)
    {
        auto &c12 = view.get<C1>(entity2);
        auto &c22 = view.get<C2>(entity2);
               // do checks beetwen entity and entity2
    }
}

But this slow down performance heavily, I tried other ways ( such as use the lambda style or create a second view for the other iterations ) but still no fortune.
So, the point is, there's a particular method or is this should work and my code is elsewhere shitty ?

Thanks for your time :D

[skypjack]

Well, it's O(N^2) only to iterate twice your entities and this would be already enough to ruin performance. Add to the result the time spent during the calls to get their components and do not forget that you're hurting your cache for sure doing this... It isn't due to the view for itself, this is a pattern of use that cannot be fast any time soon probably. Iterators visit a tightly packed array of entities and nothing more at the end of the day.

What problem are you trying to solve exactly?
I mean, if you can give me more details about why you think you need a nested loop to solve your problem and what you are trying to do, maybe I can help you figuring out an alternative approach that doesn't ruin the performance.

[skypjack]

As a side note, if you can't tell me more and you still want to use a nested loop, try to avoid doing more than once the same task.
Use iterators directly (see member functions begin and end) and start your nested loop from begin+1.
This will drastically reduce the amount of work required to perform the double check and you won't test i against j if you already checked them the opposite direction.

---

I'm closing the issue because this isn't an issue of EnTT.
Feel free to continue here our discussion anyway, not a problem for me.

[gale93]

Oh well, that should have been a fast workaround ( I knew about complexity -and for being cache unfriendly- , but I am doing tests with few entities (50) so I wrongly guessed that could work ), I will try using iterators directly, it seems as hacky as I need ! :'D

Anyway, nothing to hide, I am just trying to check collisions between entities and when I'll implement a quadtree detection this problem is basically solved !

[skypjack]

few entities (50)

It's 2500 times whatever you do in the _do checks between entity and entity2_. Not that much actually, but to be avoided possibly.

I wrongly guessed that could work

If you can make a minimal example to reproduce the issue, I can investigate a bit further. However, I do not expect to find much more than what I've said with the previous comment.
In general, nested loops should be (and can be) avoided when it comes to working with an ECS.

Can I ask you some _measures_ to know what's the performance hit you are facing? Something like: single loop N ms, nested loop M >> N ms.
Have you this information? I mean, you measured somehow that _it goes slower_, right? How did you do it?
Thank you!!

I will try using iterators directly, it seems as hacky as I need

I'm glad to help. I hope it solved your problem.

[gale93]

I didnt start implement anything complex because I instantly noticed the perfomance loss.

Basically, without many changes from the sample code i showed you ( There isnt code that actually modify something ):
this function is called at 25 hz on 50 entities

First loop without the second: 500 microseconds
First loop with the second ( without calling components ) : 4000 microseconds
First loop with the second ( calling components / the full sample posted above ): 25000 microseconds

Anyway I had already planned to upload the demo I am making on github asap, if you are interested i'll PM you when I do ( The demo is just for show some functionallities to friends, so it use only -and heavily- EnTT and SFML )

[skypjack]

Sure, feel free to drop a message here and I can look at it. If there is a chance to improve EnTT, why not? :-)
The real fuel of the project are its users, so help is always welcome!!

[skypjack]

I made some tests. Here is the code I used (without the instrumentation part used to measure it):

    struct C1 { int v; };
    struct C2 { int v; };

    entt::DefaultRegistry registry;
    auto view = registry.view<C1, C2>();

    for(auto i = 0; i < 50; ++i) {
        const auto entity = registry.create();
        registry.assign<C1>(entity, i);
        registry.assign<C2>(entity, i);
    }

    // (1)
    for (auto entity : view) { (void)entity; }

    // (2)
    for (auto entity : view) {
        for (auto entity2 : view) {
            (void)entity;
            (void)entity2;
        }
    }

    // (3)
    for (auto entity : view) {
        auto &c1 = view.get<C1>(entity);
        auto &c2 = view.get<C2>(entity);

        for (auto entity2 : view) {
            auto &c12 = view.get<C1>(entity2);
            auto &c22 = view.get<C2>(entity2);

            c1 = c12;
            c2 = c22;
        }
    }

Results are much different from what you are observing actually. In particular:

• When compiled in debug mode (-O0 among the others):

  • (1): 2.4851e-05 seconds
  • (2): 0.000839429 seconds
  • (3): 0.00520002 seconds

• When compiled in release mode (-O3 among the others):

  • (1): 2.807e-06 seconds
  • (2): 4.2327e-05 seconds
  • (3): 7.3602e-05 seconds

It confirms that the nested loop ruins a bit the performance. In debug mode (so, without any kind of optimizations) it's quite evident. However, if I switch to the release mode and therefore I compile it with optimizations enabled, performance are much, much different from what you reported.

Results are a bit better as expected if using directly iterators in debug mode:

• (1): 2.2944e-05 seconds
• (2): 0.000577582 seconds
• (3): 0.0038498 seconds

In release mode it's a bit faster as well but hardly you can observe it.

[gale93]

Oh snap, I didn't even try in Release mode, shame on me :D
I'll just do debug with few entities and all is fine !
Anyway I've put a sample on github feel free to take a look BUT (!) it's simple code not expect that much I'm doing this only in the free time of the free time :D ( randballs, where this is where I was implementing the nested loop )

[gale93]

Little update about randballs, now it have a demo video and the code is a bit less dirty :)
I wont update the status of that project here anymore ( I swear ! ) but I thought you might be interested ^^"

[skypjack]

Not a problem, you can drop a comment here whenever you want.
When you have something of which you feel confident, we can also mention your project in the README file if you want.

[gale93]

That's would be great, I plan to add a lot of features !
Oh P.s.: I quoted you on sfml forum, I hope new people will know EnTT because it really deserve it :D

[skypjack]

Really appreciated. Thank you. I'm glad to know users find EnTT so valuable!! ;-)

[gale93]

I have added a new video with some new functionalities and finally implemented a rudimental quadtree. It is a little bit dirty, but it works great and performances are very promising ( I am using a single view called more time -> look here if you are interested ! )

And yes, I am honorated now if you mention randballs in EnTT: Now all is a little more clean and my objective is to continue add stuff until it becomes a little cool tech demo 🥇

[skypjack]

Sure. EnTT needs you as an user to grow up!!
Would you mind to make a PR for randballs?
It's enough to edit the README file, it has a dedicated section for _projects that use EnTT_ close to the end.
Otherwise I can edit it myself, not a problem.

[danielytics]

@skypjack

I'm glad to know users find EnTT so valuable!! ;-)

FWIW, I really like EnTT and am in the process of integrating it as a core part of a toy project I'm working on. It has the right mix of features and performance, better than anything I would have cooked up myself anyway, so your work is very much appreciated!

(My only nitpick is that I don't like the name "tag" because in my mind tags can be applied to many things not just one -- eg tags on blog posts -- but hey, can't have everything I want, haha; I'll never bring it up again, I promise)

@gale93 what license is randballs under? I'm really interested in looking at your quadtree code since I will be implementing my own soon too, but I want to make sure its compatible with my codes license before I do (mine is MIT). I didn't see a license file in your repo.

[skypjack]

@danielytics

You are right, I wanted to change the name to something like unique_t or... well, suggestions? tag_t is quite annoying mostly for the reasons you mentioned, I agree, it's misleading somehow.

That being said, I'm glad you like EnTT. Feel free to propose features and improvements whenever you want and do not hesitate to participate in issues and discussions. I'm trying to create a small community around EnTT, so that it will grow again in the future thanks to its users.

[gale93]

@danielytics I just added MIT License, but meanwhile the performances are good enough for what it needs to achieve, it is a "static(static, static!)" implementation and could be endorsed a lot!

[skypjack]

@gale93 I added a commit with a mention on branch experimental. I'll merge it on master soon. Thank you.