need_for_speed.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a id='speed'></a>\n",
    "<div id=\"qe-notebook-header\" align=\"right\" style=\"text-align:right;\">\n",
    "        <a href=\"https://quantecon.org/\" title=\"quantecon.org\">\n",
    "                <img style=\"width:250px;display:inline;\" width=\"250px\" src=\"https://assets.quantecon.org/img/qe-menubar-logo.svg\" alt=\"QuantEcon\">\n",
    "        </a>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python for Scientific Computing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "- [Python for Scientific Computing](#Python-for-Scientific-Computing)  \n",
    "  - [Overview](#Overview)  \n",
    "  - [Scientific Libraries](#Scientific-Libraries)  \n",
    "  - [The Need for Speed](#The-Need-for-Speed)  \n",
    "  - [Vectorization](#Vectorization)  \n",
    "  - [Beyond Vectorization](#Beyond-Vectorization)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to what’s in Anaconda, this lecture will need the following libraries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": true
   },
   "outputs": [],
   "source": [
    "!pip install --upgrade quantecon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "Python is extremely popular for scientific computing, due to such factors as\n",
    "\n",
    "- the accessible and flexible nature of the language itself,  \n",
    "- the huge range of high quality scientific libraries now available,  \n",
    "- the fact that the language and libraries are open source,  \n",
    "- the popular Anaconda Python distribution, which simplifies installation and\n",
    "  management of those libraries, and  \n",
    "- the recent surge of interest in using Python for machine learning and\n",
    "  artificial intelligence.  \n",
    "\n",
    "\n",
    "In this lecture we give a short overview of scientific computing in Python,\n",
    "addressing the following questions:\n",
    "\n",
    "- What are the relative strengths and weaknesses of Python for these tasks?  \n",
    "- What are the main elements of the scientific Python ecosystem?  \n",
    "- How is the situation changing over time?  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scientific Libraries\n",
    "\n",
    "Let’s briefly review Python’s scientific libraries, starting with why we need\n",
    "them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Role of Scientific Libraries\n",
    "\n",
    "One obvious reason we use scientific libraries is because they implement\n",
    "routines we want to use.\n",
    "\n",
    "For example, it’s almost always better to use an existing routine for root\n",
    "finding than to write a new one from scratch.\n",
    "\n",
    "(For standard algorithms, efficiency is maximized if the community can coordinate on a\n",
    "common set of implementations, written by experts and tuned by users to be as fast and robust as possible.)\n",
    "\n",
    "But this is not the only reason that we use Python’s scientific libraries.\n",
    "\n",
    "Another is that pure Python, while flexible and elegant, is not fast.\n",
    "\n",
    "So we need libraries that are designed to accelerate execution of Python code.\n",
    "\n",
    "As we’ll see below, there are now Python libraries that can do this extremely well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python’s Scientific Ecosystem\n",
    "\n",
    "In terms of popularity, the big four in the world of scientific Python\n",
    "libraries are\n",
    "\n",
    "- NumPy  \n",
    "- SciPy  \n",
    "- Matplotlib  \n",
    "- Pandas  \n",
    "\n",
    "\n",
    "For us, there’s another (relatively new) library that will also be essential for\n",
    "numerical computing:\n",
    "\n",
    "- Numba  \n",
    "\n",
    "\n",
    "Over the next few lectures we’ll see how to use these libraries.\n",
    "\n",
    "But first, let’s quickly review how they fit together.\n",
    "\n",
    "- NumPy forms the foundations by providing a basic array data type (think of\n",
    "  vectors and matrices) and functions for acting on these arrays (e.g., matrix\n",
    "  multiplication).  \n",
    "- SciPy builds on NumPy by adding the kinds of numerical methods that are\n",
    "  routinely used in science (interpolation, optimization, root finding, etc.).  \n",
    "- Matplotlib is used to generate figures, with a focus on plotting data stored in NumPy arrays.  \n",
    "- Pandas provides types and functions for empirical work (e.g., manipulating data).  \n",
    "- Numba accelerates execution via JIT compilation — we’ll learn about this\n",
    "  soon.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Need for Speed\n",
    "\n",
    "Now let’s discuss execution speed.\n",
    "\n",
    "Higher-level languages like Python  are optimized for humans.\n",
    "\n",
    "This means that the programmer can leave many details to the runtime environment\n",
    "\n",
    "- specifying variable types  \n",
    "- memory allocation/deallocation, etc.  \n",
    "\n",
    "\n",
    "The upside is that, compared to low-level languages, Python is typically faster to write, less error-prone and  easier to debug.\n",
    "\n",
    "The downside is that Python is harder to optimize — that is, turn into fast machine code — than languages like C or Fortran.\n",
    "\n",
    "Indeed, the standard implementation of Python (called CPython) cannot match the speed of compiled languages such as C or Fortran.\n",
    "\n",
    "Does that mean that we should just switch to C or Fortran for everything?\n",
    "\n",
    "The answer is: No, no and one hundred times no!\n",
    "\n",
    "(This is what you should say to the senior professor insisting that the model\n",
    "needs to be rewritten in Fortran or C++.)\n",
    "\n",
    "There are two reasons why:\n",
    "\n",
    "First, for any given program, relatively few lines are ever going to\n",
    "be time-critical.\n",
    "\n",
    "Hence it is far more efficient to write most of our code in a high productivity language like Python.\n",
    "\n",
    "Second, even for those lines of code that *are* time-critical, we can now achieve the same speed as C or Fortran using Python’s scientific libraries."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Where are the Bottlenecks?\n",
    "\n",
    "Before we learn how to do this, let’s try to understand why plain vanilla\n",
    "Python is slower than C or Fortran.\n",
    "\n",
    "This will, in turn, help us figure out how to speed things up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dynamic Typing\n",
    "\n",
    "\n",
    "<a id='index-0'></a>\n",
    "Consider this Python operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "a, b = 10, 10\n",
    "a + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even for this simple operation, the Python interpreter has a fair bit of work to do.\n",
    "\n",
    "For example, in the statement `a + b`, the interpreter has to know which\n",
    "operation to invoke.\n",
    "\n",
    "If `a` and `b` are strings, then `a + b` requires string concatenation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "a, b = 'foo', 'bar'\n",
    "a + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If `a` and `b` are lists, then `a + b` requires list concatenation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "a, b = ['foo'], ['bar']\n",
    "a + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(We say that the operator `+` is *overloaded* — its action depends on the\n",
    "type of the objects on which it acts)\n",
    "\n",
    "As a result, Python must check the type of the objects and then call the correct operation.\n",
    "\n",
    "This involves substantial overheads."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Static Types\n",
    "\n",
    "\n",
    "<a id='index-1'></a>\n",
    "Compiled languages avoid these overheads with explicit, static types.\n",
    "\n",
    "For example, consider the following C code, which sums the integers from 1 to 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide-output": false
   },
   "source": [
    "```c\n",
    "#include <stdio.h>\n",
    "\n",
    "int main(void) {\n",
    "    int i;\n",
    "    int sum = 0;\n",
    "    for (i = 1; i <= 10; i++) {\n",
    "        sum = sum + i;\n",
    "    }\n",
    "    printf(\"sum = %d\\n\", sum);\n",
    "    return 0;\n",
    "}\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The variables `i` and `sum` are explicitly declared to be integers.\n",
    "\n",
    "Hence, the meaning of addition here is completely unambiguous."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data Access\n",
    "\n",
    "Another drag on speed for high-level languages is data access.\n",
    "\n",
    "To illustrate, let’s consider the problem of summing some data — say, a collection of integers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Summing with Compiled Code\n",
    "\n",
    "In C or Fortran, these integers would typically be stored in an array, which\n",
    "is a simple data structure for storing homogeneous data.\n",
    "\n",
    "Such an array is stored in a single contiguous block of memory\n",
    "\n",
    "- In modern computers, memory addresses are allocated to each byte (one byte = 8 bits).  \n",
    "- For example, a 64 bit integer is stored in 8 bytes of memory.  \n",
    "- An array of $ n $ such integers occupies $ 8n $ **consecutive** memory slots.  \n",
    "\n",
    "\n",
    "Moreover, the compiler is made aware of the data type by the programmer.\n",
    "\n",
    "- In this case 64 bit integers  \n",
    "\n",
    "\n",
    "Hence, each successive data point can be accessed by shifting forward in memory\n",
    "space by a known and fixed amount.\n",
    "\n",
    "- In this case 8 bytes  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Summing in Pure Python\n",
    "\n",
    "Python tries to replicate these ideas to some degree.\n",
    "\n",
    "For example, in the standard Python implementation (CPython), list elements are placed in memory locations that are in a sense contiguous.\n",
    "\n",
    "However, these list elements are more like pointers to data rather than actual data.\n",
    "\n",
    "Hence, there is still overhead involved in accessing the data values themselves.\n",
    "\n",
    "This is a considerable drag on speed.\n",
    "\n",
    "In fact, it’s generally true that memory traffic is a major culprit when it comes to slow execution.\n",
    "\n",
    "Let’s look at some ways around these problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vectorization\n",
    "\n",
    "\n",
    "<a id='index-3'></a>\n",
    "There is a clever method called **vectorization** that can be\n",
    "used to speed up high level languages in numerical applications.\n",
    "\n",
    "The key idea is to send array processing operations in batch to pre-compiled\n",
    "and efficient native machine code.\n",
    "\n",
    "The machine code itself is typically compiled from carefully optimized C or Fortran.\n",
    "\n",
    "For example, when working in a high level language, the operation of inverting a large matrix can be subcontracted to efficient machine code that is pre-compiled for this purpose and supplied to users as part of a package.\n",
    "\n",
    "This clever idea dates back to MATLAB, which uses vectorization extensively.\n",
    "\n",
    "Vectorization can greatly accelerate many numerical computations (but not all,\n",
    "as we shall see).\n",
    "\n",
    "Let’s see how vectorization works in Python, using NumPy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operations on Arrays\n",
    "\n",
    "\n",
    "<a id='index-4'></a>\n",
    "First, let’s run some imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "import quantecon as qe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next let’s try some non-vectorized code, which uses a native Python loop to generate,\n",
    "square and then sum a large number of random variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "n = 1_000_000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "y = 0      # Will accumulate and store sum\n",
    "for i in range(n):\n",
    "    x = random.uniform(0, 1)\n",
    "    y += x**2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following vectorized code achieves the same thing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "x = np.random.uniform(0, 1, n)\n",
    "y = np.sum(x**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the second code block runs much faster.  Why?\n",
    "\n",
    "The second code block breaks the loop down into three basic operations\n",
    "\n",
    "1. draw `n` uniforms  \n",
    "1. square them  \n",
    "1. sum them  \n",
    "\n",
    "\n",
    "These are sent as batch operators to optimized machine code.\n",
    "\n",
    "Apart from minor overheads associated with sending data back and forth, the result is C or Fortran-like speed.\n",
    "\n",
    "When we run batch operations on arrays like this, we say that the code is *vectorized*.\n",
    "\n",
    "Vectorized code is typically fast and efficient.\n",
    "\n",
    "It is also surprisingly flexible, in the sense that many operations can be vectorized.\n",
    "\n",
    "The next section illustrates this point.\n",
    "\n",
    "\n",
    "<a id='ufuncs'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Universal Functions\n",
    "\n",
    "\n",
    "<a id='index-5'></a>\n",
    "Many functions provided by NumPy are so-called *universal functions* — also called [ufuncs](https://docs.scipy.org/doc/numpy/reference/ufuncs.html).\n",
    "\n",
    "This means that they\n",
    "\n",
    "- map scalars into scalars, as expected  \n",
    "- map arrays into arrays, acting element-wise  \n",
    "\n",
    "\n",
    "For example, `np.cos` is a ufunc:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "np.cos(1.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "np.cos(np.linspace(0, 1, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By exploiting ufuncs, many operations can be vectorized.\n",
    "\n",
    "For example, consider the problem of maximizing a function $ f $ of two\n",
    "variables $ (x,y) $ over the square $ [-a, a] \\times [-a, a] $.\n",
    "\n",
    "For $ f $ and $ a $ let’s choose\n",
    "\n",
    "$$\n",
    "f(x,y) = \\frac{\\cos(x^2 + y^2)}{1 + x^2 + y^2}\n",
    "\\quad \\text{and} \\quad\n",
    "a = 3\n",
    "$$\n",
    "\n",
    "Here’s a plot of $ f $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "from mpl_toolkits.mplot3d.axes3d import Axes3D\n",
    "from matplotlib import cm\n",
    "\n",
    "def f(x, y):\n",
    "    return np.cos(x**2 + y**2) / (1 + x**2 + y**2)\n",
    "\n",
    "xgrid = np.linspace(-3, 3, 50)\n",
    "ygrid = xgrid\n",
    "x, y = np.meshgrid(xgrid, ygrid)\n",
    "\n",
    "fig = plt.figure(figsize=(8, 6))\n",
    "ax = fig.add_subplot(111, projection='3d')\n",
    "ax.plot_surface(x,\n",
    "                y,\n",
    "                f(x, y),\n",
    "                rstride=2, cstride=2,\n",
    "                cmap=cm.jet,\n",
    "                alpha=0.7,\n",
    "                linewidth=0.25)\n",
    "ax.set_zlim(-0.5, 1.0)\n",
    "ax.set_xlabel('$x$', fontsize=14)\n",
    "ax.set_ylabel('$y$', fontsize=14)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To maximize it, we’re going to use a naive grid search:\n",
    "\n",
    "1. Evaluate $ f $ for all $ (x,y) $ in a grid on the square.  \n",
    "1. Return the maximum of observed values.  \n",
    "\n",
    "\n",
    "The grid will be"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "grid = np.linspace(-3, 3, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here’s a non-vectorized version that uses Python loops."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "m = -np.inf\n",
    "\n",
    "for x in grid:\n",
    "    for y in grid:\n",
    "        z = f(x, y)\n",
    "        if z > m:\n",
    "            m = z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here’s a vectorized version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "x, y = np.meshgrid(grid, grid)\n",
    "np.max(f(x, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the vectorized version, all the looping takes place in compiled code.\n",
    "\n",
    "As you can see, the second version is **much** faster.\n",
    "\n",
    "(We’ll make it even faster again later on, using more scientific programming tricks.)\n",
    "\n",
    "\n",
    "<a id='numba-p-c-vectorization'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Beyond Vectorization\n",
    "\n",
    "At its best, vectorization yields fast, simple code.\n",
    "\n",
    "However, it’s not without disadvantages.\n",
    "\n",
    "One issue is that it can be highly memory-intensive.\n",
    "\n",
    "For example, the vectorized maximization routine above is far more memory\n",
    "intensive than the non-vectorized version that preceded it.\n",
    "\n",
    "This is because vectorization tends to create many intermediate arrays before\n",
    "producing the final calculation.\n",
    "\n",
    "Another issue is that not all algorithms can be vectorized.\n",
    "\n",
    "In these kinds of settings, we need to go back to loops.\n",
    "\n",
    "Fortunately, there are alternative ways to speed up Python loops that work in\n",
    "almost any setting.\n",
    "\n",
    "For example, in the last few years, a new Python library called [Numba](http://numba.pydata.org/) has appeared that solves the main problems\n",
    "with vectorization listed above.\n",
    "\n",
    "It does so through something called **just in time (JIT) compilation**,\n",
    "which can generate extremely fast and efficient code.\n",
    "\n",
    "We’ll learn how to use Numba [soon](https://python.quantecon.org/numba.html)."
   ]
  }
 ],
 "metadata": {
  "date": 1584334747.581735,
  "filename": "need_for_speed.rst",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "title": "Python for Scientific Computing"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}