ncollide world update much slower in 0.22

[arturoc]

After porting an application from 0.19 to 0.22 calling CollisionWorld::update after updating the positions of some objects is much slower than before, what used to take 0.3ms is now taking 1.2ms.

I've done a quick benchmark and what runs in 0.19 with nalgebra 0.18 in less than 3ms takes 12ms to run on 0.22 with nalgebra 0.20:

just uncomment the correct versions in the following cargo.toml and change the default features from old to new to test 0.22 instead of 0.19:

Cargo.toml

[package]
name = "ncollide-regression-bench"
version = "0.1.0"
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
# ncollide3d = "0.22"
# nalgebra = "0.20"

ncollide3d = "0.19"
nalgebra = "0.18"

[features]
old = []
new = []
default = ["old"]

lib.rs:

#![feature(test)]

extern crate test;
use test::Bencher;

#[cfg(feature="old")]
use ncollide3d::world::{CollisionWorld, CollisionGroups, GeometricQueryType};
#[cfg(feature="new")]
use ncollide3d::pipeline::{CollisionWorld, CollisionGroups, GeometricQueryType};
use ncollide3d::shape::{Cuboid, ShapeHandle};
use nalgebra::{Isometry3, Vector3, UnitQuaternion, Translation};

#[bench]
fn bench(b: &mut Bencher) {
    let mut world = CollisionWorld::new(0.02);
    let objects = (0..1000).map(|i| {
        let pos = Translation::from(Vector3::new(i as f32, i as f32, i as f32));
        let rot = UnitQuaternion::identity();
        let position = Isometry3::from_parts(pos, rot);

        let size = i as f32 * 0.1;
        let cuboid = Cuboid::new(Vector3::new(size, size, size));
        let shape = ShapeHandle::new(cuboid);

        let groups = CollisionGroups::new()
            .with_membership(&[0])
            .with_whitelist(&[0]);

        let query_type = GeometricQueryType::Contacts(0.0, 0.0);

        let data = ();

        #[cfg(feature="old")]
        let handle = world.add(position, shape, groups, query_type, data).handle();

        #[cfg(feature="new")]
        let handle = world.add(position, shape, groups, query_type, data).0;

        handle
    }).collect::<Vec<_>>();

    let mut t = 0.;

    b.iter(|| {
        t += 1.;
        for i in (0..1000).step_by(10){
            let rot = UnitQuaternion::identity();
            let x = i as f32 * t;
            let pos = Translation::from(Vector3::new(x, x, x));
            let position = Isometry3::from_parts(pos, rot);
            let handle = objects[i];

            #[cfg(feature="new")]
            let _ = world.get_mut(handle).unwrap().set_position(position);


            #[cfg(feature="old")]
            let _ = world.set_position(handle, position);
        }
        world.update();
    });
}

[sebcrozet]

Hi!

Thank you for the test case. After some benchmarking, it appears the performance regression is caused by that line self.garbage_collect_ids(interactions).
The fact that it iterates through all the contacts may be quite expensive.

The version 0.19 did not have this because the removal of unused contact ids was done directly by the contact generator. This has been modified that way in prevision of the parallelization of the narrow phase. Though we'll have to think of another method to avoid this performance impact.