Cython_Tutorial_One.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Cython Tutorial One.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/EveryTimeIWill18/Cython_Repo/blob/master/Cython_Tutorial_One.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "metadata": {
        "id": "ooRjCqo0JpW5",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "![alt text](https://upload.wikimedia.org/wikipedia/en/thumb/c/ce/Cython-logo.svg/1200px-Cython-logo.svg.png =200x100)\n",
        "\n",
        "# Getting started with Cython\n",
        "\n",
        "\n"
      ]
    },
    {
      "metadata": {
        "id": "KyDarRDsKfhl",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Introduction"
      ]
    },
    {
      "metadata": {
        "id": "2Jce3J8PKsyt",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "As a big data engineer and machine learning engineer at a multinational reinsurance firm, I frequently have to build data pipelines and these pipelines can often be slow when utilizing standard python.  To circumvent clogs in certain memory intensive tasks, I make use of cython\n",
        "<br>The __Cython__ language is a superset of __Python__, this means that almost all python code works in cython.  The reason for using cython is that python code can sometimes be slow and by converting some of the slow python code into cython, we can dramatically reduce the runtime.\n",
        "As always, it's best if we begin with an example of the speed benefits of cython."
      ]
    },
    {
      "metadata": {
        "id": "-WnbuIkZMpU-",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "To begin, we must load in the cython extension when working inside a jupyter notebook."
      ]
    },
    {
      "metadata": {
        "id": "WaQrJS1gMnam",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "%load_ext cython"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "IZ6gry3-s6Dz",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Cython vs. Python Speed\n",
        "As a first example, lets create two functions that compute the sum of integers 1 to n<br>\n",
        "*Example 1: Compute*<br>\n",
        "## $$s = \\sum_{i=0}^{n}s_{i}$$"
      ]
    },
    {
      "metadata": {
        "id": "TxWNxPJwt-u0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "- *__NOTE__: we must add __%%cython%%__ to enable running cython code.*\n",
        "- *Cython C level(__cdef__) functions must be wrapped in a python function to use them i standard python.*"
      ]
    },
    {
      "metadata": {
        "id": "W6ZwclJfMzlX",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "%%cython\n",
        "\n",
        "# - python version\n",
        "def py_sum(n):\n",
        "  \"\"\"Compute the sum\"\"\"\n",
        "  i = 0\n",
        "  the_sum = 0\n",
        "  for i in range(n):\n",
        "    the_sum += i\n",
        "  return the_sum\n",
        "\n",
        "# - cython version\n",
        "cdef inline int cy_sum(int n):\n",
        "  cdef int i = 0\n",
        "  cdef int the_sum = 0\n",
        "  for i in range(n):\n",
        "    the_sum += i\n",
        "  return the_sum\n",
        "\n",
        "def cy_wrapper(int n):\n",
        "  return cy_sum(n)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "QAQ9drqh0vNz",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Run Time Comparison\n",
        "As you can see, cython is clearly the winner in terms of run time, with numpy being the slowest."
      ]
    },
    {
      "metadata": {
        "id": "fieHJ3oSu10f",
        "colab_type": "code",
        "outputId": "e5e69fe1-6bbb-4475-a254-40d606b96dc4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 255
        }
      },
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "\n",
        "print(\"python time complexity\")\n",
        "%timeit py_sum(100000000)\n",
        "print('\\n')\n",
        "\n",
        "print('cython time complexity')\n",
        "%timeit cy_wrapper(100000000)\n",
        "print('\\n')\n",
        "\n",
        "print(\"python sum function\")\n",
        "%timeit sum(range(1,100000000))\n",
        "print('\\n')\n",
        "\n",
        "print(\"numpy sum\")\n",
        "%timeit np.sum(range(1, 100000000))"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "python time complexity\n",
            "1 loop, best of 3: 4.44 s per loop\n",
            "\n",
            "\n",
            "cython time complexity\n",
            "10 loops, best of 3: 36.8 ms per loop\n",
            "\n",
            "\n",
            "python sum function\n",
            "1 loop, best of 3: 2.11 s per loop\n",
            "\n",
            "\n",
            "numpy sum\n",
            "1 loop, best of 3: 21.5 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "4Tf7etyk0_pI",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Cython Funtion Types\n",
        "In cython, we can declare three types of functions:\n",
        "- __cdef__: *C level function. cdef functions cannot be called directly in pure python.*\n",
        "- __cpdef__: *C level function with a python binding so it can be called in pure python.*\n",
        "- __def__: *Pure python function.*\n",
        "\n",
        "Within cython, variables must also be declared with the __*cdef*__ declaration.\n",
        "i.e.\n",
        "```python\n",
        "cdef int i            # declare an integer variable\n",
        "cdef double d = 10.1  # declare a double and initialize it to 10.1\n",
        "```"
      ]
    },
    {
      "metadata": {
        "id": "qUfq4Grn4CSu",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Cython DataTypes\n",
        "Unlike python, where variables are infered by the python interpreter, cython variables must be declared.  The next cell demonstrates some of the data types available in cython.\n"
      ]
    },
    {
      "metadata": {
        "id": "XqUBkSD61GWp",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "%%cython\n",
        "# add -a to check python iteration\n",
        "\n",
        "\n",
        "# - declaration of basic C variable types\n",
        "cdef:\n",
        "  int i = 0       # integer \n",
        "  bint b = True   # boolean\n",
        "  char c = b'w'   # character\n",
        "  double d = 10.1 # double\n",
        "  float f = 1.10  # floating point\n",
        "  long l = 1000   # long int\n",
        "  long double ld = 100000000000.10 # long double\n",
        "  \n",
        "# - declaration of python types within C\n",
        "#    these python objects are declared by cython\n",
        "#    as C pointers to built-in Python struct type\n",
        "cdef list cy_list\n",
        "cdef dict cy_dict\n",
        "cdef str cy_str\n",
        "cdef set cy_set"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "-yuRS_PmDxPD",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Cython Pointers\n",
        "In languages like __C__,  __C++__ , __Rust__, and __Go__,\n",
        "they allow for variable types called *pointers*.\n",
        "A pointer is a variable that stores the memory location of another variable. In __C__/__C++__ we declare them like:\n",
        "```C\n",
        "int a = 10;\n",
        "// declaration of a pointer to an int\n",
        "int *aPtr = NULL;\n",
        "*aPtr = &a; // store the address of a\n",
        "\n",
        "printf('%d\\n', *aPtr); // prints out the value 10\n",
        "printf('%x\\n', aPtr);  // prints address 0x7ffee90ef768\n",
        "\n",
        "// dereference operator\n",
        "// this changes the value stored at 0x7ffee90ef768\n",
        "*aPtr = 100;  \n",
        "printf('%d\\n', a); // a is now 100\n",
        "\n",
        "```\n",
        "\n",
        "### For memory allocation, C uses the following functions from the stdlib.h library.<br> Memory is taken from the *free store(heap) *.\n",
        "```c\n",
        " #include <stdlib.h> // malloc, realloc, free\n",
        " #include <stdio.h>\n",
        " \n",
        "\n",
        " int main(int argc, char *argv[]) {\n",
        "          //declare a pointer to a char. \n",
        "          char *token = NULL; //good practice to set to NULL\n",
        "          \n",
        "          // initial memory allocation\n",
        "          token = (char*)malloc(5*sizeof(char)); // allocate 5 bytes of memory\n",
        "          \n",
        "          // fill the 5 bytes with chars\n",
        "          int i = 0;\n",
        "          *(char + i) = 'h';\n",
        "          *(char + (i+1)) = 'e';\n",
        "          *(char + (i+2)) = 'l';\n",
        "          *(char + (i+3)) = 'l';\n",
        "          *(char + (i+4)) = 'o';       //  0 1 2 3 4  memory position\n",
        "          // token hold the following: // [h|e|l|l|o] \n",
        "          // NOTE: pointers in C are equivalent to arrays.\n",
        "          \n",
        "          // If we want to store hello world into token, we use the realloc function\n",
        "          token = (char*)realloc(token, 11*sizeof(char));\n",
        "          *(char + (i+5)) = ' ';\n",
        "          *(char + (i+6)) = 'w';\n",
        "          *(char + (i+7)) = 'o';\n",
        "          *(char + (i+8)) = 'r';\n",
        "          *(char + (i+9)) = 'l';\n",
        "          *(char + (i+10)) = 'd';\n",
        "          \n",
        "          \n",
        " return 0;\n",
        " }\n",
        "\n",
        "```\n"
      ]
    },
    {
      "metadata": {
        "id": "AfwZ3TtaU9za",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Pointers and Memroy allocation in Cython\n",
        "We can do the same types of memory allocation within cython."
      ]
    },
    {
      "metadata": {
        "id": "AtO8aa4makCz",
        "colab_type": "code",
        "outputId": "e31ff467-4af9-4552-b4f7-9742f7d1d504",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 340
        }
      },
      "cell_type": "code",
      "source": [
        "%%cython\n",
        "cimport cython\n",
        "from libc.stdlib cimport malloc, realloc, free # import C level functions for memory allocation\n",
        "\n",
        "# - declare a pointer to a char\n",
        "cdef char* token = NULL; # good practice to initialize pointers to NULL\n",
        "# - allocate 5 bytes of memory to token\n",
        "token = <char*>malloc(5*sizeof(char))\n",
        "\n",
        "# - insert values into the token array\n",
        "token[0] = b'h'\n",
        "token[1] = b'e'\n",
        "token[2] = b'l'\n",
        "token[3] = b'l'\n",
        "token[4] = b'o'\n",
        "cdef int i = 0\n",
        "print(chr(token[i]))\n",
        "print(chr(token[i+1]))\n",
        "print(chr(token[i+2]))\n",
        "print(chr(token[i+3]))\n",
        "print(chr(token[i+4]))\n",
        "print('\\n\\n')\n",
        "# - !WARNING: you must be careful with pointers as you can access memory \n",
        "# that may be storing other functions or variables and you can accidentally \n",
        "# overwrite them. Use caution when using pointers.\n",
        "\n",
        "#print(chr(token[i+5])) # we access a memory location not assigned to token\n",
        "\n",
        "# - if we need more memory, we can use realloc just the C code above\n",
        "token = <char*>realloc(token, 11*sizeof(char))\n",
        "token[5] = b' '\n",
        "token[6] = b'w'\n",
        "token[7] = b'o'\n",
        "token[8] = b'r'\n",
        "token[9] = b'l'\n",
        "token[10] = b'd'\n",
        "print(chr(token[i]))\n",
        "print(chr(token[i+1]))\n",
        "print(chr(token[i+2]))\n",
        "print(chr(token[i+3]))\n",
        "print(chr(token[i+4]))\n",
        "print(chr(token[i+5]))\n",
        "print(chr(token[i+6]))\n",
        "print(chr(token[i+7]))\n",
        "print(chr(token[i+8]))\n",
        "print(chr(token[i+9]))\n",
        "print(chr(token[i+10]))\n",
        "\n",
        "# - we the C's free function to release the memory taken from the free store(heap)\n",
        "free(token) # release memory back to the heap\n",
        "#print(token) # !WARNING: this will cause an error to be raised."
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "h\n",
            "e\n",
            "l\n",
            "l\n",
            "o\n",
            "\n",
            "\n",
            "\n",
            "h\n",
            "e\n",
            "l\n",
            "l\n",
            "o\n",
            " \n",
            "w\n",
            "o\n",
            "r\n",
            "l\n",
            "d\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "g1Q2q1fshj_6",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# C Data Containers\n",
        "Cython has access to C's __*struct*__, __*enum*__, and __*union*__  data containers. In C/C++, these can be created by:\n",
        "\n",
        "```c\n",
        "\n",
        "/*Ex: struct*/\n",
        "// structs allow the user to combine data of different types.\n",
        "// example of a struct which stores character tokens\n",
        "struct __tok__ {\n",
        "  \n",
        "  char **tokens;       // store the tokens\n",
        "  int *token_lengths;  // length of each token\n",
        "\n",
        "} token; // set the alias of __tok__ to token\n",
        "\n",
        "// create a pointer to the __tok__ struct\n",
        "struct __tok__ *tPtr = (struct __tok__*)malloc(sizeof(struct __tok__));\n",
        "\n",
        "/*access tPtr's data*/\n",
        "// allocate memory for the token lengths\n",
        "// Assume the input sentence has 10 words\n",
        "tPtr->*token_lengths = (int*)malloc(10*sizeof(10));\n",
        "\n",
        "// allocate memory for 20 tokens\n",
        "// **tokens is a pointer to pointer to char\n",
        "tPtr->tokens = (char**)malloc(20*sizeof(char *));\n",
        "// each element in the tokens array is a pointer\n",
        "// so we must allocate memory for each pointer now\n",
        "for (int i=0; i < 20; i++) {\n",
        "// assume each token has length of 10 chars\n",
        "  *(tPtr->tokens + i) = (char*)malloc(10*sizeof(char));\n",
        "}\n",
        "\n",
        "\n",
        "/*Ex enum*/\n",
        "// used to assign names to integral constants\n",
        "enum week_days {Sunday, \n",
        "Monday, Tuesday, Wednesday, \n",
        "Thursday, Friday, Saturday};\n",
        "\n",
        "enum week_days day;\n",
        "day = Monday;\n",
        "printf(\"%d\\n\", day);  // prints 1\n",
        "\n",
        "/* Ex union*/\n",
        "union data {\n",
        "    int i;\n",
        "    float f;\n",
        "    char str[20];\n",
        "\n",
        "} d1, d2, *d3;\n",
        "\n",
        "\n",
        "```"
      ]
    },
    {
      "metadata": {
        "id": "6gReSZW48Vvx",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### C Data Containers in Cython"
      ]
    },
    {
      "metadata": {
        "id": "cgzq4UdHjzEn",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 187
        },
        "outputId": "138ab071-403e-41f8-e7b9-34a754f6015a"
      },
      "cell_type": "code",
      "source": [
        "%%cython\n",
        "import warnings\n",
        "from libc.stdlib cimport malloc, realloc, free\n",
        "warnings.filterwarnings(action='once')\n",
        "# - create a struct called __tok__\n",
        "cdef struct __tok__:\n",
        "  char **tokens\n",
        "  int *num_tokens\n",
        "  \n",
        "# - create an enum called week_days\n",
        "cdef enum week_days:\n",
        "  Sunday, Monday, Tuesday,\n",
        "  Wednesday, Thursday,\n",
        "  Friday, Saturday\n",
        "  \n",
        "# - create a union called data\n",
        "cdef union data:\n",
        "  double *d_data_array\n",
        "  int *i_data_array\n",
        "  char *c_data_array\n",
        "  float *f_data_array\n",
        "  \n",
        "# - create a struct pointer to __tok__ and allocate memory\n",
        "cdef __tok__ *tPtr = <__tok__*>malloc(sizeof(__tok__))\n",
        "tPtr.tokens = <char**>malloc(5*sizeof(char*)) # allocate memory for 5 tokens\n",
        "\n",
        "# - iterate through each token container and allocate memory\n",
        "cdef int j = 0\n",
        "for j in range(5):\n",
        "  tPtr.tokens[j] = <char*>malloc(5*sizeof(char)) ## assign a size of 5 for each token\n",
        "  \n",
        "# - load tokens into tPtr.tokens\n",
        "b1 = b'hello'\n",
        "b2 = b'world'\n",
        "b3 = b'there'\n",
        "b4 = b'other'\n",
        "b5 = b'nicer'\n",
        "\n",
        "tPtr.tokens[0] = b1\n",
        "tPtr.tokens[1] = b2\n",
        "tPtr.tokens[2] = b3\n",
        "tPtr.tokens[3] = b4\n",
        "tPtr.tokens[4] = b5\n",
        "\n",
        "print(tPtr.tokens[0])\n",
        "print(tPtr.tokens[1])\n",
        "print(tPtr.tokens[2])\n",
        "print(tPtr.tokens[3])\n",
        "print(tPtr.tokens[4])"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "warning: /root/.cache/ipython/cython/_cython_magic_636b3286a6262bfbe06dd7c9122f655a.pyx:38:17: Obtaining 'char *' from externally modifiable global Python value\n",
            "warning: /root/.cache/ipython/cython/_cython_magic_636b3286a6262bfbe06dd7c9122f655a.pyx:39:17: Obtaining 'char *' from externally modifiable global Python value\n",
            "warning: /root/.cache/ipython/cython/_cython_magic_636b3286a6262bfbe06dd7c9122f655a.pyx:40:17: Obtaining 'char *' from externally modifiable global Python value\n",
            "warning: /root/.cache/ipython/cython/_cython_magic_636b3286a6262bfbe06dd7c9122f655a.pyx:41:17: Obtaining 'char *' from externally modifiable global Python value\n",
            "warning: /root/.cache/ipython/cython/_cython_magic_636b3286a6262bfbe06dd7c9122f655a.pyx:42:17: Obtaining 'char *' from externally modifiable global Python value\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "stream",
          "text": [
            "b'hello'\n",
            "b'world'\n",
            "b'there'\n",
            "b'other'\n",
            "b'nicer'\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "MzsJORgNEBtH",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Cython Advanced features\n",
        "Cython has a number of useful advanced features, some taken from C, others defined only within cython.\n",
        "\n",
        "- __ctypedef__: C allows for creating an alternative name to datatypes. It's particulary useful when working with combersome function pointers.\n",
        "\n",
        "- __function pointers__: Cython can make use of C's function pointer notation, that is a pointer to a function.<br>\n",
        "To read a function pointer, have a look at the following: __int (*compute) (int, int)__. To read this, start with the first set of brakets that start with the __*__ symbol, this indicates that we are working with a function pointer. From here, look to the right, we haev a function pointer that takes in 2 ints. Now look at the left most value, so the function pointer returns an int. Thus, this function poitner takes in 2 ints and returns an int.\n",
        "\n",
        "\n",
        "### *ex*: typedef keyword in C\n",
        "```c\n",
        "// assume we have two functions add, mult that take in ints a, b and return an int\n",
        "\n",
        "// using typedef\n",
        "typedef int(*opr)(int, int);\n",
        "\n",
        "// function that takes in a function pointer and 2 ints and returns an int\n",
        "int compute(int (*operation)(int, int), int x, int y) {\n",
        "    return operation(x, y);\n",
        "}\n",
        "\n",
        "// same function as above but now using typedef\n",
        "int compute(opr op, int x, int y) {\n",
        "  return op(x, y);\n",
        "}\n",
        "\n",
        "int add(int a, int b) { return a + b;}\n",
        "int mult(int a, int b) { return a * b;}\n",
        "\n",
        "\n",
        "```\n"
      ]
    },
    {
      "metadata": {
        "id": "X4KCQWc58x9-",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "6b078121-3b83-4e16-dfe5-ffe356c8ad2f"
      },
      "cell_type": "code",
      "source": [
        "%%cython\n",
        "\n",
        "# - fused types\n",
        "# fused types allow generic programming within cython\n",
        "# Currently, only variables and function/method arguments can be fuesd types\n",
        "ctypedef fused int_float_double:\n",
        "  int\n",
        "  float\n",
        "  double\n",
        "\n",
        "# - ctypedef for the function pointer opr\n",
        "ctypedef int (*opr)(int, int)\n",
        "\n",
        "# - same as opr but using fused types\n",
        "ctypedef int_float_double (*operation)(int_float_double v1, int_float_double v2)\n",
        "\n",
        "# - compute takes in a function pointer and 2 ints\n",
        "cdef int compute(opr op, int x, int y):\n",
        "  return op(x, y)\n",
        "\n",
        "cdef int add(int a, int b):\n",
        "  return a + b\n",
        "cdef int mult(int a, int b):\n",
        "  return a * b\n",
        "\n",
        "cdef int_float_double addf(int_float_double a, int_float_double b):\n",
        "  return a + b\n",
        "cdef int_float_double multf(int_float_double a, int_float_double b):\n",
        "  return a * b\n",
        "\n",
        "\n",
        "# - utilizing the function pointer and ctypedef\n",
        "print(compute(mult, 10, 20))\n",
        "print(compute(add, 100, 99))\n",
        "\n",
        "# - utilizing fused type function pointer and ctypedef\n",
        "print(addf(10.1, 10))\n",
        "print(multf(100.1, .512))"
      ],
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "200\n",
            "199\n",
            "20.1\n",
            "51.2512\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "zbaxrrpEKvGk",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}