5-DynamicAllocation.ipynb 10.2 KB
Newer Older
GILLES Sebastien's avatar
GILLES Sebastien committed
1 2 3 4 5 6
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
7
    "# [Getting started in C++](./) - [Procedural programming](./0-main.ipynb) - [Dynamic allocations](./5-DynamicAllocation.ipynb)"
GILLES Sebastien's avatar
GILLES Sebastien committed
8 9
   ]
  },
10 11 12 13 14 15 16 17 18 19
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Introduction\" data-toc-modified-id=\"Introduction-1\">Introduction</a></span></li><li><span><a href=\"#Stack\" data-toc-modified-id=\"Stack-2\">Stack</a></span></li><li><span><a href=\"#Heap-and-free-store\" data-toc-modified-id=\"Heap-and-free-store-3\">Heap and free store</a></span><ul class=\"toc-item\"><li><span><a href=\"#Free-store?\" data-toc-modified-id=\"Free-store?-3.1\">Free store?</a></span></li></ul></li><li><span><a href=\"#Arrays-on-heap\" data-toc-modified-id=\"Arrays-on-heap-4\">Arrays on heap</a></span></li></ul></div>"
   ]
  },
GILLES Sebastien's avatar
GILLES Sebastien committed
20 21 22 23 24 25
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
26
    "In C++, we can finely control the life cycle of objects and manage the memory allocated to them. This is what makes it possible to create more powerful applications than with many other languages, but it is also the main source of errors in the language. Pointers and dynamic memory management: watch out for danger!\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
27 28 29
    "\n",
    "## Stack\n",
    "\n",
ROUVREAU Vincent's avatar
typo  
ROUVREAU Vincent committed
30
    "The ordinary variables of C++ have a lifetime limited to the current instruction block, whether it is the current function, or an instruction block attached to an `if`, `for` or just independant.\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
31 32 33 34 35 36 37 38
    "\n",
    "The memory allocated to them is located in an area called a **stack**, and is automatically relieved when exiting the current block using the **last in, first out** principle.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
39
   "execution_count": null,
GILLES Sebastien's avatar
GILLES Sebastien committed
40 41 42 43 44 45 46 47 48 49
   "metadata": {},
   "outputs": [],
   "source": [
    "{\n",
    "    {\n",
    "        int a { 5 };\n",
    "        double b { 7.4 };\n",
    "    } // at the end of this block, b is released first and then a - but 99.99 % of the time you shouldn't care\n",
    "      // about that order!\n",
    "\n",
50
    "    // a and b are not available here    \n",
GILLES Sebastien's avatar
GILLES Sebastien committed
51 52 53 54 55 56 57 58 59
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are few limitations with the stack:\n",
    "\n",
STEFF Laurent's avatar
STEFF Laurent committed
60
    "* The number of memory you can allocate on the stack is rather limited. On a current POSIX OS the order of magnitude is ~ 8 MB (on Unix type `ulimit -s` in a terminal to get this information). If you allocate more you will get a **stack overflow** (and now you know why the [most popular developers forum](https://stackoverflow.com/) is named this way!)\n",
61 62
    "* The information is very local; you can't use it elsewhere. If you pass the variable as argument in a function for instance a copy is made (or if you're using a reference or a pointer you have to be sure all is done when the block is exited!)\n",
    "* Stack information must be known at compile time: if you're allocating an array on the stack you must know its size beforehand."
GILLES Sebastien's avatar
GILLES Sebastien committed
63 64 65 66 67 68 69 70 71 72
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heap and free store\n",
    "\n",
    "You can in fact also explicitly place a variable in another memory area called **heap** or **free store**; doing so overcomes the stack limitations mentioned above.\n",
    "\n",
73
    "This is done by calling the `new` operator, which reserves the memory and returns its address, so that the user can store it _with a pointer_.\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
74 75 76 77 78 79 80 81
    "\n",
    "The **heap** is independent of the **stack** and the variable thus created exists as long as the `delete` operator is not explicitly called. The creation and destruction of this type of variable is the responsibility of the programmer. \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
82
   "execution_count": null,
GILLES Sebastien's avatar
GILLES Sebastien committed
83
   "metadata": {},
84
   "outputs": [],
GILLES Sebastien's avatar
GILLES Sebastien committed
85 86 87 88
   "source": [
    "#include <iostream>\n",
    "\n",
    "{\n",
89
    "    int* n = new int(5); // variable created on the heap and initialized with value 5.\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
    "    \n",
    "    std::cout << *n << std::endl;\n",
    "    \n",
    "    delete n; // deletion must be explicitly called; if not there is a memory leak!\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is especially tricky is that:\n",
    "\n",
    "* Creating and destroying can be done in places very disconnected in your program.\n",
    "* You must ensure that whatever the runtime path used in your program each variable allocated on the heap:\n",
    "    - is destroyed (otherwise you get a **memory leak**)\n",
    "    - is only destroyed once (or your program will likely crash with a message about **double deletion**).\n",
    "    \n",
    "In sophisticated programs, this could lead in serious and tedious bookkeeping to ensure all variables are properly handled, even if tools such as [Valgrind](http://www.valgrind.org/) or [Address sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) may help to find out those you will probably have forgotten somewhere along the way.\n",
    "\n",
110
    "To be honest, C++ gets quite a bad name due to this tedious memory handling; fortunately the RAII idiom provides a neat way to automatize nicely memory management (which we'll study [later](../5-UsefulConceptsAndSTL/2-RAII.ipynb)) and some vocal critics on forums that regret the lack of [garbage collection](https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)) might actually not be aware of this fundamental (from my point of view at least) idiom."
GILLES Sebastien's avatar
GILLES Sebastien committed
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Free store?\n",
    "\n",
    "**Free store** is very similar in functionality to the **heap** (to the point I had to [check the difference](https://stackoverflow.com/questions/1350819/c-free-store-vs-heap) before writing this...) , and more often than not one word might be used as the other. If you want to be pedantic:\n",
    "\n",
    "* When memory is handled by `new`/`delete`, you should talk about **free store**.\n",
    "* When memory is handled by `malloc`/`free` (the C functions), you should talk about **heap**.\n",
    "\n",
    "Pedantry aside, the important thing to know is to never mix both syntax: if you allocate memory by `new` don't use `free` to relieve it.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arrays on heap\n",
    "\n",
    "If you want to init an array which size you do not know at compile time or that might overflow the stack, you may to do with `new` syntax mixed with `[]`:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
139
   "execution_count": null,
GILLES Sebastien's avatar
GILLES Sebastien committed
140 141 142
   "metadata": {},
   "outputs": [],
   "source": [
STEFF Laurent's avatar
STEFF Laurent committed
143 144
    "void create_array(unsigned int ndigit) {    \n",
    "    int* pi_first_five_digits = new int[ndigit];\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
145 146 147 148 149 150 151 152
    "    \n",
    "    pi_first_five_digits[0] = 3;\n",
    "    pi_first_five_digits[1] = 1;\n",
    "    pi_first_five_digits[2] = 4;\n",
    "    pi_first_five_digits[3] = 1;\n",
    "    pi_first_five_digits[4] = 5;\n",
    "    \n",
    "    delete[] pi_first_five_digits;\n",
STEFF Laurent's avatar
STEFF Laurent committed
153 154 155 156 157 158
    "}\n",
    "\n",
    "// let's say that 5 comes from a size of an input file, or\n",
    "// whatever defined at runtime (vs compile time)\n",
    "// we would call then:\n",
    "create_array(5);"
GILLES Sebastien's avatar
GILLES Sebastien committed
159 160 161 162 163 164 165 166 167
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please notice that:\n",
    "\n",
    "* No value can be assigned in construction: you must first allocate the memory for the array and only in a second time fill it.\n",
168
    "* A `[]` **must** be added to the **delete** instruction to indicate to the compiler this is actually an array that is destroyed.\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
169 170 171 172 173 174 175
    "\n",
    "In fact, my advice would be to avoid entirely to deal directly with such arrays and use containers from the standard library such as `std::vector`:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
176
   "execution_count": null,
GILLES Sebastien's avatar
GILLES Sebastien committed
177 178 179 180 181 182 183 184 185 186 187 188 189 190
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <vector>\n",
    "\n",
    "{\n",
    "    std::vector<int> pi_first_five_digits { 3, 1, 4, 1, 5 };\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
191
    "that does the exact same job in a shorter way and is much more secure to use (spoiler: `std::vector` is built upon the RAII idiom mentioned briefly in this notebook).\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
192
    "\n",
193
    "We shall see `std::vector` more deeply [later](../5-UsefulConceptsAndSTL/3-Containers.ipynb) but will nonetheless use it before this as it is a rather elementary brick in most C++ codes."
GILLES Sebastien's avatar
GILLES Sebastien committed
194 195 196 197 198 199 200
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
201
    "© _CNRS 2016_ - _Inria 2018-2021_   \n",
202 203
    "_This notebook is an adaptation of a lecture prepared by David Chamont (CNRS) under the terms of the licence [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)](http://creativecommons.org/licenses/by-nc-sa/4.0/)_  \n",
    "_The present version has been written by Sébastien Gilles and Vincent Rouvreau (Inria)_\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
204 205 206 207 208 209 210 211
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
212
   "name": "xcpp17"
GILLES Sebastien's avatar
GILLES Sebastien committed
213 214 215 216 217 218
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
219
   "version": "17"
220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
248 249 250 251 252 253
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
254 255
   "toc_section_display": true,
   "toc_window_display": true
GILLES Sebastien's avatar
GILLES Sebastien committed
256 257 258
  }
 },
 "nbformat": 4,
259
 "nbformat_minor": 4
STEFF Laurent's avatar
STEFF Laurent committed
260
}