Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Performance Python and Introduction to Numba

Performance Python and Introduction to Numba

Python is a fantastic glue language but with Numba it can also be a high-performance language. Numba compiles a subset of Python to low-level machine code and makes it easy to take NumPy-based data and transform it extremely quickly.

Travis E. Oliphant

February 18, 2015
Tweet

More Decks by Travis E. Oliphant

Other Decks in Technology

Transcript

  1. Who am I? SciPy • PhD 2001 from Mayo Clinic

    in Biomedical Engineering • MS/BS degrees in Elec. Comp. Engineering • Creator of SciPy (1998-2001) • Professor at BYU (2001-2007) • Author of NumPy (2005-2012) • Started Numba (2012) • Founding Chair of Numfocus / PyData • Current Python Software Foundation Director
  2. Why Performance Matters "We should forget about small efficiencies, say

    about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%" - Donald E. Knuth
  3. Why Python License Community Readable Syntax Modern Constructs Batteries Included

    Free and Open Source, Permissive License • Broad and friendly community • Over 36,000 packages on PyPI • Commercial Support • Many conferences (PyData, SciPy, PyCon...) • Executable pseudo-code • Can understand and edit code a year later • Fun to develop • Use of Indentation IPython • Interactive prompt on steroids (Notebook) • Allows less working memory • Allows failing quickly for exploration • List comprehensions • Iterator protocol and generators • Meta-programming • Introspection • (JIT Compiler and Concurrency) • Internet (FTP, HTTP, SMTP, XMLRPC) • Compression and Databases • Logging, unit-tests • Glue for other languages • Distribution has much, much more....
  4. Why Python? • For many programs, the most important resource

    is developer time (both to create and to maintain) • Code that respects developer time is: - Easy to read - Easy to understand - Easy to modify • But execution speed does matter at times:
 Then what do you do?
  5. Some good books (pre-numba) Broad overview of Python tricks +

    Cython References old version of Numba
  6. Achieving Performance in Python When you need speed in Python

    the most important things you can do are: 1. Use profiling to understand where your program spends time.
 (Most of your code is irrelevant with respect to time spent. Only worry about the parts that matter.) I like the line-profiler kernprof.py binstar search -t conda line_profiler 2. Leverage NumPy-stack when working with data. 3. Use Numba to optimize hot-spots 4. Occasionally use Cython (especially for libraries).
  7. Data Structures Matter • “Organize data-together” and operate on it

    together with array-level operations (e.g. NumPy or Pandas) (column-oriented is a subset of array-oriented) • Don’t use a lot of little small objects Object Attr1 Attr2 Attr3 Object Attr1 Attr2 Attr3 Object Attr1 Attr2 Attr3 Object Attr1 Attr2 Attr3 Object Attr1 Attr2 Attr3 Object Attr1 Attr2 Attr3 Attr1 Attr2 Attr3 Object1 Object2 Object3 Object4 Object5 Object6
  8. How can Numba help? • If you have big NumPy

    arrays with your data (remember Pandas uses NumPy under-the-covers, so this applies to Pandas). Numba makes it easy to write simple functions that are fast that work with that data. • Numba is an open source Just-In-Time compiler for Python functions. • From the types of the function arguments, Numba can often generate a specialized, fast, machine code implementation at runtime. • Designed to work best with numerical code and NumPy arrays. • Uses the LLVM library as the compiler backend.
  9. Numba Features •Numba supports: - Windows (XP and later), OS

    X (10.7 and later), and Linux - 32 and 64-bit x86 CPUs and NVIDIA GPUs - Python 2 and 3 - NumPy versions 1.6 through 1.9 • It does not require a C/C++ compiler on the user’s system. • Requires less than 70 MB to install. • Does not replace the standard Python interpreter
 (it’s just another module — all of your existing Python libraries are still available)
  10. More Ranting • Today’s vector machines (and vector co-processors, or

    GPUS) were made for array-oriented computing (and Numba and Fortran). • There is a reason Fortran remains popular.
  11. Do we have to write the full compiler?? No! LLVM

    has done much heavy lifting LLVM = Compilers for everybody
  12. Face of a modern compiler Intermediate Representation (IR) x86 C++

    ARM PTX C Fortran ObjC Parsing Code Generation Front-End Back-End
  13. Face of a modern compiler Intermediate Representation (IR) x86 ARM

    PTX Python Code Generation Back-End Numba LLVM Parsing Front-End
  14. Numba (comes from NumPy + Mamba) LLVM Library Intel Nvidia

    Apple AMD OpenCL ISPC CUDA CLANG OpenMP LLVMPY Python Function Machine Code ARM
  15. How it works Function Call Site @jit compiled cache compiler

    *args Result type inference Object Mode Native Mode
  16. Simple API --- jit • with arguments --- provide type

    information (fastest to call at run-time) • without arguments --- detects input types, infers output, generates code if needed, and dispatches (a little more run- time call overhead) #@jit('void(double[:,:], double, double)') #@jit def numba_update(u, dx2, dy2): nx, ny = u.shape for i in xrange(1,nx-1): for j in xrange(1, ny-1): u[i,j] = ((u[i+1,j] + u[i-1,j]) * dy2 + (u[i,j+1] + u[i,j-1]) * dx2) / (2*(dx2+dy2)) # un-comment one of the ‘jit’ lines
  17. Image Processing @jit('void(f8[:,:],f8[:,:],f8[:,:])') def filter(image, filt, output): M, N =

    image.shape m, n = filt.shape for i in range(m//2, M-m//2): for j in range(n//2, N-n//2): result = 0.0 for k in range(m): for l in range(n): result += image[i+k-m//2,j+l-n//2]*filt[k, l] output[i,j] = result ~800x speed-up
  18. Fast vectorize NumPy’s ufuncs take “kernels” and apply the kernel

    element-by-element over entire arrays Write kernels in Python! from numba import vectorize from math import sin @vectorize([‘f8(f8)’, ‘f4(f4)’]) def sinc(x): if x==0.0: return 1.0 else: return sin(x*pi)/(pi*x)
  19. What is a Universal Function (ufunc) • Ufuncs are the

    core of NumPy’s calculation element-by-element infrastructure • It’s how +,-,*,/, **, sin, cos, etc. work • It is not how linear-algebra calcs work (typically) — though see generalized ufuncs for a way.
  20. Creating a “Ufunc” • Numba is the best way to

    make new ufuncs for working with NumPy arrays
  21. Case-study -- j0 from scipy.special • scipy.special was one of

    the first libraries I wrote • extended “umath” module by adding new “universal functions” to compute many scientific functions by wrapping C and Fortran libs. • Bessel functions are solutions to a differential equation: x 2 d 2 y dx 2 + x dy dx + ( x 2 ↵ 2) y = 0 y = J↵ ( x ) Jn (x) = 1 ⇡ Z ⇡ 0 cos (n⌧ x sin (⌧)) d⌧
  22. Result --- equivalent to compiled code In [6]: %timeit vj0(x)

    10000 loops, best of 3: 75 us per loop In [7]: from scipy.special import j0 In [8]: %timeit j0(x) 10000 loops, best of 3: 75.3 us per loop But! Now code is in Python and can be experimented with more easily (and moved to the GPU / accelerator more easily)!
  23. Compiling a Function • Sometimes you can’t create a simple

    or efficient array expression or ufunc. Use Numba to work with array elements directly. • Example: Suppose you have a boolean grid and you want to find the maximum number neighbors a cell has in the grid: 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 2 1 2 2 1 1 2 1 2 2 2 2 2 1 1 1 1 1 1 1 1
  24. Compiling a Function • Very hard to express this calculation

    purely as array operations (and even if you do, it is likely unreadable to non-NumPy experts). • Numba let’s you write out the loops, but avoid the penalty for having to loop over individual elements in 169x faster!
  25. Laplace Example @jit('void(double[:,:], double, double)') def numba_update(u, dx2, dy2): nx,

    ny = u.shape for i in xrange(1,nx-1): for j in xrange(1, ny-1): u[i,j] = ((u[i+1,j] + u[i-1,j]) * dy2 + (u[i,j+1] + u[i,j-1]) * dx2) / (2*(dx2+dy2)) Adapted from http://www.scipy.org/PerformancePython originally by Prabhu Ramachandran @jit('void(double[:,:], double, double)') def numbavec_update(u, dx2, dy2): u[1:-1,1:-1] = ((u[2:,1:-1]+u[:-2,1:-1])*dy2 + (u[1:-1,2:] + u[1:-1,:-2])*dx2) / (2*(dx2+dy2))
  26. Results of Laplace example Version Time Speed Up NumPy 3.19

    1 Numba 2.32 1.38 Vect. Numba 2.33 1.37 Cython 2.38 1.34 Weave 2.47 1.29 Numexpr 2.62 1.22 Fortran Loops 2.3 1.39 Vect. Fortran 1.5 2.13 https://github.com/teoliphant/speed.git
  27. Numba can change the game! LLVM IR x86 C++ ARM

    PTX C Fortran Numba Numba turns Python into a “compiled language” (but much more flexible). You don’t have to reach for C/C++
  28. Software Stack Future? LLVM Python C OBJC FORTRA R C++

    Plateaus of Code re-use + DSLs Matlab SQL TDPL Julia
  29. Different Modes of Compilation •Numba automatically selects between two different

    levels of optimization when compiling a function: - “object mode”: supports nearly all of Python, but generally cannot speed up code by a large factor
 (exception: see next slide) - “nopython mode”: supports a subset of Python, but runs at C/C++/FORTRAN speeds
  30. Loop-Lifting • In object mode, Numba will attempt to extract

    loops and compile them in nopython mode. • Works great for functions that are bookended by uncompilable code, but have a compilable core loop. • All happens automatically.
  31. nopython Mode Features • Standard control and looping structures: if,

    else, while, for, range • NumPy arrays, int, float, complex, booleans, and tuples • Almost all arithmetic, logical, and bitwise operators as well as functions from the math and numpy modules • Nearly all NumPy dtypes: int, float, complex, datetime64, timedelta64 • Array element access (read and write) • Array reduction functions: sum, prod, max, min, etc • Calling other nopython mode compiled functions • Calling ctypes or cffi-wrapped external functions
  32. Compiling for the GPU GPU functions are called differently, but

    it is still Python! MacBook Pro w/ GTX 650M GPU
  33. Example of CUDA Python from numbapro import cuda from numba

    import autojit @autojit(target=‘gpu’) def array_scale(src, dst, scale): tid = cuda.threadIdx.x blkid = cuda.blockIdx.x blkdim = cuda.blockDim.x i = tid + blkid * blkdim if i >= n: return dst[i] = src[i] * scale src = np.arange(N, dtype=np.float) dst = np.empty_like(src) array_scale[grid, block](src, dst, 5.0) CUDA Development directly in Python
  34. Matrix Multiply @cuda.jit(argtypes=[f4[:,:], f4[:,:], f4[:,:]]) def cu_square_matrix_mul(A, B, C): sA

    = cuda.shared.array(shape=(tpb, tpb), dtype=f4) sB = cuda.shared.array(shape=(tpb, tpb), dtype=f4) tx = cuda.threadIdx.x ty = cuda.threadIdx.y bx = cuda.blockIdx.x by = cuda.blockIdx.y bw = cuda.blockDim.x bh = cuda.blockDim.y x = tx + bx * bw y = ty + by * bh acc = 0. for i in range(bpg): if x < n and y < n: sA[ty, tx] = A[y, tx + i * tpb] sB[ty, tx] = B[ty + i * tpb, x] cuda.syncthreads() if x < n and y < n: for j in range(tpb): acc += sA[ty, j] * sB[j, tx] cuda.syncthreads() if x < n and y < n: C[y, x] = acc bpg = 50 tpb = 32 n = bpg * tpb A = np.array(np.random.random((n, n)), dtype=np.float32) B = np.array(np.random.random((n, n)), dtype=np.float32) C = np.empty_like(A) stream = cuda.stream() with stream.auto_synchronize(): dA = cuda.to_device(A, stream) dB = cuda.to_device(B, stream) dC = cuda.to_device(C, stream) cu_square_matrix_mul[(bpg, bpg), (tpb, tpb), stream](dA, dB, dC) dC.to_host(stream)
  35. Advanced Use Cases • Compile new functions based on user

    input. - Great for inserting a user-provided math expression into a larger algorithm, while still achieving C speeds. • Optimization (least squares, etc) libraries that can recompile themselves to inline a specific objective function right into the algorithm • Multithreaded calculation without having to worry about the global interpreter lock (GIL).
  36. NumbaPro (part of Anaconda Accelerate) •NumbaPro adds higher level features

    on top of Numba: - Create ufuncs that run multithreaded on the CPU or on the GPU - GPU linear algebra - GPU FFTs
  37. Examples from numbapro import vectorize from math import sin @vectorize([‘f8(f8)’,

    ‘f4(f4)’], target=‘gpu’) def sinc(x): if x==0.0: return 1.0 else: return sin(x*pi)/(pi*x) @vectorize([‘f8(f8)’, ‘f4(f4)’], target=‘parallel’) def sinc2(x): if x==0.0: return 1.0 else: return sin(x*pi)/(pi*x)
  38. Example from numbapro import vectorize sig = 'uint8(uint32, f4, f4,

    f4, f4, uint32, uint32, uint32)' @vectorize([sig], target='gpu') def mandel(tid, min_x, max_x, min_y, max_y, width, height, iters): pixel_size_x = (max_x - min_x) / width pixel_size_y = (max_y - min_y) / height x = tid % width y = tid / width real = min_x + x * pixel_size_x imag = min_y + y * pixel_size_y c = complex(real, imag) z = 0.0j for i in range(iters): z = z * z + c if (z.real * z.real + z.imag * z.imag) >= 4: return i return 255 Kind Time Speed-up Python 263.6 1.0x CPU 2.639 100x GPU 0.1676 1573x Tesla S2050
  39. Example with cuFFT # host -> device d_img = cuda.to_device(img)

    # image d_fltr = cuda.to_device(fltr) # filter # FFT forward cufft.fft_inplace(d_img) cufft.fft_inplace(d_fltr) # multply vmult(d_img, d_fltr, out=d_img) # inplace # FFT inverse cufft.ifft_inplace(d_img) # device -> host filted_img = d_img.copy_to_host() @vectorize(['complex64(complex64, complex64)'], target='gpu') def vmult(a, b): return a * b
  40. Conclusion • Numba is a JIT compiler than understands Python!

    • Achieve the same speeds as compiled languages for numerical and array-processing code. • Can be used to create advanced workflows where user input drives compilation at runtime. • NumbaPro is part of Anaconda Accelerate and adds more features. • Numba is open source, available at: http://numba.pydata.org/ • Or: conda  install  numba