5

I've seen various answers to the ball collision detection question explaining why sqrt operations are slow, why absolute value operations are fast on floating ponts etc. How can I find out which operations are expensive and which are not?

Basically, I'm looking for a resource where I can learn about the implementation of all the python library functions. When people are saying those things they aren't actually thinking about how that stuff is implemented in C are they?

Thanks, looking to learn more about implementation details on this slick language.

Improve this question
3
  • I think you're asking specifically about floating-point functions/subroutines, not algorithmic efficiency (e.g. don't take sqrt when not necessary, just compare squared-distances directly), big-O or bytecode in general? "looking for a resource... about the implementation of all the python library functions" is way too general. Also, the bytecode compiler is getting improvements every version, as of 2024 the current release is 3.12; see the whatsnew. As to optimizations of floating-point esp. for 2D/3D games, there are tons of discussions on that since the 1970s, see those. Commented Mar 4, 2024 at 22:44
  • e.g. for collision detection, bounding-boxes in 3D were developed to use octrees as a data structure that can quickly be searched. There's about half a century of literature on that, going back to C and assembler. See also e.g. gamedev.stackexchange.com/questions/tagged/collision-detection . Always look first for high-level algorithmic and data-structure optimizations like octrees, not low-level stuff. Commented Mar 4, 2024 at 23:05
  • One legendary eighties compilation of efficient F-P algorithms for graphics is the "Graphics Gems" series of books, free PDFs and repo online. Commented Mar 5, 2024 at 0:06

4 Answers 4

Reset to default
3

Python is, like any language, translated to machine code and then run. So yes, they could be talking about low-level implementation details.

Anyway, the best way to learn about speed implementation of the various Python functions is taking a look in the source code.

Have fun!

EDIT: This tip actually applies to any open source project I worked with: Got a problem? Take a look at the source code and you should be fine.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Ok so I downloaded the source code and unzipped it. Now I have a folder called Python-3.1.2 and it is confusing! Any tips on sifting through the source and finding what I'm really looking for? Thanks
I took a quick look on the source, and if my guesses are correct, the source file you should take a look at cmathmodule.c. There is a function called c_sqrt that does the job of finding the square root, and it is written in C. So, it really comes down to the implementation of sqrt in C after all.
2

You find out which operations are slow and which ones are fast by using the timeit module.

For example, let's compare the various methods of checking if a point falls within a circle, from the command line:

python -m timeit -s 'import math; x = 42.5; y = 17.2; r = 50.0' 'math.sqrt(x**2 + y**2) <= r'
python -m timeit -s 'import math; x = 42.5; y = 17.2; r = 50.0' 'math.hypot(x, y) <= r'
python -m timeit -s 'import math; x = 42.5; y = 17.2; r = 50.0' 'x**2 + y**2 <= r**2'

On my machine the results are:

$ python -m timeit -s 'import math; x = 42.5; y = 17.2; r = 50.0' 'math.sqrt(x**2 + y**2) <= r'
1000000 loops, best of 3: 0.744 usec per loop
$ python -m timeit -s 'import math; x = 42.5; y = 17.2; r = 50.0' 'math.hypot(x, y) <= r'
1000000 loops, best of 3: 0.374 usec per loop
$ python -m timeit -s 'import math; x = 42.5; y = 17.2; r = 50.0' 'x**2 + y**2 <= r**2'
1000000 loops, best of 3: 0.724 usec per loop

so math.hypot wins! Incidentally, if you remove the dotted name lookup from the inner loop, you get slightly better results:

$ python -m timeit -s 'from math import hypot; x = 42.5; y = 17.2; r = 50.0' 'hypot(x, y) <= r'
1000000 loops, best of 3: 0.334 usec per loop
Improve this answer

Comments

1

If you're looking for tips on Python speed in general, these performance tips are a good resource.

Improve this answer

1 Comment

90% of the stuff in that article only applies to ~Python2.1 (that was 8 years ago) and is just plain false for todays Python implementation. It can show you how much Python improved, but that's about it.
0

The Python standard library includes a disassembler:

>>> def foo(): print
... 
>>> import dis
>>> dis.dis(foo)
  1           0 PRINT_NEWLINE       
              1 LOAD_CONST               0 (None)
              4 RETURN_VALUE

It doesn't work on everything, though:

>>> from math import sqrt
>>> import dis
>>> dis.dis(sqrt)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.6/dis.py", line 48, in dis
    type(x).__name__
TypeError: don't know how to disassemble builtin_function_or_method objects
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.