Deep-Learning/mxnet-notes/mshadow-expression-template-tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 表达式模板教程\n",
    "\n",
    "本页解释mshadow如何工作。 mshadow后面的主要技巧是表达式模板。我们将解释它将如何影响编译代码的性能。表达式模板是C ++矩阵库的主要技巧，例如Eigen，GSL，boost.uBLAS。\n",
    "\n",
    "## 如何编写高效的机器学习代码\n",
    "在我们开始之前，让我们想一想上面的问题。假设我们要实现如下更新规则  \n",
    "```c\n",
    "weight =  - eta * (grad + lambda * weight);\n",
    "```\n",
    "其中weight和grad是长度为n的向量。当你选择C ++作为你的编程语言，我想主要关注的是效率。在大多数C / C ++程序中有一个重要的原则：\n",
    "* 预分配必要的内存，在运行期间没有临时内存分配。  \n",
    "例如以下的示例代码\n",
    "```c\n",
    "void UpdateWeight (const float *grad, float eta, float lambda, int n, float *weight) {\n",
    "      for (int i = 0; i < n; ++i) {\n",
    "        weight[i] =  - eta * (grad[i] + lambda * weight[i]);\n",
    "      }\n",
    "}\n",
    "```\n",
    "该函数接受预分配的空间grad和weight，并运行计算。写这些函数很简单，但是，当我们重复写它们时，它可能很烦人。所以问题是，我们可以写出如下代码，并获得与以前的代码相同的性能？\n",
    "```c\n",
    "void UpdateWeight (const Vec& grad, float eta, float lambda, Vec& weight) {\n",
    "      weight = -eta * (grad + lambda * weight);\n",
    "} \n",
    "```\n",
    "答案是肯定的，但不是最明显的解决方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 一个Naive的解决方案\n",
    "让我们先来看看一个最直接的解决方案：操作符重载。\n",
    "```c\n",
    "// Naive solution for vector operation overloading \n",
    "struct Vec {\n",
    "  int len;\n",
    "  float* dptr;\n",
    "  Vec(int len) : len(len) { \n",
    "    dptr = new float[len];\n",
    "  }\n",
    "  Vec(const Vec& src) : len(src.len) {\n",
    "    dptr = new float[len];\n",
    "    memcpy(dptr, src.dptr, sizeof(float)*len ); \n",
    "  }\n",
    "  ~Vec(void) {\n",
    "    delete [] dptr;\n",
    "  }\n",
    "};\n",
    "\n",
    "inline Vec operator+(const Vec &lhs, const Vec &rhs) {\n",
    "  Vec res(lhs.len);\n",
    "  for (int i = 0; i < lhs.len; ++i) {\n",
    "    res.dptr[i] = lhs.dptr[i] + rhs.dptr[i];\n",
    "  } \n",
    "  return res;\n",
    "} \n",
    "```\n",
    "\n",
    "如果我们以相同的风格添加更多的运算符重载，我们可以得到我们想要的，并写成表达式，而不是循环。然而，这种方法是低效的，因为临时内存在每个操作期间被分配和释放，而我们可以做得更好。  \n",
    "\n",
    "一个替代的，更有效的方法是只重载operator + =，operator- =，这可以在没有临时内存分配的情况下实现。但这限制了我们可以写的方程。  \n",
    "\n",
    "我们将讨论为什么我们仍然需要表达式模板，尽管C ++ 11在本教程结尾处提供了移动赋值运算符和右值引用。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 惰性求值\n",
    "让我们想想为什么我们在做operator +时需要临时内存分配。这是因为我们不知道将在operator +中赋值的目标，否则我们可以直接存储到目标内存而不是临时内存中。  \n",
    "\n",
    "如果我们能知道目标怎么办？下面的代码（exp_lazy.cpp）实现了这一点。\n",
    "```c\n",
    "// Example Lazy evaluation code\n",
    "// for simplicity, we use struct and make all members public\n",
    "#include <cstdio>\n",
    "struct Vec;\n",
    "// expression structure holds the expression\n",
    "struct BinaryAddExp {\n",
    "  const Vec &lhs;\n",
    "  const Vec &rhs;\n",
    "  BinaryAddExp(const Vec &lhs, const Vec &rhs)\n",
    "  : lhs(lhs), rhs(rhs) {}\n",
    "};\n",
    "// no constructor and destructor to allocate and de-allocate memory,\n",
    "//  allocation done by user\n",
    "struct Vec {\n",
    "  int len;\n",
    "  float* dptr;\n",
    "  Vec(void) {}\n",
    "  Vec(float *dptr, int len)\n",
    "      : len(len), dptr(dptr) {}\n",
    "  // here is where evaluation happens\n",
    "  inline Vec &operator=(const BinaryAddExp &src) {\n",
    "    for (int i = 0; i < len; ++i) {\n",
    "      dptr[i] = src.lhs.dptr[i] + src.rhs.dptr[i];\n",
    "    }\n",
    "    return *this;\n",
    "  }\n",
    "};\n",
    "// no evaluation happens here\n",
    "inline BinaryAddExp operator+(const Vec &lhs, const Vec &rhs) {\n",
    "  return BinaryAddExp(lhs, rhs);\n",
    "}\n",
    "\n",
    "const int n = 3;\n",
    "int main(void) {\n",
    "  float sa[n] = {1, 2, 3};\n",
    "  float sb[n] = {2, 3, 4};\n",
    "  float sc[n] = {3, 4, 5};\n",
    "  Vec A(sa, n), B(sb, n), C(sc, n);\n",
    "  // run expression\n",
    "  A = B + C;\n",
    "  for (int i = 0; i < n; ++i) {\n",
    "    printf(\"%d:%f==%f+%f\\n\", i, A.dptr[i], B.dptr[i], C.dptr[i]);\n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "```\n",
    "这个想法是，我们实际上不是在operator +中执行计算，而是只返回一个表达式结构（如抽象语法树），当我们重载operator =时，我们看到目标，以及所有的操作数，我们可以运行计算无需引入额外的内存！类似地，我们可以定义一个DotExp并且在operator =处进行延迟计算，并将矩阵（向量）乘法重定向到BLAS。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 更长的表达式和表达式模板\n",
    "通过使用惰性求值，我们通过避免临时内存分配很酷。但是代码的能力有限：\n",
    "\n",
    "* 我们只能写A = B + C，但不能更长的表达式。\n",
    "* 当我们添加更多的表达式时，我们需要写更多的operator =来计算每个方程。\n",
    "\n",
    "这里需要模板编程的魔力来救援。下面的代码（exp_template.cpp），有点更长，也允许你写长的方程。\n",
    "```c\n",
    "// Example code, expression template, and more length equations\n",
    "// for simplicity, we use struct and make all members public\n",
    "#include <cstdio>\n",
    "\n",
    "// this is expression, all expressions must inheritate it,\n",
    "//  and put their type in subtype\n",
    "template<typename SubType>\n",
    "struct Exp {\n",
    "  // returns const reference of the actual type of this expression\n",
    "  inline const SubType& self(void) const {\n",
    "    return *static_cast<const SubType*>(this);\n",
    "  }\n",
    "};\n",
    "\n",
    "// binary add expression\n",
    "// note how it is inheritates from Exp\n",
    "// and put its own type into the template argument\n",
    "template<typename TLhs, typename TRhs>\n",
    "struct BinaryAddExp: public Exp<BinaryAddExp<TLhs, TRhs> > {\n",
    "  const TLhs &lhs;\n",
    "  const TRhs &rhs;\n",
    "  BinaryAddExp(const TLhs& lhs, const TRhs& rhs)\n",
    "      : lhs(lhs), rhs(rhs) {}\n",
    "  // evaluation function, evaluate this expression at position i\n",
    "  inline float Eval(int i) const {\n",
    "    return lhs.Eval(i) + rhs.Eval(i);\n",
    "  }\n",
    "};\n",
    "// no constructor and destructor to allocate\n",
    "// and de-allocate memory, allocation done by user\n",
    "struct Vec: public Exp<Vec> {\n",
    "  int len;\n",
    "  float* dptr;\n",
    "  Vec(void) {}\n",
    "  Vec(float *dptr, int len)\n",
    "      :len(len), dptr(dptr) {}\n",
    "  // here is where evaluation happens\n",
    "  template<typename EType>\n",
    "  inline Vec& operator= (const Exp<EType>& src_) {\n",
    "    const EType &src = src_.self();\n",
    "    for (int i = 0; i < len; ++i) {\n",
    "      dptr[i] = src.Eval(i);\n",
    "    }\n",
    "    return *this;\n",
    "  }\n",
    "  // evaluation function, evaluate this expression at position i\n",
    "  inline float Eval(int i) const {\n",
    "    return dptr[i];\n",
    "  }\n",
    "};\n",
    "// template add, works for any expressions\n",
    "template<typename TLhs, typename TRhs>\n",
    "inline BinaryAddExp<TLhs, TRhs> operator+(const Exp<TLhs> &lhs, const Exp<TRhs> &rhs) {\n",
    "  return BinaryAddExp<TLhs, TRhs>(lhs.self(), rhs.self());\n",
    "}\n",
    "\n",
    "const int n = 3;\n",
    "int main(void) {\n",
    "  float sa[n] = {1, 2, 3};\n",
    "  float sb[n] = {2, 3, 4};\n",
    "  float sc[n] = {3, 4, 5};\n",
    "  Vec A(sa, n), B(sb, n), C(sc, n);\n",
    "  // run expression, this expression is longer:)\n",
    "  A = B + C + C;\n",
    "  for (int i = 0; i < n; ++i) {\n",
    "    printf(\"%d:%f == %f + %f + %f\\n\", i,\n",
    "           A.dptr[i], B.dptr[i],\n",
    "           C.dptr[i], C.dptr[i]);\n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "```\n",
    "代码的关键思想是模板Exp <SubType>将其派生类的类型作为模板参数，因此它可以通过self（）将自身转换为SubType。 BinaryAddExp现在是一个模板类，可以将表达式复合在一起，像模板版本的复合模式。求值是通过函数Eval完成的，这是在BinaryAddExp中以递归方式完成的。\n",
    "\n",
    "* 由于内联，在编译时将在operator =中的src.Eval（i）的函数调用编译成B.dptr [i] + C.dptr [i] + C.dptr [i]。\n",
    "* 我们可以用相同的效率编写element-wise操作的方程，就像我们写一个循环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 使其更灵活\n",
    "正如我们在前面的例子中可以看到的，模板编程是一个强大的功能，使编译时更灵活，我们的最后一个例子，更接近mshadow，允许用户自定义二元运算符（exp_template_op.cpp）。\n",
    "```c\n",
    "// Example code, expression template\n",
    "// with binary operator definition and extension\n",
    "// for simplicity, we use struct and make all members public\n",
    "#include <cstdio>\n",
    "\n",
    "// this is expression, all expressions must inheritate it,\n",
    "// and put their type in subtype\n",
    "template<typename SubType>\n",
    "struct Exp{\n",
    "  // returns const reference of the actual type of this expression\n",
    "  inline const SubType& self(void) const {\n",
    "    return *static_cast<const SubType*>(this);\n",
    "  }\n",
    "};\n",
    "\n",
    "// binary operators\n",
    "struct mul{\n",
    "  inline static float Map(float a, float b) {\n",
    "    return a * b;\n",
    "  }\n",
    "};\n",
    "\n",
    "// binary add expression\n",
    "// note how it is inheritates from Exp\n",
    "// and put its own type into the template argument\n",
    "template<typename OP, typename TLhs, typename TRhs>\n",
    "struct BinaryMapExp: public Exp<BinaryMapExp<OP, TLhs, TRhs> >{\n",
    "  const TLhs& lhs;\n",
    "  const TRhs& rhs;\n",
    "  BinaryMapExp(const TLhs& lhs, const TRhs& rhs)\n",
    "      :lhs(lhs), rhs(rhs) {}\n",
    "  // evaluation function, evaluate this expression at position i\n",
    "  inline float Eval(int i) const {\n",
    "    return OP::Map(lhs.Eval(i), rhs.Eval(i));\n",
    "  }\n",
    "};\n",
    "// no constructor and destructor to allocate and de-allocate memory\n",
    "// allocation done by user\n",
    "struct Vec: public Exp<Vec>{\n",
    "  int len;\n",
    "  float* dptr;\n",
    "  Vec(void) {}\n",
    "  Vec(float *dptr, int len)\n",
    "      : len(len), dptr(dptr) {}\n",
    "  // here is where evaluation happens\n",
    "  template<typename EType>\n",
    "  inline Vec& operator=(const Exp<EType>& src_) {\n",
    "    const EType &src = src_.self();\n",
    "    for (int i = 0; i < len; ++i) {\n",
    "      dptr[i] = src.Eval(i);\n",
    "    }\n",
    "    return *this;\n",
    "  }\n",
    "  // evaluation function, evaluate this expression at position i\n",
    "  inline float Eval(int i) const {\n",
    "    return dptr[i];\n",
    "  }\n",
    "};\n",
    "// template add, works for any expressions\n",
    "template<typename OP, typename TLhs, typename TRhs>\n",
    "inline BinaryMapExp<OP, TLhs, TRhs>\n",
    "F(const Exp<TLhs>& lhs, const Exp<TRhs>& rhs) {\n",
    "  return BinaryMapExp<OP, TLhs, TRhs>(lhs.self(), rhs.self());\n",
    "}\n",
    "\n",
    "template<typename TLhs, typename TRhs>\n",
    "inline BinaryMapExp<mul, TLhs, TRhs>\n",
    "operator*(const Exp<TLhs>& lhs, const Exp<TRhs>& rhs) {\n",
    "  return F<mul>(lhs, rhs);\n",
    "}\n",
    "\n",
    "// user defined operation\n",
    "struct maximum{\n",
    "  inline static float Map(float a, float b) {\n",
    "    return a > b ? a : b;\n",
    "  }\n",
    "};\n",
    "\n",
    "const int n = 3;\n",
    "int main(void) {\n",
    "  float sa[n] = {1, 2, 3};\n",
    "  float sb[n] = {2, 3, 4};\n",
    "  float sc[n] = {3, 4, 5};\n",
    "  Vec A(sa, n), B(sb, n), C(sc, n);\n",
    "  // run expression, this expression is longer:)\n",
    "  A = B * F<maximum>(C, B);\n",
    "  for (int i = 0; i < n; ++i) {\n",
    "    printf(\"%d:%f == %f * max(%f, %f)\\n\",\n",
    "           i, A.dptr[i], B.dptr[i], C.dptr[i], B.dptr[i]);\n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结\n",
    "到目前为止，你应该已经了解它的工作原理：\n",
    "\n",
    "* 惰性求值，让我们看到所有的操作数和目标\n",
    "* 模板组合和递归求值，允许我们评估任意使用element-wise操作的复合表达式。\n",
    "* 由于模板和内联，写表达式就像我们直接编写for循环来实现更新规则一样高效:)\n",
    "\n",
    "所以在写机器学习代码时写表达式，并将重点放在重要的算法部分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MShadow中的表达式模板\n",
    "mshadow中的表达式模板使用与教程中介绍的相同的要点，但有一些细微的差别：\n",
    "\n",
    "* 我们将评估代码与表达式构造和组合代码分开。\n",
    "    * 而不是将Eval放在Exp类中。从表达式创建计划类，并用于评估结果。\n",
    "    * 这允许我们在Plan中放置较少的变量，例如，当我们评估数据时，我们不需要数组长度。\n",
    "    * 一个重要的原因是CUDA内核不能带有const引用的类\n",
    "    * 这个设计选择是有争议的，但我们发现它到目前为止是有用的。\n",
    "* 对矩阵点乘等复杂表达式的惰性支持\n",
    "    * 除了element-wise的表达式，我们还想支持语法糖，如A = dot（B.T（），C），再次，惰性求值没有额外的内存分配。\n",
    "* 类型检查和数组长度检查。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 备注\n",
    "\n",
    "* 表达式模板和C ++ 11：在C ++ 11中，move构造函数可以用来保存重复分配内存，这消除了对表达式模板的一些需要。然而，该空间仍然需要至少分配一次。\n",
    "* 这只消除了表达式模板然后表达式生成空间的需要，说dst = A + B + C，dst不包含赋值前分配的空间。\n",
    "* 如果我们想要保留一切都预先分配的语法，并且表达式执行没有内存分配（这是我们在mshadow中做的），我们仍然需要表达式模板。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "原文：  \n",
    "https://github.com/dmlc/mshadow/tree/master/guide/exp-template"
   ]
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}