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.020 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 30.113 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
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [2] used 54.469 MiB RAM in 0.180s, peaked 0.000 MiB above current, total RAM usage 84.582 MiB\n"
     ]
    }
   ],
   "source": [
    "a = [float(i) for i in range(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": [
      "100 loops, best of 3: 6.13 ms per loop\n",
      "In [3] used 0.059 MiB RAM in 2.548s, peaked 0.000 MiB above current, total RAM usage 84.641 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:', 163.1)\n",
      "In [4] used 0.016 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 84.656 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"MFLOPS:\", round((1e6 / 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": [
    "## Containers using the array module in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [5] used 0.004 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 84.660 MiB\n"
     ]
    }
   ],
   "source": [
    "# Create an array of 'd'oubles\n",
    "import array\n",
    "%load_ext memory_profiler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "peak memory: 84.86 MiB, increment: 0.19 MiB\n",
      "In [6] used 0.199 MiB RAM in 0.237s, peaked 0.000 MiB above current, total RAM usage 84.859 MiB\n"
     ]
    }
   ],
   "source": [
    "%memit arr = array.array('d', a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7.7 ~ 15 MB vs 31 MB seems like a good deal, although sometimes Python is allocating more memory than necessary.  In fact, the array module seems to provide optimal containers from a memory consumption point of view:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.208896"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [7] used 0.059 MiB RAM in 0.006s, peaked 0.000 MiB above current, total RAM usage 84.918 MiB\n"
     ]
    }
   ],
   "source": [
    "# Size per element:\n",
    "(mw.memory_delta * 2**20) / 1e6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But how it performs during reductions?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 8.09 ms per loop\n",
      "In [8] used 0.012 MiB RAM in 3.346s, peaked 0.000 MiB above current, total RAM usage 84.930 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('MFLOPS:', 123.6)\n",
      "In [9] used 0.008 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 84.938 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"MFLOPS:\", round(1e6 / t.best / 1e6, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, that's a bit disappointing, as the array object performs about 2x slower than a regular list.  Not sure about the resons, but probably the array module is not getting too much attention performance-wise mainly because the NumPy existance.  Speaking of NumPy: here we go!"
   ]
  },
  {
   "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 4.648 MiB RAM in 0.039s, peaked 0.000 MiB above current, total RAM usage 89.586 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.043 MiB RAM in 0.028s, peaked 0.000 MiB above current, total RAM usage 89.629 MiB\n"
     ]
    }
   ],
   "source": [
    "na = np.array(a, dtype=np.float64)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that, with 8 bytes/element, NumPy is also an efficient container (much more than the `array` package in standard library which takes ~16 bytes/element)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 71.6 ms per loop\n",
      "In [12] used 0.020 MiB RAM in 2.933s, peaked 0.000 MiB above current, total RAM usage 89.648 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o sum(na)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('MFLOPS:', 13.964)\n",
      "In [13] used 0.004 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 89.652 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"MFLOPS:\", round(1e6 / t.best / 1e6, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oops, this is more than several times slower than the `array` module.  Why so?\n",
    "\n",
    "**Answer:** NumPy has a lot of overhead in producing a Python integer for every element in the array.\n",
    "\n",
    "*Hint:* Use internal methods (ufuncs) when possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 426 µs per loop\n",
      "In [14] used 0.250 MiB RAM in 1.767s, peaked 0.000 MiB above current, total RAM usage 89.902 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o na.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('FLOPS:', 2345.387)\n",
      "In [15] used 0.000 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 89.902 MiB\n"
     ]
    }
   ],
   "source": [
    "print(\"FLOPS:\", round(1e6 / 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": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17.47449143638083"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [16] used 0.000 MiB RAM in 0.004s, peaked 0.000 MiB above current, total RAM usage 89.902 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 18 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": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n",
      "bcolz version:     0.12.1.dev2\n",
      "NumPy version:     1.10.1\n",
      "Blosc version:     1.4.1 ($Date:: 2014-07-08 #$)\n",
      "Blosc compressors: ['blosclz', 'lz4', 'lz4hc', 'snappy', 'zlib']\n",
      "Numexpr version:   2.4.4\n",
      "Python version:    2.7.10 |Continuum Analytics, Inc.| (default, Oct 19 2015, 18:04:42) \n",
      "[GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]\n",
      "Platform:          linux2-x86_64\n",
      "Byte-ordering:     little\n",
      "Detected cores:    8\n",
      "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [17] used 24.461 MiB RAM in 0.129s, peaked 0.000 MiB above current, total RAM usage 114.363 MiB\n"
     ]
    }
   ],
   "source": [
    "import bcolz\n",
    "bcolz.print_versions()\n",
    "bcolz.defaults.cparams['cname'] = 'blosclz'\n",
    "bcolz.defaults.cparams['clevel'] = 9\n",
    "bcolz.set_nthreads(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [18] used 0.809 MiB RAM in 0.007s, peaked 0.000 MiB above current, total RAM usage 115.172 MiB\n"
     ]
    }
   ],
   "source": [
    "ca = bcolz.carray(na)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('mem_used:', 0.80859375)\n",
      "In [19] used 0.016 MiB RAM in 0.001s, peaked 0.000 MiB above current, total RAM usage 115.188 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": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "carray((1000000,), float64)\n",
       "  nbytes: 7.63 MB; cbytes: 332.78 KB; ratio: 23.48\n",
       "  cparams := cparams(clevel=9, shuffle=True, cname='blosclz')\n",
       "[  0.00000000e+00   1.00000000e+00   2.00000000e+00 ...,   9.99997000e+05\n",
       "   9.99998000e+05   9.99999000e+05]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [20] used 0.559 MiB RAM in 0.002s, peaked 0.000 MiB above current, total RAM usage 115.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": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 1.32 ms per loop\n",
      "('MFLOPS:', 759.465)\n",
      "In [21] used 0.277 MiB RAM in 5.431s, peaked 0.000 MiB above current, total RAM usage 116.023 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o ca.sum()\n",
    "print(\"MFLOPS:\", round(1e6 / t.best / 1e6, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is around 2~4x slower (depending on the machine) than a regular NumPy array, but the size of the array is an impressive 10x 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": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [22] used 13.816 MiB RAM in 0.038s, peaked 0.000 MiB above current, total RAM usage 129.840 MiB\n"
     ]
    }
   ],
   "source": [
    "cau = bcolz.carray(a, cparams=bcolz.cparams(clevel=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "carray((1000000,), float64)\n",
       "  nbytes: 7.63 MB; cbytes: 7.75 MB; ratio: 0.98\n",
       "  cparams := cparams(clevel=0, shuffle=True, cname='blosclz')\n",
       "[  0.00000000e+00   1.00000000e+00   2.00000000e+00 ...,   9.99997000e+05\n",
       "   9.99998000e+05   9.99999000e+05]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In [23] used 0.012 MiB RAM in 0.004s, peaked 0.000 MiB above current, total RAM usage 129.852 MiB\n"
     ]
    }
   ],
   "source": [
    "cau"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 1.46 ms per loop\n",
      "('MFLOPS:', 682.943)\n",
      "In [24] used 0.020 MiB RAM in 6.072s, peaked 0.000 MiB above current, total RAM usage 129.871 MiB\n"
     ]
    }
   ],
   "source": [
    "t = %timeit -o cau.sum()\n",
    "print(\"MFLOPS:\", round(1e6 / 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 (the later is actually faster here!), 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Using bcolz in real scenarios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "bcolz does not get good compression ratios only with synthetic data, but with real data too.  Be sure to check out this URL:\n",
    "\n",
    "http://nbviewer.ipython.org/gist/alimanfoo/e93a532eb6bde311ea39/genotype_bitshuffle.ipynb\n",
    "\n",
    "and let's discuss this specific case of bcolz usage in genomics:\n",
    "\n",
    "* Which are the typical compression ratios for this case?\n",
    "\n",
    "* Is there a difference in speed accessing data in compressed and non-compressed state (clevel=0)\n",
    "\n",
    "* Which are the compressors achieving the best compression/speed ratio?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}