-
-
Notifications
You must be signed in to change notification settings - Fork 3.3k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
High performance sorted queries #13464
Comments
This is a follow-up to #1470. The other thing that this opens up is efficiently querying (using dynamic queries only, since enum variants aren't types) for enum variants. If we can store tables in a sorted form, requesting all |
First of all, thanks for the issue! I'd like to go through the parts of your suggested solution:
On the example itself (other than the already presented issues above):
|
// A, B
A(0), B
A(4), B
A(5), B
// A, B, C
A(1), B, C
A(2), B, C
A(3), B, C And you want to sort by
If you want different sorts in different systems. You will get dense iteration across
I don't think you actually understand the difference between these.
That is another reason why it has |
I've updated the seek example to be more flexible. |
On |
|
|
3./4./5. Most improvements to |
With queries as entities queries can have row polymorphism like everything else that's at an ECS level. This means caching is no longer limited to either:
Query entities can have different components for whatever caches they need. Aside from sort caches they will need other cache structures as we add new features. Two things that come to mind:
I would not worry about queries as entities as they're one of the prerequisite/accompanying features for relations and the sort cache can be refactored when they land. |
Another question I have about the final API example: |
This will either remove the existing API or exist along side it.
This sounds like an esoteric misfeature. How would a user know exactly which subset of items they would want sorted in the first place? There are zero guarantees about iteration order.
There should be no single use vectors.
If |
F.e. if we want to sort the children of an entity. The |
That's not a subset of entities in a query that's mapping an entity list. Which is at best niche because
|
When should the command be executed? If it's executed right away and reorders the The logical conclusion is that the reordering of the table must happen right before the system that requires the sort runs (or after the last mutable access, but its impossible to know when that would be). After thinking about it, I think there are 3 options that allow for dense, sorted iteration:
|
In the next sync point. So basically the first run would be without dense iteration, the second run will need to rebuild the sort cache again and every run after that will be dense. (Until you have a mutation which will start this whole process again) |
What problem does this solve or what need does it fill?
#13417 adds sorting at an iterator level. These sorts:
What solution would you like?
low..=high
ranges for cache friendly iteration.Final API should look something like this:
What alternative(s) have you considered?
Additional context
Missing prerequisite features:
World::parallel_commands
/make the world command queue thread local by default (needed to allow queries to do2.
).3.
).Not required but helpful missing feature:
The text was updated successfully, but these errors were encountered: