03_multiprocessing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multiprocessing\n",
    "\n",
    "The ```multiprocessing``` package has a similar interface to the ```threading``` module but, instead of spawning threads, it spawns processes. These are separate processes in the operating system that have their own memory space. This means that sharing information between processes is more complicated than sharing information between threads. However, it also means that race conditions are less likely and, as each process is independent, the GIL is not a problem. This allows for code to be executed in parallel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spawning Processes\n",
    "\n",
    "The main class is the ```Process``` class. We can create a new instance of this class using ```Process(target=func, args=(arg1, arg2))```. We can then start the process using ```p.start()``` and wait for it to finish using ```p.join()```. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import multiprocessing\n",
    "\n",
    "def greeting(processes_number):\n",
    "    print(f'Hello from process number {processes_number} {__name__}')\n",
    "\n",
    "processes = []\n",
    "\n",
    "print(__name__)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    for i in range(2):\n",
    "        p =multiprocessing.Process(target=greeting, args=(i,))\n",
    "        p.start()\n",
    "        processes.append(p)\n",
    "\n",
    "    for p in processes:\n",
    "        p.join()\n",
    "\n",
    "    print('Main process is done')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Much of this is similar to what you've already done with threads, but there are a few important differences. \n",
    "\n",
    "The first thing to note is the line ```if __name == '__main__':```. This is necessary because, when a new process is spawned, it will run the code from the beginning of the script. This is necessary because the new process has a separate memory space and so needs to run the code again so that the function (in this case ```greetings```) is defined in the new process.\n",
    "\n",
    "To explain this, we need to consider the built in variable ```__name__```. This variable is created automatically when Python is run and will have different names in different circumstances. In the piece of code which is being run directly,it will have the value ```__main__```. In the case of a piece of code which is being run as the main script of a new process it will have the value ```__mp_main__```. You can check the values of ```__name__``` by running [```03_multiprocessing_scripts/print_example.py```](03_multiprocessing_scripts/print_example.py).\n",
    "\n",
    "This means that the line ```if __name__ == '__main__':``` will only be true in the main script and not in any new processes that are spawned. This is important because it means that the code inside this block will only be run in the main script and not in any new processes that are spawned. This prevents each new process from spawning more processes and so creating an infinite loop. We also include the code waiting for the processes to finish and the final call to the ```print``` function in the if-block so they are only run in the main script and not in any new processes that are spawned.\n",
    "\n",
    "If you are running this code on a Codespace, you may not see all of the above behaviour described in the paragraph above. The reason for this is that the Codespace handles its processes slightly differently than the Windows system I wrote the code on. In a Codespace, when the process is spawned the ```def``` sections are performed by each thread but the ```print``` statements are ignored. In fact, in a Codespace, we can remove the `if __name__ == '__main__'` line entirely and the processes will only be spawned from the main process. However, leaving this out would cause the code break when run outside the Codespace, so we'll leave it in this course as its important for writing portable code.\n",
    "\n",
    "When running this code outside of a Codespace, the result of the print statement in ```greetings``` is not displayed under the code cell. This is because it is being run in a separate process and so its output is not captured and displayed by the Jupyter notebook. Within a Codespace, however, it is captured and displayed by the Jupyter notebook.\n",
    "\n",
    "A copy of this code is found in the file [```03_multiprocessing_scripts/print_example.py```](03_multiprocessing_scripts/print_example.py). If you are running this code outside of a Codespace, you can run this code and see that the output of all processes is captured by the terminal and displayed there."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting Values from Processes\n",
    "\n",
    "Just like a thread created with the ```threading``` module, any value returned from a function called in a process will be lost. However, there are a few ways we can communicate between processes. We'll look at ```Pipe```, ```Queue```, ```Value``` and ```Array```."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pipes\n",
    "\n",
    "A pipe is a two-way communication channel between two processes. We can create a pipe using ```Pipe()```. The two ends of the pipe are known as connectors. These can be passed to two processes to allow communication between them. By default, communication is allowed in two directions. We can then use the ```send()``` and ```recv()``` methods of the connectors to send and receive data through the pipe. When the ```recv()``` method is called, the process will wait until data is available to be received.\n",
    "\n",
    "Note that there is a maximum size of data which can be sent through the pipe (this may be around 32MB depending on operating system).\n",
    "\n",
    "The example below shows a simple example using a pipe to communicate between the main process and a child process:\n",
    "\n",
    "```python\n",
    "import multiprocessing\n",
    "import numpy\n",
    "\n",
    "def calculate_sum(conn):\n",
    "    # Wait to receive an array from the parent process\n",
    "    array = conn.recv()\n",
    "    # Calculate the sum of the array\n",
    "    result = numpy.sum(array)\n",
    "    # Send the result back to the parent process\n",
    "    conn.send(result)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a Pipe() object\n",
    "    # This function returns a pair of connection objects connected by a pipe\n",
    "    parent_conn, child_conn = multiprocessing.Pipe()\n",
    "    # Create a process and pass the child connection object to it\n",
    "    # The process will implement the calculate_sum function\n",
    "    p = multiprocessing.Process(target=calculate_sum, args=(child_conn,))\n",
    "    # Start the process\n",
    "    p.start()\n",
    "    # Send an array to the child process\n",
    "    parent_conn.send(numpy.arange(1, 6))\n",
    "    # Receive the result from the child process\n",
    "    print(parent_conn.recv())\n",
    "    # Wait until the process is finished\n",
    "    p.join()\n",
    "    print('Main process is done')\n",
    "```\n",
    "\n",
    "The above code will not work in a Jupyter notebook in all contexts due to incompatibilities between ```multiprocessing``` and Jupyter. However, you can run this code in a Python script and see that the result is printed to the terminal. A copy of this code is found in the file [```03_multiprocessing_scripts/pipe_example.py```](03_multiprocessing_scripts/pipe_example.py) which you can run.\n",
    "\n",
    "In the above code, the parent process creates a pipe and passes one end of the pipe to the child process. The parent process then sends an array to the child process. The child process receives the array, calculates the sum of the array and sends the result back to the parent process. The parent process then receives the result and prints it.\n",
    "\n",
    "This method of communicating requires careful thought regarding the order in which processes will need to communicate with each other to make sure data is sent and received in the correct order. This can be difficult to manage in more complex programs. It can also lead to processes waiting for data from another process, reducing the benefits of parallel execution. Once we have more than one child process, we will need to create a pipe for each pair of processes that need to communicate, further increasing complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deadlocks\n",
    "\n",
    "A deadlock is a situation where two or more processes are waiting for each other before progressing. This can happen in a number of conditions in concurrent programming. One possible cause of deadlocks is when two processes are waiting for each other to send data through a pipe. The following code is an adapted version of the code above but without the call to ```parent_conn.send``` in the main thread:\n",
    "\n",
    "```python\n",
    "import multiprocessing\n",
    "import numpy\n",
    "\n",
    "def calculate_sum(conn):\n",
    "    # Wait to receive an array from the parent process\n",
    "    array = conn.recv()\n",
    "    # Calculate the sum of the array\n",
    "    result = numpy.sum(array)\n",
    "    # Send the result back to the parent process\n",
    "    conn.send(result)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a Pipe() object\n",
    "    # This function returns a pair of connection objects connected by a pipe\n",
    "    parent_conn, child_conn = multiprocessing.Pipe()\n",
    "    # Create a process and pass the child connection object to it\n",
    "    # The process will implement the calculate_sum function\n",
    "    p = multiprocessing.Process(target=calculate_sum, args=(child_conn,))\n",
    "    # Start the process\n",
    "    p.start()\n",
    "    # Receive the result from the child process\n",
    "    print(parent_conn.recv())\n",
    "    # Wait until the process is finished\n",
    "    p.join()\n",
    "    print('Main process is done')\n",
    "```\n",
    "\n",
    "This code can be run in the file [`03_multiprocessing_scripts/deadlock_example.py`](03_multiprocessing_scripts/deadlock_example.py). You will see that the code hangs and does not finish. This is because the parent process is waiting for the child process to send data through the pipe and the child process is waiting for the parent process to send data through the pipe. This is a deadlock. Care should be taken to avoid situations like this in concurrent programming."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queues\n",
    "\n",
    "A queue is a datatype which allows for communication between many processes. We can create a queue using ```multiprocessing.Queue()```. We can then use the ```put()``` and ```get()``` methods to add and remove items from the queue. The data will be stored in a First In First Out (FIFO) order. The example below shows a simple example of how data is added to and removed from a queue using only the main process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "import multiprocessing\n",
    "\n",
    "queue = multiprocessing.Queue()\n",
    "\n",
    "queue.put(1)\n",
    "queue.put(2)\n",
    "queue.put(3)\n",
    "\n",
    "print(queue.get())\n",
    "print(queue.get())\n",
    "print(queue.get())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A queue may be passed to multiple different processes and each processes with access to the ```Queue``` can add data to the queue or retrieve data from it. If many processes may add data to a ```Queue``` at the same time, the exact order in which they add data is not guaranteed as the order of execution across different processes is not guaranteed. This limits the way in which a ```Queue``` can be used as it may not be clear which process a piece of data is from. \n",
    "\n",
    "When the ```get``` method is called, the execution of the code will block (meaning \"wait\") until data is available in the queue. This means we don't need to worry about if the computations required to put data in the queue have been completed when we call the ```get``` method. However, we do need to make sure the same amount of data is added to the queue as is removed from it. If we try to remove more data from the queue than will be added to it, the code will block indefinitely.\n",
    "\n",
    "The queue is thread and process safe, meaning that it can be used to communicate between many processes without the need for locks. The example below shows how we can use a ```Queue``` to collect the results from an arbitrary number of processes:\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "import multiprocessing\n",
    "import time\n",
    "\n",
    "# Note the start time\n",
    "start_time = time.time()\n",
    "\n",
    "def find_smallest_multiple(n_data, factor, queue):\n",
    "    # This function generates n_data random integers and finds the smallest multiple of factor\n",
    "\n",
    "    # Initially we have found no multiples of factor\n",
    "    result = None\n",
    "\n",
    "    # Create the random data\n",
    "    data = np.random.randint(1, 1000, n_data)\n",
    "\n",
    "    for d in data:\n",
    "        # Loop over the data and check if it's a multiple of factor\n",
    "        if d % factor == 0:\n",
    "            # If it is, check if it's the smallest we've found so far\n",
    "            if result is None or d < result:\n",
    "                # Update the result\n",
    "                result = d\n",
    "\n",
    "    # After considering each value, put the result in the queue\n",
    "    queue.put(result)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Set up the problem data\n",
    "    n_processes = 2\n",
    "    n_data = int(1e6)\n",
    "    factor = 7\n",
    "    n_data_per_process = n_data // n_processes\n",
    "\n",
    "    # Set up the queue\n",
    "    queue = multiprocessing.Queue()\n",
    "\n",
    "    for i in range(n_processes):\n",
    "        # Spawn and start the processes\n",
    "        p = multiprocessing.Process(target=find_smallest_multiple, args=(n_data_per_process, factor, queue))\n",
    "        p.start()\n",
    "\n",
    "    # We haven't found any multiples of factor yet\n",
    "    result = None\n",
    "\n",
    "    for i in range(n_processes):\n",
    "        # Get each result from the queue\n",
    "        # The code will pause here while the main process waits for each child process to finish\n",
    "        r = queue.get()\n",
    "\n",
    "        if result is None or r < result:\n",
    "            # If it's smaller than the current result, update it\n",
    "            result = r\n",
    "\n",
    "    # Note the end time and print the elapsed time\n",
    "    end_time = time.time()\n",
    "    print(f'Time taken: {end_time - start_time}')\n",
    "\n",
    "    print(f'The smallest multiple of {factor} in the data is {result}')\n",
    "```\n",
    "\n",
    "This code can be run in the file [```03_multiprocessing_scripts/queue_example.py```](03_multiprocessing_scripts/queue_example.py). In the main process we create a ```Queue``` object and pass it to each of the child processes. Each child process calculates the smallest multiple of a given factor in a subset of the data and adds the result to the ```Queue```. \n",
    "\n",
    "The main process collects the same number of bits of data from the ```Queue``` as there are child processes. Initially, the processes won't have completed their calculations and added them to the ```Queue``` so the main process will block until the data is available. As the result from each thread is added to the ```Queue```, the main process will collect the data and process it. This sort of process is particularly well suited to a ```Queue``` as the order in which the data is added to the ```Queue``` is not important. We don't need to wait for the processes to finish as the ```queue.get()``` method will automatically block until data is available. As a result, we also don't need to create a list of the processes.\n",
    "\n",
    "We can observe the performance of the code by changing the number of processes and the size of the data:\n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"resources/queue_smallest_factor.png\" alt=\"A figure showing the runtime for different numbers of processes as a function of n_data\" class=\"center\">\n",
    "</p>\n",
    "\n",
    "When we completely remove the multiprocessing and run the code in a single process, we can see that the runtime is much less for low values of ```n_data```. This is because spawning processes takes some time, slowing down the code. However, as the size of ```n_data``` increases, this overhead becomes less significant and at around 100,000,0000 data points, the performance of the multiprocessing code equals that of the serial implementation. For 10,000,000,000 pieces of data, the multiprocessing implementation with both 4 and 8 courses is around 4 times faster than the serial implementation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Monte Carlo Pi\n",
    "\n",
    "The value of $\\pi$ can be estimated using a Monte Carlo method. This involves generating a large number of random points in a square and counting the number of points that fall within a circle inscribed in the square. The ratio of the number of points in the circle to the total number of points is an estimate of the ratio of the area of the circle to the area of the square. This ratio is equal to $\\frac{\\pi}{4}$. By multiplying this ratio by 4, we can estimate the value of $\\pi$. \n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"resources/monte_carlo_circle.png\" alt=\"A circle with a radius inside a square with side length 2r\" class=\"center\">\n",
    "</p>\n",
    "\n",
    "In the diagram above, the circle has an area of $\\pi r^2$ and the square has an area of $(2r)^2 = 4r^2$. The ratio of the area of the circle to the area of the square is $\\frac{\\pi r^2}{4r^2} = \\frac{\\pi}{4}$. This means that the ratio of the number of points in the circle to the total number of points is also $\\frac{\\pi}{4}$. When performing this calculation, it is convenient to use a circle with a radius of 1, so that the area of the circle is $\\pi$ and the area of the square is 4. A non-concurrent implementation of this method is shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The value of pi is approximately 3.1416268\n",
      "Time taken: 3.0846166610717773\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import time\n",
    "\n",
    "# Note the starting time\n",
    "start_time = time.time()\n",
    "\n",
    "# Number of points to generate\n",
    "n_points = int(1e7)\n",
    "\n",
    "# Counter for the number of points inside the circle\n",
    "n_inside = 0\n",
    "\n",
    "for i in range(n_points):\n",
    "    # Generate a random point in the unit square\n",
    "    # random.random generates a random number between 0 and 1\n",
    "    x = random.random()\n",
    "    y = random.random()\n",
    "\n",
    "    if x ** 2 + y ** 2 <= 1:\n",
    "        # If the point is inside the circle, increment the counter\n",
    "        n_inside += 1\n",
    "\n",
    "# Calculate the approximate value of pi\n",
    "pi_approximation = 4 * n_inside / n_points\n",
    "\n",
    "print(f'The value of pi is approximately {pi_approximation}')\n",
    "\n",
    "print(f'Time taken: {time.time() - start_time}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To do this, we need to generate a large number of random points and count how many fall within the circle. We can split this task between multiple processes to speed up the calculation. Create a new `.py` file and adapt the code to use multiple processes. Reminder: if you want to use more than 2 processes, you will need to [increase the number of cores the Codespace is using](https://docs.github.com/en/codespaces/customizing-your-codespace/changing-the-machine-type-for-your-codespace).\n",
    "\n",
    "A sample solution can be found in the file [`sample_soluitons/monte_carlo_pi.py`](sample_solutions/monte_carlo_pi.py)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Values\n",
    "\n",
    "The ```multiprocessing``` module also provides a way to share data between processes using the ```Value``` class. This class create a variable which references the same location in our computer's memory for each process. This means that changes to the variable in one process will be reflected in all other processes.\n",
    "\n",
    "The data stored in ```Value```  will be in the form of a ```ctype``` object. This is a C-style data type which is used to store data in memory. The C family of languages underpins much of Python and other languages and this is why it is used here. When we create a ```Value``` object, we need to specify the type of data we want to store. We may import the different objects types from the ```ctype``` module (which is part of the Python Standard Library). The most common types are:\n",
    "\n",
    "- ```ctype.c_int```: A 32-bit integer\n",
    "- ```ctype.c_double```: A double precision floating point number\n",
    "- ```ctype.c_bool```: A boolean value\n",
    "\n",
    "We can retrieve and set the value of a ```Value``` object using its ```value``` attribute. The example below shows how we can create a shared ```Value``` object and increment it in a child process:\n",
    "\n",
    "```python\n",
    "import multiprocessing\n",
    "import ctypes\n",
    "\n",
    "# Create a shared memory value\n",
    "# It is an integer with an initial value of 0\n",
    "v = multiprocessing.Value(ctypes.c_int, 0)\n",
    "\n",
    "def increment(v):\n",
    "    v.value += 1\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a process that increments the value\n",
    "    p = multiprocessing.Process(target=increment, args=(v,))\n",
    "    p.start()\n",
    "    p.join()\n",
    "\n",
    "    # Print the value\n",
    "    print(v.value)\n",
    "\n",
    "```\n",
    "\n",
    "This code can be run in the file [```03_multiprocessing_scripts/value_example.py```](03_multiprocessing_scripts/value_example.py). \n",
    "\n",
    "As the data in a ```Value``` is shared between processes, it would now be possible to encounter race conditions as we did with threads. However, the ```Value``` class has a built in lock which we can access with the ```get_lock``` method and use to prevent this. We can use the ```acquire()``` and ```release()``` methods of the lock to acquire and release the lock, as below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "import multiprocessing\n",
    "import ctypes\n",
    "\n",
    "# Create a shared memory value\n",
    "# It is an integer with an initial value of 0\n",
    "v = multiprocessing.Value(ctypes.c_int, 0)\n",
    "\n",
    "# Get the lock\n",
    "v.get_lock().acquire()\n",
    "# Do our calculations altering the value\n",
    "v.value += 1\n",
    "# Release the lock\n",
    "v.get_lock().release()\n",
    "\n",
    "print(v.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also use a context manager to acquire and release the lock. The example below shows how we can use the lock:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "import multiprocessing\n",
    "import ctypes\n",
    "\n",
    "# Create a shared memory value\n",
    "# It is an integer with an initial value of 0\n",
    "v = multiprocessing.Value(ctypes.c_int, 0)\n",
    "\n",
    "with v.get_lock():\n",
    "    # Perform our calculations altering the value in the indented code\n",
    "    v.value += 1\n",
    "\n",
    "print(v.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a more Pythonic way of managing locks and is less error-prone, as we cannot forget to release the lock.\n",
    "\n",
    "The example below shows how we can use both types of locks to increment a ```Value``` object safely across multiple processes:\n",
    "\n",
    "```python\n",
    "import multiprocessing\n",
    "import ctypes\n",
    "\n",
    "def increment(v):\n",
    "    # Manually acquire and release the lock\n",
    "    v.get_lock().acquire()\n",
    "    v.value += 1\n",
    "    v.get_lock().release()\n",
    "\n",
    "    # Use the context manager to acquire and release the lock\n",
    "    with v.get_lock():\n",
    "        v.value += 100\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a shared memory value\n",
    "    # It is an integer with an initial value of 0\n",
    "    v = multiprocessing.Value(ctypes.c_int, 0)\n",
    "\n",
    "    # Create n_process processes which increment the value\n",
    "    n_process = 8\n",
    "    processes = []\n",
    "    for i in range(n_process):\n",
    "        p = multiprocessing.Process(target=increment, args=(v,))\n",
    "        p.start()\n",
    "        processes.append(p)\n",
    "\n",
    "    for i in range(n_process):\n",
    "        p.join()\n",
    "\n",
    "    # Print the value\n",
    "    print(v.value)\n",
    "```\n",
    "\n",
    "This code can be run in the file [```03_multiprocessing_scripts/value_lock_example.py```](03_multiprocessing_scripts/value_lock_example.py)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Arrays\n",
    "\n",
    "The ```Array``` class of the ```multiprocessing``` module is similar to the ```Value``` class but allows us to store more than one value in a shared memory location. We can create an ```Array``` object using ```multiprocessing.Array()```. We need to specify the type of data we want to store and the size of the array. We can use the same ```ctype``` objects as we did with the ```Value``` class, and we set the initial values using a tuple of values, as below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n",
      "[0.0, 7.0, 0.0, 0.0, 0.0]\n",
      "0.0\n",
      "7.0\n",
      "0.0\n",
      "0.0\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "import multiprocessing\n",
    "import ctypes\n",
    "\n",
    "# Create a shared memory array\n",
    "# It is an array of 5 floats with an initial value of 0\n",
    "a = multiprocessing.Array(ctypes.c_double, (0, 0, 0, 0, 0))\n",
    "\n",
    "# We can access a single value from the array using an index\n",
    "print(a[1])\n",
    "\n",
    "# We can modify a single value in the array using an index\n",
    "a[1] = 7\n",
    "\n",
    "# We access every value in the array using ':' as an index\n",
    "print(a[:])\n",
    "\n",
    "# We can iterate over the array\n",
    "for x in a:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the example above, we also saw how we can access and modify data in the array. Note that an array cannot be extended or shortened once it has been created.\n",
    "\n",
    "It's also possible to create an array by specifying its type and the number of entries as an integer. If we do this, each value will be initially set to zero. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]\n"
     ]
    }
   ],
   "source": [
    "import multiprocessing\n",
    "import ctypes\n",
    "\n",
    "# Create an array with 10 floating point zeros\n",
    "array = multiprocessing.Array(ctypes.c_double, 10)\n",
    "\n",
    "print(array[:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An ```array``` has a lock in a similar way to a ```Value```.\n",
    "\n",
    "The code below shows how we can create an array which keeps track of the number of times each number has been rolled on a six-sided dice:\n",
    "\n",
    "```python\n",
    "import multiprocessing\n",
    "import ctypes\n",
    "import random\n",
    "\n",
    "def roll_n_dice(n, array):\n",
    "    local_results = [0, 0, 0, 0, 0, 0]\n",
    "    for i in range(n):\n",
    "        current_roll = random.randint(1, 6)\n",
    "        local_results[current_roll - 1] += 1\n",
    "\n",
    "    with array.get_lock():\n",
    "        for i in range(6):\n",
    "            array[i] += local_results[i]\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a shared memory array\n",
    "    # It is an array of 6 floats with an initial value of 0\n",
    "    a = multiprocessing.Array(ctypes.c_int, 6)\n",
    "\n",
    "    n_rolls_total = int(1e6)\n",
    "\n",
    "    # Create n_process processes\n",
    "    n_process = 4\n",
    "    processes = []\n",
    "    for i in range(n_process):\n",
    "        p = multiprocessing.Process(target=roll_n_dice, args=(n_rolls_total // n_process, a))\n",
    "        processes.append(p)\n",
    "        p.start()\n",
    "\n",
    "    # Wait for all processes to finish\n",
    "    for p in processes:\n",
    "        p.join()\n",
    "\n",
    "    # Print the results\n",
    "    print(f'Results after {n_rolls_total} rolls: {list(a[:])}')\n",
    "```\n",
    "\n",
    "This code can be run in the file [```03_multiprocessing_scripts/array_example.py```](03_multiprocessing_scripts/array_example.py).\n",
    "\n",
    "In the example above, the results are summed up each process independently and then added to the shared array. This means each process only needs access to the shared array for a short amount of time, meaning most of the code in each process can be run in parallel. This is a good way to structure code when using shared memory as it means each process will not spend much time waiting for other processes to release the lock on the shared array.\n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"resources/array_dice_rolls.png\" alt=\"A figure showing the runtime for different numbers of processes as a function of n_data\" class=\"center\">\n",
    "</p>\n",
    "\n",
    "As we can see above, the use of `multiprocessing` adds an overhead to the code, causing the calculation to take longer for small numbers of dice rolls compared to the serial implementation. This overhead is the creation and management of the processes. However, as the number of dice rolls increases, the performance of the multiprocessing implementation improves and above about 10,000,000 rolls the `multiprocessing` implementation using 8 processes is around 3.5 times faster than the serial implementation.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Projectile Ranges\n",
    "\n",
    "In this exercise we'll consider a projectile which is launched. However, there is some imprecision relating to the angle and the speed it is launched at. Your job is quantify the resulting uncertainty in the range of the projectile. The physics is very simplified, with no air resistance. The projectile is flying over a flat surface. The range of both angles and speeds will be uniformly distributed.\n",
    "\n",
    "The distribution of ranges is calculated by randomly sampling from the distributions of angles and speeds and calculating the range for each combination of angle and speed. The number of samples which produced a range in a number of bins is counted.\n",
    "\n",
    "A non-concurrent version of the code is written in the file [`03_multiprocessing_scripts/projectile_exercises.py`](03_multiprocessing_scripts/projectile_exercise.py). Your task is to parallelise this code using the `multiprocessing` module. You should create a new copy of the file and adapt the code to use multiple processes. You should not need to modify the function `calculate_range`, but you will need to modify `calculate_range_distribution` and the code outside of the functions. You may create other functions if you wish. Do not feel obliged to keep the same interface to the functions as the original code. So long as the number of samples in each bin is printed at the end of the code, you can structure the code as you wish. As the angle and speed are generated randomly for each sample, the results will not be exactly the same each time the code is run, but you should check they are similar to the original code.\n",
    "\n",
    "Once you have rewritten the code to use multiple processes, you can compare the performance of the code for different numbers of processes and samples.\n",
    "\n",
    "Reminder: if you want to use more than 2 processes, you will need to [increase the number of cores the Codespace is using](https://docs.github.com/en/codespaces/customizing-your-codespace/changing-the-machine-type-for-your-codespace). There is a sample solution in the file [`sample_solutions/projectile.py`](sample_solutions/projectile.py)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pools\n",
    "\n",
    "A `Pool` is class from the `multiprocessing` module which can make it easy to distribute work across a number of processes. We can create a `Pool` object using `multiprocessing.Pool()`, providing an argument specifying the number of processes to create. We can then use the `map` method of the `Pool` object to apply a function to a list of arguments. The `map` method will distribute the arguments across the processes in the `Pool` and return the results returned by the function in a list in the same order as the arguments. The `map` method will block until all the processes have finished.\n",
    "\n",
    "```python\n",
    "from multiprocessing import Pool, current_process\n",
    "import time\n",
    "import random\n",
    "\n",
    "# This is the function we want to apply to each entry in the list\n",
    "def f(x):\n",
    "    # multiprocessing.current_process().name is a way to get the name of the process\n",
    "    print(f'Process {current_process().name} is working on the value {x}')\n",
    "    # Wait for a random amount of time between 0 and 1 seconds\n",
    "    time.sleep(random.uniform(0, 1))\n",
    "    # Perform a simple calculation and return the result\n",
    "    return x * x\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a list of values to apply the function to\n",
    "    data = list(range(10))\n",
    "    print(data)\n",
    "\n",
    "    # Create a Pool object with 4 processes\n",
    "    # The Pool will be discarded when the block is exited\n",
    "    with Pool(4) as p:\n",
    "        # Apply the function f to each entry in the list\n",
    "        output = p.map(f, data)\n",
    "\n",
    "    # Print the output\n",
    "    print(output)\n",
    "```\n",
    "\n",
    "The code above can be found and run in [```03_multiprocessing_scripts/map_example.py```](03_multiprocessing_scripts/map_example.py). The code will create a `Pool` object with 4 processes and apply the function `f` to each entry in the list.\n",
    "\n",
    "The random wait time represents how different calculations in different processes may take different amounts of time to execute, which is common in parallel programming. As each process finishes working on one value, it will receive a new one to work on, meaning it's not possible to predict in advance which process will work on which value and that each process may work on a different number of values. However, regardless of which process worked on which input value, the results will be returned in a list in the same order as the input list.\n",
    "\n",
    "The `starmap` method is similar to the `map` method but allows us to pass arguments multiple arguments to a function by receiving a collection of collections with each inner collection containing the arguments for one call to the function.\n",
    "\n",
    "```python\n",
    "from multiprocessing import Pool, current_process\n",
    "import time\n",
    "import random\n",
    "\n",
    "# This is the function we want to apply to pairs of values in a list\n",
    "def g(x, y):\n",
    "    print(f'Process {current_process().name} is working on the values {x} and {y}')\n",
    "    # Wait a random time between 0 and 1 seconds\n",
    "    time.sleep(random.uniform(0, 1))\n",
    "    # Perform a simple calculation and return the result\n",
    "    return x * y\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # Create a list of values to apply the function to\n",
    "    data = [(i, i+1) for i in range(10)]\n",
    "    print(data)\n",
    "\n",
    "    # Create a Pool object with 4 processes\n",
    "    # The Pool will be discarded when the block is exited\n",
    "    with Pool(4) as p:\n",
    "        # Apply the function g to each set of arguments in a list\n",
    "        output = p.starmap(g, data)\n",
    "\n",
    "    # Print the output\n",
    "    print(output)\n",
    "```\n",
    "\n",
    "The code above can be found and run in [```03_multiprocessing_scripts/starmap_example.py```](03_multiprocessing_scripts/starmap_example.py). The code will create a `Pool` object with 4 processes and apply the function `g` to each pair of values in the list.\n",
    "\n",
    "A `Pool` can be a simple an convenient way to distribute independent calculations across multiple processes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Approximating The Sine Function\n",
    "\n",
    "In maths, the sine function can be approximated using the Taylor series:\n",
    "\n",
    "$$\n",
    "\\sin(x) = \\sum_{k=0}^{\\infty}\\frac{(-1)^{k}x^{2k + 1}}{(2k + 1)!} =x - \\frac{x^3}{3!} + \\frac{x^5}{5!} - \\frac{x^7}{7!} + \\ldots\n",
    "$$\n",
    "\n",
    "where $n!$ is the factorial of $n$ (you can use `math.factorial` to calculate this). The approximation will completely accurate if we include infinitely many terms, but we can get a good approximation for a small value of $x$ by including only a few terms.\n",
    "\n",
    "Your task is to write a function which receives two arguments and calculates the approximation of the sine function. The first argument is the value of $x$ and the second argument is the number of terms to include in the approximation. For instance, if first argument is 0.5 and the second is 3, the function should calculate the approximation:\n",
    "\n",
    "$$\n",
    "\\sin(0.5) \\approx 0.5 - \\frac{0.5^3}{3!} + \\frac{0.5^5}{5!}\n",
    "$$\n",
    "\n",
    "In this case, the precise value of $\\sin(0.5)$ is 0.4794255 and the approximation with 3 terms is 0.4794270.\n",
    "\n",
    "Your function should split up the calculation of each term in the approximation across 2 processes using a `Pool`. You should create a new file and write the code to do this. You may structure the code as you wish, but you should print the result of the approximation at the end of the code. Once you have written your code, test it with a few examples.\n",
    "\n",
    "There is a sample solution in the file [`sample_solutions/sine_approximation.py`](sample_solutions/sine_approximation.py)."
   ]
  }
 ],
 "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.11.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}