Why are tactical computational distances so slow in Python?

Question

Why are tactical computational distances so slow in Python?

My Python program was too slow. So, I profiled and found that most of the time is spent on a function that calculates the distance between two points (the point is a list of 3 floating Python):

def get_dist(pt0, pt1):
    val = 0
    for i in range(3):
        val += (pt0[i] - pt1[i]) ** 2
    val = math.sqrt(val)
    return val

To analyze why this function was so slow, I wrote two test programs: one in Python and one in C ++ that perform similar calculations. They calculate the distance between 1 million pairs of points. (Test code in Python and C ++ below.)

Python calculation takes 2 seconds and C ++ takes 0.02 seconds. The difference is 100 times!

Why is Python code so slower than C ++ code for such simple math? How to speed it up to match C ++ performance?

Python code used for testing:

import math, random, time

num = 1000000

# Generate random points and numbers

pt_list = []
rand_list = []

for i in range(num):
    pt = []
    for j in range(3):
        pt.append(random.random())
    pt_list.append(pt)
    rand_list.append(random.randint(0, num - 1))

# Compute

beg_time = time.clock()
dist = 0

for i in range(num):
    pt0 = pt_list[i]
    ri  = rand_list[i]
    pt1 = pt_list[ri]

    val = 0
    for j in range(3):
        val += (pt0[j] - pt1[j]) ** 2
    val = math.sqrt(val)

    dist += val

end_time = time.clock()
elap_time = (end_time - beg_time)

print elap_time
print dist

C ++ code used for testing:

#include <cstdlib>
#include <iostream>
#include <ctime>
#include <cmath>

struct Point
{
    double v[3];
};

int num = 1000000;

int main()
{
    // Allocate memory
    Point** pt_list = new Point*[num];
    int* rand_list = new int[num];

    // Generate random points and numbers
    for ( int i = 0; i < num; ++i )
    {
        Point* pt = new Point;

        for ( int j = 0; j < 3; ++j )
        {
            const double r = (double) rand() / (double) RAND_MAX;
            pt->v[j] = r;
        }

        pt_list[i] = pt;
        rand_list[i] = rand() % num;
    }

    // Compute

    clock_t beg_time = clock();
    double dist = 0;
    for ( int i = 0; i < num; ++i )
    {
        const Point* pt0 = pt_list[i];
        int r = rand_list[i];
        const Point* pt1 = pt_list[r];

        double val = 0;
        for ( int j = 0; j < 3; ++j )
        {
            const double d = pt0->v[j] - pt1->v[j];
            val += ( d * d );
        }

        val = sqrt(val);
        dist += val;
    }
    clock_t end_time = clock();
    double sec_time = (end_time - beg_time) / (double) CLOCKS_PER_SEC;

    std::cout << sec_time << std::endl;
    std::cout << dist << std::endl;

    return 0;
}

+5

performance python

Ashwin nanjappa Apr 25 '13 at 9:00

source share

5 answers

:

main()

if __name__ == "__main__":
    main()

. - . . Python ? .

range(), , ; xrange(), .

+4

Fredrik Pihl 25 . '13 9:09

++ Python, Python, :

def get_dist(pt0, pt1):
    val = 0
    for i in range(3):
        val += (pt0[i] - pt1[i]) ** 2
    val = math.sqrt(val)
    return val

for ++ for . Python , , ++ . Python, - , Python for.

def get_dist(pt0, pt1, sqrt=math.sqrt): # cache function at definition time
    return sqrt((pt0[0] - pt1[0]) ** 2 + (pt0[1] - pt1[1]) ** 2 + (pt0[2] - pt1[2]) ** 2)

, , , ( numpy) , , .

+2

jamylak 25 . '13 9:11

Python , " ", python. "" - , , C. . - , , .

PyPy, Cython, , python C.

PyPy, 250ms < - , ? Cython 500 .

So the best option would be to use PyPy or Cython when speed is REALLY important.

+2

Jholta Apr 25 '13 at 9:21

source share

This page gets really confusing, and most of the answers are actually written in the comments, so it gives a brief overview of the possible optimizations:

Jamlaks answer : optimize your Python code:

def get_dist(pt0, pt1, sqrt=math.sqrt):  # cache function at definition time
    return sqrt((pt0[0] - pt1[0]) ** 2 + (pt0[1] - pt1[1]) ** 2 + (pt0[2] - pt1[2]) ** 2)

Use the numpy module for calories
Run pypy code instead of CPython
Observe temporary critical code with Cython

0

Chronial Apr 25 '13 at 10:00

source share

David Hammen · Accepted Answer · 2013-04-25T14:21:02+0000

Optimization sequence:

Source code with minor changes

import math, random, time

num = 1000000

# Generate random points and numbers

# Change #1: Sometimes it good not to have too much randomness.
# This is one of those cases.
# Changing the code shouldn't change the results.
# Using a fixed seed ensures that the changes are valid.
# The final 'print dist' should yield the same result regardless of optimizations.
# Note: There nothing magical about this seed.
# I randomly picked a hash tag from a git log.
random.seed (0x7126434a2ea2a259e9f4196cbb343b1e6d4c2fc8)
pt_list = []
rand_list = []

for i in range(num):
    pt = []
    for j in range(3):
        pt.append(random.random())
    pt_list.append(pt)

# Change #2: rand_list is computed in a separate loop.
# This ensures that upcoming optimizations will get the same results as
# this unoptimized version.
for i in range(num):
    rand_list.append(random.randint(0, num - 1))

# Compute

beg_time = time.clock()
dist = 0

for i in range(num):
    pt0 = pt_list[i]
    ri  = rand_list[i]
    pt1 = pt_list[ri]

    val = 0
    for j in range(3):
        val += (pt0[j] - pt1[j]) ** 2
    val = math.sqrt(val)

    dist += val

end_time = time.clock()
elap_time = (end_time - beg_time)

print elap_time
print dist

Optimization # 1: Put the code in a function.

The first optimization (not shown) is to insert all the code except importinto the function. This simple change provides a 36% increase in performance on my computer.

Optimization # 2: Release the statement `**`.

pow(d,2) C-, , C. python. Python ** ; x**2 x*x. , , . , d*d, . :

for i in range(num):
    pt0 = pt_list[i]
    ri  = rand_list[i]
    pt1 = pt_list[ri]

    val = 0 
    for j in range(3):
        d = pt0[j] - pt1[j]
        val += d*d 
    val = math.sqrt(val)

    dist += val

# 3: pythonic.

Python , C-. .

import math, random, time, itertools

def main (num=1000000) :
    # This small optimization speeds things up by a couple percent.
    sqrt = math.sqrt

    # Generate random points and numbers

    random.seed (0x7126434a2ea2a259e9f4196cbb343b1e6d4c2fc8)

    def random_point () :
        return [random.random(), random.random(), random.random()]

    def random_index () :
       return random.randint(0, num-1)

    # Big optimization:
    # Don't generate the lists of points.
    # Instead use list comprehensions that create iterators.
    # It best to avoid creating lists of millions of entities when you don't
    # need those lists. You don't need the lists; you just need the iterators.
    pt_list = [random_point() for i in xrange(num)]
    rand_pts = [pt_list[random_index()] for i in xrange(num)]


    # Compute

    beg_time = time.clock()
    dist = 0 

    # Don't loop over a range. That too C-like.
    # Instead loop over some iterable, preferably one that doesn't create the
    # collection over which the iteration is to occur.
    # This is particularly important when the collection is large.
    for (pt0, pt1) in itertools.izip (pt_list, rand_pts) :

        # Small optimization: inner loop inlined,
        # intermediate variable 'val' eliminated.
        d0 = pt0[0]-pt1[0]
        d1 = pt0[1]-pt1[1]
        d2 = pt0[2]-pt1[2]

        dist += sqrt(d0*d0 + d1*d1 + d2*d2)

    end_time = time.clock()
    elap_time = (end_time - beg_time)

    print elap_time
    print dist

Update

# 4, numpy

1/40- . , C, .

"Mondo slow". , . numpy. , , numpy # 3.

: numpy, .

import numpy, random, time

def main (num=1000000) :

    # Generate random points and numbers

    random.seed (0x7126434a2ea2a259e9f4196cbb343b1e6d4c2fc8)

    def random_point () :
        return [random.random(), random.random(), random.random()]

    def random_index () :
       return random.randint(0, num-1)

    pt_list = numpy.array([random_point() for i in xrange(num)])
    rand_pts = pt_list[[random_index() for i in xrange(num)],:]

    # Compute

    beg_time = time.clock()

    # Mondo slow.
    # dist = numpy.sum (
    #            numpy.apply_along_axis (
    #                numpy.linalg.norm, 1, pt_list - rand_pts))

    # Mondo fast.
    dist = numpy.sum ((numpy.sum ((pt_list-rand_pts)**2, axis=1))**0.5)

    end_time = time.clock()
    elap_time = (end_time - beg_time)

    print elap_time
    print dist

Why are tactical computational distances so slow in Python?

Source code with minor changes

Optimization # 1: Put the code in a function.

Optimization # 2: Release the statement **.

# 3: pythonic.

Update

# 4, numpy

More articles:

Optimization # 2: Release the statement `**`.