#Is there any way to optimize the distance equation?

136 messages · Page 1 of 1 (latest)

round brook
#

So I'm running a particle simulation where all particles orbit an object but there are some issues with the speed of my code, I did some testing and found two parts of my code which have issues, 1. my distance equation function, and 2. my force calculator

double distance(sf::Vector2f position1, sf::Vector2f position2) {
    float dx = position1.x - position2.x;
    float dy = position1.y - position2.y;
    return sqrt(pow(dx, 2) + pow(dy, 2) * 1.0);
}


sf::Vector2f gravitate(float fa, sf::VertexArray* blackHoles, sf::Vertex point, sf::Vector2f velocity) {
    for (int i = 0; i < (*blackHoles).getVertexCount(); i++) {
        float dist = distance(point.position, (*blackHoles)[i].position);
        float force = fa / (std::pow(dist, 2));

        velocity += ((*blackHoles)[i].position - point.position) * force;
    }

    return velocity;
}
sick girderBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

pearl shard
#

you're square rooting it just to square it again

#

just make another function

# 
distanceSquared(p1, p2)
#

and use it instead

#

sqrt is relatively slow operation

#

and you can easily parallelize this algorithm

#

it seems like the outcome of gravitate doesn't rely on continuous change during the loop execution

#

instead it can be run on multiple threads

# 
sf::Vector2f gravitate(float fa, sf::VertexArray const& blackHoles, sf::Vertex point, sf::Vector2f velocity) {
  auto begin = &blackHoles[0];
  auto end = begin + blackHoles.getVertexCount();

  auto calcVelocityChangeFor = [&](sf::Vertex const& v){
    float force = fa / distanceSquared(point.position, v.position);
    return (v.position - point.position) * force;
  };

  velocity += std::reduce(std::execution::par, begin, end,
    [&](sf::Vertex const& v1, sf::Vertex const& v2)
    {
      return calcVelocityChangeFor(v1) + calcVelocityChangeFor(v2);
    });

  return velocity;
}
#

and a tip

#

do not pass things by pointer when you require it to be valid

#

you didn't check whether blackHoles is nullptr or not

#

probably because you require it to be valid for this function to work

#

so use a reference

#

this implementation will be a lot faster, because it uses parallel algorithm

#

and skips the sqrt in each computation

#

don't forget to #include <execution>

#

and <algorithm>

unique ginkgo
#

pretty sure you could actually use std::execution::par_unseq here. also, do note that only a single compiler actually implements C++17 parallel algorithms. unless you're using msvc, chances are that it's not gonna be any faster for you…

tropic stirrup
#

Make sure you're compiling with optimizations

#

You can turn on some extra optimizations for floating point math like -ffast-math and -fno-math-errno

#

For the loop I'd say look for ways to make sure the loop can be vectorized

unique ginkgo
#

yeah, par_unseq is basically telling the compiler that it can vectorize

tropic stirrup
#

par_unseq isn't really relevant here

#

it's all about writing the loop in a way that the compiler actually can and will automatically vectorize

pearl shard
#

cppreference says that GCC9 supports it

#

with -ltbb

unique ginkgo
unique ginkgo
#

personally, i don't consider that a proper implementation

pearl shard
unique ginkgo
#

^^

sick girderBOT
#

This question thread is being automatically closed. If your question is not answered feel free to bump the post or re-ask. Take a look at !howto ask for tips on improving your question.

sick girderBOT
#

@round brook

This question thread is being automatically marked as solved.

round brook
pearl shard
# 
#include <algorithm>
#include <execution>
round brook
pearl shard
# 
#include <numeric>
round brook
little plover
round brook
little plover
#

Debug -> General -> C++ Language Standard

round brook
#

General?

little plover
#

ah sorry

#

debug properties

#

at the bottom

#

and then general

round brook
little plover
#

yeah c++14

#

you need at least 17 i believe

round brook
#

oh daymn what is the difference and how can i upgrade?

little plover
#

you click that

#

and choose 17

#

its that easy

#

difference is its a newer c++17 standard and std::reduce was introduced in c++17

round brook
little plover
#

there are some features that could be of use in 20 but it depends usually lower cpp standard is more compatible

pearl shard
unique ginkgo
round brook
#

alright ive changed it, should i restart vs?

round brook
little plover
#

Well you might have to rebuild first

#

And also fix your distanceSquared function which seems to have errors too

unique ginkgo
round brook
#

Algorithm
Execution
Numeric

Were included

round brook
little plover
#

Thats from 2017

#

5 years ago not true anymore

#

There should be an option to clean something

round brook
round brook
little plover
#

Clean all previous built files sometimes you need to do that

#

Or maybe restart Msvc idk

round brook
tropic stirrup
#

They’re just compiler flags

round brook
placid marten
placid marten
#

gcc 3.x kekwait ?

#

dafuq google?

#

oh well, same idea tho

round brook
placid marten
#

I mean I do know, but it depends on what you use to build your app

round brook
#

Uhh visual studio?

placid marten
#

as for the original question, btw, you might look at implementing an octree or quadtree

#

though if it's literally only one central object and all particles only ever orbit that one object, and if they don't collide with each other, then an octree doesn't help

round brook
#

there are 3 "blackholes" and the points only interact with the blackholes

placid marten
round brook
#

Hold up, I just increased my preformance by replacing

std::pow(dist, 2)

With

dist*dist

#

How does that work?

#

I'd assume the function would be better?

little plover
#

Also i think if you use g++ instead of msvc to compile you can get another nice speedup

round brook
#

And how can I swap?

little plover
#

Different compiler

#

Well you can still program in msvc but just build the release executable outside of msvc

round brook
little plover
#

Did you ever compile cpp outside of msvc

#

? If not it might be time to do that as a learning experience

round brook
round brook
little plover
#

And then just write a small test program and do
g++ testfile.cpp -o testfile

#

And you should have an executable that’s named testfile

round brook
#

Oh how I love leaving the nice warm arms of python code in persuit of better preformance

round brook
placid marten
#

btw, I'd probably recommend using Mingw-w64 via Msys2 rather than installing Mingw itself directly

#

CMake has an "Msys Makefiles" generator, meaning it's trivially easy to install some lib you want with e.g. pacman -Ss libcurl libboost libwhatever and then use it

#

no need for Conan or vcpkg

#

well, at least, if the lib you want is in Msys2, which many probably are

little plover
placid marten
#

the vscode page links directly to mingw

#

in the first paragraph

#

not sure if it suggests to use msys later

#

Msys2, Cygwin and WSL2 are all "Linux like environments for windows", with varying degrees of "likeness"

#

mingw is just a compiler that runs natively on windows, I don't think it has e.g. a package manager like pacman

#

but Msys2 does have pacman

#

years ago I would have recommended Cygwin, but that was when Msys2 did not have pacman, and now it does, so now I recommend Msys2

#

though depending on goals, I might recommend WSL2 instead, but again, WSL wasn't a thing even just a few years ago

#

at least... WSL1 was objectively crap, WSL2 is pretty good

placid marten
little plover