21

PEP 484 says "Using type hints for performance optimizations is left as an exercise for the reader." This suggests to me that, like Common Lisp, type declarations can be used to set aside type dispatch inside performance-intensive functions when I swear I know what I'm doing. To try this out for myself, I whipped up a little benchmark to calculate pi using a p-series. First I do it the naive way, then I try to be clever and exploit the type hints for performance:

import math
import time

def baselpi0(n):
    baselsum = 0;
    for i in range(1,n):
        baselsum += 1.0 / (i * i)
    return math.sqrt(6.0 * baselsum)

def baselpi1(n : int) -> float:
    n = float(n)
    baselsum  = 0.0
    i = 1.0
    while i < n:
        baselsum += 1.0 / (i * i)
        i += 1.0
    return math.sqrt(6.0 * baselsum)

start = time.time()
print(baselpi0(1000000000))
end = time.time()
print(end - start)
start = time.time()
print(baselpi1(1000000000))
end = time.time()
print(end - start)

The Common Lisp analogy I'm trying to emulate is:

(defun baselpi0 (n)
  (let ((baselsum 0.0d0))
    (loop for i from 1 to n do
      (setf baselsum (+ baselsum (/ 1.0 (* i i)))))
    (sqrt (* 6 baselsum))))

(defun baselpi1 (n)
  (let ((baselsum 0.0d0)
        (n (coerce n 'double-float)))
    (declare (type double-float baselsum n)
         (optimize (speed 3) (safety 0) (debug 0)))
    (loop for i from 1.0d0 to n do
          (setf baselsum (+ baselsum (/ 1.0d0 (* i i)))))
    (sqrt (* 6.0d0 baselsum))))

(time (princ (baselpi0 1000000000)))
(time (princ (baselpi1 1000000000)))
(exit)

On my machine, the lisp version run with sbcl takes 22 seconds for the slow version and 4 seconds for the type-hinted version, same as C. CPython takes 162 seconds for the naive version and 141 for the type-hinted version. Pypy runs the non-type-hinted version in just under 5 seconds, but the library support isn't good enough for my project.

Is there a way I can improve my type hinted version to get performance closer to lisp or Pypy?

3 Answers 3

14

The speed difference is not due to type-hinting. Python currently, and for the foreseeable future, just discards any hints you offer and continues executing dynamically as it always does.

It's due to the fact that in one case you use floating arithmetic throughout the code (which results in faster execution) while in the other case you don't.

Case in point: Change baselpi1 to the following:

def baselpi1(n : int) -> float:
    n = float(n)
    baselsum  = 0
    i = 1
    while i < n:
        baselsum += 1.0 / (i * i)
        i += 1
    return math.sqrt(6.0 * baselsum)

And take a look at the execution times now:

3.141591698659554
0.2511475086212158
3.141591698659554
0.4525010585784912

Yes, it is way slower.

6
  • 1
    Are you saying I shouldn't expect type hinting to help performance in general? The "exercise" in the PEP suggests it should.
    – Juanote
    Commented Oct 23, 2016 at 17:59
  • 4
    @Juanote No, not in general. You might take advantage of them in your own code as long as you figure out how to do it, that's the exercise. But you can't expect someone else's code (read: CPython) to do anything with type hints unless it's documented. Commented Oct 23, 2016 at 18:19
  • I see. Is there another language feature that would let me do what I've shown in Common Lisp, or do I have to drop to C for fast arithmetic? I'm rather new to Python and it seems very close to Common Lisp in terms of semantics, but it's pretty frustrating that go-fast declarations aren't available as far as I can tell.
    – Juanote
    Commented Oct 23, 2016 at 18:43
  • I don't really know, in this case I would say that you have to drop to C (cython?) for fast looping. Looping in python is expensive. Commented Oct 23, 2016 at 19:38
  • Raw numeric performance in Python is nearly non-existent. Once you layd- out your algorithm to number cruching (and not network connecting/routing higher level data), you need to switch to another technology to do the math itself, or suffer from a 200X + penalty. The easiest ways out are: run all your code in Pypy which does JIT, or compile the numeric functions themselves in binary module using Cython.
    – jsbueno
    Commented Oct 24, 2016 at 11:09
2

If you need to do large amounts of numerical computation then numpy offers a good choice generally. Numpy works with lower level data types (such as fixed-width integers -- python's is unbounded). This gives you the sort of type-hinting you are interested in. As numpy is designed to work with large amounts of data in arrays with known types, it can efficiently perform the same operation on an entire array. This also allows numpy to work well with CPUs that SIMD instructions (I'm not aware of a modern CPU without SIMD).

I would normally rewrite your function as such:

import math
import numpy

def baselpi_numpy(n):
    i = numpy.arange(1, n) # array of 1..n
    baselsum = (1 / (i * i)).sum()
    return math.sqrt(6 * baselsum)

However, for large n you will not have enough memory. You'll have to add a bit of extra code to batch the the operation for you. That is:

def baselpi_numpy(n, batch_size=1 << 16):
    basel_sum = 0
    i = 1
    for i in range(1, n, batch_size):
        j = min(n, i + batch_size)
        basel_sum += baselsum_numpy(i, j)
    return math.sqrt(6 * basel_sum)

def baselsum_numpy(start, end):
    # equivalent -> sum(1 / (i * i) for i in range(start, end)) 
    i = numpy.arange(start, end, dtype=float)
    # this line and next are memory optimisations which double speed
    # equivalent to i = 1 / (i * i)
    i *= i 
    i = numpy.divide(1, i, out=i)
    basel_sum = i.sum()
    return basel_sum

I get the result back in 5.2 seconds on my laptop. Though I haven't tested for the value of n you use, for lower n the numpy version is more than 20 times faster.

0

If you're willing to do some minor adjustments to your code, you might find mypyc a useful tool for cases like this. It's an ahead-of-time Python-to-C compiler that makes heavy use of type hints, in particular as checked by the mypy type checker (so much so that the compilation will fail if there are type hint errors reported by mypy).

The project claims a ~10x speedup when compared to interpreted Python, and interoperability with any other library.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.