This article continues our series on Data Structures and Algorithms (DSA). So far, you have likely written "working" and "non-working" code while learning elementary programming. While the concepts apply similarly to JavaScript, we will focus on Python in this article.

Maybe you wrote messy code that "got the job done," littered it with print() statements, or even debugged it manually. However, if you understand how your code works in memory, you will go back to optimize this "messy" code.

There are two mechanisms for storing data on your computer:

Storage: This includes devices like flash drives and hard disks. Data stored here is permanent, meaning it persists even after turning your computer off and back on.

Memory: Also known as RAM (Random Access Memory). Data stored on it is temporary, which means it disappears once you turn off your computer or exit the application.

Given that storage can hold data permanently, why use memory? The answer lies in speed. Accessing data from storage is much slower than accessing it from memory. So, when you need to use data, it gets temporarily copied to memory for faster processing. Once you are done, you can save it back to storage for long-term retention.

To understand this better, let's take a look at the types of memory.

Computers have two types of memory:
Short-term memory: Used for immediate tasks.
Long-term memory: Used for storing data, this memory serves as a more permanent storage.

When you run a program, your CPU allocates a portion of short-term memory to execute its instructions.

To see memory in action, open your Task Manager and launch applications like Chrome. Observe that memory usage increases as you open more apps. This increased usage eventually slows down your computer. To improve performance, close some applications to free up memory space.

Why do we need to learn Memory?

• To use the memory optimally.
• To make the right decision when writing code. It's either speed or space preference, depending on what you are ready to forgo.

Memory Hierarchy

Every computer relies on a layered system called the memory hierarchy to manage data storage and access. This system balances speed, cost, and capacity by using different memory types with distinct characteristics.

Registers & Cache:
These two memories reside on the CPU itself.

Registers are the fastest areas of memory on the CPU, but they are also the smallest. They store data that is required immediately.

The cache is an area of memory on the CPU that is used to store the next instructions that need to be executed. They are slower compared to registers. It stores data that is required shortly. There are further levels within the hierarchy, like L1, L2, and L3 cache, for varying speeds and sizes.
L1 - fastest but smallest
L2 - slower but bigger
L3 - slowest but biggest

Main Memory (RAM):
The main memory is the primary working memory of your computer. It holds data and instructions currently being used by programs. Main memory is faster than secondary storage but volatile: meaning data vanishes when you power it off.

Secondary Storage (Hard Drives, SSDs):
This is a persistent storage that retains data even after power is off. Slower than RAM but much more affordable and larger. It is ideal for long-term data archiving and accessing less frequently used information.

Network-based Storage:
This storage is located on external servers accessed through networks. Offers flexibility and scalability for sharing data among multiple users and devices. It can be slower than local storage but offers remote access benefits.

Measuring Space

Have you ever wondered how the computer stores all the information you use? To understand how computers represent data, it is crucial to first grasp the decimal system.

Understanding the Decimal system

You are likely already familiar with the decimal system, also known as base-10. This decimal system uses ten digits (0-9) to represent numbers, where each digit's position holds a specific weight based on powers of 10. For instance, in the number 123, the "1" represents 1 x 10² (100), the "2" represents 2 x 10¹ (20), and the "3" represents 3 x 10⁰ (1).

The Binary System

Computers primarily rely on the binary system(bit). This base-2 system is composed of only two digits: 0 and 1. These digits symbolize different states, often likened to electrical switches, where 0 represents "off" and 1 represents "on."

Bits

The bit (short for binary digit and denoted by b) is the basic unit to measure data in a computer. It can only hold one value at a time, either 0 or 1. Just like a single switch can only be on or off.

Nibbles

A nibble (or half-byte) comprises four bits (4 bits). This grouping of bits allows for efficient representation of certain data types, such as storing a single hexadecimal digit (0-F), which requires four bits.

Bytes

A byte (denoted by B), consisting of eight bits (8 bits), is the standard unit for measuring computer memory and storage capacity. Most modern character encodings, like ASCII, assign one byte to represent a single character. For example, the ASCII encoding of letter 'A' is represented as 01000001. You can view the ASCII chart by clicking here.

Unit of measurement

While bytes are the fundamental unit, larger storage capacities utilize prefixes like kilo (103), mega (106), giga (109), and tera (1012) to represent multiples of bytes. For example, a kilobyte (KB) is equivalent to 1000 bytes, and a megabyte (MB) is equal to 1,000,000 bytes. However, some operating systems and software may use the decimal and binary systems interchangeably, which can lead to discrepancies in the reported storage capacities, as explained in the IEC article.

Metric Prefixes

Units representing larger groups of bits and bytes use the metric prefixes. Here is an overview:

Binary-Based Units

Units based on powers of 2 have slightly different prefixes:

Prefix generation

The prefixes for binary-based units were generated by combining the standard metric prefixes with “bi,” resulting in “Kibi,” “Mebi,” “Gibi,” and “Tebi.” See example below:
Kilo + Binary = Kibi
Mega + Binary = Mebi
Giga + Binary = Gibi
Tera + Binary = Tebi

Memory Model in Python

We have seen the importance of space in algorithms. Ideally, we want to limit how much space our program uses and also optimize our program so that they can use the fast parts of the memory hierarchy. Before we can do that, we have to understand how the Python program stores data.

How are Python objects stored in Memory?
Remember that in Python, all data is represented as an object. These include numbers, strings, lists, functions, and classes. Each object has properties/attributes and methods.

The Stack and the Heap

When a Python program executes, all of its data is stored in the main memory.
It creates a runtime stack and dynamic memory heap.

The Stack

Functions and variables are created in the stack.
A new stack frame is created on the invocation of a function or method. Inside the stack frame, we have local variables and parameters.
A stack frame is destroyed as soon as the function or method returns.

def my_function1():
    x = 4
    print(x)

def my_function2():
    y = 7
    return y

my_function1()
print(my_function2())

Let’s click through our example step by step using an online visualizer.
Step 1: It creates a global frame for the functions.
Step 2: It accesses the variable within the scope and prints it in the terminal.
Step 3: my_function1() returns None because we didn’t use a return statement, while my_function2() returns 7.

Scope

We can't talk of a stack frame without discussing the concept of scope.
There are two types of scopes:

Local scope: Variables and functions within a function are only accessible through that function.

Global scope: Variables and functions declared outside any function have a global scope. They are accessible from anywhere in the program, including within functions. Using global variables excessively is generally not recommended because as your program grows, you find it hard to think of a variable name as everything is already used, leading to a name clash and many other reasons. You can check out this article for a detailed explanation of why global variables are generally bad.

In summary, think of a local scope as functions and variables declared in a function and a global scope as functions and variables declared outside a function. When you create a function, you automatically create a scope for the variables and functions inside, and for this reason, we use a return value to end the function and return a value.

y = 5
print(y)

def my_function():
    x = 4
    print(x)

my_function()
print(x)

Let’s click through our example step by step.
Step 1: It creates a global frame for y.
Step 2: It gets printed to the terminal.
Step 3: It executes my_function() and returns None.
Step 4: When it gets to print(x) it returns a NameError. But why?
The answer boils down to scope. x is within the scope of my_function() so when Python tries to find x it checks the global scope and when it can’t find it, it returns an error.

Let’s look at another example. Step through the code.

x = 5

def my_function():
    x = 4
    print(x)

my_function()
print(x)

Step 1: It creates a global frame for x and my_function().
Step 2: It prints out x and returns None.
Step 3: It checks for x in the global frame and prints it out.

Let’s take a look at another example.

x = 5

def my_function():
    print(x)

my_function()

And another.

def my_function():
    x = 5
    return x

x = my_function()
print(x)

As a rule of thumb, Python typically looks for a variable's name by:

• looking at the current frame.
• If not found, looking at the global frame.
• If not found, raising an error.

The image above is a recursive function, we will dive deep into it in future tutorials. But I want you to take note of something. You can see a local and global scope as well as a call stack.
Try debugging your programs on vscode and take note of these things. We move on to the next concept.

The Heap

Think of the stack as the reference memory address of the object on the heap.
The heap stores the values along with its memory address.

NOTE: All values are stored in the heap. Objects are created on the heap.

When we discuss heap there are two concepts we have to learn.

1. Reference counting
2. Garbage Collector

A value in memory has references to the stack, or the stack references the value in memory. More than one stack can reference a value in memory. Once we reassign the variables in the stack it points to another memory address and another until the reference is 0. The garbage collector will deallocate it from memory. This is done automatically, so you won't have to worry about it. So this algorithm used for garbage collection is called reference counting.

To see this in action, step through this code using the online visualizer. What did you notice?

x = ['a', 'b', 'c']
y = x
print(x)
print(y)

Answer: Two arrows are pointing to the object on the heap.

Let’s make it even more fun. We will use an id to print its memory address on the terminal.

x = ['a', 'b', 'c']
y = x
print(id(x))
print(id(y))

Let’s see more examples.

# purpose - want to switch the values i.e x = 3, y = 1

x = 1
y = 3
x = y
y = x

print(x)  # result: 3
print(y)  # result: 3

This doesn’t work because we have lost xvalue in the process of reassignment. Let’s create a temp variable to store the value of x.

x = 1
y = 3
temp = x
x = y
y = temp

print(x)
print(y)

Let’s use another method and it works the same.

x = 1
y = 3
x, y = y, x

print(x)
print(y)

Let’s create an object in Python and compare the memory address.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

point1 = Point(1, 2)
point2 = Point(3, 4)
print(point1 == point2)  # result: False

It returns False for this reason.

NOTE: When comparing objects we are comparing the address they contain in memory.

Mutability

Immutable objects cannot be modified by the program. All primitive data types are immutable.
E.g., strings, integers, floats, booleans, and tuples.
You may argue that you can reassign a variable containing these primitives and it does change.
But here is the deal. In your eyes, when it gets reassigned, it changes, but in memory, it simply changes the reference. Do you remember that the stack is a reference to the value in the heap? So if the memory address were previously 1021, now it would point to 1053. If no variable references 1053 anymore, the reference count is 0, and it gets garbage collected.

Mutable objects can be modified. E.g. Lists, dict, and user-defined object types.

We might not be able to visualize this properly using the online visualizer, so I have used a diagram and id to explain it.

name = 'Praise'
print(id(name))  # result: 140700969655408

name = 'John'
print(id(name))  # result: 140700766157320

print(name)  # result: John

Step 1: It points an arrow to 1011(lets imagine that's the memory address of Praise).
Step 2: When we reassign it points it to 1022.

Step through this code.

names = ['Praise', 'John', 'Paul']
print(id(names))

names[0] = 'Tinuke'
print(names)
print(id(names))

You will notice that the memory address is the same.

Understanding how objects are made

1. A space is created in memory for our object.
2. The variable is initialized using init.
3. A reference to the object created is returned.

Tracing Code using diagrams

The best way to understand how memory works is to write some codes and see the step-by-step execution of memory. I have shown you some examples so far. Look at the codes you have previously written and step through them. Python tutor visualizer has some limitations, so you would have to use the debugging tools in your code editor.

Resources & References

• Python tutor visualizer
• Kibo DSA lecture material
• Binary
• Binary and transistors
• Memory allocation and management
• IEC article
• Kibibytes, minibytes, gigabytes
• ASCII chart

Summary

In this lesson, you have learned:

• Storage and Memory
• Short-term and long-term memory
• Memory hierarchy
• Measuring Space
• Stacks, Heaps, Scopes, References, Garbage collector, and Mutability
• Tracing the code using an online visualizer tool

Until next time, for more insights:
☕ If you enjoy my content, you can buy me a cup of coffee here.
📰 To read more from me, subscribe to my newsletter.
🧸 Check my social media profiles: Twitter, Github, and LinkedIn.