Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: best way to calculate length of vector  (Read 5988 times)

0 Members and 1 Guest are viewing this topic.

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
best way to calculate length of vector
« on: May 24, 2016, 03:30:30 pm »
usually when i wanted to compute the length of vector, i used traditional way as i have learnt from many tutorials by squared root the dot product of given vector. and these were usually defined in free function for each of them. like so,

//calculates dot product of 2 vectors
inline float dot(const sf::Vector2f& lv, const sf::Vector2f& rv)
{
    return lv.x * rv.x + lv.y * rv.y;
}

//Returns length of a given vector
inline float length(const sf::Vector2f& source)
{
    return std::sqrt(dot(source, source));
}

//Returns a given vector with its length normalized to 1
inline sf::Vector2f normalise(sf::Vector2f source)
{
    float length = std::sqrt(dot(source, source));
    if (length != 0) source /= length;
    return source;
}
 

and usage:
auto speed = length(velocity) * dt.asSeconds();
auto amount = normalise(velocity) * speed;
sprite.move(amount );

however, i have found in math.h header file a builtin function hypotf(x,y) that do exactly same thing. later in c++11 defined in cmath by std::hypot(x, y) where x and y is float, which is equivalent to std::fabs(std::complex<float>(x,y)).
typical usage would be some thing like this:

//Returns a given vector with its length normalized to 1
inline sf::Vector2f normalise(sf::Vector2f source)
{
    float length = std::hypot(source.x, source.y);
    if (length != 0) source /= length;
    return source;
}

auto speed = std::hypot(velocity.x, velocity.y) * dt.asSeconds();
auto amount = normalise(velocity) * speed;
sprite.move(amount );
 

as you can see both did same job while the first is most popular and other rarely used in game dev if not used ever.

my question why most of game dev don't use std::hypot and save them from rewriting those free functions of length and the dot every times, is it because of some performance drawbacks due to std::hypot. or they simply don't know about it.
« Last Edit: May 25, 2016, 03:35:27 pm by MORTAL »

Hiura

  • SFML Team
  • Hero Member
  • *****
  • Posts: 4321
    • View Profile
    • Email
Re: best way to calculate length of vector
« Reply #1 on: May 24, 2016, 08:52:21 pm »
It's not news that people don't read the doc and reimplement the same stuff over and over again.  ;)

Maybe in some very narrow situations you can use domain specific information to use some nasty trick to tune the hypotenuse function, but I've never seen this one being a bottleneck so...
SFML / OS X developer

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: best way to calculate length of vector
« Reply #2 on: May 25, 2016, 02:02:22 am »
thanks Hiura
that's what i thought too.

fer_t

  • Newbie
  • *
  • Posts: 18
    • View Profile
    • Email
Re: best way to calculate length of vector
« Reply #3 on: May 25, 2016, 02:04:13 am »
250 000 000 iterations
custom vs STL

GCC 5.3.1: 1.79349 seconds vs 2.45667 seconds
clang++:      1.52534 seconds vs 2.7238 seconds

No idea why the custom version is faster, maybe because it can inline a lot and the optimize it better.

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: best way to calculate length of vector
« Reply #4 on: May 25, 2016, 03:31:20 am »
250 000 000 iterations
custom vs STL

GCC 5.3.1: 1.79349 seconds vs 2.45667 seconds
clang++:      1.52534 seconds vs 2.7238 seconds

No idea why the custom version is faster, maybe because it can inline a lot and the optimize it better.
thanks for your time to test it,
me too i have run it in small test about 1000 iterations in Code::block/GCC 4.9.2 both have same result in debug/release mode, but when i tested for 250 000 000 iterations, i got about
debug
for custom:  6.125 - 10.240
for STL:       120.536 - 121.730

while in release mode both optimized and almost the same about 0.150 - 0.140

here test code:
#include <iostream>
#include <chrono>
#include <cmath>
#include <SFML/Graphics.hpp>

inline float dot(const sf::Vector2f& lv, const sf::Vector2f& rv)
{
    return lv.x * rv.x + lv.y * rv.y;
}

inline float length(const sf::Vector2f& source)
{
    return std::sqrt(dot(source, source));
}

int main()
{
    using namespace std::chrono;
   
    sf::Vector2f velocity(200.f, 200.f);
   
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    for (int i = 0; i < 250000000; ++i)
    {
        length(velocity);
        //std::hypot(velocity.x, velocity.y);
    }
    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    auto duration = duration_cast<microseconds>( t2 - t1 ).count();

    std::cout << duration << std::endl;
}

Hiura

  • SFML Team
  • Hero Member
  • *****
  • Posts: 4321
    • View Profile
    • Email
Re: best way to calculate length of vector
« Reply #5 on: May 25, 2016, 08:06:10 am »
Be careful how you measure those kind of things. Microbenchmarks are harder than we think. Have a look at this talk for example: http://youtu.be/nXaxk27zwlk
SFML / OS X developer

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: best way to calculate length of vector
« Reply #6 on: May 25, 2016, 10:31:58 am »
Oh My, that was insane and intense as well, really i won't lie about it, it is hard to grasp the details.

FRex

  • Hero Member
  • *****
  • Posts: 1843
    • View Profile
    • My GitHub Page
    • Email
Re: best way to calculate length of vector
« Reply #7 on: May 25, 2016, 08:40:40 pm »
Hypot also doesn't over or underflow on intermediate values like sqrt(x*x + y*y) can.
ZipSavings, script to count rar/7z/zip savings: https://goo.gl/vvBj5M
LuaConsole: https://goo.gl/X4kRUk
FoxRaycaster: https://goo.gl/27nVS8
Small Games - Heart, Routing and Snek: https://goo.gl/15ZGWE https://goo.gl/k5gwWD https://goo.gl/4nKPnT
Botes - a notes app in Pascal: https://goo.gl/bzTqsi

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: best way to calculate length of vector
« Reply #8 on: May 26, 2016, 08:07:45 am »
Hypot also doesn't over or underflow on intermediate values like sqrt(x*x + y*y) can.
yes, that's true std::Hypot is done its computation without overflow or underflow while custom is not guaranteed but this can be fixed by template to ensure that.

possible implementation:
template <typename R> constexpr R dot() { return {}; }

template <typename R, typename T, typename... Ts>
constexpr R dot(T t, Ts... ts)
{
    return t + dot<R>(ts...);
}

template <typename... Ts>
constexpr typename std::common_type<Ts...>::type length(Ts... ts)
{
    // or assert for not allowing different types
    using R = typename std::common_type<Ts...>::type;
    return std::sqrt(dot<R>( (R(ts) * R(ts))... )); // cast it to ensure not overflow
}
« Last Edit: May 26, 2016, 08:42:57 am by MORTAL »

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6254
  • Thor Developer
    • View Profile
    • Bromeon
Re: best way to calculate length of vector
« Reply #9 on: May 27, 2016, 10:01:15 pm »
The reason why std::hypot() is rarely used is not at least because it was added only in C++11. Besides, you should really try such benchmarks on different compilers (possibly even different processors), as the results at that level may vary significantly.

Performance optimization really matters at the low level (for reusable components and hardware-abstracting libraries) as well as the high level (choosing correct algorithms and data structures), but... Don't waste your time on irrelevant micro optimizations when you could write a game instead. Once you have that game at a meaningful state where such things start to even matter, there's actual reason to investigate micro bottlenecks, but until that point it appears like a pointless academic exercise... And the overengineered dot product implementation doesn't really weaken this impression ;)

Btw: why does normalise() injure its implied postcondition (i.e. that the result have length 1)? With an assert, you could avoid that if. Not only is passing zero vectors a logic error, but silently returning them where nobody expects it won't make things better.
« Last Edit: May 27, 2016, 10:07:25 pm by Nexus »
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development: first SFML book

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: best way to calculate length of vector
« Reply #10 on: May 28, 2016, 12:18:50 pm »
thanks Nexus for comprehensive comment, i really appreciate.

The reason why std::hypot() is rarely used is not at least because it was added only in C++11. Besides, you should really try such benchmarks on different compilers (possibly even different processors), as the results at that level may vary significantly.
it seems that, Micro-benchmarks needs tools and sold knowledge in both hardware and compilers as well as assembly language, and i dont have ability to do it. i barely have basic knowledge in assembly language from a course that i had to take it in my collage where it required to take a course in 8080 & 8081 microprocessors in my major EE (Electrical Engineer). but for modern processors i'm totally lost.

Performance optimization really matters at the low level (for reusable components and hardware-abstracting libraries) as well as the high level (choosing correct algorithms and data structures)
that's a precious advise, thanks, i will keep that in mined

Don't waste your time on irrelevant micro optimizations when you could write a game instead. Once you have that game at a meaningful state where such things start to even matter, there's actual reason to investigate micro bottlenecks, but until that point it appears like a pointless academic exercise... And the overengineered dot product implementation doesn't really weaken this impression ;)
yeah, now, i'm aware of that, at least i've tried and i experienced how irrelevant it is in this stage.

Btw: why does normalise() injure its implied postcondition (i.e. that the result have length 1)? With an assert, you could avoid that if. Not only is passing zero vectors a logic error, but silently returning them where nobody expects it won't make things better.
cool, fixed
« Last Edit: May 28, 2016, 01:17:50 pm by MORTAL »

Mario

  • SFML Team
  • Hero Member
  • *****
  • Posts: 877
    • View Profile
Re: best way to calculate length of vector
« Reply #11 on: May 28, 2016, 01:34:20 pm »
Don't forget over all the performance comparisons that there are many cases where you can avoid having to calculate the full length of a vector, so depending on your actual use case, you might not have to do it at all.

Specifically, if you just want to compare some vector lengths, simply omit the square root completely. on both sides, e .g. "v1.x * v1.x + v1.y * v1.y < 100" for a distance of less than 10.

Besides that...

auto speed = length(velocity) * dt.asSeconds();
auto amount = normalise(velocity) * speed;
sprite.move(amount );

Maybe I missed it, but why would you even calculate this "speed"? If you multiply a normalized vector with the original vector's length, you'll get the original vector once again.

Hapax

  • Hero Member
  • *****
  • Posts: 3040
  • My number of posts is shown in hexadecimal.
    • View Profile
Re: best way to calculate length of vector
« Reply #12 on: May 28, 2016, 02:35:07 pm »
The reason why std::hypot() is rarely used is not at least because it was added only in C++11.
Is this true?

http://en.cppreference.com/w/cpp/numeric/math/hypot
seems to be clear to suggest that it's only been around since C++11

whereas

http://www.cplusplus.com/reference/cmath/hypot/
seems to suggest that it's been around a bit longer (only in its currently overloaded form since C++11)
Selba Ward - SFML drawables
Kairos - Timing Library
Rectangular Boundary Collision - Rectangular SAT Collision

@Hapaxiation - Hapaxia on Twitter

Mortal

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: best way to calculate length of vector
« Reply #13 on: May 28, 2016, 02:51:17 pm »
Don't forget over all the performance comparisons that there are many cases where you can avoid having to calculate the full length of a vector, so depending on your actual use case, you might not have to do it at all.

Specifically, if you just want to compare some vector lengths, simply omit the square root completely. on both sides, e .g. "v1.x * v1.x + v1.y * v1.y < 100" for a distance of less than 10.
thanks Mario, that's make more sense, since std::sqrt() is a bit expensive better a void it when possible. and your example makes it very obvious

Besides that...

auto speed = length(velocity) * dt.asSeconds();
auto amount = normalise(velocity) * speed;
sprite.move(amount );

Maybe I missed it, but why would you even calculate this "speed"? If you multiply a normalized vector with the original vector's length, you'll get the original vector once again.
yeah, i'm totally agree with you, i just took it from the original open source game where it treats velocity as vector literally by computing its magnitude as "speed" and its direction as "normalise(velocity)". probably the author has a good reason to do it this way. for me i would simply use it like so:
sprite.move(velocity * dt.asSeconds());
« Last Edit: May 28, 2016, 03:23:21 pm by MORTAL »

 

anything