{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parallel Map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Parallelism* means doing multiple things at once.  Writing your programs in a parallel way can make them faster in two scenarios:\n",
    "\n",
    "1. when your computer has multiple CPUs (or multiple cores, which are like CPUs on a bigger chip).\n",
    "2. when some of the things being done in parallel involve waiting (for example, for a file to download or time to pass)\n",
    "\n",
    "There are many ways to write parallel code.  We'll use Python's multiprocessing pools, which start multiple Python processes, then split work across them.\n",
    "\n",
    "First, we'll create a function that is artificially slow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: 5\n",
      "0.10309100151062012 seconds\n"
     ]
    }
   ],
   "source": [
    "from time import sleep, time\n",
    "\n",
    "def add(xy):\n",
    "    sleep(0.1) # you could imagine this is some complicated, slow calculation\n",
    "    return xy[0] + xy[1]\n",
    "\n",
    "t0 = time()\n",
    "print(\"result:\", add((2,3)))\n",
    "t1 = time()\n",
    "print(t1 - t0, \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we add 10 numbers *sequentially* (meaning one-at-a-time -- the opposite of in parallely), it will take 10 times that long (~1 second total).  A loop is one way to perform this task sequentially."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: 11\n",
      "result: 12\n",
      "result: 13\n",
      "result: 14\n",
      "result: 15\n",
      "result: 6\n",
      "result: 4\n",
      "result: 2\n",
      "result: 4\n",
      "result: 7\n",
      "1.032318115234375 seconds\n"
     ]
    }
   ],
   "source": [
    "xy_pairs = [(10,1), (10,2), (10,3), (10,4), (10,5), (3,3), (2,2), (1,1), (1,3), (4,3)]\n",
    "\n",
    "t0 = time()\n",
    "for xy in xy_pairs:\n",
    "    print(\"result:\", add(xy))\n",
    "t1 = time()\n",
    "print(t1 - t0, \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python's `map` function calls a function for us on each input, yielding each result, but it still works sequentially."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: 11\n",
      "result: 12\n",
      "result: 13\n",
      "result: 14\n",
      "result: 15\n",
      "result: 6\n",
      "result: 4\n",
      "result: 2\n",
      "result: 4\n",
      "result: 7\n",
      "1.0275828838348389 seconds\n"
     ]
    }
   ],
   "source": [
    "t0 = time()\n",
    "for result in map(add, xy_pairs):\n",
    "    print(\"result:\", result)\n",
    "t1 = time()\n",
    "print(t1 - t0, \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember that `map` works with function references, something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mymap(func_ref, inputs):\n",
    "    for v in inputs:\n",
    "        result = func_ref(v)\n",
    "        yield result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python's `multiprocessing` module has a `Pool` class.  A pool is a collection of processes.  We can create a pool with a specified number of processes (say 5), then use the pool's version of `map`, which IS parallel (each process does a subset of the work)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: 11\n",
      "result: 12\n",
      "result: 13\n",
      "result: 14\n",
      "result: 15\n",
      "result: 6\n",
      "result: 4\n",
      "result: 2\n",
      "result: 4\n",
      "result: 7\n",
      "0.20520401000976562 seconds\n"
     ]
    }
   ],
   "source": [
    "from multiprocessing import Pool\n",
    "\n",
    "with Pool(5) as p:\n",
    "    t0 = time()\n",
    "    for result in p.map(add, xy_pairs):\n",
    "        print(\"result:\", result)\n",
    "    t1 = time()\n",
    "    print(t1 - t0, \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It looks like using 5 processes made it 5 times faster!  Let's try 10 processes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: 11\n",
      "result: 12\n",
      "result: 13\n",
      "result: 14\n",
      "result: 15\n",
      "result: 6\n",
      "result: 4\n",
      "result: 2\n",
      "result: 4\n",
      "result: 7\n",
      "0.10577178001403809 seconds\n"
     ]
    }
   ],
   "source": [
    "with Pool(10) as p:\n",
    "    t0 = time()\n",
    "    for result in p.map(add, xy_pairs):\n",
    "        print(\"result:\", result)\n",
    "    t1 = time()\n",
    "    print(t1 - t0, \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're getting good speedups as we add more processes as most of the \"work\" is sleeping, and we can do plenty of that with limited cores.  If we need to do actual computation (for example, looping 3 million times), "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: 11\n",
      "result: 12\n",
      "result: 13\n",
      "result: 14\n",
      "result: 15\n",
      "result: 6\n",
      "result: 4\n",
      "result: 2\n",
      "result: 4\n",
      "result: 7\n",
      "0.6721689701080322 seconds (1 process)\n",
      "result: 11\n",
      "result: 12\n",
      "result: 13\n",
      "result: 14\n",
      "result: 15\n",
      "result: 6\n",
      "result: 4\n",
      "result: 2\n",
      "result: 4\n",
      "result: 7\n",
      "0.16287779808044434 seconds (10 process)\n"
     ]
    }
   ],
   "source": [
    "def add(xy):\n",
    "    for i in range(3000000): # 3 million\n",
    "        pass\n",
    "    return xy[0] + xy[1]\n",
    "\n",
    "with Pool(1) as p:\n",
    "    t0 = time()\n",
    "    for result in p.map(add, xy_pairs):\n",
    "        print(\"result:\", result)\n",
    "    t1 = time()\n",
    "    print(t1 - t0, \"seconds (1 process)\")\n",
    "    \n",
    "with Pool(10) as p:\n",
    "    t0 = time()\n",
    "    for result in p.map(add, xy_pairs):\n",
    "        print(\"result:\", result)\n",
    "    t1 = time()\n",
    "    print(t1 - t0, \"seconds (10 process)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The difference between the speed with 1 process vs. 10 processes will depend on the number of cores.  If there is only 1 core, the times are probably the same.  If there are 10 or more cores, the second measurement will probably be ten times faster.  In most cases, it will be somewhere between.\n",
    "\n",
    "Based on the two times above, can you estimate how many core's your instructor's laptop has?\n",
    "\n",
    "## Bugs\n",
    "\n",
    "Using multiple processes for parallelism is tricky because each process has its own variables/state.  It will take care of passing in inputs and returning outputs, but avoid modifying global varialbles.  They'll get modified in the pool processes, but not in the process used for your Jupyter notebook (which is what people making this mistake are usually trying to do)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUB TOTAL SO FAR 3\n",
      "SUB TOTAL SO FAR 2\n",
      "SUB TOTAL SO FAR 12\n",
      "SUB TOTAL SO FAR 3\n"
     ]
    }
   ],
   "source": [
    "total = 0\n",
    "\n",
    "def increment(amt):\n",
    "    global total\n",
    "    total += amt\n",
    "    print(\"SUB TOTAL SO FAR\", total)\n",
    "\n",
    "with Pool(2) as p:\n",
    "    p.map(increment, [3,2,9,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are two processes, each with it's own `total` global variable, so even though they do some counting, they don't see the total of 15.  Worse, the process that made the `map` call (this Jupyter notebook) has yet another `total` global variable, which didn't get modified at all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total"
   ]
  }
 ],
 "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}