At the dawn of programming, C reigned supreme. C offered three memory allocation methods: static, automatic, and dynamic. While static variables, akin to constants within the source code, are straightforward due to their fixed size, automatic allocation, resembling stack allocation, allocates memory upon entering a lexical block and releases it upon exit. Notably, before C99, automatic variables needed pre-determined sizes at compile time, pushing structures like strings, lists, and maps to the heap, residing in dynamic memory.

Dynamic memory management relied on the programmer’s explicit instructions using malloc, realloc, calloc, and free. While the first two lacked initialization, potentially leaving remnants in memory, all but free could fail, returning a null pointer. Accessing this null pointer spelled disaster – the best outcome being a program crash and the worst, a ticking time bomb of garbled data.

This manual approach burdened programmers with upholding invariants to prevent catastrophic failures. Each variable access demanded a preceding malloc, success verification, and a corresponding free. Mismatches resulted in memory leaks or crashes. Accessing freed variables was forbidden. Let’s illustrate this precarious dance:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main() {
   char *str = (char *) malloc(7); 
   strcpy(str, "toptal");
   printf("char array = \"%s\" @ %u\n", str, str);

   str = (char *) realloc(str, 11);
   strcat(str, ".com");
   printf("char array = \"%s\" @ %u\n", str, str);

   free(str);
   
   return(0);
}

1
2
3
4
5

$ make runc
gcc -o c c.c
./c
char * (null terminated): toptal @ 66576
char * (null terminated): toptal.com @ 66576

This seemingly innocuous code harbors an anti-pattern and a questionable practice. Hardcoding byte counts is discouraged; employing the sizeof function is preferred. Similarly, allocating memory for the character array twice, accounting for null-termination, proves inefficient. A more refined approach would involve a dynamic string buffer, permitting size adjustments.

RAII: The Dawn of a New Era

Managing memory manually was, to put it mildly, unpleasant. In the mid-1980s, Bjarne Stroustrup, the mastermind behind C++, introduced a revolutionary concept: Resource Acquisition Is Initialization (RAII). Its core tenets were: objects could possess constructors and destructors automatically invoked by the compiler, providing a streamlined memory management approach, and this technique extended beyond memory to encompass other resources.

Consequently, our previous C++ example transformed into an elegant solution:

1
2
3
4
5
6
7
8
9

int main() {
   std::string str = std::string ("toptal");
   std::cout << "string object: " << str << " @ " << &str << "\n";
   
   str += ".com";
   std::cout << "string object: " << str << " @ " << &str << "\n";
   
   return(0);
}

1
2
3

$ g++ -o ex_1 ex_1.cpp && ./ex_1
string object: toptal @ 0x5fcaf0
string object: toptal.com @ 0x5fcaf0

Memory management vanished! Object construction, method invocation, and automatic destruction upon function exit became effortless. However, this simplicity concealed potential complexities, as demonstrated below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

vector<string> read_lines_from_file(string &file_name) {
	vector<string> lines;
	string line;
	
	ifstream file_handle (file_name.c_str());
	while (file_handle.good() && !file_handle.eof()) {
		getline(file_handle, line);
		lines.push_back(line);
	}
	
	file_handle.close();
	
	return lines;
}

int main(int argc, char* argv[]) {
	// get file name from the first argument
	string file_name (argv[1]);
	int count = read_lines_from_file(file_name).size();
	cout << "File " << file_name << " contains " << count << " lines.";
	
	return 0;
}

1
2
3

$ make cpp && ./c++ makefile
g++ -o c++ c++.cpp
File makefile contains 38 lines.

The code functions flawlessly, populating and returning the vector of lines. However, efficiency-minded programmers would notice a potential bottleneck. Value semantics dictate copying the vector before its destruction during the return, an expensive operation for substantial data.

Seeking optimization, returning a pointer seems tempting. Despite syntactic nuances, the code remains conceptually similar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

vector<string> * read_lines_from_file(string &file_name) {
	vector<string> * lines;
	string line;
	
	ifstream file_handle (file_name.c_str());
	while (file_handle.good() && !file_handle.eof()) {
		getline(file_handle, line);
		lines->push_back(line);
	}
	
	file_handle.close();
	
	return lines;
}

1
2
3

$ make cpp && ./c++ makefile
g++ -o c++ c++.cpp
Segmentation fault (core dumped)

Disaster strikes! With lines as a pointer, the stack’s ephemeral nature becomes evident. The vector’s destruction upon exiting its scope leaves the pointer dangling, resulting in a segmentation fault when accessing forbidden memory. A viable solution involves migrating the variable from the stack to the heap using a new keyword. A simple modification suffices:

1

vector<string> * lines = new vector<string>;

1
2
3

$ make cpp && ./c++ makefile
g++ -o c++ c++.cpp
File makefile contains 38 lines.

While seemingly flawless, this solution harbors a subtle flaw: memory leakage. C++ mandates manual deletion of heap-allocated pointers; otherwise, the memory becomes inaccessible after the last pointer vanishes, recoverable only by the OS upon process termination. Modern C++ advocates for unique_ptr, automatically deleting the pointed object upon scope exit. Regrettably, this feature was absent until C++11.

Rectifying this example is straightforward:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

vector<string> * read_lines_from_file(string &file_name) {
	vector<string> * lines = new vector<string>;
	string line;
	
	ifstream file_handle (file_name.c_str());
	while (file_handle.good() && !file_handle.eof()) {
		getline(file_handle, line);
		lines->push_back(line);
	}
	
	file_handle.close();
	
	return lines;
}

int main(int argc, char* argv[]) {
	// get file name from the first argument
	string file_name (argv[1]);
	vector<string> * file_lines = read_lines_from_file(file_name);
	int count = file_lines->size();
	delete file_lines;
	cout << "File " << file_name << " contains " << count << " lines.";
	
	return 0;
}

However, as programs escalate in complexity, pinpointing the precise location and time for pointer deletion becomes increasingly challenging. Ownership ambiguity arises: should a function returning a pointer relinquish or retain ownership? Errors lead to memory leaks or data structure corruption as invalid pointers are dereferenced.

Enter the Garbage Collector

Garbage collection, a concept dating back to John McCarthy’s Lisp in 1959, gained traction with Smalltalk-80 in 1980. However, the 1990s witnessed its widespread adoption with languages like Haskell, Python, Lua, Java, JavaScript, Ruby, OCaml, and C#.

Garbage collection encompasses techniques to automate memory management. While available as libraries for languages like C and C++, it’s predominantly integrated into languages that mandate it. The allure lies in abstracting away memory management, freeing programmers from this burden. Our file-reading example in Python illustrates this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def read_lines_from_file(file_name):
	lines = []
	with open(file_name) as fp: 
		for line in fp:
			lines.append(line)
	return lines
	
if __name__ == '__main__':
	import sys
	file_name = sys.argv[1]
	count = len(read_lines_from_file(file_name))
	print("File {} contains {} lines.".format(file_name, count))

1
2

$ python3 python3.py makefile
File makefile contains 38 lines.

The array of lines materializes upon assignment and returns without duplication. Garbage collection handles cleanup after it exits its scope, albeit at an indeterminate time. Interestingly, RAII for non-memory resources isn’t idiomatic in Python. While permissible (e.g., fp = open(file_name)), context managers are preferred for deterministic release.

Abstracting memory management comes at a cost. Reference counting incurs overhead for variable assignment and scope exits. Mark-and-sweep systems introduce unpredictable pauses for cleanup, known as “stop-the-world” events. Python, employing both, suffers from both drawbacks, making it unsuitable for performance-critical or real-time applications. These penalties are evident even in trivial programs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

$ make cpp && time ./c++ makefile
g++ -o c++ c++.cpp
File makefile contains 38 lines.
real    0m0.016s
user    0m0.000s
sys     0m0.015s

$ time python3 python3.py makefile
File makefile contains 38 lines.

real    0m0.041s
user    0m0.015s
sys     0m0.015s

The Python version takes nearly three times longer than the C++ counterpart. While other factors contribute, garbage collection’s impact is undeniable.

Ownership: RAII’s Resurgence

Must performance and ease of programming be mutually exclusive? Not necessarily! Programming language research continues, ushering in new paradigms. Notably, the language called Rust promises Python’s ergonomics and C’s speed while rendering dangling and null pointers impossible – they simply won’t compile. How is this achieved?

The key lies in the borrow checker, a static analysis tool ensuring memory safety at compile time. However, understanding its implications requires delving into its prerequisites.

Ownership

Recall ownership in C++, denoting responsibility for variable deletion. Rust formalizes this concept, bestowing ownership of the bound resource upon every variable binding. The borrow checker enforces singular ownership, as illustrated in this snippet from the Rust Book, which fails to compile:

1
2
3

let v = vec![1, 2, 3];
let v2 = v;
println!("v[0] is: {}", v[0]);

1
2
3

error: use of moved value: `v`
println!("v[0] is: {}", v[0]);
                        ^

Rust’s default move semantics transfer ownership during assignment. While copy semantics are possible, they are uncommon. Consequently, after the third line, v2 assumes ownership, rendering v inaccessible. This strictness ensures a single point of scope exit for each resource, determinable at compile time. Rust leverages this to deliver on RAII’s promise, initializing and destroying resources deterministically based on scope without garbage collection or manual intervention.

Contrast this with reference counting, where pointers store the object’s address and its reference count. Destruction occurs when the count reaches zero, doubling memory usage and introducing runtime overhead for count manipulation. Rust’s ownership achieves the same goal without runtime cost, analyzing ownership and inserting destruction calls during compilation.

Borrowing

Move semantics alone would make function return types cumbersome. Returning multiple unmodified vectors would necessitate including them in the return type. Rust addresses this with borrowing. The following function borrows references to vectors, returning ownership upon completion:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fn foo(v1: Vec<i32>, v2: Vec<i32>) -> (Vec<i32>, Vec<i32>, i32) {
    // do stuff with v1 and v2

    // hand back ownership, and the result of our function
    (v1, v2, 42)
}

let v1 = vec![1, 2, 3];
let v2 = vec![1, 2, 3];

let (v1, v2, answer) = foo(v1, v2);

1
2
3
4
5
6
7
8
9

fn foo(v1: &Vec<i32>, v2: &Vec<i32>) -> i32 {
    // do stuff
    42
}

let v1 = vec![1, 2, 3];
let v2 = vec![1, 2, 3];

let answer = foo(&v1, &v2);

v1 and v2 revert to their original scope after fn foo returns, facing destruction upon their containing scope’s exit.

The borrow checker enforces borrowing restrictions, concisely outlined in the Rust Book:

A borrow’s lifespan cannot exceed its owner’s scope. Additionally, only one of the following borrow types is allowed simultaneously:

• One or more immutable references (&T)

• Exactly one mutable reference (&mut T)

This restriction underpins Rust’s protection against data races. Preventing concurrent mutable access guarantees deterministic behavior, eliminating issues like iterator invalidation and use-after-free errors.

The Borrow Checker in Action

Let’s revisit our file line counter, now implemented in Rust:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

fn read_lines_from_file(file_name: &str) -> io::Result<Vec<String>> {
	// variables in Rust are immutable by default. The mut keyword allows them to be mutated.
	let mut lines = Vec::new();
	let mut buffer = String::new();
	
	if let Ok(mut fp) = OpenOptions::new().read(true).open(file_name) {
		// We enter this block only if the file was successfully opened.
		// This is one way to unwrap the Result<T, E> type Rust uses instead of exceptions.
		
		// fp.read_to_string can return an Err. The try! macro passes such errors 
		// upwards through the call stack, or continues otherwise.
		try!(fp.read_to_string(&mut buffer));
		lines = buffer.split("\n").map(|s| s.to_string()).collect();
	}
	
	Ok(lines)
}

fn main() {
	// Get file name from the first argument.
	// Note that args().nth() produces an Option<T>. To get at the actual argument, we use
	// the .expect() function, which panics with the given message if nth() returned None, 
	// indicating that there weren't at least that many arguments. Contrast with C++, which
	// segfaults when there aren't enough arguments, or Python, which raises an IndexError.
	// In Rust, error cases *must* be accounted for.
	let file_name = env::args().nth(1).expect("This program requires at least one argument!");
	if let Ok(file_lines) = read_lines_from_file(&file_name) {
		println!("File {} contains {} lines.", file_name, file_lines.len());
	} else {
		// read_lines_from_file returned an error
		println!("Could not read file {}", file_name);
	}
}

Beyond the in-code explanations, tracing variable lifetimes is insightful. file_name and file_lines persist until main() concludes, their destructors invoked automatically. When calling read_lines_from_file, file_name is immutably borrowed. Within read_lines_from_file, buffer follows suit, destroyed upon scope exit. lines, however, endures, returned to main().

Rust’s expression-based nature dictates that the last expression in a function, without a semicolon, serves as the return value. Return values, intended to outlive the function, receive special treatment. Due to move semantics, transferring ownership from Ok(lines) to Ok(file_lines) requires no copying; the compiler merely adjusts the pointer.

“The True Power of RAII Reveals Itself in the End”

Manual memory management, a programmer’s bane, has fueled the quest for automated solutions. RAII, while promising, faltered in C++ when handling heap-allocated objects without awkward workarounds. Consequently, the 1990s witnessed a surge in garbage-collected languages, prioritizing programmer convenience over performance.

However, language design evolves. Rust, armed with ownership and borrowing, reconciles RAII’s scope-based approach with garbage collection’s memory safety. It achieves this without the need for stop-the-world pauses, offering unparalleled safety guarantees. This is the future of systems programming. After all, “to err is human, but compilers never forget.”