Slowdown with 1'000 entities

[emilk]

When we have 1k entities the viewer starts slowing down due to a score of places where we do store lookups for each entity each frame.

Some of these store lookups is due to scene ingestion: every entity is checked against every archetype ("is this a point? is this a mesh? is this an arrow?"). This O(N*K) complexity needs to be solved.

Furthermore, these queries are taking up way too much time, they could be a lot faster.

We also need a good example/test of this to work from.

[emilk]

Here is a screenshot of puffin profiler with 1k entities (in a release build). App::update takes around 50ms.

About half (!) of this time is overhead from puffin scopes (there are just too many of them), but even with them off this takes around 25 ms/frame.

[teh-cmc]

Some of these store lookups is due to scene ingestion: every entity is checked against every archetype ("is this a point? is this a mesh? is this an arrow?"). This O(N*K) complexity needs to be solved.

Furthermore, these queries are taking up way too much time, they could be a lot faster.

I believe this is the result of us addressing the problem backwards at the moment.
I.e. we should be asking the store "hey, i have this archetype: which entities might possibly be concerned at all?", rather than that O(nk) query we're doing right now.

In fact the store might actually already be capable of answering that question efficiently, iirc.

[emilk]

@jleibs brought up the idea of entity tagging, which is very relevant for this. Each archetype logged to an entity adds a tag for that archetype (e.g. its name). This means each entity has a set of archetype tags (usually only one tag). This means archetypes are no longer duck-typed.

We also have the question of wether to categorize entities every frame, or once when they are added to a space view.

[emilk]

A simple reproduce is running examples/python/open_photogrammetry_format/main.py --no-frames and then hiding the points (the world/pcl entity). There are 116 cameras = 348 entities.

Enhance:

[emilk]

Me, @Wumpf, @jleibs and @teh-cmc discussed this, with a bunch of conclusions.

The first low-hanging fruit we should do is just to speed up the mapping, without changing any behavior or ui.

This can be done in a few hours

For each space view we pre-calculate a lookup map of ComponentName -> ViewPartSystemId like so (pseudo-code):

let mut component_view_parts : HashMap<ComponentName, Set<ViewPartSystemId>> = {}
for view_part in all_view_part_categories {
    for required in view_part.required_components() {
        component_view_parts[required].insert(view_part.id());
    }
}

This will produce a lookup looking something like:

{
    "rerun.mesh": {"mesh"},
    "rerun.point3d": {"point3d", "arrow"},
    "rerun.transform": {"transform_arrows"},
     …
}

Note that the cardinality of the Set<ViewPartSystemId> is usually very low, and we may want to optimize based on this.

Using this we then each frame categorize the entities of a Space View like so:

let mut view_part_entities: Map<ViewPartSystemId, Vec<Entity>> = {}

for entity in space_view.entities {
    let entity_comps = db.all_components(entity);

    let mut potential_parts: Set<ViewPartSystemId> = {}
    for component_name in entity_comps {
        potential_parts = potential_parts.union(potential_parts[component_name]);
    }

    for part_id in potential_parts {
        let view_part_system = all_view_part_systems[id];
        if view_part_system.required_components().all(|comp| db.entity_has_component(comp)) {
            // It is a hit!
            view_part_entities[part_id].push(entity);
        }
    }
}

And then we have what we wanted: for each view part system, we have a list of entities for that.
Will this be faster? Probably. It can also be trivially parallelized (e.g. using rayon).

We would need to add an id to the trait ViewPartSystem, or just use Any::type_id (ViewPartSystem already has as_any).

---

This same idea can later be reused to speed up the broader query of "What SpaceViewClasses does this Entity fit?" which we use as a heuristic for generating Space Views, and populating them with any new entity.

[emilk]

In the future we want to be able to expose to users a setting for "What ViewParts should be used to show this Entity?". For instance, given a mesh with a transform, should we show it as a mesh, a transform, or both? This would require a BTreeMap<EntityPath, EditableAutoValue<HashSet<ViewPartSystemId>>> stored in each SpaceView, and a UI for that. This would also replace the special checkbox for wether or not to show the transform-axis for an entity.

[Wumpf]

Got this quite a bit faster, however we figured out in the process that as long as auto-adding space views is enabled that takes a significant amount of time. @jleibs and me discussed how to improve the way we do space view heuristics in the future and came up with a new schema where each space view class would decide on its own heuristic (this has the added benefit of removing remaining knowledge of specific views from re_viewport. The heuristic method per class would look something like this:

    fn auto_spawn_heuristic(
        &self,
        ctx: &ViewerContext<'_>,
        ent_paths: &PerSystemEntities,
        max_num_candidates: usize,
    ) -> Vec<(AutoSpawnHeuristic, EntityPath)>;

meaning that candidate creation can be done in a much more sensible way. Some challenges there are dealing with disconnected-components.

[Wumpf]

to ilustrate the issue: this is what performance in examples/python/open_photogrammetry_format/main.py --no-frames without points looks like after my current batch of optimizations:

(once a space view is added or removed this becomes a lot faster since we no longer run auto space view heuristics)

[Wumpf]

separated this out into #3079

[emilk]

cargo r -p raw_mesh is also a pretty good benchmark