Rust code is extremely slow. Tips on speeding up

Question

I am facing some challenges with optimizing my Rust code for a standard inertia weight global best particle swarm algorithm, specifically for the well-known sphere benchmark function. As a newcomer to Rust, I understand that my code may not be the most efficient. However, I have hit a wall with speeding it up without resorting to parallelism. It's worth noting that I cannot assume the dimension and swarm size at compile time, hence my use of vectors. I am aware that my code utilizes clone in a hot loop, but I am at a loss for alternatives. Could someone kindly offer pointers on how to increase the speed of my code? I would greatly appreciate any tips or advice. It is currently running 3x slower than an equivalent program I wrote in Python.

Thank you!

Here is the code:

use std::fmt::Display;

use rand::Rng;

struct ObjectiveFunctionStruct {
    name: String,
    function: fn(&Vec<f64>) -> f64,
    lower_bound: Vec<f64>,
    upper_bound: Vec<f64>,
}

struct Particle {
    position: Vec<f64>,
    velocity: Vec<f64>,
    personal_best_position: Vec<f64>,
    personal_best_fitness: f64,
}

impl Display for Particle {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "(Position: {:?}, Velocity: {:?}, Personal Best Position: {:?}, Personal Best Fitness: {})", self.position, self.velocity, self.personal_best_position, self.personal_best_fitness)
    }
}

struct Swarm {
    w: f64,
    c1: f64,
    c2: f64,
    particles: Vec<Particle>,
    global_best_position: Vec<f64>,
    global_best_fitness: f64,
    objective_function_struct: ObjectiveFunctionStruct,
    rng_thread: rand::rngs::ThreadRng,
}

impl Swarm {
    fn new(w: f64, c1: f64, c2: f64, swarm_size: usize, objective_function_struct: ObjectiveFunctionStruct) -> Swarm {
        let dimension: usize = objective_function_struct.lower_bound.len();
        let mut particles: Vec<Particle> = Vec::new();
        let mut rng_thread: rand::rngs::ThreadRng = rand::thread_rng();
        let mut global_best_position: Vec<f64> = vec![0.0; dimension];
        let mut global_best_fitness: f64 = std::f64::MAX;
        for _ in 0..swarm_size {
            let mut particle: Particle = Particle {
                position: (0..dimension).map(|i| rng_thread.gen_range(objective_function_struct.lower_bound[i]..objective_function_struct.upper_bound[i])).collect(),
                velocity: vec![0.0; dimension],
                personal_best_position: vec![0.0; dimension],
                personal_best_fitness: std::f64::MAX,
            };
            particle.personal_best_position = particle.position.clone();
            particle.personal_best_fitness = (objective_function_struct.function)(&particle.position);
            if particle.personal_best_fitness < global_best_fitness {
                global_best_fitness = particle.personal_best_fitness;
                global_best_position = particle.personal_best_position.clone();
            }
            particles.push(particle);
        }
        Swarm {
            w,
            c1,
            c2,
            particles,
            global_best_position,
            global_best_fitness,
            objective_function_struct,
            rng_thread,
        }
    }

    fn update_particles(&mut self) {
        for particle in &mut self.particles {
            let dimension: usize = particle.position.len();
            for i in 0..dimension {
                particle.velocity[i] = self.w * particle.velocity[i] + self.c1 * self.rng_thread.gen_range(0.0..1.0) * (particle.personal_best_position[i] - particle.position[i]) + self.c2 * self.rng_thread.gen_range(0.0..1.0) * (self.global_best_position[i] - particle.position[i]);
                particle.position[i] += particle.velocity[i];
            }
            let fitness: f64 = (self.objective_function_struct.function)(&particle.position);
            if fitness < self.global_best_fitness {
                particle.personal_best_fitness = fitness;
                particle.personal_best_position = particle.position.clone();
                self.global_best_fitness = fitness;
                self.global_best_position = particle.position.clone();
            } else if fitness < particle.personal_best_fitness {
                particle.personal_best_fitness = fitness;
                particle.personal_best_position = particle.position.clone();
            }
        }
    }


    fn run(&mut self, iterations: usize) {
        for _ in 0..iterations {
            self.update_particles();
        }
    }

    fn print(&self) {
        println!("Global Best Position: {:?}", self.global_best_position);
        println!("Global Best Fitness: {}", self.global_best_fitness);
    }
}

fn sphere_function(x: &Vec<f64>) -> f64 {
    x.iter().map(|a: &f64| a.powi(2)).sum()
}

fn main() {
    use std::time::Instant;
    let now = Instant::now();
    let dim = 100;
    let objective_function_struct: ObjectiveFunctionStruct = ObjectiveFunctionStruct {
        name: "Sphere Function".to_string(),
        function: sphere_function,
        lower_bound: vec![-5.12; dim],
        upper_bound: vec![5.12; dim],
    };
    let mut swarm: Swarm = Swarm::new(0.729, 1.49445, 1.49445, 1000, objective_function_struct);
    swarm.run(10000);
    swarm.print();
    let elapsed = now.elapsed();
    println!("Elapsed: {} ms", elapsed.as_millis());
}

Answer 1

• While optimizing global fitness, you clone vectors on each iteration. I would take a reference, then clone it once after the loop.
• You may need random number generator tuning, as the default implementation may be secure but slow.
• Data locality is significant. Lines of Vec<f64> are sparse in memory, so the CPU invalidates its L1/L2/L3 caches too often. You may allocate a single contiguous array for all particles. Also, switching from f64 to f32 serves the same purpose.
• Parallelize computations either with SIMD or rayon.
• Follow guidelines from the Rust Performance Book.