Immutable Tree slower than Mutable one ?

[Pierre-ZACHARY]

Hello! I think I've found a usecase where the immutable tree is slower than mutable one ..?

I'm trying to build a kdtree from 3D points on a sphere

I'm not too sure if I'm doing something wrong here

You can easily reproduce with this code snippet :

#[test]
    fn kiddo_immutablevsmutable(){
        use hexasphere::shapes::IcoSphere;
        use kiddo::float::kdtree::KdTree;
        use std::time::Instant;
        use kiddo::immutable::float::kdtree::ImmutableKdTree;

        let subdivision = 150;
        let subdivided = IcoSphere::new(subdivision, |_| ());
        let content_to_add: Vec<[f32; 3]> = subdivided.raw_points().iter().map(|point| [point.x, point.y, point.z]).collect();

        let start = Instant::now();
        let mut kdtree: KdTree<f32, u32, 3, 256, u16> = (&content_to_add).into();
        println!(
            "KdTree Construction complete. ({:?})",start.elapsed()
        );

        let start_immutable = Instant::now();
        let kdtree_immutable: ImmutableKdTree<f32, u32, 3, 256> = ImmutableKdTree::new_from_slice(&content_to_add);
        println!(
            "Immutable Construction complete. ({:?})",start_immutable.elapsed()
        );
    }

KdTree Construction complete. (107.4033ms) Immutable Construction complete. (1.0911594s)

[acshi]

I think this is expected because creating the immutable tree does more work.

From the release notes: "ImmutableKdTree balances and optimises the tree at construction time, ensuring much more efficient memory usage (and a correspondingly smaller size on-disk for serialized trees)."

[sdd]

Hi, @acshi is correct here. The ImmutableTree achieves a smaller memory footprint and more efficient query at the cost of increased construction time.

[Pierre-ZACHARY]

I see; I was thinking it should be around the same, tho I can't even construct the immutable tree past 300+ division, seems exponential; for 500 divisions the kdtree takes 1.7s on my computer / i7 8th; immutable timed out after 5 min