2-A-Reduction-Tale.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A Reduction Tale"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Objectives:\n",
    "> * Compare operations taking place in different data containers\n",
    "> * Compare sizes for these data containers\n",
    "> * Help deciding when it is best to use a container or another"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's suppose that we are going to need reductions a lot and we want to choose the best container for performing them.  First, let's start by activating our MemWatcher agent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [1] used 0.031 MiB RAM in 0.002s, peaked 0.000 MiB above current, total RAM usage 34.965 MiB\n"
     ]
    }
   ],
   "source": [
    "from ipython_memwatcher import MemWatcher\n",
    "mw = MemWatcher()\n",
    "mw.start_watching_memory()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and choose a different container for the data that we want to reduce, starting with a list:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regular lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [2] used 545.145 MiB RAM in 8.569s, peaked 70.184 MiB above current, total RAM usage 580.109 MiB\n"
     ]
    }
   ],
   "source": [
    "a = [float(i) for i in range(10*1000*1000)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, proceed with a simple reduction (sum):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 231 ms per loop\n",
      "In [3] used 0.062 MiB RAM in 0.957s, peaked 0.000 MiB above current, total RAM usage 580.172 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o sum(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which, in MFLOPS (Mega-FloatingPointOps-Per-Second) is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('MFLOPS:', 43.3)\n",
      "In [4] used 0.008 MiB RAM in 0.003s, peaked 0.000 MiB above current, total RAM usage 580.180 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"MFLOPS:\", round((len(a) / t.best / 1e6), 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, so that seems fast, but we don't have other references to compare with.  In addition, a list is not the best kind of container in terms of space consumption.  So let's try now a container that seems quite optimal in terms of memory savings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## NumPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [10] used 0.000 MiB RAM in 0.003s, peaked 0.000 MiB above current, total RAM usage 672.172 MiB\n"
     ]
    }
   ],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [11] used 0.000 MiB RAM in 1.102s, peaked 0.000 MiB above current, total RAM usage 672.172 MiB\n"
     ]
    }
   ],
   "source": [
    "na = np.array(a, dtype=np.float64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('SIZE:', 76.294)\n",
      "In [7] used 0.004 MiB RAM in 0.004s, peaked 0.000 MiB above current, total RAM usage 672.148 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"SIZE:\", round((na.size * na.itemsize) / 2**20., 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that, with 8 bytes/element, NumPy is a very efficient container."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 3.52 s per loop\n",
      "In [8] used 0.020 MiB RAM in 14.138s, peaked 0.000 MiB above current, total RAM usage 672.168 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o sum(na)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('MFLOPS:', 2.842)\n",
      "In [9] used 0.004 MiB RAM in 0.005s, peaked 0.000 MiB above current, total RAM usage 672.172 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"MFLOPS:\", round(len(a) / t.best / 1e6, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The performance for NumPy is several times slower than the computation with the list.  Why so?\n",
    "\n",
    "*Hint: * We are using sum() which is a Python function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NumPy has a lot of overhead in producing a Python integer for every element in the array for feeding it to the sum().\n",
    "\n",
    "*Hint:* Use internal NumPy methods (ufuncs) when possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 19 ms per loop\n",
      "In [12] used 0.086 MiB RAM in 0.812s, peaked 0.000 MiB above current, total RAM usage 672.258 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o na.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('FLOPS:', 525.329)\n",
      "In [13] used 0.004 MiB RAM in 0.004s, peaked 0.000 MiB above current, total RAM usage 672.262 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"FLOPS:\", round(len(a) / t.best / 1e6, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is about 100x the speed of sum() on a Python list and it is also pretty optimal in terms of both execution time and space consumed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "The speed in the above reduction is limited by memory speed, not CPU speed.  Could you provide a hint on the maximum memory speed that supports your laptop?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.914004621656657"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [14] used 0.090 MiB RAM in 0.049s, peaked 0.000 MiB above current, total RAM usage 672.352 MiB\n"
     ]
    }
   ],
   "source": [
    "# This is an easy one.  Just divide the size of the dataset by the time that takes the reduction\n",
    "(na.size * na.itemsize) / t.best / 2**30"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, in this case the memory bandwidth is close to 10 GB/s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using compressed in-memory containers with bcolz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But let us suppose that we have really big data to process in our laptop and want to see if we can store our data in less space.  Enter compression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n",
      "bcolz version:     1.0.0rc2\n",
      "NumPy version:     1.10.4\n",
      "Blosc version:     1.8.0 ($Date:: 2016-03-31 #$)\n",
      "Blosc compressors: ['blosclz', 'lz4', 'lz4hc', 'snappy', 'zlib']\n",
      "Numexpr version:   2.5.1\n",
      "Python version:    2.7.11 |Continuum Analytics, Inc.| (default, Dec  6 2015, 18:08:32) \n",
      "[GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]\n",
      "Platform:          linux2-x86_64\n",
      "Byte-ordering:     little\n",
      "Detected cores:    4\n",
      "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [15] used 22.062 MiB RAM in 1.776s, peaked 0.000 MiB above current, total RAM usage 694.414 MiB\n"
     ]
    }
   ],
   "source": [
    "import bcolz\n",
    "bcolz.print_versions()\n",
    "bcolz.defaults.cparams['cname'] = 'blosclz'\n",
    "bcolz.defaults.cparams['clevel'] = 9\n",
    "bcolz.defaults.cparams['shuffle'] = bcolz.SHUFFLE\n",
    "bcolz.set_nthreads(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [16] used 0.309 MiB RAM in 0.103s, peaked 0.000 MiB above current, total RAM usage 694.723 MiB\n"
     ]
    }
   ],
   "source": [
    "ca = bcolz.carray(na)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('mem_used:', 0.30859375)\n",
      "In [17] used 0.008 MiB RAM in 0.004s, peaked 0.000 MiB above current, total RAM usage 694.730 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"mem_used:\", mw.measurements.memory_delta)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, this time the amount of memory used seems much lower.  Also, bcolz containers can provide an estimation on how much memory they are taking; let's have a look:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "carray((10000000,), float64)\n",
       "  nbytes: 76.29 MB; cbytes: 1.01 MB; ratio: 75.31\n",
       "  cparams := cparams(clevel=9, shuffle=1, cname='blosclz')\n",
       "[  0.00000000e+00   1.00000000e+00   2.00000000e+00 ...,   9.99999700e+06\n",
       "   9.99999800e+06   9.99999900e+06]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [18] used 0.016 MiB RAM in 0.016s, peaked 0.000 MiB above current, total RAM usage 694.746 MiB\n"
     ]
    }
   ],
   "source": [
    "ca"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case we see that bcolz estimation is reasonably close to `ipython_memwatcher` measurements.  Let's have a look at the speed of the reduction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 79.8 ms per loop\n",
      "('MFLOPS:', 125.344)\n",
      "In [19] used 0.020 MiB RAM in 3.307s, peaked 0.000 MiB above current, total RAM usage 694.766 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o ca.sum()\n",
    "print(\"MFLOPS:\", round(len(a) / t.best / 1e6, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is around 2~5x slower (depending on the machine) than a regular NumPy array, but the size of the array is an impressive 75x smaller.  But is compression the only responsible of the overhead?  Let's investigate a bit further."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using uncompressed containers with bcolz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "In order to see if this is because of the compression overhead, let's use an uncompressed array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [20] used 0.039 MiB RAM in 1.154s, peaked 0.000 MiB above current, total RAM usage 694.805 MiB\n"
     ]
    }
   ],
   "source": [
    "cau = bcolz.carray(a, cparams=bcolz.cparams(clevel=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "carray((10000000,), float64)\n",
       "  nbytes: 76.29 MB; cbytes: 76.52 MB; ratio: 1.00\n",
       "  cparams := cparams(clevel=0, shuffle=1, cname='blosclz')\n",
       "[  0.00000000e+00   1.00000000e+00   2.00000000e+00 ...,   9.99999700e+06\n",
       "   9.99999800e+06   9.99999900e+06]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [21] used 0.004 MiB RAM in 0.011s, peaked 0.000 MiB above current, total RAM usage 694.809 MiB\n"
     ]
    }
   ],
   "source": [
    "cau"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 52 ms per loop\n",
      "('MFLOPS:', 192.383)\n",
      "In [22] used 0.008 MiB RAM in 2.206s, peaked 0.000 MiB above current, total RAM usage 694.816 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o cau.sum()\n",
    "print(\"MFLOPS:\", round(len(a) / t.best / 1e6, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the times with an uncompressed `carray` are very close to a compressed one, so compressing is not the only source of the overhead (and it is very minor in fact).  The actual source of the difference is the memory layout of the different containers (bcolz layout is a bit more complex than NumPy).\n",
    "\n",
    "So, bcolz allows to use compressed in-memory data containers at the cost of some performance (compared with NumPy).  But the performance overhead is rather small, and sometimes you prefer to keep more data in-memory.\n",
    "\n",
    "On another hand, in the next notebooks we are going to see that bcolz can be pretty close to NumPy, performance wise, in some scenarios."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}