01-python-slow.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Why is Python so slow\\*?\n",
    "\n",
    "\\* relative to other languages, for interpreted, dynamically typed code, etc, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tracing CPython code execution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def foo(a, b):\n",
    "    return a + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's disassemble it with the `dis` module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  2           0 LOAD_FAST                0 (a)\n",
      "              3 LOAD_FAST                1 (b)\n",
      "              6 BINARY_ADD\n",
      "              7 RETURN_VALUE\n"
     ]
    }
   ],
   "source": [
    "from dis import dis\n",
    "dis(foo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's `BINARY_ADD`?\n",
    "\n",
    "We crack open CPython's source code and take a look inside `Python/ceval.c`:\n",
    "\n",
    "```c\n",
    "/* Python/ceval.c */\n",
    "TARGET(BINARY_ADD) {\n",
    "    PyObject *right = POP();\n",
    "    PyObject *left = TOP();\n",
    "    PyObject *sum;\n",
    "    /* NOTE(haypo): Please don't try to micro-optimize int+int on\n",
    "       CPython using bytecode, it is simply worthless.\n",
    "       See http://bugs.python.org/issue21955 and\n",
    "       http://bugs.python.org/issue10044 for the discussion. In short,\n",
    "       no patch shown any impact on a realistic benchmark, only a minor\n",
    "       speedup on microbenchmarks. */\n",
    "    if (PyUnicode_CheckExact(left) &&\n",
    "            PyUnicode_CheckExact(right)) {\n",
    "        sum = unicode_concatenate(left, right, f, next_instr);\n",
    "        /* unicode_concatenate consumed the ref to left */\n",
    "    }\n",
    "    else {\n",
    "        sum = PyNumber_Add(left, right); // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
    "        Py_DECREF(left);\n",
    "    }\n",
    "    Py_DECREF(right);\n",
    "    SET_TOP(sum);\n",
    "    if (sum == NULL)\n",
    "        goto error;\n",
    "    DISPATCH();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's `PyNumber_Add(left, right)`?\n",
    "\n",
    "```c\n",
    "/* Objects/abstract.c */\n",
    "PyObject *\n",
    "PyNumber_Add(PyObject *v, PyObject *w)\n",
    "{\n",
    "    PyObject *result = binary_op1(v, w, NB_SLOT(nb_add)); // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
    "    if (result == Py_NotImplemented) {\n",
    "        PySequenceMethods *m = v->ob_type->tp_as_sequence;\n",
    "        Py_DECREF(result);\n",
    "        if (m && m->sq_concat) {\n",
    "            return (*m->sq_concat)(v, w);\n",
    "        }\n",
    "        result = binop_type_error(v, w, \"+\");\n",
    "    }\n",
    "    return result;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's `binary_op1()`?\n",
    "\n",
    "```c\n",
    "static PyObject *\n",
    "binary_op1(PyObject *v, PyObject *w, const int op_slot)\n",
    "{\n",
    "    PyObject *x;\n",
    "    binaryfunc slotv = NULL;\n",
    "    binaryfunc slotw = NULL;\n",
    "\n",
    "    if (v->ob_type->tp_as_number != NULL)\n",
    "        slotv = NB_BINOP(v->ob_type->tp_as_number, op_slot);\n",
    "    if (w->ob_type != v->ob_type &&\n",
    "        w->ob_type->tp_as_number != NULL) {\n",
    "        slotw = NB_BINOP(w->ob_type->tp_as_number, op_slot); // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
    "        if (slotw == slotv)\n",
    "            slotw = NULL;\n",
    "    }\n",
    "    if (slotv) {\n",
    "        if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {\n",
    "            x = slotw(v, w);\n",
    "            if (x != Py_NotImplemented)\n",
    "                return x;\n",
    "            Py_DECREF(x); /* can't do it */\n",
    "            slotw = NULL;\n",
    "        }\n",
    "        x = slotv(v, w);\n",
    "        if (x != Py_NotImplemented)\n",
    "            return x;\n",
    "        Py_DECREF(x); /* can't do it */\n",
    "    }\n",
    "    if (slotw) {\n",
    "        x = slotw(v, w);\n",
    "        if (x != Py_NotImplemented)\n",
    "            return x;\n",
    "        Py_DECREF(x); /* can't do it */\n",
    "    }\n",
    "    Py_RETURN_NOTIMPLEMENTED;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's `NB_BINOP()`?\n",
    "\n",
    "```c\n",
    "#define NB_BINOP(nb_methods, slot) \\\n",
    "        (*(binaryfunc*)(& ((char*)nb_methods)[slot]))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cut to the chase: where's the addition function for two ints (longs)?\n",
    "\n",
    "```c\n",
    "/* Objects/longobject.c */\n",
    "static PyObject *\n",
    "long_add(PyLongObject *a, PyLongObject *b)\n",
    "{\n",
    "    PyLongObject *z;\n",
    "\n",
    "    CHECK_BINOP(a, b);\n",
    "\n",
    "    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {\n",
    "        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b)); // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
    "    }\n",
    "    if (Py_SIZE(a) < 0) {\n",
    "        if (Py_SIZE(b) < 0) {\n",
    "            z = x_add(a, b);\n",
    "            if (z != NULL) {\n",
    "                /* x_add received at least one multiple-digit int,\n",
    "                   and thus z must be a multiple-digit int.\n",
    "                   That also means z is not an element of\n",
    "                   small_ints, so negating it in-place is safe. */\n",
    "                assert(Py_REFCNT(z) == 1);\n",
    "                Py_SIZE(z) = -(Py_SIZE(z));\n",
    "            }\n",
    "        }\n",
    "        else\n",
    "            z = x_sub(b, a);\n",
    "    }\n",
    "    else {\n",
    "        if (Py_SIZE(b) < 0)\n",
    "            z = x_sub(a, b);\n",
    "        else\n",
    "            z = x_add(a, b);\n",
    "    }\n",
    "    return (PyObject *)z;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's `MEDIUM_VALUE()`?\n",
    "\n",
    "```c\n",
    "/* Objects/longobject.c */\n",
    "#define MEDIUM_VALUE(x) (assert(-1 <= Py_SIZE(x) && Py_SIZE(x) <= 1),  \\\n",
    "     Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] :  \\\n",
    "         (Py_SIZE(x) == 0 ? (sdigit)0 :  \\\n",
    "          (sdigit)(x)->ob_digit[0]))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why so much code for such a simple operation?\n",
    "\n",
    "* C-level is interpreting bytecodes (`BINARY_ADD` in this case).\n",
    "* Polymorphism -- code can handle `foo('a', 'b')` or any types that support `+`.\n",
    "* Works for user-defined types, too, with an `__add__` or `__radd__` magic method.\n",
    "* Error checking everywhere...\n",
    "* For adding ints, does overflow checking and conversions, etc.\n",
    "\n",
    "All these features mean a lot of code at the C level."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is the performance?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000000 loops, best of 3: 112 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit foo(1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 9.73 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 159 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit foo('a', 'b')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "### CPython slowdown 1: interpreted bytecode execution\n",
    "\n",
    "* Fetching CPython bytecode ops, managing the stack machine, all ops in `ceval.c`.\n",
    "* Extensive error checking and handling.\n",
    "\n",
    "### CPython slowdown 2: dynamic type resolution\n",
    "\n",
    "* Type introspection, dynamic dispatch on every operation / method call, supporting generic operations.\n",
    "* And extensive error checking and handling, up-and-down the call stack."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How does Cython speed it up? [02-cython-comparison.ipynb](02-cython-comparison.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}