Sign in to follow this  

Fast Square Root For Distance Calculations?

This topic is 492 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am facing a problem that calculating length of many vectors leads to huge performance drops and I am pretty much sure that the main reason is the square root algorithm that the programming language uses. What I thought - is there any faster, yet accurate approximation that I could use for the vector length calculation? Either faster square root equation or whole different vector length calculation.

 

Thanks!

Share this post


Link to post
Share on other sites

I am pretty much sure that the main reason is the square root algorithm that the programming language uses.

Which language? Most square roots will go direct to the processor these days, rather than be implemented via a software algorithm. This means it's unlikely you're going to get a faster implementation that is accurate.

If you have space, you might consider calculating and caching vector length whenever the vector value changes, making accessing it a O(1) operation - useful if you change the vector infrequently but measure them often.

Share this post


Link to post
Share on other sites

Hello!

Thanks for answers. Well, I don't need to compare 2 distances so the squared distance won't work. It turns out that square root wasn't my problem. I have the vector length calculated in a for loop together with few more(but actually lighter) equations. I was surprised how 1500 calculations in loop like this and a target game frequency of 500 Hz(100 Hz game frequency and 5 sub-steps) ended up in 20 FPS. That's incredibly bad result(especially knowing that I have decent laptop CPU(2.3 GHz, 4 cores). I am using Python and after a few analysis I found the problem - it turns out that Python is incredibly bad at for loops, like 50 times slower that C++ or Java. Hm... I didn't expect this. I am wondering - can I somehow optimize Python for loops and/or class access?

 

This isn't that important anyways as I'm using Python only for test stage(as it's incredibly easy to code in Python), I'll switch to C++ after.

Share this post


Link to post
Share on other sites

Well, it's working. I got a Python script that does mathematical calculations with use of vectors(but no matrices or any other similars). It does it all in loops. I write it in OOP. Somehow it seems that I got performance issues, but after checking my code several times I find it being clean and well-optimized. I read at some resources that loops in Python are incredibly slow. I just wanna get confirmation for this and, if possible, some ways to speed it up.

Share this post


Link to post
Share on other sites
One way to speed these things up in Python is to use numpy:
 
import numpy as np

vectors = np.random.rand(1500, 3)
lengths = np.linalg.norm(vectors, axis=1)

Voila, no (Python) loops. Edited by kloffy

Share this post


Link to post
Share on other sites

Python is not the optimal language for CPU-intensive operations because it intrinsically has layers of indirection between the language and the processor - the bytecode interpreter, the C objects representing your variables, the system calls implementing those objects, etc.

Therefore optimising Python is often a case of reducing the number of Python operations and replacing them with C operations. This can be done a few ways:

1) Replacing algorithms implemented in Python with standard library or built-in functions. For example, sometimes an explicit loop can be replaced with a call to the map() function - this moves the looping part into C code, and therefore is sometimes faster.
2) 3rd party C libraries like numpy (see above). For heavy mathematical lifting this is the number 1 choice.
3) Replacing the standard Python interpreter with one that compiles down to machine code. PyPy is the main choice here. Note that some extensions won't work with it.

4) Creating extensions in C that your Python program can use. You can make a module in C that Python can import and it'll usually run a lot faster than the equivalent Python code. Cython can help you a lot here.

5) Ditching Python entirely in favour of a faster language. Python is great but sometimes it's the wrong tool for the job. This might be a good time to consider whether you're using the right language. Consider also the target platforms and deployment method - Python is not great for mobile, won't run on the web, and deployment is a mess.

Share this post


Link to post
Share on other sites

Thanks for info! Well, yeah... Final project will be written in C++. I was just hoping to write the code for Blender Game Engine. In my case the map() won't work because my for loop looks near like this:

for j in self.joints:
    o1 = j.object1
    o2 = j.object2
    j.integrate(o1, o2)

# j is a class, j.object1 and j.object2 are classes, integrate(self, o1, o2) is a function inside j class
class j:
    ...some stuff here...
    def integrate(o1, o2):
        distance = (o1.position - o2.position).magnitude
        ...more stuff here...

This is how the code looks, more or less...

Share this post


Link to post
Share on other sites

um... Welll... The integrate function calls one more function several times at one position. And if I wrote it all inside the code - it'd make the code a huge mess + I doubt it would be any faster. But you wanna tell that OOP + Python = slow?

Share this post


Link to post
Share on other sites

This topic is 492 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this