5-DynamicAllocation.ipynb 10.1 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
143
   "metadata": {},
   "outputs": [],
   "source": [
    "{\n",
144
    "    const unsigned int Ndigit = 5; // not known at compile-time!\n",
145
    "    \n",
146
    "    int* pi_first_five_digits = new int[Ndigit];\n",
GILLES Sebastien's avatar
GILLES Sebastien committed
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
    "    \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",
    "}"
   ]
  },
  {
   "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",
165
    "* 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
166
167
168
169
170
171
172
    "\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",
173
   "execution_count": null,
GILLES Sebastien's avatar
GILLES Sebastien committed
174
175
176
177
178
179
180
181
182
183
184
185
186
187
   "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": [
188
    "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
189
    "\n",
190
    "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
191
192
193
194
195
196
197
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
198
    "© _CNRS 2016_ - _Inria 2018-2021_   \n",
199
200
    "_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
201
202
203
204
205
206
207
208
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
209
   "name": "xcpp17"
GILLES Sebastien's avatar
GILLES Sebastien committed
210
211
212
213
214
215
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
216
   "version": "17"
217
218
219
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
  },
  "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,
245
246
247
248
249
250
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
251
252
   "toc_section_display": true,
   "toc_window_display": true
GILLES Sebastien's avatar
GILLES Sebastien committed
253
254
255
  }
 },
 "nbformat": 4,
256
 "nbformat_minor": 4
STEFF Laurent's avatar
STEFF Laurent committed
257
}