Abysmal performance with vectors in c++

Question

Disclaimer: i just started programming in c++.

---

So i made a little program in c++ using SFML where i have 300 particles stored in a vector that are attracted to each other.

The program runs at 17 FPS!! i tried doing the same using a standard array and it didn't run much faster.

The same code in java using the Array libgdx class runs at 5000 FPS. Using the java.util.Vector class runs at 2000 FPS.

Debugging i found out that most of the delay comes from retrieving an element from the vector.

I know i'm doing something wrong in that regard, so i would be grateful if someone can help me out.

Here is the update loop.

void update(RenderWindow& window) {
    window.clear();

    for (size_t i = 0, size = particles.size(); i != size; ++i) {
        Particle &part = particles[i];

        glm::vec2 forceSum;

        for (size_t j = 0, size = particles.size(); j != size; ++j) {
            Particle &part2 = particles[j];
            if (j == i) 
                continue;

            glm::vec2 v1 = part.getPos() - part2.getPos();
            glm::vec2 v2 = glm::normalize(v1);

            if (glm::length(v1) < 50)
                forceSum += (v2 * -0.1f);
        }

        part.applyForce(forceSum);
        part.update();

        shape.setPosition(part.getPos().x, part.getPos().y);
        window.draw(shape);
    }

    window.display();
}

I can show more code if requested.

Thanks in advance!

---

main.cpp

#include "stdafx.h"


using namespace std;
using namespace sf;

void update(RenderWindow& window);

int t = 0;
CircleShape shape(4);

vector<Particle> particles;

int main() {
    ContextSettings settings;
    settings.antialiasingLevel = 16;
    RenderWindow window(VideoMode(800, 800), "test", Style::Default, settings);

    shape.setFillColor(Color(155, 155, 155, 124));
    srand(4);

    for (int i = 0; i < 300; i++) {
        Particle particle = Particle(glm::vec2(rand() % 800, rand() % 800), rand() % 10);
        particles.push_back(particle);
    }

    while (window.isOpen())
    {
        Event event;
        while (window.pollEvent(event))
        {
            if (event.type == Event::Closed)
                window.close();
        }

        update(window);
    }
    return 0;
}

void update(RenderWindow& window) {
    window.clear();

    for (size_t i = 0, size = particles.size(); i != size; ++i) {
        Particle &part = particles[i];

        glm::vec2 forceSum;

        for (size_t j = 0, size = particles.size(); j != size; ++j) {
            Particle &part2 = particles[j];
            if (j == i) 
                continue;

            glm::vec2 v1 = part.getPos() - part2.getPos();
            glm::vec2 v2 = glm::normalize(v1);

            if (glm::length(v1) < 50)
                forceSum += (v2 * -0.1f);
        }

        part.applyForce(forceSum);
        part.update();

        shape.setPosition(part.getPos().x, part.getPos().y);
        window.draw(shape);
    }

    window.display();
}

Particle.h

#pragma once

#include <SFML/Graphics.hpp>

class Particle {
public:
    Particle(glm::vec2 pos, float m);
    void update();
    void applyForce(const glm::vec2 &fce);
    void setPos(const glm::vec2 &pos);
    void setV(const glm::vec2 &vel);
    const glm::vec2 getPos();
    const glm::vec2 getV();
private:
    float mass;
    glm::vec2 acceleration = glm::vec2(0, 0);
    glm::vec2 position = glm::vec2(0, 0);
    glm::vec2 velocity = glm::vec2(0, 0);
};

Particle.cpp

#include "stdafx.h"
#include "Particle.h"
#include <iostream>

using glm::vec2;

Particle::Particle(vec2 pos, float m) {
    mass = m;
    position = pos;
}

void Particle::update() {
    velocity += acceleration;
    if (position.x + velocity.x > 800 || position.x + velocity.x < 0 ||     position.y + velocity.y > 800 || position.y + velocity.y < 0) {
        velocity.x = 0; velocity.y = 0;
    }
    position += velocity;
}

void Particle::applyForce(const vec2 &fce) {
    acceleration = fce/mass;
}

void Particle::setPos(const vec2 &pos) {
    position = pos;
}

void Particle::setV(const vec2 &vel) {
    velocity = vel;
}

const vec2 Particle::getV() {
    return velocity;
}


const vec2 Particle::getPos() {
    return position;
}

Answer 1

I've ran a vs studio profiler session on your code.

The app spends 59% of its time calculating square roots. You should optimize your code as follow:

    glm::vec2 v1 = part.getPos() - part2.getPos();
    glm::vec2 v2 = glm::normalize(v1);     // <- 1 square root computed here

    if (glm::length(v1) < 50)              // <- another one here
        forceSum += (v2 * -0.1f);

Becomes:

    glm::vec2 v1 = part.getPos() - part2.getPos();
    float l = glm::dot(v1, v1);
    if (l < 2500)
    {
        forceSum += (v1 / sqrt(l));
    }

 }  // end inner loop
 part.applyForce(forceSum * .1f);

This will divide the time spent calculating square roots by 2 or more.

With null vec2s this optimization made execution on my machine go from 38s/10000 frames to 7s/10000 frames.

Thanks to BorgLeader and Rabbid76, who helped optimize your code further.