_posts/2017-01-23-go-faster-python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preamble\n",
    "\n",
    "This blog post gives an introduction to some techniques for benchmarking, profiling and optimising Python code. If you would like to try the code examples for yourself, you can [download the Jupyter notebook](https://github.com/alimanfoo/alimanfoo.github.io/blob/master/_posts/2017-01-23-go-faster-python.ipynb) (right click the \"Raw\" button, save link as...) that this blog post was generated from. To run the notebook, you will need a working Python 3 installation, and will also need to install a couple of Python packages. The way I did that was to first [download](http://conda.pydata.org/miniconda.html) and [install](http://conda.pydata.org/docs/install/quick.html) miniconda into my home directory. I then ran the following from the command line:\n",
    "\n",
    "<pre>\n",
    "user@host:~$ export PATH=~/miniconda3/bin/:$PATH\n",
    "user@host:~$ conda create -n go_faster_python python=3.5\n",
    "user@host:~$ source activate go_faster_python\n",
    "(go_faster_python) user@host:~$ conda config --add channels conda-forge\n",
    "(go_faster_python) user@host:~$ conda install cython numpy jupyter line_profiler\n",
    "(go_faster_python) user@host:~$ jupyter notebook &\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "I use Python both for writing software libraries and for interactive data analysis. Python is an **interpreted**, **dynamically-typed** language, with lots of convenient **high-level data structures** like lists, sets, dicts, etc. It's great for getting things done, because no compile step means no delays when developing and testing code or when exploring data. No type declarations means lots of flexibility and less typing (on the keyboard I mean - sorry, bad joke). The high-level data structures mean you can focus on solving the problem rather than low-level nuts and bolts.\n",
    "\n",
    "But the down-side is that Python can be slow. If you have a Python program that's running slowly, what are your options?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Benchmarking and profiling\n",
    "\n",
    "My intuitions for why a piece of code is running slowly are very often wrong, and many other programmers more experienced than me [say the same thing](http://cython.readthedocs.io/en/latest/src/tutorial/profiling_tutorial.html#profiling-tutorial). If you're going to try and optimise something, you need to do some benchmarking and profiling first, to find out (1) exactly how slow it goes, and (2) where the bottleneck is.\n",
    "\n",
    "To introduce some basic Python benchmarking and profiling tools, let's look at a toy example: computing the sum of 2-dimensional array of integers. Here's some example data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "data = [[90, 62, 33, 78, 82],\n",
    "        [37, 31, 0, 72, 32],\n",
    "        [7, 71, 79, 81, 100],\n",
    "        [33, 50, 66, 81, 71],\n",
    "        [87, 26, 54, 78, 81],\n",
    "        [37, 22, 96, 79, 41],\n",
    "        [88, 75, 100, 19, 88],\n",
    "        [24, 72, 59, 33, 92],\n",
    "        [71, 6, 59, 8, 11],\n",
    "        [89, 76, 65, 12, 13]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strictly speaking this isn't an array, it's a list of lists. But using lists is a common and natural way to store data in Python. \n",
    "\n",
    "Here is a naive implementation of a function called `sum2d` to compute the overall sum of a 2-dimensional data structure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum1d(l):\n",
    "    \"\"\"Compute the sum of a list of numbers.\"\"\"\n",
    "    s = 0\n",
    "    for x in l:\n",
    "        s += x\n",
    "    return s\n",
    "\n",
    "\n",
    "def sum2d(ll):\n",
    "    \"\"\"Compute the sum of a list of lists of numbers.\"\"\"\n",
    "    s = 0\n",
    "    for l in ll:\n",
    "        s += sum1d(l)\n",
    "    return s\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the implementation to check it works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2817"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum2d(data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need a bigger dataset to illustrate slow performance. To make a bigger test dataset I'm going to make use of the multiplication operator ('\\*') which when applied to a Python list will create a new list by repeating the elements of the original list. E.g., here's the original list repeated twice: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[90, 62, 33, 78, 82],\n",
       " [37, 31, 0, 72, 32],\n",
       " [7, 71, 79, 81, 100],\n",
       " [33, 50, 66, 81, 71],\n",
       " [87, 26, 54, 78, 81],\n",
       " [37, 22, 96, 79, 41],\n",
       " [88, 75, 100, 19, 88],\n",
       " [24, 72, 59, 33, 92],\n",
       " [71, 6, 59, 8, 11],\n",
       " [89, 76, 65, 12, 13],\n",
       " [90, 62, 33, 78, 82],\n",
       " [37, 31, 0, 72, 32],\n",
       " [7, 71, 79, 81, 100],\n",
       " [33, 50, 66, 81, 71],\n",
       " [87, 26, 54, 78, 81],\n",
       " [37, 22, 96, 79, 41],\n",
       " [88, 75, 100, 19, 88],\n",
       " [24, 72, 59, 33, 92],\n",
       " [71, 6, 59, 8, 11],\n",
       " [89, 76, 65, 12, 13]]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data * 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make a bigger dataset by repeating the original data a million times:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "big_data = data * 1000000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have a dataset that is 10,000,000 rows by 5 columns:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10000000"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(big_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(big_data[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try running the function on these data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2817000000"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum2d(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On my laptop this takes a few seconds to run."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmarking:  `%time`, `%timeit`, `timeit`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you start optimising, you need a good estimate of performance as a place to start from, so you know when you've improved something. If you're working in a Jupyter notebook there are a couple of magic commands available which are very helpful for benchmarking: [`%time`](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=%25time#magic-time) and [`%timeit`](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=%25timeit#magic-timeit). If you're writing a Python script to do the benchmarking, you can use the [`timeit`](https://docs.python.org/3/library/timeit.html) module from the Python standard library.\n",
    "\n",
    "Let's look at the output from [`%time`](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=%25time#magic-time):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.89 s, sys: 0 ns, total: 2.89 s\n",
      "Wall time: 2.89 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2817000000"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time sum2d(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first line of the output gives the amount of CPU time, broken down into 'user' (your code) and 'sys' (operating system code). The second line gives the wall time, which is the actual amount of time elapsed. Generally the total CPU time and the wall time will be the same, but sometimes not. E.g., if you are benchmarking a multi-threaded program, then wall time may be less than CPU time, because CPU time counts time spent by each CPU separately and adds them together, but the CPUs may actually be working in parallel.\n",
    "\n",
    "One thing to watch out for when benchmarking is that performance can be variable, and may be affected by other processes running on your computer. To see this happen, try running the cell above again, but while it's running, give your computer something else to do at the same time, e.g., play some music, or a video, or just scroll the page up and down a bit.\n",
    "\n",
    "To control for this variation, it's a good idea to benchmark several runs (and avoid the temptation to check your email while it's running). The [`%timeit`](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=%25timeit#magic-timeit) magic will automatically benchmark a piece of code several times: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 2.84 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sum2d(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, using the [`timeit`](https://docs.python.org/3/library/timeit.html) module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2.892044251999323, 2.8372464299973217, 2.8505056829999376]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import timeit\n",
    "timeit.repeat(stmt='sum2d(big_data)', repeat=3, number=1, globals=globals())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function profiling: `%prun`, `cProfile`\n",
    "\n",
    "The next thing to do is investigate which part of the code is taking the most time. If you're working in a Jupyter notebook, the [`%prun`](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=%25prun#magic-prun) command is a very convenient way to profile some code. Use it like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " "
     ]
    }
   ],
   "source": [
    "%prun sum2d(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output from [`%prun`](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=%25prun#magic-prun) pops up in a separate panel, but for this blog post I need to get the output inline, so I'm going to use the [`cProfile`](https://docs.python.org/3/library/profile.html?highlight=cprofile) module from the Python standard library directly, which does the same thing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         10000004 function calls in 3.883 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      " 10000000    2.378    0.000    2.378    0.000 <ipython-input-2-12b138a62a96>:1(sum1d)\n",
      "        1    1.505    1.505    3.883    3.883 <ipython-input-2-12b138a62a96>:9(sum2d)\n",
      "        1    0.000    0.000    3.883    3.883 {built-in method builtins.exec}\n",
      "        1    0.000    0.000    3.883    3.883 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import cProfile\n",
    "cProfile.run('sum2d(big_data)', sort='time')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a couple of things to notice here. \n",
    "\n",
    "First, the time taken to execute the profiling run is quite a bit longer than the time we got when benchmarking earlier. This is because profiling adds some overhead. Generally this doesn't affect the conclusions you would draw about which functions take the most time, but it's something to be aware of.\n",
    "\n",
    "Second, most of the time is being taken up in the `sum1d` function, although a decent amount of time is also being spent within the `sum2d` function. You can see this from the 'tottime' column, which shows the total amount of time spent within a function, **not** including any calls made to other functions. The 'cumtime' column shows the total amount of time spent in a function, including any function calls.\n",
    "\n",
    "Also, you'll notice that there were 10,000,004 function calls. Calling a Python function has some overhead. Maybe the code would go faster if we reduced the number of function calls? Here's a new implementation, combining everything into a single function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum2d_v2(ll):\n",
    "    \"\"\"Compute the sum of a list of lists of numbers.\"\"\"\n",
    "    s = 0\n",
    "    for l in ll:\n",
    "        for x in l:\n",
    "            s += x\n",
    "    return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 2.22 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sum2d_v2(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a bit faster. What does the profiler tell us?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         4 function calls in 2.223 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "        1    2.223    2.223    2.223    2.223 <ipython-input-14-81d66843d00e>:1(sum2d_v2)\n",
      "        1    0.000    0.000    2.223    2.223 {built-in method builtins.exec}\n",
      "        1    0.000    0.000    2.223    2.223 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "cProfile.run('sum2d_v2(big_data)', sort='time')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact we've hit a dead end here, because there is only a single function to profile, and function profiling cannot tell us which lines of code within a function are taking up most time. To get further we need to do some..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Line profiling: `%lprun`, `line_profiler`\n",
    "\n",
    "You can do line profiling with a Python module called [`line_profiler`](https://github.com/rkern/line_profiler). This is not part of the Python standard library, so you have to install it separately, e.g., via pip or conda.\n",
    "\n",
    "For convenience, the `line_profiler` module provides a `%lprun` magic command for use in a Jupyter notebook, which can be used as follows: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%load_ext line_profiler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%lprun -f sum2d_v2 sum2d_v2(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also do the same thing via regular Python code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<line_profiler.LineProfiler at 0x7fcf947c4d68>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import line_profiler\n",
    "l = line_profiler.LineProfiler()\n",
    "l.add_function(sum2d_v2)\n",
    "l.run('sum2d_v2(big_data)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timer unit: 1e-06 s\n",
      "\n",
      "Total time: 31.6946 s\n",
      "File: <ipython-input-14-81d66843d00e>\n",
      "Function: sum2d_v2 at line 1\n",
      "\n",
      "Line #      Hits         Time  Per Hit   % Time  Line Contents\n",
      "==============================================================\n",
      "     1                                           def sum2d_v2(ll):\n",
      "     2                                               \"\"\"Compute the sum of a list of lists of numbers.\"\"\"\n",
      "     3         1            2      2.0      0.0      s = 0\n",
      "     4  10000001      2338393      0.2      7.4      for l in ll:\n",
      "     5  60000000     15348131      0.3     48.4          for x in l:\n",
      "     6  50000000     14008119      0.3     44.2              s += x\n",
      "     7         1            0      0.0      0.0      return s\n",
      "\n"
     ]
    }
   ],
   "source": [
    "l.print_stats()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that this takes *a lot* longer than with just function profiling or without any profiling. Line profiling adds *a lot* more overhead, and this can skew benchmarking results sometimes, so it's a good idea after each optimisation you make to benchmark without any profiling at all, as well as running function and line profiling.\n",
    "\n",
    "If you are getting bored waiting for the line profiler to finish, you can interrupt it and it will still output some useful statistics.\n",
    "\n",
    "Note that you have to explicitly tell `line_profiler` which functions to do line profiling within. When using the `%lprun` magic this is done via the `-f` option. \n",
    "\n",
    "Most of the time is spent in the inner for loop, iterating over the inner lists, and performing the addition. Python has a built-in `sum()` function, maybe we could try that? ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum2d_v3(ll):\n",
    "    \"\"\"Compute the sum of a list of lists of numbers.\"\"\"\n",
    "    s = 0\n",
    "    for l in ll:\n",
    "        x = sum(l)\n",
    "        s += x\n",
    "    return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.91 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sum2d_v3(big_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've shaved off a bit more time. What do the profiling results tell us?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         10000004 function calls in 2.714 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      " 10000000    1.358    0.000    1.358    0.000 {built-in method builtins.sum}\n",
      "        1    1.356    1.356    2.714    2.714 <ipython-input-21-baa7cce51590>:1(sum2d_v3)\n",
      "        1    0.000    0.000    2.714    2.714 {built-in method builtins.exec}\n",
      "        1    0.000    0.000    2.714    2.714 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "cProfile.run('sum2d_v3(big_data)', sort='time')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timer unit: 1e-06 s\n",
      "\n",
      "Total time: 9.65201 s\n",
      "File: <ipython-input-21-baa7cce51590>\n",
      "Function: sum2d_v3 at line 1\n",
      "\n",
      "Line #      Hits         Time  Per Hit   % Time  Line Contents\n",
      "==============================================================\n",
      "     1                                           def sum2d_v3(ll):\n",
      "     2                                               \"\"\"Compute the sum of a list of lists of numbers.\"\"\"\n",
      "     3         1            1      1.0      0.0      s = 0\n",
      "     4  10000001      2536840      0.3     26.3      for l in ll:\n",
      "     5  10000000      4125789      0.4     42.7          x = sum(l)\n",
      "     6  10000000      2989380      0.3     31.0          s += x\n",
      "     7         1            1      1.0      0.0      return s\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import line_profiler\n",
    "l = line_profiler.LineProfiler()\n",
    "l.add_function(sum2d_v3)\n",
    "l.run('sum2d_v3(big_data)')\n",
    "l.print_stats()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now a decent amount of time is being spent inside the built-in `sum()` function, and there's not much we can do about that. But there's also still time being spent in the for loop, and in arithmetic. \n",
    "\n",
    "You've probably realised by now that this is a contrived example. We've actually been going around in circles a bit, and our attempts at optimisation haven't got us very far. To optimise further, we need to try something different..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NumPy\n",
    "\n",
    "For numerical problems, the first port of call is [NumPy](http://www.numpy.org/). Let's use it to solve the sum2d problem. First, let's create a new test dataset, of the same size (10,000,000 rows, 5 columns), but this time using the `np.random.randint()` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[34, 55, 45, 16, 83],\n",
       "       [20, 34, 77, 55, 64],\n",
       "       [45, 61, 65,  8, 37],\n",
       "       ..., \n",
       "       [73, 86, 73,  5, 88],\n",
       "       [70, 57, 92, 40, 21],\n",
       "       [50, 46, 93, 38, 43]])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "big_array = np.random.randint(0, 100, size=(10000000, 5))\n",
    "big_array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `big_array` variable is a NumPy array. Here's a few useful properties:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of dimensions\n",
    "big_array.ndim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10000000, 5)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# size of each dimension\n",
    "big_array.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dtype('int64')"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# data type of each array element\n",
    "big_array.dtype"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "400000000"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of bytes of memory used to store the data\n",
    "big_array.nbytes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "  C_CONTIGUOUS : True\n",
       "  F_CONTIGUOUS : False\n",
       "  OWNDATA : True\n",
       "  WRITEABLE : True\n",
       "  ALIGNED : True\n",
       "  UPDATEIFCOPY : False"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# some other features of the array\n",
    "big_array.flags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NumPy also has its own `np.sum()` function which can operate on N-dimensional arrays. Let's try it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 30.5 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit np.sum(big_array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So using NumPy is almost two orders of magnitude faster than our own Python sum2d implementation. Where does the speed come from? NumPy's functions are implemented in C, so all of the looping and arithmetic is done in native C code. Also, a NumPy array stores it's data in a single, contiguous block of memory, which can be accessed quickly and efficiently."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aside: array arithmetic\n",
    "\n",
    "There are lots of things you can do with NumPy arrays, without ever having to write a for loop. E.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([494856187, 495018159, 495000327, 494824068, 494760222])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# column sum\n",
    "np.sum(big_array, axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([233, 250, 216, ..., 325, 280, 270])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# row sum\n",
    "np.sum(big_array, axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[36, 57, 47, 18, 85],\n",
       "       [22, 36, 79, 57, 66],\n",
       "       [47, 63, 67, 10, 39],\n",
       "       ..., \n",
       "       [75, 88, 75,  7, 90],\n",
       "       [72, 59, 94, 42, 23],\n",
       "       [52, 48, 95, 40, 45]])"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# add 2 to every array element\n",
    "big_array + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 68, 110,  90,  32, 166],\n",
       "       [ 40,  68, 154, 110, 128],\n",
       "       [ 90, 122, 130,  16,  74],\n",
       "       ..., \n",
       "       [146, 172, 146,  10, 176],\n",
       "       [140, 114, 184,  80,  42],\n",
       "       [100,  92, 186,  76,  86]])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# multiply every array element by 2\n",
    "big_array * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 68, 110,  90,  32, 166],\n",
       "       [ 40,  68, 154, 110, 128],\n",
       "       [ 90, 122, 130,  16,  74],\n",
       "       ..., \n",
       "       [146, 172, 146,  10, 176],\n",
       "       [140, 114, 184,  80,  42],\n",
       "       [100,  92, 186,  76,  86]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# add two arrays element-by-element\n",
    "big_array + big_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ True,  True,  True,  True,  True],\n",
       "       [ True,  True,  True,  True,  True],\n",
       "       [ True,  True,  True,  True,  True],\n",
       "       ..., \n",
       "       [ True,  True,  True,  True,  True],\n",
       "       [ True,  True,  True,  True,  True],\n",
       "       [ True,  True,  True,  True,  True]], dtype=bool)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# more complicated operations\n",
    "t = (big_array * 2) == (big_array + big_array)\n",
    "t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.all(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cython\n",
    "\n",
    "For some problems, there is no convenient way to solve them with NumPy alone. Or in some cases, the problem can be solved with NumPy, but the solution requires too much memory. If this is the case, another option is to try optimising with [Cython](http://docs.cython.org/en/latest/). Cython takes your Python code and transforms it into C code, which can then be compiled just like any other C code. A key feature is that Cython allows you to add static type declarations to certain variables, which then enables it to generate highly efficient native C code for certain critical sections of your code.\n",
    "\n",
    "To illustrate the use of Cython I'm going to walk through an example from the Cython profiling tutorial. The task is to compute an approximate value for pi, using the formula below:\n",
    "\n",
    "<img src='/assets/approx_pi.png'>\n",
    "\n",
    "In fact there is a way to solve this problem using NumPy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def approx_pi_numpy(n):\n",
    "    pi = (6 * np.sum(1 / (np.arange(1, n+1)**2)))**.5\n",
    "    return pi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.1415925580968325"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "approx_pi_numpy(10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 84.6 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit approx_pi_numpy(10000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The NumPy solution is pretty quick, but it does require creating several reasonably large arrays in memory. If we wanted a higher precision estimate, we might run out of memory. Also, allocating memory has some overhead, and so we should be able to find a Cython solution that is even faster.\n",
    "\n",
    "Let's start from a pure Python solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def recip_square(i):\n",
    "    x = i**2\n",
    "    s = 1 / x\n",
    "    return s\n",
    "\n",
    "\n",
    "def approx_pi(n):\n",
    "    \"\"\"Compute an approximate value of pi.\"\"\"\n",
    "    val = 0\n",
    "    for k in range(1, n+1):\n",
    "        x = recip_square(k)\n",
    "        val += x\n",
    "    pi = (6 * val)**.5\n",
    "    return pi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.1415925580959025"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "approx_pi(10000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Benchmark and profile:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 3.79 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit approx_pi(10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         10000004 function calls in 4.660 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      " 10000000    3.092    0.000    3.092    0.000 <ipython-input-42-2f54265e4169>:1(recip_square)\n",
      "        1    1.568    1.568    4.660    4.660 <ipython-input-42-2f54265e4169>:7(approx_pi)\n",
      "        1    0.000    0.000    4.660    4.660 {built-in method builtins.exec}\n",
      "        1    0.000    0.000    4.660    4.660 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "cProfile.run('approx_pi(10000000)', sort='time')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timer unit: 1e-06 s\n",
      "\n",
      "Total time: 3.36972 s\n",
      "File: <ipython-input-42-2f54265e4169>\n",
      "Function: approx_pi at line 7\n",
      "\n",
      "Line #      Hits         Time  Per Hit   % Time  Line Contents\n",
      "==============================================================\n",
      "     7                                           def approx_pi(n):\n",
      "     8                                               \"\"\"Compute an approximate value of pi.\"\"\"\n",
      "     9         1            2      2.0      0.0      val = 0\n",
      "    10   2000001       676782      0.3     20.1      for k in range(1, n+1):\n",
      "    11   2000000      2007925      1.0     59.6          x = recip_square(k)\n",
      "    12   2000000       685011      0.3     20.3          val += x\n",
      "    13         1            5      5.0      0.0      pi = (6 * val)**.5\n",
      "    14         1            0      0.0      0.0      return pi\n",
      "\n"
     ]
    }
   ],
   "source": [
    "l = line_profiler.LineProfiler()\n",
    "# l.add_function(recip_square)\n",
    "l.add_function(approx_pi)\n",
    "# use a smaller value of n, otherwise line profiling takes ages\n",
    "l.run('approx_pi(2000000)')\n",
    "l.print_stats()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that I commented out line profiling for the `recip_square()` function. If you're running this yourself, I recommend running line profiling with and without including `recip_square()`, and each time take a look at the results for the outer `approx_pi()` function. This is a good example of how the overhead of line profiling can skew timings, so again, something to beware of. \n",
    "\n",
    "Now let's start constructing a Cython implementation. If you're working in a Jupyter notebook, there is a very convenient `%%cython` magic which enables you to write a Cython module within the notebook. When you execute a `%%cython` code cell, behind the scenes Cython will generate and compile your module, and import the functions into the current session so they can be called from other code cells. To make the `%%cython` magic available, we need to load the Cython notebook extension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%load_ext cython"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin with, all I'll do is copy-paste the pure Python implementation into the Cython module, then change the function names so we can benchmark and profile separately:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%%cython\n",
    "\n",
    "\n",
    "def recip_square_cy1(i):\n",
    "    x = i**2\n",
    "    s = 1 / x\n",
    "    return s\n",
    "\n",
    "\n",
    "def approx_pi_cy1(n):\n",
    "    \"\"\"Compute an approximate value of pi.\"\"\"\n",
    "    val = 0\n",
    "    for k in range(1, n+1):\n",
    "        x = recip_square_cy1(k)\n",
    "        val += x\n",
    "    pi = (6 * val)**.5\n",
    "    return pi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.1415925580959025"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "approx_pi_cy1(10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 2.74 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit approx_pi_cy1(10000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the Cython function is a bit faster than the pure-Python function, even though the code is identical. However, we're still a long way short of the NumPy implementation.\n",
    "\n",
    "What we're going to do next is make a number of modifications to the Cython implementation. If you're working through this in a notebook, I recommend copy-pasting the Cython code cell from above into a new empty code cell below, and changing the function names to `approx_py_cy2()` and `recip_square_cy2()`. Then, work through the optimisation steps below, one-by-one. After each step, run benchmarking and profiling to see where and how much speed has been gained, and examine the HTML diagnostics generated by Cython to see how much yellow (Python interaction) there is left. The goal is to remove all yellow from critical sections of the code. \n",
    "\n",
    "* Copy-paste Cython code cell from above into a new cell below; rename `approx_pi_cy1` to `approx_pi_cy2` and `recip_square_cy1` to `recip_square_cy2`. Be careful to rename all occurrences of the function names.\n",
    "* Change `%%cython` to `%%cython -a` at the top of the cell. Adding the `-a` flag causes Cython to generate an HTML document with some diagnostics. This includes colouring of every line of code according to how much interaction is happening with Python. The more you can remove interaction with Python, the more Cython can optimise and generate efficient native C code.\n",
    "* Add support for function profiling by adding the following comment (special comments like this are interpreted by Cython as compiler directives): \n",
    "\n",
    "<pre># cython: profile=True\n",
    "</pre>\n",
    "\n",
    "* Add support for line profiling by adding the following comments:\n",
    "\n",
    "<pre>\n",
    "# cython: linetrace=True\n",
    "# cython: binding=True\n",
    "# distutils: define_macros=CYTHON_TRACE_NOGIL=1\n",
    "</pre>\n",
    "\n",
    "The following steps optimise the `recip_square` function:\n",
    "\n",
    "* Add a static type declaration for the `i` argument to the `recip_square` function, by changing the function signature from `recip_square(i)` to `recip_square(int i)`.\n",
    "* Add static type declarations for the `x` and `s` variables within the `recip_square` function, via a `cdef` section at the start of the function.\n",
    "* Tell Cython to use C division instead of Python division within the `recip_square` function by adding the `@cython.cdivision(True)` annotation immediately above the function definition. This also requires adding the import statement `cimport cython`.\n",
    "\n",
    "Now the `recip_square` function should be fully optimised. The following steps optimise the outer `approx_pi_cy2` function:\n",
    "\n",
    "* Optimise the `for` loop by adding static type declarations for the `n` argument and the `k` variable.\n",
    "* Make `recip_square` a `cdef` function and add a return type.\n",
    "* Add a static type declaration for the `val` variable.\n",
    "* Remove line profiling support.\n",
    "* Remove function profiling support.\n",
    "* Make `recip_square` an `inline` function.\n",
    "\n",
    "Here is the end result..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.25.2 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_c1207dcff1d0d009517ab1cb3466abf5.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "    <script>\n",
       "    function toggleDiv(id) {\n",
       "        theDiv = id.nextElementSibling\n",
       "        if (theDiv.style.display != 'block') theDiv.style.display = 'block';\n",
       "        else theDiv.style.display = 'none';\n",
       "    }\n",
       "    </script>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.25.2</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-0\">&#xA0;<span class=\"\">01</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">02</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">03</span>: <span class=\"k\">cimport</span> <span class=\"nn\">cython</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">05</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">cdivision</span><span class=\"p\">(</span><span class=\"bp\">True</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">07</span>: <span class=\"k\">cdef</span> <span class=\"kr\">inline</span> <span class=\"kt\">double</span> <span class=\"nf\">recip_square_cy2</span><span class=\"p\">(</span><span class=\"nb\">int</span> <span class=\"n\">i</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-0 '>static CYTHON_INLINE double __pyx_f_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_recip_square_cy2(int __pyx_v_i) {\n",
       "  double __pyx_v_x;\n",
       "  double __pyx_v_s;\n",
       "  double __pyx_r;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"recip_square_cy2\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">08</span>:     <span class=\"k\">cdef</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">09</span>:         <span class=\"n\">double</span> <span class=\"n\">x</span><span class=\"p\">,</span> <span class=\"n\">s</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">10</span>:     <span class=\"n\">x</span> <span class=\"o\">=</span> <span class=\"n\">i</span><span class=\"o\">**</span><span class=\"mf\">2</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_x = __Pyx_pow_long(((long)__pyx_v_i), 2);\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">11</span>:     <span class=\"n\">s</span> <span class=\"o\">=</span> <span class=\"mf\">1</span> <span class=\"o\">/</span> <span class=\"n\">x</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_s = (1.0 / __pyx_v_x);\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">12</span>:     <span class=\"k\">return</span> <span class=\"n\">s</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_r = __pyx_v_s;\n",
       "  goto __pyx_L0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">13</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">14</span>: </pre>\n",
       "<pre class=\"cython line score-23\" onclick='toggleDiv(this)'>+<span class=\"\">15</span>: <span class=\"k\">def</span> <span class=\"nf\">approx_pi_cy2</span><span class=\"p\">(</span><span class=\"nb\">int</span> <span class=\"n\">n</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-23 '>/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_1approx_pi_cy2(PyObject *__pyx_self, PyObject *__pyx_arg_n); /*proto*/\n",
       "static char __pyx_doc_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_approx_pi_cy2[] = \"Compute an approximate value of pi.\";\n",
       "static PyMethodDef __pyx_mdef_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_1approx_pi_cy2 = {\"approx_pi_cy2\", (PyCFunction)__pyx_pw_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_1approx_pi_cy2, METH_O, __pyx_doc_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_approx_pi_cy2};\n",
       "static PyObject *__pyx_pw_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_1approx_pi_cy2(PyObject *__pyx_self, PyObject *__pyx_arg_n) {\n",
       "  int __pyx_v_n;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"approx_pi_cy2 (wrapper)\", 0);\n",
       "  assert(__pyx_arg_n); {\n",
       "    __pyx_v_n = <span class='pyx_c_api'>__Pyx_PyInt_As_int</span>(__pyx_arg_n); if (unlikely((__pyx_v_n == (int)-1) &amp;&amp; <span class='py_c_api'>PyErr_Occurred</span>())) __PYX_ERR(0, 15, __pyx_L3_error)\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_c1207dcff1d0d009517ab1cb3466abf5.approx_pi_cy2\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_approx_pi_cy2(__pyx_self, ((int)__pyx_v_n));\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_approx_pi_cy2(CYTHON_UNUSED PyObject *__pyx_self, int __pyx_v_n) {\n",
       "  int __pyx_v_k;\n",
       "  double __pyx_v_val;\n",
       "  double __pyx_v_x;\n",
       "  double __pyx_v_pi;\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"approx_pi_cy2\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_3);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_c1207dcff1d0d009517ab1cb3466abf5.approx_pi_cy2\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "/* … */\n",
       "  __pyx_tuple_ = <span class='py_c_api'>PyTuple_Pack</span>(6, __pyx_n_s_n, __pyx_n_s_n, __pyx_n_s_k, __pyx_n_s_val, __pyx_n_s_x, __pyx_n_s_pi); if (unlikely(!__pyx_tuple_)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_tuple_);\n",
       "  <span class='refnanny'>__Pyx_GIVEREF</span>(__pyx_tuple_);\n",
       "/* … */\n",
       "  __pyx_t_1 = PyCFunction_NewEx(&amp;__pyx_mdef_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_1approx_pi_cy2, NULL, __pyx_n_s_cython_magic_c1207dcff1d0d00951); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_approx_pi_cy2, __pyx_t_1) &lt; 0) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">16</span>:     <span class=\"sd\">&quot;&quot;&quot;Compute an approximate value of pi.&quot;&quot;&quot;</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">17</span>:     <span class=\"k\">cdef</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">18</span>:         <span class=\"nb\">int</span> <span class=\"n\">k</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">19</span>:         <span class=\"n\">double</span> <span class=\"n\">val</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">20</span>:     <span class=\"n\">val</span> <span class=\"o\">=</span> <span class=\"mf\">0</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_val = 0.0;\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">21</span>:     <span class=\"k\">for</span> <span class=\"n\">k</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"mf\">1</span><span class=\"p\">,</span> <span class=\"n\">n</span><span class=\"o\">+</span><span class=\"mf\">1</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_t_1 = (__pyx_v_n + 1);\n",
       "  for (__pyx_t_2 = 1; __pyx_t_2 &lt; __pyx_t_1; __pyx_t_2+=1) {\n",
       "    __pyx_v_k = __pyx_t_2;\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">22</span>:         <span class=\"n\">x</span> <span class=\"o\">=</span> <span class=\"n\">recip_square_cy2</span><span class=\"p\">(</span><span class=\"n\">k</span><span class=\"p\">)</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_v_x = __pyx_f_46_cython_magic_c1207dcff1d0d009517ab1cb3466abf5_recip_square_cy2(__pyx_v_k);\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">23</span>:         <span class=\"n\">val</span> <span class=\"o\">+=</span> <span class=\"n\">x</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_v_val = (__pyx_v_val + __pyx_v_x);\n",
       "  }\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">24</span>:     <span class=\"n\">pi</span> <span class=\"o\">=</span> <span class=\"p\">(</span><span class=\"mf\">6</span> <span class=\"o\">*</span> <span class=\"n\">val</span><span class=\"p\">)</span><span class=\"o\">**.</span><span class=\"mf\">5</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_pi = pow((6.0 * __pyx_v_val), .5);\n",
       "</pre><pre class=\"cython line score-6\" onclick='toggleDiv(this)'>+<span class=\"\">25</span>:     <span class=\"k\">return</span> <span class=\"n\">pi</span></pre>\n",
       "<pre class='cython code score-6 '>  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  __pyx_t_3 = <span class='py_c_api'>PyFloat_FromDouble</span>(__pyx_v_pi); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 25, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_3);\n",
       "  __pyx_r = __pyx_t_3;\n",
       "  __pyx_t_3 = 0;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython -a\n",
    "\n",
    "\n",
    "cimport cython\n",
    "\n",
    "\n",
    "@cython.cdivision(True)\n",
    "cdef inline double recip_square_cy2(int i):\n",
    "    cdef:\n",
    "        double x, s\n",
    "    x = i**2\n",
    "    s = 1 / x\n",
    "    return s\n",
    "\n",
    "\n",
    "def approx_pi_cy2(int n):\n",
    "    \"\"\"Compute an approximate value of pi.\"\"\"\n",
    "    cdef:\n",
    "        int k\n",
    "        double val\n",
    "    val = 0\n",
    "    for k in range(1, n+1):\n",
    "        x = recip_square_cy2(k)\n",
    "        val += x\n",
    "    pi = (6 * val)**.5\n",
    "    return pi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 11.6 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit approx_pi_cy2(10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cProfile.run('approx_pi_cy2(10000000)', sort='time')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l = line_profiler.LineProfiler()\n",
    "# l.add_function(recip_square_cy2)\n",
    "l.add_function(approx_pi_cy2)\n",
    "# use a smaller value of n, otherwise line profiling takes ages\n",
    "l.run('approx_pi_cy2(2000000)')\n",
    "l.print_stats()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So the optimised Cython implementation is about 8 times faster than the NumPy implementation. You may have noticed that a couple of the optimisation steps didn't actually make much difference to performance, and so weren't really necessary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Cython and NumPy\n",
    "\n",
    "Finally, here's a Cython implementation of the sum2d function, just to give an example of how to use Cython and NumPy together. As above, you may want to introduce the optimisations one at a time, and benchmark and profile after each step, to get a sense of which optimisations really make a difference."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.25.2 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_e638c34ce8e90ea82c9e0687d99dcc24.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "    <script>\n",
       "    function toggleDiv(id) {\n",
       "        theDiv = id.nextElementSibling\n",
       "        if (theDiv.style.display != 'block') theDiv.style.display = 'block';\n",
       "        else theDiv.style.display = 'none';\n",
       "    }\n",
       "    </script>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.25.2</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-0\">&#xA0;<span class=\"\">01</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">02</span>: </pre>\n",
       "<pre class=\"cython line score-11\" onclick='toggleDiv(this)'>+<span class=\"\">03</span>: <span class=\"k\">cimport</span> <span class=\"nn\">numpy</span> <span class=\"k\">as</span> <span class=\"nn\">np</span></pre>\n",
       "<pre class='cython code score-11 '>  __pyx_t_1 = <span class='py_c_api'>PyDict_New</span>(); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 3, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_test, __pyx_t_1) &lt; 0) __PYX_ERR(0, 3, __pyx_L1_error)\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>: <span class=\"k\">cimport</span> <span class=\"nn\">cython</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">05</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">07</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">wraparound</span><span class=\"p\">(</span><span class=\"bp\">False</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">08</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">boundscheck</span><span class=\"p\">(</span><span class=\"bp\">False</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-18\" onclick='toggleDiv(this)'>+<span class=\"\">09</span>: <span class=\"k\">def</span> <span class=\"nf\">sum2d_cy</span><span class=\"p\">(</span><span class=\"n\">np</span><span class=\"o\">.</span><span class=\"n\">int64_t</span><span class=\"p\">[:,</span> <span class=\"p\">:]</span> <span class=\"n\">ll</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-18 '>/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_1sum2d_cy(PyObject *__pyx_self, PyObject *__pyx_arg_ll); /*proto*/\n",
       "static char __pyx_doc_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_sum2d_cy[] = \"Compute the sum of a 2-dimensional array of integers.\";\n",
       "static PyMethodDef __pyx_mdef_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_1sum2d_cy = {\"sum2d_cy\", (PyCFunction)__pyx_pw_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_1sum2d_cy, METH_O, __pyx_doc_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_sum2d_cy};\n",
       "static PyObject *__pyx_pw_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_1sum2d_cy(PyObject *__pyx_self, PyObject *__pyx_arg_ll) {\n",
       "  __Pyx_memviewslice __pyx_v_ll = { 0, 0, { 0 }, { 0 }, { 0 } };\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"sum2d_cy (wrapper)\", 0);\n",
       "  assert(__pyx_arg_ll); {\n",
       "    __pyx_v_ll = __Pyx_PyObject_to_MemoryviewSlice_dsds_nn___pyx_t_5numpy_int64_t(__pyx_arg_ll); if (unlikely(!__pyx_v_ll.memview)) __PYX_ERR(0, 9, __pyx_L3_error)\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24.sum2d_cy\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_sum2d_cy(__pyx_self, __pyx_v_ll);\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_sum2d_cy(CYTHON_UNUSED PyObject *__pyx_self, __Pyx_memviewslice __pyx_v_ll) {\n",
       "  int __pyx_v_i;\n",
       "  int __pyx_v_j;\n",
       "  __pyx_t_5numpy_int64_t __pyx_v_s;\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"sum2d_cy\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_7);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24.sum2d_cy\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  __PYX_XDEC_MEMVIEW(&amp;__pyx_v_ll, 1);\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "/* … */\n",
       "  __pyx_tuple__23 = <span class='py_c_api'>PyTuple_Pack</span>(5, __pyx_n_s_ll, __pyx_n_s_ll, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_s); if (unlikely(!__pyx_tuple__23)) __PYX_ERR(0, 9, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_tuple__23);\n",
       "  <span class='refnanny'>__Pyx_GIVEREF</span>(__pyx_tuple__23);\n",
       "/* … */\n",
       "  __pyx_t_1 = PyCFunction_NewEx(&amp;__pyx_mdef_46_cython_magic_e638c34ce8e90ea82c9e0687d99dcc24_1sum2d_cy, NULL, __pyx_n_s_cython_magic_e638c34ce8e90ea82c); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 9, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_sum2d_cy, __pyx_t_1) &lt; 0) __PYX_ERR(0, 9, __pyx_L1_error)\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "  __pyx_codeobj__24 = (PyObject*)<span class='pyx_c_api'>__Pyx_PyCode_New</span>(1, 0, 5, 0, 0, __pyx_empty_bytes, __pyx_empty_tuple, __pyx_empty_tuple, __pyx_tuple__23, __pyx_empty_tuple, __pyx_empty_tuple, __pyx_kp_s_home_aliman_cache_ipython_cytho, __pyx_n_s_sum2d_cy, 9, __pyx_empty_bytes); if (unlikely(!__pyx_codeobj__24)) __PYX_ERR(0, 9, __pyx_L1_error)\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">10</span>:     <span class=\"sd\">&quot;&quot;&quot;Compute the sum of a 2-dimensional array of integers.&quot;&quot;&quot;</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">11</span>:     <span class=\"k\">cdef</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">12</span>:         <span class=\"nb\">int</span> <span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">j</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">13</span>:         <span class=\"n\">np</span><span class=\"o\">.</span><span class=\"n\">int64_t</span> <span class=\"n\">s</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">14</span>:     <span class=\"n\">s</span> <span class=\"o\">=</span> <span class=\"mf\">0</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_s = 0;\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">15</span>:     <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">ll</span><span class=\"o\">.</span><span class=\"n\">shape</span><span class=\"p\">[</span><span class=\"mf\">0</span><span class=\"p\">]):</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_t_1 = (__pyx_v_ll.shape[0]);\n",
       "  for (__pyx_t_2 = 0; __pyx_t_2 &lt; __pyx_t_1; __pyx_t_2+=1) {\n",
       "    __pyx_v_i = __pyx_t_2;\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">16</span>:         <span class=\"k\">for</span> <span class=\"n\">j</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">ll</span><span class=\"o\">.</span><span class=\"n\">shape</span><span class=\"p\">[</span><span class=\"mf\">1</span><span class=\"p\">]):</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_t_3 = (__pyx_v_ll.shape[1]);\n",
       "    for (__pyx_t_4 = 0; __pyx_t_4 &lt; __pyx_t_3; __pyx_t_4+=1) {\n",
       "      __pyx_v_j = __pyx_t_4;\n",
       "</pre><pre class=\"cython line score-0\" onclick='toggleDiv(this)'>+<span class=\"\">17</span>:             <span class=\"n\">s</span> <span class=\"o\">+=</span> <span class=\"n\">ll</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">j</span><span class=\"p\">]</span></pre>\n",
       "<pre class='cython code score-0 '>      __pyx_t_5 = __pyx_v_i;\n",
       "      __pyx_t_6 = __pyx_v_j;\n",
       "      __pyx_v_s = (__pyx_v_s + (*((__pyx_t_5numpy_int64_t *) ( /* dim=1 */ (( /* dim=0 */ (__pyx_v_ll.data + __pyx_t_5 * __pyx_v_ll.strides[0]) ) + __pyx_t_6 * __pyx_v_ll.strides[1]) ))));\n",
       "    }\n",
       "  }\n",
       "</pre><pre class=\"cython line score-1\" onclick='toggleDiv(this)'>+<span class=\"\">18</span>:     <span class=\"k\">return</span> <span class=\"n\">s</span></pre>\n",
       "<pre class='cython code score-1 '>  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  __pyx_t_7 = __Pyx_PyInt_From_npy_int64(__pyx_v_s); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 18, __pyx_L1_error)\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_7);\n",
       "  __pyx_r = __pyx_t_7;\n",
       "  __pyx_t_7 = 0;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython -a\n",
    "\n",
    "\n",
    "cimport numpy as np\n",
    "cimport cython\n",
    "\n",
    "\n",
    "@cython.wraparound(False)\n",
    "@cython.boundscheck(False)\n",
    "def sum2d_cy(np.int64_t[:, :] ll):\n",
    "    \"\"\"Compute the sum of a 2-dimensional array of integers.\"\"\"\n",
    "    cdef:\n",
    "        int i, j\n",
    "        np.int64_t s\n",
    "    s = 0\n",
    "    for i in range(ll.shape[0]):\n",
    "        for j in range(ll.shape[1]):\n",
    "            s += ll[i, j]\n",
    "    return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 34.3 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sum2d_cy(big_array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 30.4 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit np.sum(big_array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case the Cython and NumPy implementations are nearly identical, so there is no value in using Cython."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Further reading\n",
    "\n",
    "There are loads of good resources on the Web on the topics covered here. Here's just a few:\n",
    "\n",
    "* [The Python profilers](https://docs.python.org/3.6/library/profile.html)\n",
    "* [A guide to analyzing Python performance](https://www.huyng.com/posts/python-performance-analysis) by Huy Nguyen\n",
    "* [SnakeViz](https://jiffyclub.github.io/snakeviz/)\n",
    "* [NumPy tutorial](https://docs.scipy.org/doc/numpy-dev/user/quickstart.html)\n",
    "* [Cython tutorials](http://cython.readthedocs.io/en/latest/src/tutorial/)\n",
    "* [The fallacy of premature optimization](http://ubiquity.acm.org/article.cfm?id=1513451) by Randall Hyde"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}