00:00:00
in my previous video I talked about how
00:00:02
providing the size of your variables in
00:00:03
your code can help compilers speed up
00:00:05
your programs I ended that video by
00:00:08
mentioning that you might want your
00:00:09
types to grow or Shrink dynamically at
00:00:11
runtime but that's a problem because in
00:00:14
low-level programming languages
00:00:16
compilers complain when you are not
00:00:17
explicit about sizes so you can't
00:00:21
declare custom types with arrays unless
00:00:23
you give the array a specific size but
00:00:26
that means your array will have that
00:00:28
size during the entire lifetime of your
00:00:29
program
00:00:30
by the end of this video you will
00:00:32
understand the reasons behind this
00:00:35
limitation hi friends my name is George
00:00:38
and this is core dumped today we are
00:00:41
going to take a look at the stack that
00:00:44
memory region that everybody tells you
00:00:45
is super fast and you should always try
00:00:47
to put data on it but almost nobody
00:00:49
tells you why a stack is a data
00:00:51
structure that follows the last in first
00:00:53
out principle this means that the last
00:00:56
element added to the stack is the first
00:00:58
one to be removed
00:01:00
usually its size is limited so if we
00:01:03
push too many elements and run out of
00:01:05
space we say the stack has overflowed
00:01:07
which may sound familiar to you although
00:01:10
recently the site is dead due to the
00:01:12
rise of large language models like me I
00:01:14
mean like
00:01:15
gp4 Anyway the stack in this video is
00:01:18
not a software stack although there is a
00:01:21
relationship as you'll see what we are
00:01:23
studying right now is the execution
00:01:25
stack sometimes called the program stack
00:01:28
or even the hardware stack
00:01:30
when we run a program theoretically
00:01:32
there is nothing preventing us from
00:01:34
writing our values anywhere in memory
00:01:36
even though we are specifying the size
00:01:38
of our values randomly placing them
00:01:40
could result in wasted space to
00:01:42
comprehend this it's crucial to consider
00:01:45
the role of the operating system you
00:01:47
might be familiar with the concept that
00:01:49
the operating system always acts as an
00:01:50
intermediary between programs and
00:01:53
Hardware well memory is no
00:01:56
exception when a program is executed it
00:01:59
cannot simply begin storing data
00:02:01
anywhere in physical memory as other
00:02:03
programs might already be utilizing some
00:02:05
of that space therefore before it must
00:02:08
request memory from the operating system
00:02:11
the operating system in turn will search
00:02:13
for available spaces where our program
00:02:15
can write if we try to read from or
00:02:18
write to a memory address that the
00:02:19
operating system hasn't allocated to our
00:02:21
program it will promptly terminate the
00:02:24
program's execution for safety
00:02:28
reasons this is when we encounter the
00:02:30
infamous error known as segmentation
00:02:32
fault core dumped from which this
00:02:34
channel derives its
00:02:36
name the important part here is that the
00:02:39
operating system doesn't allocate memory
00:02:41
precisely to the amount we need instead
00:02:44
it provides a memory chunk where we can
00:02:45
freely read and
00:02:48
write however if we don't organize our
00:02:50
data and just place it anywhere we might
00:02:52
face this issue where there is
00:02:54
sufficient free memory but we can't
00:02:55
store data due to the lack of contiguous
00:02:58
space this problem is commonly referred
00:03:00
to as external
00:03:03
fragmentation in this case the only way
00:03:06
to store our value in memory is to
00:03:08
request another
00:03:12
chunk if we had organized our data more
00:03:15
efficiently there would be no
00:03:16
requirement to request additional
00:03:20
memory it's worth noting that asking for
00:03:22
more memory can be considerably
00:03:23
expensive in terms of performance as a
00:03:26
brief preview this is why many recommend
00:03:28
minimizing the use of the Heap we'll
00:03:30
delve deeper into this topic in my
00:03:32
upcoming video about the Heap so
00:03:33
consider subscribing for more
00:03:35
details furthermore when the operating
00:03:38
system allocates memory to our program
00:03:40
it doesn't track whether we utilize that
00:03:42
memory or not its sole awareness is that
00:03:44
the specified memory region belongs to
00:03:47
our program if another program requires
00:03:49
memory it will have to put its data
00:03:51
somewhere else even if there is enough
00:03:54
free contiguous memory in our program
00:03:55
memory
00:03:57
region but memory is finite
00:04:01
so what do we do if all the memory is
00:04:03
already in use by other
00:04:05
programs once again the answer lies with
00:04:07
the operating system modern operating
00:04:10
systems are specifically designed to
00:04:11
address this type of issue in the
00:04:14
absence of available memory they
00:04:15
leverage storage space as if it were
00:04:17
additional
00:04:19
memory have you ever seen that partition
00:04:21
called swap in Linux systems well now
00:04:24
you know what it
00:04:26
does this is what we call virtual memory
00:04:29
and it is very useful because it not
00:04:31
only creates the illusion of having much
00:04:32
more memory than is actually present but
00:04:35
it also gives the appearance of writing
00:04:36
directly to physical memory so as
00:04:39
programmers we don't have to worry about
00:04:41
all the underlying Concepts I could
00:04:44
spend 30 minutes talking about virtual
00:04:45
memory but that's out of the scope of
00:04:47
this video however it's important to
00:04:50
note that relying on storage to extend
00:04:51
main memory is a double-edged sword
00:04:54
storage is thousands of times slower
00:04:56
than RAM and this feature that operating
00:04:58
systems provide should be used with with
00:05:00
caution in my previous video Someone
00:05:03
commented that in modern days the size
00:05:05
of our data in memory might not seem
00:05:07
crucial due to the virtually unlimited
00:05:09
memory available while it's true that
00:05:11
memory appears Limitless for us as
00:05:13
programmers it's essential to exercise
00:05:15
caution and consider that performance
00:05:17
still plays a significant
00:05:19
role and speaking of performance it
00:05:22
turns out that even memory can be a
00:05:24
bottleneck despite the immense speed of
00:05:26
modern CPUs fetching data from memory
00:05:28
incurs a noticeable
00:05:30
cost to address this manufacturers
00:05:33
integrate a feature called cache into
00:05:35
modern chips cache is essentially a
00:05:38
small dedicated memory inside the
00:05:40
processor where a copy of a memory
00:05:42
region is stored this way when the CPU
00:05:45
requires data for manipulation or an
00:05:47
operation it can promptly retrieve it
00:05:49
from the cache instead of searching for
00:05:51
it in the main
00:05:52
memory when the necessary information is
00:05:55
present in the cache we refer to it as a
00:05:58
cach hit however if the required data is
00:06:01
not in the cache it results in a cache
00:06:04
Miss in such cases the CPU is compelled
00:06:08
to wait for the data to be fetched from
00:06:09
the main memory incurring additional
00:06:11
time once again this is completely
00:06:14
invisible to us the programmers in this
00:06:16
case is the hardware and not the
00:06:18
operating system who decides what memory
00:06:20
region is kept in
00:06:22
Cache if we care about performance the
00:06:25
best we can do is to keep our data as
00:06:27
compact as possible this this way there
00:06:30
is a higher probability that it will fit
00:06:32
in the cache this proximity increases
00:06:35
the chances of a cash
00:06:37
hit this new concept of keeping data as
00:06:40
close as possible to the CPU is what
00:06:42
low-level people know as locality and
00:06:45
there you have the second reason to keep
00:06:46
data compact
00:06:49
performance now you might be thinking
00:06:51
what the hell all of this has to do with
00:06:53
the stack well it turns out if we want
00:06:55
to keep data compact a good way to
00:06:57
organize things is using a stack let's
00:07:00
take a look the first thing we can do to
00:07:02
speed things up is to pre-allocate
00:07:04
memory when our program starts this way
00:07:07
every time we need to store some value
00:07:09
we already have somewhere to write it
00:07:11
since our goal here is to avoid
00:07:13
requesting memory from the operating
00:07:15
system on the Fly the size of this
00:07:17
pre-allocated region remains fixed
00:07:19
throughout the entire lifetime of our
00:07:21
program therefore we must be careful
00:07:23
when determining its size while there's
00:07:25
nothing preventing us from allocating
00:07:27
gigabytes to this region it's essential
00:07:29
to consider the Simplicity of our
00:07:30
program if it only uses a couple of
00:07:33
variables it may never fully occupy such
00:07:35
a large memory space as mentioned
00:07:38
earlier this would result in memory
00:07:40
wastage as the operating system would
00:07:42
Reserve that free space for our program
00:07:45
preventing other programs from utilizing
00:07:46
it for this reason the size of this
00:07:49
pre-allocated region is typically kept
00:07:51
small the exact size depends on the
00:07:54
compiler we are using but generally it
00:07:56
won't exceed a few megabytes this might
00:07:59
seem seem insufficient at first glance
00:08:01
but if you do the math in only 1
00:08:02
Megabyte you can fit more than 13,
00:08:05
64-bit
00:08:09
integers when our program starts the
00:08:11
main function serves as our entry point
00:08:14
each time a new variable is encountered
00:08:16
its value is stacked into this
00:08:17
designated region this is where the term
00:08:20
the stack becomes apparent the memory
00:08:22
address marking the beginning of the
00:08:24
stack is referred to as the stack origin
00:08:26
while the stack pointer indicates the
00:08:28
current topmost data on the
00:08:30
stack of course the stack pointer is
00:08:32
stored somewhere it can be done in
00:08:34
memory but modern architectures
00:08:36
incorporate a register exclusively
00:08:38
dedicated to holding the stack pointer
00:08:40
value directly within the CPU
00:08:42
consequently the processor doesn't need
00:08:44
to wait for it to be fetched from memory
00:08:46
or even from the
00:08:47
cache one of the reasons why memory
00:08:49
allocation on the stack is highly
00:08:51
efficient lies in the constant guidance
00:08:53
provided by the stack pointer to write
00:08:55
something onto the stack all that's
00:08:57
required is to fetch the stack pointer
00:08:58
address address add one to that value
00:09:01
and the result is the memory address
00:09:03
where we can write more data and that's
00:09:04
it that's all it takes to allocate
00:09:06
memory on the stack as you'll discover
00:09:08
in my upcoming video this process is not
00:09:11
as straightforward when allocating
00:09:12
memory on the Heap in that scenario we
00:09:15
must request memory from the operating
00:09:17
system wait for it to locate available
00:09:19
space and due to the system not
00:09:21
returning the exact amount of needed
00:09:22
memory we must employ fancy strategies
00:09:25
to avoid fragmentation and all of those
00:09:27
are extra steps that make the process
00:09:30
slower when a function is called all its
00:09:33
local values are pushed onto the stack
00:09:36
but it's crucial to remember the
00:09:37
starting point of these local values
00:09:39
because when the function concludes we
00:09:41
need to reset the stack pointer to its
00:09:43
position just before the function calls
00:09:46
these distinct sub regions are known as
00:09:48
stack
00:09:51
frames when a function being called is
00:09:53
expected to return a value such as in
00:09:55
this example we allocate a distinct
00:09:57
space called the return link following
00:09:59
this we start pushing our local
00:10:03
values upon the function's conclusion
00:10:05
the return value is directly written
00:10:07
into the return link subsequently the
00:10:10
stack frame of the Cali function is
00:10:11
removed except for the returning value
00:10:14
which now integrates into the stack
00:10:15
frame of the caller function here it's
00:10:18
important to note that for the compiler
00:10:19
to generate efficient machine code it
00:10:21
requires knowledge of the exact size of
00:10:24
the return link this is why systems
00:10:26
programming languages mandate specifying
00:10:28
the size of the Val value a function is
00:10:30
returning which you do by providing a
00:10:32
return
00:10:34
type finally let's consider some
00:10:36
important limitations in this example we
00:10:39
write some values in the stack a number
00:10:42
an array then more
00:10:45
numbers and let's say then we want to
00:10:47
add some elements to the array see the
00:10:50
problem
00:10:52
here adding elements to an array on the
00:10:55
stack means we might have to overwrite
00:10:57
other values that we might need
00:11:00
later this is exactly what I talked
00:11:02
about in my previous
00:11:04
video the compiler will complain if you
00:11:06
don't specify the size of any array even
00:11:09
if the array is a member of a custom
00:11:12
type sorry if I made you wait a lot for
00:11:14
this answer but I think everything I've
00:11:15
talked about up to this point was
00:11:17
necessary to understand
00:11:19
this when you specify the size of an
00:11:21
array the compiler gains precise
00:11:23
knowledge about the amount of space
00:11:25
required to accommodate that value in
00:11:27
the
00:11:27
stack
00:11:30
but to the finite size of the stack even
00:11:32
with provided sizes exceeding this limit
00:11:34
can lead to a program crash resulting in
00:11:36
a stack Overflow
00:11:39
error this scenario is particularly
00:11:41
pertinent when dealing with recursion
00:11:43
when a function calls itself new stack
00:11:45
frames are successively pushed into the
00:11:47
stack for each recursive call if a base
00:11:50
case isn't defined to Halt the recursion
00:11:52
the program will keep adding stack
00:11:54
frames until it overflows furthermore
00:11:57
even with a base case a stack overflow
00:11:59
can occur if the program doesn't reach
00:12:01
it before surpassing the Stack's
00:12:03
capacity hence there are instances where
00:12:06
using iterative Solutions is recommended
00:12:08
over recursive ones it's essential to
00:12:11
clarify that the behavior of the stack
00:12:12
is influenced by the programming
00:12:14
language and its compiler what you've
00:12:16
seen in this video might not precisely
00:12:18
mirror the implementation in every
00:12:20
language therefore it's important to
00:12:22
understand that I aim to simplify
00:12:24
concepts for the purpose of illustration
00:12:26
in these
00:12:27
videos in summary
00:12:29
today we learned that maintaining
00:12:30
compact data is crucial for reducing
00:12:33
memory usage by avoiding fragmentation
00:12:35
and enhancing performance through an
00:12:37
increased probability of cach a hits
00:12:39
specifying the size of our variables
00:12:41
enables compilers to organize our data
00:12:43
more efficiently and predictably in the
00:12:45
stack this organization facilitates the
00:12:48
handling of function calls and local
00:12:49
variables in a seamless and Speedy
00:12:51
manner we also delved into the
00:12:53
limitations of the stack it possesses a
00:12:56
size constraint and lacks the
00:12:57
flexibility for types to Dynam
00:12:58
dynamically grow or Shrink Additionally
00:13:01
the stack operates as a single-threaded
00:13:03
entity in the context of multi-threading
00:13:06
each thread necessitates its own stack
00:13:08
posing a limitation when attempting to
00:13:10
share memory between threads all these
00:13:13
challenges find a common solution in
00:13:14
what is known as the Heap a topic that
00:13:16
we will explore in a future video and
00:13:19
that is a very very simplified version
00:13:21
of how the stack Works hopefully you now
00:13:24
have an idea of why it is so fast if you
00:13:27
learned something hit that like button
00:13:29
that will help me a lot making these
00:13:31
videos is kind of timec consuming but
00:13:33
I've been enjoying it so consider
00:13:35
subscribing if you want to learn more
00:13:37
it's free and by the way this is where I
00:13:40
say goodbye because as a free AI model I
00:13:43
have a token limit of 250
