5. The Python GIL.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import itertools\n",
    "from queue import Queue\n",
    "from threading import Thread\n",
    "\n",
    "import requests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_prime(n):\n",
    "    if n in (2, 3):\n",
    "        return True\n",
    "    if n % 2 == 0:\n",
    "        return False\n",
    "    for divisor in range(3, n, 2):\n",
    "        if n % divisor == 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(19)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15492781\n",
      "15492787\n",
      "15492803\n",
      "15492811\n",
      "15492810\n",
      "15492833\n",
      "15492859\n",
      "1549289\n"
     ]
    }
   ],
   "source": [
    "!head data/prime_mixture.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('data/prime_mixture.txt') as fp:\n",
    "    numbers = [int(n.strip()) for n in fp.read().split() if n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[15492781, 15492787, 15492803, 15492811, 15492810]"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching primes\n",
    "\n",
    "#### Understanding the problem, designing the solution\n",
    "\n",
    "As great software engineers we are, we'll start first by understanding our problem. How much time does it take to find out if a number is prime or not?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(numbers[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5961849689483643"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time.time() - start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approximately 0.5 seconds (we don't need to be very accurate, don't worry). If we have 10 prime numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we could expect a single threaded solution to take ~5 seconds. Let's start with that approach first:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Single threaded approach\n",
    "\n",
    "A single threaded solution is the most basic one we can think of. No threads, locks, queues or concurrency. Plain old Python code to get the job done:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search_primes_single_thread(numbers):\n",
    "    return [n for n in numbers if is_prime(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = search_primes_single_thread(numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Time: 3.8426270484924316 seconds. Found 9 primes out of 10 total numbers.'"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"Time: {time.time() - start} seconds. Found {len(results)} primes out of {len(numbers)} total numbers.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, it took less than 5 seconds, but it's within the same order of magnitude: between 1 and 10 seconds."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Speeding things up with multiple threads\n",
    "\n",
    "We quickly realize that we could improve a lot the solution by using multiple threads. If I have 16 cores in this computer, each one of them can calculate a prime at the same time, and we'll be done a lot quicker. How quicker? Well, assuming I have 16 cores, and each core will definitively take 1 number to process, our solution should take no more than a second. The slowest prime to compute will be the total time.\n",
    "\n",
    "Let's try it out!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_prime_worker(number, results):\n",
    "    if is_prime(number):\n",
    "        results.append(number)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(We should potentially use a thread safe collection, I know in CPython list append operations are thread safe)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "threads = [Thread(target=check_prime_worker, args=(number, results)) for number in numbers]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "[t.start() for t in threads];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "[t.join() for t in threads];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Time: 4.015429973602295 seconds. Found 9 primes out of 10 total numbers.'"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"Time: {time.time() - start} seconds. Found {len(results)} primes out of {len(numbers)} total numbers.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**WHAT! 😦** 4 seconds! That's even slower than the sequential single-threaded solution. What is going on here? 🤔\n",
    "\n",
    "Congratulations, let me introduce you to:\n",
    "\n",
    "<center>\n",
    "    <img src=\"img/gil_meme.jpeg\" />\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is the GIL?\n",
    "\n",
    "The GIL is a safety mechanism added to **cpython** (and Cpython only) that prevents multiple threads from running at the same time. This is completely counter intuitive, as the objective of having multiple threads is to make them run **in parallel**: that is, 2 or more at the same time.\n",
    "\n",
    "Understanding the GIL is outside the scope of this presentation. There's one important point that you should understand about the GIL: your threads will \"suffer\" the GIL **ONLY** if you're running CPU Bound tasks. I/O tasks will _release_ the GIL and let other threads run.\n",
    "\n",
    "\n",
    "If you want to know more about the GIL, this talk from Larry Hastings is just amazing: https://www.youtube.com/watch?v=KVKufdTphKs\n",
    "As a summary:\n",
    "\n",
    "* The GIL is a necessary evil. It made Python's C API simple to understand and extend.\n",
    "* Guido is open to remove the GIL, ONLY if it doesn't hurt performance (Larry demonstrated in another talk that it's very hard to achieve that)\n",
    "* Only CPython has a GIL. Other interpreters (Jython, PyPy, Ironpython) don't.\n",
    "* The GIL was \"broken\" in Python 2, but has been fixed in Python 3.2. We've reached \"peak\" performance so Larry doesn't think there will be significant improvements there."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An I/O bound demonstration\n",
    "\n",
    "Let's revisit the example from our first lesson and run an I/O bound task multithreaded to prove the GIL is not an issue in this case.\n",
    "\n",
    "#### Sequential first\n",
    "\n",
    "We'll check our crypto prices again. This time, each request is artificially delayed 3 seconds. We'll check only 3 prices, for the same date, so it's going to take approximately 6 seconds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "BASE_URL = \"http://localhost:5000\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "EXCHANGES = ['bitfinex', 'bitstamp', 'kraken']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "prices = [\n",
    "    requests.get(f\"{BASE_URL}/price/{exchange}/btc/2020-04-01\").json()['close']\n",
    "    for exchange in EXCHANGES\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.828252077102661"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time.time() - start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, ~6 seconds.\n",
    "\n",
    "#### Now, the multithreaded version\n",
    "\n",
    "We'll try now the same example with multiple threads. If our claims about the GIL being released by I/O Bound tasks is true, then the whole task should take around 2 seconds, let's check it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_price(exchange, results):\n",
    "    BASE_URL = \"http://localhost:5000\"\n",
    "    return requests.get(f\"{BASE_URL}/price/{exchange}/btc/2020-04-01\").json()['close']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "threads = [Thread(target=check_price, args=(exchange, results)) for exchange in EXCHANGES]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "[t.start() for t in threads];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "[t.join() for t in threads];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.3815770149230957"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time.time() - start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Success! We've now corroborated that the GIL is actually released when waiting for I/O, which makes our programs \"feel\" like running in parallel.\n",
    "\n",
    "## Summary\n",
    "\n",
    "In this lesson we learned about one of the most \"hated\" features of Python: the GIL. Every post you read that is titled \"why not Python?\" or \"Python vs \\[insert language\\]\" will mention the GIL as a major drawback.\n",
    "\n",
    "In our next lesson we'll learn how we can improve our code if it's CPU bound."
   ]
  }
 ],
 "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}