bevyengine / bevyengine/bevy

High performance sorted queries

Open
#13,464 31 comments 7 reactions 0 assignees View on GitHub
A-ECS C-Feature C-Performance D-Complex S-Needs-Design-Doc X-Needs-SME
Dominant language
Rust
Stars
48.2k
Forks
4.8k
Avg merge
3d 16h
Merged PRs (30d)
171

Description

## What problem does this solve or what need does it fill?

#13417 adds sorting at an iterator level. These sorts:
- Do not persist across system runs (it will be common for sorted data to rarely be mutated).
- Make query iteration completely random access.

## What solution would you like?
1. Command to reorder tables.
2. Rearrange tables for sorted queries by default.
3. Make queries cache sorts & use change detection to early out of resorting.
4. Condense sorts to `low..=high` ranges for cache friendly iteration.
5. Optionally cache iteration position to allow suspending and resuming iteration between system runs. This is useful for ui scroll areas and any rhythm game.

Final API should look something like this:
```rs
fn cmp(left: FilteredEntityRef, right: FilteredEntityRef) -> std::cmp::Ordering {
left.get::().unwrap().cmp(&right.get::().unwrap())
}

fn sys(mut query: Query<(&A, &B)>) {
for (a, b) in query.sort(cmp)
// Optional call that will prevent tables from being reorderd.
// Useful if you have multiple systems requesting slightly different sorts or
// just completely opting out of reordering & doing multiple ordering manually.
// User could do multiple stable sorts to get dense iteration across multiple systems.
.no_reorder()
.iter()
{
// ..
}
}

#[derive(Component)]
struct Offset(pub f64);

fn sort_by_offset(left: FilteredEntityRef, right: FilteredEntityRef) -> std::cmp::Ordering {
left.get::().unwrap().0.cmp(&right.get::().unwrap().0)
}

fn seek_by_offset(entity: FilteredEntityRef, needle: f64) -> std::cmp::Ordering {
entity.get::().unwrap().0.cmp(&needle)
}

fn timeline(mut query: Query<(&Offset, &A, &B)>, time: Res

## What alternative(s) have you considered?

- Putting things in resources and doing these sorts myself. This is only viable when you've feature frozen your project and need no changes to data architecture. You completely lose the flexibility of ECS doing this.
- Despawning entities & reinserting them into tables. This first requires knowing all the components to take out of an entity and secondly relies on side effects. Table order is not part of the API contract.

## Additional context

Missing prerequisite features:
- `World::parallel_commands`/make the world command queue thread local by default (needed to allow queries to do `2.`).
- Archetype level change detection: #5097 (needed for `3.`).

Not required but helpful missing feature:
- Queries as entities (can avoid introducing the cache structure for queries that aren't sorted).

Contributor guide

Open the contributing guide

Research direction

Start by reviewing #13417 and the listed prerequisites, especially World::parallel_commands and #5097. Assess how persistent table reordering, cached sorts, range condensation, and resumable seeking would fit the Query API. Done would require an agreed scope and API for these design points, followed by implementation and validation.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
game-dev, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.